Simulated Annealing Algorithm क्या है? | Optimization in Hindi

Simulated Annealing (SA) एक popular meta-heuristic optimization algorithm है। यह complex और NP-hard problems के लिए global optimum solution find करने के लिए probabilistic search technique use करता है।

Simulated Annealing की परिभाषा

Simulated Annealing algorithm thermodynamics के annealing process से inspired है, जिसमें metals को heat किया जाता है और धीरे-धीरे cool किया जाता है ताकि crystal structure stable और low-energy state में आए। Optimization में यह high-energy (bad) solutions को accept करके local optima से बचता है और global optimum की तलाश करता है।

Simulated Annealing के Features

• Probabilistic search technique
• Global search के लिए local search को escape करने में सक्षम
• Flexible और multiple optimization problems पर apply किया जा सकता है
• Simple memory-less algorithm, previous solutions store नहीं करता
• High-quality approximate solution provide करता है

Simulated Annealing Algorithm के Steps

1. Initial solution (S) select करें और initial temperature (T) set करें।
2. Current solution के neighborhood में random solution (S’) generate करें।
3. Cost या objective function difference Δ = Cost(S’) - Cost(S) calculate करें।
4. यदि Δ < 0 (better solution) तो S = S’ update करें।
5. यदि Δ ≥ 0, तो S’ को probability e^(-Δ/T) के अनुसार accept करें।
6. Temperature T को gradually decrease करें (cooling schedule)।
7. Stopping criteria check करें (final temperature या max iterations)।
8. Iteration repeat करें जब तक stopping criteria पूरा न हो।

Applications of Simulated Annealing

• Traveling Salesman Problem (TSP)
• Job Scheduling Problems
• Network Design Optimization
• Resource Allocation Problems
• VLSI Layout Optimization

Example

मान लीजिए TSP problem में 6 cities हैं। Simulated Annealing algorithm initial random route select करता है। फिर neighborhood search के माध्यम से new routes generate करता है। Bad routes probabilistically accept किए जाते हैं ताकि local optima से escape किया जा सके। Iterations के बाद shortest route find हो जाता है।

निष्कर्ष

Simulated Annealing एक effective meta-heuristic algorithm है जो probabilistic search strategy का use करके complex optimization problems में near-optimal solution efficiently find करता है। यह local optima में फंसने से बचता है और flexible, high-quality solutions provide करता है।