Chapterبەش 5 · Lectureوانە 5.2

Simulated Annealingsimulated annealing

How can a search be fast and still find the highest peak? Simulated annealing sometimes accepts worse moves — often while it is “hot”, rarely when it is “cold” — so it escapes local maxima and then climbs. Learn where the name comes from, the course's cinema-seat example, the acceptance rule e^(ΔE/T), cooling schedules, and run it in Python.

گەڕانێک چۆن دەتوانێت خێرا بێت و هێشتا بەرزترین لووتکە بدۆزێتەوە؟ هەندێک جار جووڵەی خراپتر وەردەگرێت — زۆر جار کاتێک «گەرم»ە، بە دەگمەن کاتێک «سارد»ە — بۆیە لە دەرباز دەبێت و پاشان سەردەکەوێت. فێر دەبیت ناوەکە لە کوێوە هاتووە، نموونەی کورسیی سینەما، یاسای وەرگرتنی e^(Δ⁦E/T⁩) و ، هەروەها بە کاری پێ دەکەیت.

21 min read21 خولەک خوێندنەوە · 16 stepsهەنگاو

What you will learnچی فێر دەبیت

Explain why hill climbing is incomplete and a random walk is inefficient, and how simulated annealing gets both properties.
Describe real annealing correctly (heating, slow cooling, a stable inner order) and link it to the algorithm.
Apply the acceptance rule e^(ΔE/T) and a cooling schedule, with numbers.
Run and read a Python simulation of the cinema-seat problem.

ڕوونی بکەیتەوە بۆچی تەواو نییە و کارا نییە و چۆن هەردوو تایبەتمەندییەکە بەدەست دەهێنێت.
annealingی ڕاستەقینە بە دروستی وەسف بکەیت (گەرمکردن، ساردکردنەوەی هێواش، ڕیزبەندییەکی ناوەکیی جێگیر) و بە ئەلگۆریزمەکەوە ببەستیتەوە.
یاسای وەرگرتنی e^(Δ⁦E/T⁩) و بە ژمارەوە جێبەجێ بکەیت.
لاساییکردنەوەیەکی بۆ کێشەی کورسیی سینەما کار پێ بکەیت و بیخوێنیتەوە.

The question: fast and complete at the same time?پرسیارەکە: لە هەمان کاتدا خێرا و تەواو؟

Remember the two extremes of local search:

دوو لای توندی بهێنەرەوە یادت:

Hill climbing never makes a move to a lower value. It is efficient (it climbs straight up), but it is incomplete: it can get stuck on a and never reach the .
A moves to a random neighbour every time, good or bad. Given enough time it visits every state, so it is complete, but it is not efficient: it wastes almost all its moves.

هەرگیز جووڵەیەک بەرەو بەهای نزمتر ناکات. کارایە (ڕاستەوخۆ سەردەکەوێت)، بەڵام تەواو نییە: دەکرێت لەسەر بچەقێت و هەرگیز نەگاتە .
هەموو جارێک دەچێتە دراوسێیەکی هەڕەمەکی، باش بێت یان خراپ. ئەگەر کاتی تەواوی هەبێت سەردانی هەموو دەکات، بۆیە تەواوە، بەڵام کارا نییە: نزیکەی هەموو جووڵەکانی بە فیڕۆ دەدات.

Here complete means: if a best state exists, the algorithm can reach it. Efficient means: it does not waste a huge number of steps.

لێرەدا تەواو واتە: ئەگەر باشترین هەبێت، ئەلگۆریزمەکە دەتوانێت پێی بگات. کارا واتە: ژمارەیەکی زۆر هەنگاو بە فیڕۆ نادات.

The exercise question of the courseپرسیاری ڕاهێنانی کۆرسەکە

“Simulated annealing is an algorithm which yields both efficiency and completeness. How?” In the words of the course's Kurdish paper: hill climbing does not step downwards, which is a weakness, because it may get stuck in a local maximum. How does simulated annealing bring in random steps, so that the search is carried to the peak of peaks (the global maximum)? This whole lesson answers the question; a model answer is in the exercises.

«⁦Simulated annealing is an algorithm which yields both efficiency and completeness. How?⁩» بە وشەکانی وتارە کوردییەکەی کۆرسەکە: وەک ئاشکرایە، ئەلگۆریزمی هەنگاو بەرەو خوارەوە نانێت، ئەمەش لاوازییە چونکە ڕەنگە لە بچەقێت. چۆن ئەلگۆریزمی هەنگاوی هەڕەمەکی دەهێنێتە ئاراوە تاکو جووڵەکە بەرەو ببرێت؟ هەموو ئەم وانەیە وەڵامی ئەم پرسیارە دەداتەوە؛ وەڵامێکی نموونەیی لە ڕاهێنانەکاندایە.

The idea of this lesson in one tableبیرۆکەی ئەم وانەیە لە یەک خشتەدا
Methodڕێگە	Efficient?کارایە؟	Complete?تەواوە؟
	yesبەڵێ	no: stuck on local maximaنەخێر: لەسەر دەچەقێت
	noنەخێر	yes, given enough timeبەڵێ، ئەگەر کاتی تەواو هەبێت
	yes, mostlyبەڵێ، زۆربەی کات	yes, with a probability near 1 if it cools slowlyبەڵێ، بە نزیک لە 1 ئەگەر هێواش سارد بکرێتەوە

Quick checkپشکنینی خێراWhy is a random walk complete but not efficient?بۆچی تەواوە بەڵام کارا نییە؟It remembers every state it has seenهەموو ئەو دۆخانەی بینیونی لە بیر دەگرێتIt eventually visits every state, but most of its moves are wastedلە کۆتاییدا سەردانی هەموو دۆخەکان دەکات، بەڵام زۆربەی جووڵەکانی بە فیڕۆ دەچنIt only moves uphillتەنیا بەرەو سەرەوە دەجووڵێت

Climbing a mountain blindfoldedسەرکەوتن بەسەر شاخدا بە چاوی بەستراو

Hill climbing does not move downward. That is a problem, because it can get stuck on a small peak (a local maximum). Simulated annealing solves this by sometimes taking random steps, even downward, to escape small peaks and keep searching for the highest peak. Over time it reduces these random steps and focuses more and more on climbing up.

بەرەو خوارەوە ناجووڵێت. ئەمە کێشەیە، چونکە دەکرێت لەسەر لووتکەیەکی بچووک () بچەقێت. ئەمە چارەسەر دەکات بەوەی هەندێک جار هەنگاوی هەڕەمەکی دەنێت، تەنانەت بەرەو خوارەوەش، تاکو لە لووتکە بچووکەکان دەرباز ببێت و بەردەوام بێت لە گەڕان بۆ بەرزترین لووتکە. بە تێپەڕبوونی کات ئەم هەنگاوە هەڕەمەکییانە کەم دەکاتەوە و زیاتر و زیاتر سەرنج دەخاتە سەر سەرکەوتن.

The blindfolded climberشاخەوانی چاوبەستراو

The name of hill climbing says it all: it is climbing a mountain. It is like closing your eyes (or wearing a blindfold: a piece of cloth over your eyes so that you cannot see) and climbing as long as the ground under your feet feels higher. You keep stepping until you reach the top of a small mountain, a “local maximum”, and you think it is the highest peak. But near that small mountain there may be a taller one, the “global maximum”, which is your real goal. Now you do not want to step down, because you fear losing the way to the highest peak, so you get stuck there. To solve this, you must take random steps and try the paths, until in the end they may save you. This solution is known as simulated annealing.

ئەلگۆریزمی ناوەکەی بە خۆیەوەیەتی، واتە سەرکەوتن بەسەر شاخدا. وەک ئەوەیە چاوت دابخەیت (یان چاوبەستێک ببەستیت: پارچە قوماشێک بەسەر چاوتدا تاکو هیچ نەبینیت) و بەسەر چیایەکدا سەربکەویت، تا ئەو کاتەی هەست دەکەیت خاکی ژێر پێت بەرزترە. لەو هەنگاونانە بەردەوام دەبیت تا دەگەیتە لووتکەی چیایەکی بچووک (کە لە بە ناسراوە) و پێت وایە بەرزترین لووتکەیە، لە کاتێکدا ڕەنگە لە نزیک ئەو چیا بچووکەوە چیایەکی بەرزتر هەبێت و ئەوە ئامانجی ڕاستەقینەی تۆ بێت (کە بە ناسراوە). لەم کاتەدا ناتەوێت بەرەو خوارەوە هەنگاو بنێیت لە ترسی ونکردنی ڕێگەی بەرزترین لووتکە، بۆیە لەو شوێنەدا دەچەقیت. بۆ چارەسەرکردنی ئەمە، پێویستە هەندێک هەنگاوی هەڕەمەکی بنێیت و ڕێگاکان تاقی بکەیتەوە، تا لە کۆتاییدا ڕەنگە ڕزگارت بکەن. ئەم ڕێگەچارەیە بە ناسراوە.

Where the analogy stops workingسنووری ئەم نموونەیە

A real climber decides by feeling; simulated annealing decides with a clear rule and a probability (you will see it below). It also does not “try paths” one by one: it keeps only one current state.

شاخەوانێکی ڕاستەقینە بە هەست بڕیار دەدات؛ بە یاسایەکی ڕوون و بڕیار دەدات (لە خوارەوە دەیبینیت). هەروەها ڕێگاکان یەک بە یەک «تاقی ناکاتەوە»: تەنیا یەک ئێستا ڕادەگرێت.

Hill climbing stops on the first top. Simulated annealing is allowed to go down first. لەسەر یەکەم لووتکە دەوەستێت. ڕێگەی پێدراوە سەرەتا دابەزێت.CêIT

Quick checkپشکنینی خێراWhat does simulated annealing do that hill climbing never does? چی دەکات کە هەرگیز نایکات؟It remembers the whole pathهەموو ڕێگەکە لە بیر دەگرێتIt sometimes accepts a step to a worse (lower) stateهەندێک جار هەنگاوێک بەرەو دۆخێکی خراپتر (نزمتر) وەردەگرێتIt looks at the whole landscape at onceیەکجار سەیری هەموو دیمەنەکە دەکات

Where the name comes from: annealing metalناوەکە لە کوێوە هاتووە: گەرمکردن و ساردکردنەوەی کانزا

The name has two words. “Simulated” means imitated: it is a synonym of the English word imitate. “Annealing” is a word from physics and metal work. So the method imitates a physical and chemical process.

ناوەکە لە دوو وشە پێکهاتووە. «Simulated» واتە لاساییکراوە: هاوواتای وشەی ئینگلیزیی imitateە بە واتای «لاساییکردنەوە». «Annealing» وشەیەکی بواری فیزیا و کانزاکاریە. کەواتە ئەم ڕێگەیە لە لاسایی کارلێکێکی فیزیایی و کیمیایی دەکاتەوە.

Annealing is a heat treatment. A metal (or glass) is heated to a high temperature, held there, and then cooled slowly in a controlled way. While it is hot, its atoms move around freely. When it cools slowly, the atoms have time to settle into a regular, low-energy arrangement with less inner stress. The metal becomes softer and less brittle. If it is cooled very fast (quenched), the atoms are frozen in a disordered arrangement instead.

Annealing چارەسەرێکی گەرمییە. کانزایەک (یان شووشە) تا پلەیەکی بەرز گەرم دەکرێت، ماوەیەک لەو پلەیەدا دەهێڵدرێتەوە و پاشان بە هێواشی و بە کۆنترۆڵەوە سارد دەکرێتەوە. کاتێک گەرمە، گەردیلەکانی بە ئازادی دەجووڵێن و ئەملاوئەولا دەکەن. کاتێک بە هێواشی سارد دەبێتەوە، گەردیلەکان کاتیان هەیە لە ڕیزبەندییەکی ڕێکوپێک و کەموزەدا جێگیر ببن کە فشاری ناوەکیی کەمترە. کانزاکە نەرمتر دەبێت و کەمتر دەشکێت. ئەگەر زۆر بە خێرایی سارد بکرێتەوە، گەردیلەکان لەبری ئەوە لە ڕیزبەندییەکی ناڕێکدا دەبەستن.

Annealing does not change the shapeAnnealing شێوە ناگۆڕێت

The notes say that annealing is “heating an object to change its shape, then cooling it to lock in that new shape” (iron is heated, shaped, then cooled), and that when it cools “the particles stop”. Shaping hot iron is forging, a different process. Annealing is about the inside of the metal: slow cooling lets the particles settle into a stable, low-energy order. They do not stop; they settle. That is exactly the idea the algorithm copies: lots of movement while hot, then settling into the best arrangement.

تێبینییەکان دەڵێن annealing «گەرمکردنی تەنێکە بۆ گۆڕینی شێوەکەی، پاشان ساردکردنەوەی بۆ جێگیرکردنی شێوە نوێیەکە» (ئاسن گەرم دەکرێت، شێوەی پێ دەدرێت، پاشان سارد دەکرێتەوە) و کاتێک سارد دەبێتەوە «گەردیلەکان دەوەستن». شێوەدان بە ئاسنی گەرم ئاسنگەرییە، کە کارێکی ترە. Annealing پەیوەندی بە ناوەوەی کانزاکەوە هەیە: ساردکردنەوەی هێواش ڕێگە دەدات گەردیلەکان لە ڕیزبەندییەکی جێگیر و کەموزەدا ڕێک ببن. ناوەستن؛ جێگیر دەبن. ئەمە ڕێک ئەو بیرۆکەیەیە کە ئەلگۆریزمەکە لاسایی دەکاتەوە: جووڵەی زۆر لە کاتی گەرمیدا، پاشان جێگیربوون لە باشترین ڕیزبەندیدا.

The same idea applies to a search algorithm. When you are stuck on a hillock, you have to move here and there a lot to find the way to the highest peak. Even if the start of the path and the first steps look bad, there are many directions to try, and you have to try some of them so that you do not stay stuck where you are.

لە بە هەمان شێوەیە: کاتێک لەسەر تەپۆلکەیەک چەقیویت، پێویستە زۆر ئەملاوئەولا بکەیت تاکو ڕێی بەرزترین لووتکە بدۆزیتەوە. ئەگەرچی دەستپێکی ڕێگەکە و یەکەم هەنگاوەکان خراپیش دەربکەون، چەندین ئاڕاستەی ئەگەری هەن و ناچاریت هەندێکیان تاقی بکەیتەوە، تاکو لە شوێنی خۆتدا بە چەقیوی نەمێنیتەوە.

From metal to algorithmلە کانزاوە بۆ ئەلگۆریزم
In metalلە کانزادا	In the algorithmلە ئەلگۆریزمەکەدا
an arrangement of the atomsڕیزبەندیی گەردیلەکان	a state
energy (lower is more stable)وزە (کەمتر جێگیرترە)	the value or cost of the stateبەها یان کۆستی
temperatureپلەی گەرما	the number T: how often worse moves are acceptedژمارەی T: چەند جار جووڵەی خراپتر وەردەگیرێت
atoms jumping around while hotبازدانی گەردیلەکان لە کاتی گەرمیدا	random moves, also to worse statesجووڵەی هەڕەمەکی، بۆ خراپتریش
slow, controlled coolingساردکردنەوەی هێواش و کۆنترۆڵکراو	the : T falls step by step: T هەنگاو بە هەنگاو دادەبەزێت
a stable, low-energy metalکانزایەکی جێگیر و کەموزە	a very good state, often the best زۆر باش، زۆر جار باشترینیان

Quick checkپشکنینی خێراIn real annealing, why is the metal cooled slowly?لە annealingی ڕاستەقینەدا بۆچی کانزاکە بە هێواشی سارد دەکرێتەوە؟So that the atoms stop moving at onceبۆ ئەوەی گەردیلەکان دەستبەجێ لە جووڵە بکەونSo that the atoms have time to settle into a stable, low-energy orderبۆ ئەوەی گەردیلەکان کاتیان هەبێت لە ڕیزبەندییەکی جێگیر و کەموزەدا ڕێک ببنTo give it a new shapeبۆ ئەوەی شێوەیەکی نوێی پێ بدرێت

The Most Metal Algorithm in Computer ScienceSciShow · Englishئینگلیزی · 253K viewsبینین · 11K likesلایک · Partبەشی 1:21–4:56 (ofلە 6:46)
Shows what annealing does to hot metal, cooled slowly, and how simulated annealing copies the idea to escape bad solutions.
پیشان دەدات ساردکردنەوەی هێواش (annealing) چی بە کانزای گەرم دەکات و چۆن هەمان بیرۆکە لاسایی دەکاتەوە بۆ دەربازبوون لە چارەسەرە خراپەکان.
Plays 1:21–4:56: the idea from nature, the physics of annealing metal, and how simulated annealing imitates it.
لە ⁦1:21⁩ تا ⁦4:56⁩ لێدەدرێت: بیرۆکەکە لە سروشتەوە، فیزیای ساردکردنەوەی هێواشی کانزا و چۆن لاسایی دەکاتەوە.

The cinema problemکێشەی سینەماکە

Here is a real-life example from the course's Kurdish paper. Suppose you enter a cinema and want to sit on the best seat: the one that gives you the best view of the screen, neither too far nor too near. Some problems come up: the hall is dark, you can only see the seats near you, and you do not know whether a better seat than these is free.

لێرەدا بە نموونەیەکی کەتواری (واتە واقیعی) بابەتەکە دەخەینە ڕوو. وەهای دابنێ کە چوویتەتە نێو سینەمایەکەوە و دەتەوێت لەسەر نایابترین کورسی دابنیشیت، ئەوەی جوانترین دیمەنی شاشەکەت پێ دەبەخشێت — نە دوور بێت و نە نزیک. کۆمەڵێک کێشە دێنە ئاراوە: هۆڵەکە تاریکە، تەنیا ئەو کورسییانە دەبینیت کە لە خۆتەوە نزیکن و نازانیت ئاخۆ کورسییەکی باشتر لەمانەی ئێستا بەردەستە یان نا.

Our version of the course's cinema: each number is how good the view from that seat is.وەشانی ئێمە لە سینەماکەی کۆرسەکە: هەر ژمارەیەک ئەوەیە کە دیمەنی ئەو کورسییە چەند باشە.CêIT

Every seat is a state, the seats next to you are its neighbours, and the view number is the value. The hall is a small state-space landscape: seat C3 (8) is a local maximum, seat D7 (10) is the global maximum, and the poor seats behind the pillar form a valley between them.

هەر کورسییەک ، ئەو کورسییانەی لە تەنیشتتن دراوسێکانین و ژمارەی دیمەنەکە بەهاکەیە. هۆڵەکە نموونەیەکی بچووکی : کورسیی ⁦C3 (8)⁩ ، کورسیی ⁦D7 (10)⁩ و کورسییە خراپەکانی پشت کۆڵەکەکە دۆڵێک لە نێوانیاندا پێک دەهێنن.

The cinema problemکێشەی سینەماکە

Choosing a seat with hill climbingهەڵبژاردنی کورسی بە چیاهەڵەگڕی

If simple hill climbing is usedئەگەر چیاهەڵەگڕی بە سادەیی بەکار بهێنرێت

You sit on a seat at random.
بە شێوەیەکی هەڕەمەکی لەسەر کورسییەک دادەنیشیت.
You check the seats around you.
کورسییەکانی چواردەورت دەپشکنیت.
If a nearby seat is better than your seat, you move there.
ئەگەر کورسییەکی نزیک لەچاو ئەمەی ئێستا باشتر بوو، دەچیتە ئەوێ.
If the nearby seats are worse than your seat, you do not change your place.
ئەگەر کورسییە نزیکەکان لەچاو ئەمەی ئێستا خراپتر بوون، شوێنی ئێستای خۆت ناگۆڕیت.

Quick checkپشکنینی خێراYou sit on seat C3 (view 8). Its neighbours are B3 (5), D3 (6), C2 (6) and C4 (6). What does hill climbing do?لەسەر کورسیی ⁦C3⁩ (دیمەن ⁦8⁩) دانیشتوویت. دراوسێکانی ⁦B3 (5)⁩، ⁦D3 (6)⁩، ⁦C2 (6)⁩ و ⁦C4 (6)⁩ن. چی دەکات؟Stays on C3, because no neighbour is betterلەسەر ⁦C3⁩ دەمێنێتەوە، چونکە هیچ دراوسێیەک باشتر نییەMoves to C4, the way to the best seatدەچێتە ⁦C4⁩، ڕێگەی نایابترین کورسیMoves to a random neighbourدەچێتە دراوسێیەکی هەڕەمەکی

The cinema problemکێشەی سینەماکە

Choosing a seat with simulated annealingهەڵبژاردنی کورسی بە simulated annealing

If simulated annealing is usedئەگەر simulated annealing بەکار بهێنرێت

You sit on a seat at random.
بە شێوەیەکی هەڕەمەکی لەسەر کورسییەک دادەنیشیت.
At the start (at a high temperature 🔥) you check seats at random and you are willing to move, even if a seat turns out worse than the one you are sitting on now.
لە سەرەتادا (لە بەرزدا 🔥) کورسییەکان بە شێوەیەکی هەڕەمەکی دەپشکنیت و ئامادەیت بگوازیتەوە، ئەگەرچی کورسییەکە لەچاو ئەوەی ئێستا لەسەری دانیشتوویت خراپتریش دەربکەوێت.
As time passes (as the temperature falls ❄), you become more and more picky: you mostly accept only a seat that is better than the seats you have already checked.
هەتا کات تێدەپەڕێت (تا نزم دەبێتەوە ❄)، بەردەوام زیاتر دەبیتە کەسێکی درەنگهەڵبژێر (ئینگلیزی: picky) و زۆربەی جار تەنیا ئەو کورسییەت بەدڵ دەبێت کە لەچاو کورسییە پشکنراوەکان باشترە.
In the end you reach the very best seat — very often, but not always.
لە کۆتاییدا دەگەیت بە کورسییە هەرە نایابەکە — زۆر جار، بەڵام نەک هەمیشە.

“Picky” and “always the best seat”, made exact«درەنگهەڵبژێر» و «هەمیشە نایابترین کورسی»، بە وردی

Two details are sharper than in the notes. (1) Even when it is cold, a worse seat can still be accepted, but the chance is tiny: the lower the temperature and the worse the seat, the smaller the chance (the exact rule is on the next screen). (2) The notes say “in the end you reach the very best seat”. Simulated annealing finds the best seat with high probability if the temperature falls slowly enough, not every time. Our Python test below finds the best seat in 90 of 100 runs with slow cooling.

دوو وردەکاری لێرەدا لە تێبینییەکان وردترن. ⁦(1)⁩ تەنانەت کاتێک سارد بووە، هێشتا دەکرێت کورسییەکی خراپتر وەربگیرێت، بەڵام ئەگەرەکەی زۆر کەمە: هەتا نزمتر و کورسییەکە خراپتر بێت، ئەگەرەکە کەمترە (یاسا وردەکە لە پەڕەی داهاتوودایە). ⁦(2)⁩ تێبینییەکان دەڵێن «لە کۆتاییدا دەگەیت بە کورسییە هەرە نایابەکە». ئەگەر بە تەواوی هێواش دابەزێت، نایابترین کورسی بە زۆر دەدۆزێتەوە، نەک هەموو جارێک. تاقیکردنەوەی لە خوارەوە بە ساردکردنەوەی هێواش لە ⁦90⁩ جار لە ⁦100⁩ جاردا نایابترین کورسی دەدۆزێتەوە.

Quick checkپشکنینی خێراEarly, when the temperature is high, you are offered a seat that is worse than yours. What happens?لە سەرەتادا، کاتێک بەرزە، کورسییەکت پێشنیار دەکرێت کە لە هی خۆت خراپترە. چی ڕوودەدات؟You may well take it: worse moves are often accepted while it is hotزۆر ئەگەری هەیە وەری بگریت: لە کاتی گەرمیدا جووڵەی خراپتر زۆر جار وەردەگیرێتYou always take itهەمیشە وەری دەگریتYou never take itهەرگیز وەری ناگریت

The algorithm and its acceptance ruleئەلگۆریزمەکە و یاسای وەرگرتنەکەی

The notes explain the idea but not how the random steps are chosen. This is the real algorithm, as it is written in the standard textbook (Russell and Norvig). It needs a value for every state, a temperature T, and a that says how T falls over time.

تێبینییەکان بیرۆکەکە ڕوون دەکەنەوە، بەڵام نەک چۆن هەنگاوە هەڕەمەکییەکان هەڵدەبژێردرێن. ئەمە ئەلگۆریزمە ڕاستەقینەکەیە، وەک لە کتێبی ستانداردی ئەم بوارەدا نووسراوە (ڕاسڵ و نۆرڤیگ). پێویستی بە بەهایەک بۆ هەر ، T و هەیە کە دەڵێت T بە تێپەڕبوونی کات چۆن دادەبەزێت.

Simulated annealing, step by stepsimulated annealing هەنگاو بە هەنگاو

Startدەستپێک
Take a start state as the current state, and a high temperature T.
سەرەتا وەک ئێستا وەربگرە و T بەرز دابنێ.
Try a random neighbourدراوسێیەکی هەڕەمەکی تاقی بکەرەوە
Pick ONE neighbour at random and compute ΔE = value(neighbour) − value(current).
یەک دراوسێ بە هەڕەمەکی هەڵبژێرە و ΔE بژمێرە: ΔE = بەهای دراوسێ − بەهای ئێستا.
Better: always moveباشتر: هەمیشە بجووڵێ
If ΔE > 0 (the neighbour is better), move to it.
ئەگەر Δ⁦E > 0⁩ بوو (دراوسێکە باشترە)، بچۆ بۆی.
Worse: move only sometimesخراپتر: تەنیا هەندێک جار بجووڵێ
If ΔE ≤ 0 (the neighbour is not better), move to it only with probability e^(ΔE/T). Otherwise stay.
ئەگەر Δ⁦E ≤ 0⁩ بوو (دراوسێکە باشتر نییە)، تەنیا بە e^(Δ⁦E/T⁩) بچۆ بۆی. ئەگینا بمێنەرەوە.
Cool downسارد بکەرەوە
Lower T a little, as the schedule says (for example T = T × 0.99).
T کەمێک دابەزێنە بەپێی (بۆ نموونە ⁦T = T × 0.99⁩).
Stopوەستان
Repeat from “Try a random neighbour” until T is (almost) 0. Return the current state.
لە «دراوسێیەکی هەڕەمەکی تاقی بکەرەوە»ەوە دووبارەی بکەرەوە تا T (نزیکەی) دەبێتە 0. ئێستا بگەڕێنەوە.

The algorithm and its acceptance ruleئەلگۆریزمەکە و یاسای وەرگرتنەکەی

How likely is a worse move?جووڵەیەکی خراپتر چەند ئەگەری هەیە؟

Look at the rule e^(ΔE/T) (e ≈ 2.718). For a worse neighbour ΔE is negative, so the result is between 0 and 1: it is a probability. It is large when the step is only a little worse or the temperature is high, and tiny when the step is much worse or the temperature is low:

سەیری یاسای e^(Δ⁦E/T⁩) بکە (e ≈ ⁦2.718⁩). بۆ دراوسێیەکی خراپتر ΔE سالبە، بۆیە ئەنجامەکە لە نێوان 0 و 1دایە: . کاتێک هەنگاوەکە تەنیا کەمێک خراپترە یان بەرزە، گەورەیە؛ کاتێک هەنگاوەکە زۆر خراپترە یان نزمە، زۆر بچووکە:

How often a worse move is acceptedجووڵەی خراپتر چەند جار وەردەگیرێت
Temperature T T	ΔE = −1 (a little worse)Δ⁦E = −1⁩ (کەمێک خراپتر)	ΔE = −5 (much worse)Δ⁦E = −5⁩ (زۆر خراپتر)
10	e^(−0.1) ≈ 0.90 (90%)	e^(−0.5) ≈ 0.61 (61%)
2	e^(−0.5) ≈ 0.61 (61%)	e^(−2.5) ≈ 0.08 (8%)
0.5	e^(−2) ≈ 0.14 (14%)	e^(−10) ≈ 0.00005 (0.005%)

A cooling schedule: hot at first (many worse moves accepted), cold at the end (almost only better moves).: سەرەتا گەرم (زۆر جووڵەی خراپتر وەردەگیرێت)، لە کۆتاییدا سارد (نزیکەی تەنیا جووڵەی باشتر).CêIT

This is the answer to the question of the lesson. While T is high, the search behaves almost like a random walk, so it can leave local maxima and explore (completeness). While T falls, it behaves more and more like hill climbing, so it climbs quickly (efficiency). If T falls slowly enough, the probability of ending at the global maximum approaches 1. The price: a very slow schedule can take a very long time.

ئەمە وەڵامی پرسیارەکەی وانەکەیە. کاتێک T بەرزە، گەڕانەکە نزیکەی وەک ڕەفتار دەکات، بۆیە دەتوانێت بەجێ بهێڵێت و بگەڕێت (). کاتێک T دادەبەزێت، زیاتر و زیاتر وەک ڕەفتار دەکات، بۆیە بە خێرایی سەردەکەوێت (کارایی). ئەگەر T بە تەواوی هێواش دابەزێت، کۆتاییهاتن لە لە 1 نزیک دەبێتەوە. نرخەکەی: زۆر هێواش دەکرێت کاتێکی زۆر درێژ ببات.

Who invented it?کێ دایهێنا؟

Kirkpatrick, Gelatt and Vecchi used this method in 1983 for hard optimization problems such as the traveling salesman problem and gave it the name “simulated annealing”; Černý described a similar method independently in 1985. The acceptance rule comes from a 1953 method by Metropolis and colleagues for simulating hot atoms.

کێرکپاتریک، گێلات و ڤێکی لە ساڵی ⁦1983⁩دا ئەم ڕێگەیەیان بۆ قورس، وەک ، بەکار هێنا و ناوی «⁦simulated annealing⁩»یان لێ نا؛ چێرنی لە ساڵی ⁦1985⁩دا بە جیا ڕێگەیەکی هاوشێوەی باس کرد. یاسای وەرگرتنەکە لە ڕێگەیەکی ساڵی ⁦1953⁩ی مێترۆپۆلیس و هاوکارەکانییەوە هاتووە بۆ لاساییکردنەوەی گەردیلە گەرمەکان.

The algorithm and its acceptance ruleئەلگۆریزمەکە و یاسای وەرگرتنەکەی

Watch it decide, step by stepتەماشای بکە چۆن بڕیار دەدات، هەنگاو بە هەنگاو

This small program uses the cinema of the figure. It starts on the good seat C3 (the local maximum) with T = 5 and cools quickly (T = T × 0.8), and it prints every decision. Save it next to cinema_annealing.py (on the next screen), because it borrows three functions from it.

ئەم بەرنامە بچووکە سینەماکەی وێنەکە بەکار دەهێنێت. لەسەر کورسیی باشی ⁦C3⁩ () بە ⁦T = 5⁩ دەست پێدەکات و بە خێرایی سارد دەبێتەوە ⁦(T = T × 0.8)⁩ و هەموو بڕیارێک چاپ دەکات. لە تەنیشت cinema_annealing.py (پەڕەی داهاتوو) پاشەکەوتی بکە، چونکە سێ لەوێوە وەردەگرێت.

A trace of simulated annealingبەدواداچوونی simulated annealingsa_trace.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

# Watch simulated annealing decide, step by step. Save next to cinema_annealing.py.
import math
import random
from cinema_annealing import name, value, neighbours

random.seed(3)
seat, t = (2, 2), 5.0                   # start on the "good" seat C3 (view 8)
for step in range(1, 15):
    new = random.choice(neighbours(seat))
    delta = value(new) - value(seat)
    if delta > 0:
        chance, accept = 1.0, True      # better: always move
    else:
        chance = math.exp(delta / t)    # worse: move only sometimes
        accept = random.random() < chance
    print(f"{step:2}  T={t:4.2f}  {name(seat)}({value(seat)}) -> "
          f"{name(new)}({value(new)})  change {delta:+}  "
          f"chance {chance:4.2f}  {'move' if accept else 'stay'}")
    if accept:
        seat = new
    t = t * 0.8
print("now at", name(seat), "| view", value(seat))

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 6-7

A fixed seed gives the same run every time. Start on C3 (view 8) with T = 5.

تۆوێکی جێگیر هەمان کارپێکردن هەموو جارێک دەدات. لەسەر ⁦C3⁩ (دیمەن ⁦8⁩) بە ⁦T = 5⁩ دەست پێبکە.

Lineدێڕی 9-10

Try ONE random neighbour and compute the change ΔE (delta).

یەک دراوسێی هەڕەمەکی تاقی بکەرەوە و گۆڕانەکەی ΔE (delta) بژمێرە.

Lineدێڕی 11-15

Better: always move. Worse: move only if a random number is below e^(ΔE/T).

باشتر: هەمیشە بجووڵێ. خراپتر: تەنیا ئەگەر لە e^(Δ⁦E/T⁩) بچووکتر بوو، بجووڵێ.

Lineدێڕی 21

Cool down after every step.

دوای هەر هەنگاوێک سارد بکەرەوە.

Steps 1–4 (hot): the search accepts four worse seats in a row and leaves the good seat C3. Hill climbing could never do this.
Steps 5, 6 and 9: better seats are always taken, up to D7, the best seat.
Steps 10–14 (cold): worse seats now have a chance of 5% or less, and all are refused. The search stays on D7.
A chance shown as 0.00 is not exactly zero: at step 11 it is e^(−4/0.54) ≈ 0.0006.

هەنگاوەکانی ⁦1–4⁩ (گەرم): گەڕانەکە چوار کورسیی خراپتر لە دوای یەک وەردەگرێت و کورسیی باشی ⁦C3⁩ بەجێ دەهێڵێت. هەرگیز ناتوانێت ئەمە بکات.
هەنگاوەکانی 5، 6 و 9: کورسیی باشتر هەمیشە وەردەگیرێت، تا ⁦D7⁩، نایابترین کورسی.
هەنگاوەکانی ⁦10–14⁩ (سارد): کورسیی خراپتر ئێستا ئەگەری ⁦5%⁩ یان کەمتری هەیە و هەموویان ڕەت دەکرێنەوە. گەڕانەکە لەسەر ⁦D7⁩ دەمێنێتەوە.
ئەگەرێک کە وەک ⁦0.00⁩ پیشان دراوە بە تەواوی سفر نییە: لە هەنگاوی ⁦11⁩دا e^⁦(−4/0.54)⁩ ≈ ⁦0.0006⁩ـە.

The algorithm and its acceptance ruleئەلگۆریزمەکە و یاسای وەرگرتنەکەی

The cinema in Python: hill climbing against simulated annealingسینەماکە بە Python: چیاهەڵەگڕی بەرامبەر simulated annealing

Now the full experiment. Both methods start on seat C2. Hill climbing runs once (it has no randomness). Simulated annealing runs 100 times for each of three cooling speeds, and we count how often it ends on the best seat D7.

ئێستا تاقیکردنەوە تەواوەکە. هەردوو ڕێگەکە لە کورسیی ⁦C2⁩ەوە دەست پێدەکەن. یەک جار کار دەکات (هیچ هەڕەمەکییەکی تێدا نییە). بۆ هەر یەک لە سێ خێرایی ساردکردنەوە ⁦100⁩ جار کار دەکات و دەژمێرین چەند جار لەسەر نایابترین کورسی، ⁦D7⁩، کۆتایی دێت.

Hill climbing and simulated annealing in the dark cinemaچیاهەڵەگڕی و simulated annealing لە سینەما تاریکەکەداcinema_annealing.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

import math
import random

# How good the view is from each seat (row A is nearest to the screen).
# A pillar stands in front of the middle seats (column 5), so their view is poor.
VIEW = [
    [1, 2, 2, 3, 3, 3, 2, 2, 1],    # A
    [2, 4, 5, 4, 3, 5, 6, 5, 2],    # B
    [3, 6, 8, 6, 4, 7, 9, 7, 3],    # C
    [3, 5, 6, 5, 4, 8, 10, 8, 3],   # D
    [2, 3, 4, 3, 2, 5, 6, 5, 2],    # E
]
ROWS, SEATS = len(VIEW), len(VIEW[0])


def name(seat):
    row, col = seat
    return "ABCDE"[row] + str(col + 1)          # (2, 1) -> "C2"


def value(seat):
    row, col = seat
    return VIEW[row][col]


def neighbours(seat):
    """In the dark you can only reach the seats right next to you."""
    row, col = seat
    steps = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    return [(row + dr, col + dc) for dr, dc in steps
            if 0 <= row + dr < ROWS and 0 <= col + dc < SEATS]


def hill_climbing(seat):
    while True:
        best = max(neighbours(seat), key=value)
        if value(best) <= value(seat):
            return seat                         # no better seat next to me
        seat = best


def simulated_annealing(seat, cooling, t=5.0, t_min=0.05):
    while t > t_min:
        new = random.choice(neighbours(seat))   # try a RANDOM seat next to me
        delta = value(new) - value(seat)        # > 0 means better
        if delta > 0 or random.random() < math.exp(delta / t):
            seat = new                          # move (sometimes to a worse seat)
        t = t * cooling                         # cool down a little
    return seat


if __name__ == "__main__":
    start = (2, 1)
    print("start at", name(start), "| view", value(start))
    end = hill_climbing(start)
    print("hill climbing stops at", name(end), "| view", value(end))

    random.seed(2025)
    for cooling in (0.9, 0.99, 0.999):
        ends = [simulated_annealing(start, cooling) for _ in range(100)]
        found = sum(1 for seat in ends if value(seat) == 10)
        print(f"simulated annealing, cooling {cooling}: best seat D7 found "
              f"{found} times out of 100")

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 6-12

The view from each seat. Column 5 (behind the pillar) is a valley of poor seats.

دیمەنی هەر کورسییەک. ستوونی 5 (لە پشت کۆڵەکەکە) دۆڵێکە لە کورسیی خراپ.

Lineدێڕی 26-31

In the dark you can only reach the four seats next to you.

لە تاریکیدا تەنیا دەتوانیت بگەیتە ئەو چوار کورسییەی لە تەنیشتتن.

Lineدێڕی 34-39

Hill climbing (steepest ascent), as in the previous lesson.

، وەک وانەی پێشوو.

Lineدێڕی 42-49

Simulated annealing: the whole algorithm in eight lines.

: هەموو ئەلگۆریزمەکە لە هەشت دێڕدا.

Lineدێڕی 52-63

The experiment: one hill climb, then 3 × 100 annealing runs.

تاقیکردنەوەکە: یەک ، پاشان ⁦3 × 100⁩ جار کارپێکردنی annealing.

Hill climbing from C2 always stops on the good seat C3 (8). It never sees D7.
Simulated annealing finds D7 often, and slower cooling finds it more often: 12, then 73, then 90 times out of 100.
Even with slow cooling it is not 100 out of 100. That is the honest version of the paper's “in the end you reach the very best seat”.
The price of slow cooling is time: cooling 0.9 makes 44 steps per run, cooling 0.999 makes about 4,600.

لە ⁦C2⁩ەوە هەمیشە لەسەر کورسیی باشی ⁦C3 (8)⁩ دەوەستێت. هەرگیز ⁦D7⁩ نابینێت.
زۆر جار ⁦D7⁩ دەدۆزێتەوە و ساردکردنەوەی هێواشتر زیاتر دەیدۆزێتەوە: ⁦12⁩، پاشان ⁦73⁩، پاشان ⁦90⁩ جار لە ⁦100⁩ جار.
تەنانەت بە ساردکردنەوەی هێواشیش ⁦100⁩ لە ⁦100⁩ نییە. ئەمە وەشانی ڕاستگۆیانەی «لە کۆتاییدا دەگەیت بە کورسییە هەرە نایابەکە»ی وتارەکەی کۆرسەکەیە.
نرخی ساردکردنەوەی هێواش کاتە: ساردکردنەوەی ⁦0.9⁩ لە هەر کارپێکردنێکدا ⁦44⁩ هەنگاو دەنێت، ⁦0.999⁩ نزیکەی ⁦4,600⁩.

Quick checkپشکنینی خێراWhat happens if you make the cooling slower (0.999 instead of 0.9)?چی ڕوودەدات ئەگەر ساردکردنەوەکە هێواشتر بکەیت (⁦0.999⁩ لەبری ⁦0.9⁩)؟It always finds the best seat at onceهەمیشە دەستبەجێ نایابترین کورسی دەدۆزێتەوەThe best seat is found more often, but each run takes more stepsنایابترین کورسی زیاتر دەدۆزرێتەوە، بەڵام هەر کارپێکردنێک هەنگاوی زیاتر دەباتIt becomes plain hill climbingدەبێتە چیاهەڵەگڕیی سادە

Another picture: the delivery driverوێنەیەکی تر: شۆفێری گەیاندن

Finding a quicker delivery routeدۆزینەوەی ڕێگەیەکی خێراتری گەیاندن

Imagine you are a delivery driver who wants the most efficient way to deliver packages to different places. From your start, the first route you choose may not be the best: you may be stuck in traffic or take longer roads. But instead of sticking to that first route, you explore other routes, even ones that look worse at first, by trying different turns and detours. Over time you may find a quicker route that avoids the traffic. Simulated annealing works the same way: it explores different possibilities and then “cools down” on the best choice, to find the optimal solution.

بیهێنە بەرچاوت کە شۆفێری گەیاندنیت و دەتەوێت باشترین ڕێگە بدۆزیتەوە بۆ گەیاندنی بەستەکان بۆ شوێنی جیاواز. لە سەرەتاوە، یەکەم ڕێگە کە هەڵیدەبژێریت ڕەنگە باشترین نەبێت: لەوانەیە لە قەرەباڵغیی هاتوچۆدا گیر بخۆیت یان ڕێگەی درێژتر بگریت. بەڵام لەبری ئەوەی لەسەر ئەو یەکەم ڕێگەیە بمێنیتەوە، ڕێگەی تر تاقی دەکەیتەوە، تەنانەت ئەوانەی سەرەتا خراپتر دەردەکەون، بە تاقیکردنەوەی پێچی جیاواز و ڕێگەی لادان. بە تێپەڕبوونی کات ڕەنگە ڕێگەیەکی خێراتر بدۆزیتەوە کە لە قەرەباڵغی دوور بێت. بە هەمان شێوە کار دەکات: ئەگەرە جیاوازەکان دەپشکنێت و پاشان لەسەر باشترین هەڵبژاردن «سارد دەبێتەوە»، تاکو باشترین چارەسەر بدۆزێتەوە.

Where the analogy stops workingسنووری ئەم نموونەیە

A real driver remembers the good routes he has tried and can return to them. Simulated annealing keeps only its current state; it does not keep a list of the best routes so far (you may add that as an extra).

شۆفێرێکی ڕاستەقینە ڕێگە باشەکانی کە تاقی کردوونەتەوە لە بیر دەگرێت و دەتوانێت بۆیان بگەڕێتەوە. تەنیا ئێستای ڕادەگرێت؛ لیستی باشترین ڕێگاکانی تا ئێستا هەڵناگرێت (دەتوانیت ئەمە وەک زیادە بخەیتە سەری).

Detour: a way from one place to another that is longer than the usual way, or a different road that traffic uses when the usual road is closed.
Optimal: the best or most suitable.

ڕێگەی لادان ⁦(detour)⁩: ڕێگەیەک لە شوێنێکەوە بۆ شوێنێکی تر کە لە ڕێگە ئاساییەکە درێژترە، یان ڕێگەیەکی تر کە هاتوچۆ بەکاری دەهێنێت کاتێک ڕێگە ئاساییەکە داخراوە.
Optimal: باشترین یان گونجاوترین.

Quick checkپشکنینی خێراIn the delivery-driver picture, what plays the role of a “worse move”?لە وێنەی شۆفێری گەیاندندا، چی ڕۆڵی «جووڵەی خراپتر» دەبینێت؟Trying a detour that looks longer at firstتاقیکردنەوەی ڕێگەیەکی لادان کە سەرەتا درێژتر دەردەکەوێتStopping at the first routeوەستان لەسەر یەکەم ڕێگەDelivering a packageگەیاندنی بەستەیەک

The lesson behind it: do not give upوانەی پشتەوەی: کۆڵ مەدە

If you look carefully, simulated annealing contains perseverance (not giving up): it gets you out of a bad situation now, even if the next steps include some wrong steps. A step backwards is sometimes the way forward.

ئەگەر سەرنج بدەیت، کۆڵنەدانی لەخۆ گرتووە، تاکو لە بارودۆخی ناهەموار و خراپی ئێستادا دەربازت بێت، ئەگەرچی هەنگاونانی داهاتوو هەندێک هەنگاوی هەڵەشی لەخۆ گرتبێت. هەندێک جار هەنگاوێک بۆ دواوە ڕێگەی پێشەوەیە.

Common mistakesهەڵە باوەکان

Mistakeهەڵە	What is trueڕاستییەکە
“Annealing means heating metal to change its shape.”«Annealing واتە گەرمکردنی کانزا بۆ گۆڕینی شێوەکەی.»	Annealing is heating and then slow cooling so the inside settles into a stable order.Annealing گەرمکردن و پاشان ساردکردنەوەی هێواشە تاکو ناوەوەی کانزاکە لە ڕیزبەندییەکی جێگیردا ڕێک بێت.
“It takes random steps all the time.”«هەموو کاتێک هەنگاوی هەڕەمەکی دەنێت.»	Better moves are always taken; worse moves only with probability e^(ΔE/T), which shrinks as T falls.جووڵەی باشتر هەمیشە وەردەگیرێت؛ جووڵەی خراپتر تەنیا بە e^(Δ⁦E/T⁩)، کە بە دابەزینی T بچووک دەبێتەوە.
“It always finds the global maximum.”«هەمیشە دەدۆزێتەوە.»	Only with a probability that approaches 1 when cooling is slow enough. Our test: 90 of 100.تەنیا بە کە لە 1 نزیک دەبێتەوە ئەگەر ساردکردنەوەکە بە تەواوی هێواش بێت. تاقیکردنەوەکەمان: ⁦90⁩ لە ⁦100⁩.
“Cool fast to save time.”«بە خێرایی سارد بکەرەوە بۆ ئەوەی کات بگەڕێتەوە.»	Fast cooling turns it into hill climbing too early: in our test only 12 of 100 runs found the best seat.ساردکردنەوەی خێرا زوو دەیکات بە : لە تاقیکردنەوەکەماندا تەنیا ⁦12⁩ لە ⁦100⁩ کارپێکردن نایابترین کورسیی دۆزییەوە.
Using e^(ΔE/T) for better moves too.بەکارهێنانی e^(Δ⁦E/T⁩) بۆ جووڵەی باشتریش.	For ΔE > 0 the formula is above 1; simply always move. The probability is only for ΔE ≤ 0.بۆ Δ⁦E > 0⁩ ئەنجامی فۆرمولەکە لە 1 زیاترە؛ بە سادەیی هەمیشە بجووڵێ. تەنیا بۆ Δ⁦E ≤ 0⁩ـە.

Exercises and the exam questionڕاهێنانەکان و پرسیاری تاقیکردنەوە

ExerciseڕاهێنانAnswer the course questionوەڵامی پرسیاری کۆرسەکە بدەرەوە

“A hill-climbing algorithm that never makes a move towards a lower value is guaranteed to be incomplete, because it can get stuck on a local maximum. A random walk may be complete but not efficient. Simulated annealing yields both efficiency and completeness. How?” Write a short answer (5–6 sentences).

« کە هەرگیز بەرەو بەهای نزمتر ناجووڵێت، بێگومان تەواو نییە، چونکە دەکرێت لەسەر بچەقێت. لەوانەیە تەواو بێت بەڵام کارا نییە. هەم کارایی و هەم دەبەخشێت. چۆن؟» وەڵامێکی کورت بنووسە (⁦5–6⁩ ڕستە).

Hintئاماژە

Use the words: temperature, worse moves, probability, cooling.

ئەم وشانە بەکار بهێنە: ، جووڵەی خراپتر، ، ساردکردنەوە.

Show answerوەڵامەکە پیشان بدە

Simulated annealing mixes the two methods and changes the mix over time. It always accepts a better neighbour, and it accepts a worse one with probability e^(ΔE/T). At the start the temperature T is high, so many worse moves are accepted: the search behaves like a random walk and can leave local maxima (this gives completeness). The temperature then falls slowly, so worse moves become rare and the search behaves like hill climbing, climbing quickly to a top (this gives efficiency). If T falls slowly enough, the probability of ending at the global maximum approaches 1.

دوو ڕێگەکە تێکەڵ دەکات و ڕێژەی تێکەڵەکە بە تێپەڕبوونی کات دەگۆڕێت. دراوسێی باشتر هەمیشە وەردەگرێت و دراوسێی خراپتر بە e^(Δ⁦E/T⁩) وەردەگرێت. لە سەرەتادا T بەرزە، بۆیە زۆر جووڵەی خراپتر وەردەگیرێت: گەڕانەکە وەک ڕەفتار دەکات و دەتوانێت بەجێ بهێڵێت (ئەمە دەبەخشێت). پاشان بە هێواشی دادەبەزێت، بۆیە جووڵەی خراپتر دەگمەن دەبێت و گەڕانەکە وەک ڕەفتار دەکات و بە خێرایی بەرەو لووتکەیەک سەردەکەوێت (ئەمە کارایی دەبەخشێت). ئەگەر T بە تەواوی هێواش دابەزێت، کۆتاییهاتن لە لە 1 نزیک دەبێتەوە.

ExerciseڕاهێنانCompute the chancesئەگەرەکان بژمێرە

A neighbour is 3 worse than the current state (ΔE = −3). Compute the probability of accepting it at T = 6, T = 3 and T = 1. (e^(−0.5) ≈ 0.61, e^(−1) ≈ 0.37, e^(−3) ≈ 0.05)

دراوسێیەک 3 لە ئێستا خراپترە (Δ⁦E = −3⁩). وەرگرتنی لە ⁦T = 6⁩، ⁦T = 3⁩ و ⁦T = 1⁩ بژمێرە. (e^⁦(−0.5)⁩ ≈ ⁦0.61⁩، e^⁦(−1)⁩ ≈ ⁦0.37⁩، e^⁦(−3)⁩ ≈ ⁦0.05⁩)

Show answerوەڵامەکە پیشان بدە

T = 6: e^(−3/6) = e^(−0.5) ≈ 0.61 → accepted about 61% of the time.
T = 3: e^(−3/3) = e^(−1) ≈ 0.37 → about 37%.
T = 1: e^(−3/1) = e^(−3) ≈ 0.05 → about 5%. The colder it is, the more “picky” the search becomes.

⁦T = 6: e⁩^⁦(−3/6) = e⁩^⁦(−0.5)⁩ ≈ ⁦0.61⁩ ← نزیکەی لە ⁦61%⁩ی جارەکاندا وەردەگیرێت.
⁦T = 3: e⁩^⁦(−3/3) = e⁩^⁦(−1)⁩ ≈ ⁦0.37⁩ ← نزیکەی ⁦37%⁩.
⁦T = 1: e⁩^⁦(−3/1) = e⁩^⁦(−3)⁩ ≈ ⁦0.05⁩ ← نزیکەی ⁦5%⁩. هەتا ساردتر بێت، گەڕانەکە «درەنگهەڵبژێرتر» دەبێت.

ExerciseڕاهێنانTwo extreme schedulesدوو بەرنامەی ساردکردنەوەی توند

In cinema_annealing.py, what would happen (a) if T never fell (cooling = 1.0, and you stop after a fixed number of steps), and (b) if T started tiny, for example t=0.1 (just above t_min = 0.05, otherwise the loop would not run at all)? Which earlier algorithm does each case become?

لە cinema_annealing.pyدا چی ڕوودەدات (أ) ئەگەر T هەرگیز دانەبەزێت (⁦cooling = 1.0⁩ و پاش ژمارەیەکی دیاریکراو هەنگاو بوەستیت)، (ب) ئەگەر T زۆر بچووک دەست پێبکات، بۆ نموونە t=0.1 (کەمێک لە t_min = 0.05 زیاتر، ئەگینا هەر کار ناکات)؟ هەر حاڵەتێک دەبێتە کام ئەلگۆریزمی پێشوو؟

Hintئاماژە

Look at e^(ΔE/T) when T is very large and when T is very small.

سەیری e^(Δ⁦E/T⁩) بکە کاتێک T زۆر گەورەیە و کاتێک زۆر بچووکە.

Show answerوەڵامەکە پیشان بدە

(a) With a high T that never falls, e^(ΔE/T) stays large (for a seat that is 1 worse at T = 5 it is e^(−0.2) ≈ 0.82), so most worse moves are accepted: it behaves almost like a random walk. It wanders forever and ends on whatever seat it happens to be on.
(b) With a tiny T, e^(ΔE/T) is almost 0 for every worse move, so only better moves are taken, chosen at random: it becomes stochastic hill climbing. From C2 it moves to C3 and stays there, like plain hill climbing (tested: 10 runs out of 10).

(أ) بە T ـێکی بەرز کە هەرگیز دانابەزێت، e^(Δ⁦E/T⁩) گەورە دەمێنێتەوە (بۆ کورسییەک کە 1 خراپترە لە ⁦T = 5⁩دا e^⁦(−0.2)⁩ ≈ ⁦0.82⁩ـە)، بۆیە زۆربەی جووڵە خراپترەکان وەردەگیرێن: نزیکەی وەک ڕەفتار دەکات. بۆ هەمیشە دەسوڕێتەوە و لەسەر هەر کورسییەک کۆتایی دێت کە بە ڕێکەوت لەسەری بێت.
(ب) بە T ـێکی زۆر بچووک، e^(Δ⁦E/T⁩) بۆ هەموو جووڵەیەکی خراپتر نزیکەی 0ـە، بۆیە تەنیا جووڵەی باشتر وەردەگیرێت کە بە هەڕەمەکی هەڵدەبژێردرێن: دەبێتە . لە ⁦C2⁩ەوە دەچێتە ⁦C3⁩ و لەوێ دەمێنێتەوە، وەک سادە (تاقی کرایەوە: ⁦10⁩ جار لە ⁦10⁩ جار).

ExerciseڕاهێنانRemember the best seatباشترین کورسی لە بیر بگرە

Change simulated_annealing so that it also remembers the best seat it has ever sat on and returns that one at the end. Why can this only help?

simulated_annealing بگۆڕە تاکو باشترین کورسیش لە بیر بگرێت کە هەرگیز لەسەری دانیشتووە و لە کۆتاییدا ئەوە بگەڕێنێتەوە. بۆچی ئەمە تەنیا سوودی هەیە؟

Show answerوەڵامەکە پیشان بدە

best_seat.pyPYTHONType in a terminalلە تێرمیناڵدا بینووسە

def simulated_annealing(seat, cooling, t=5.0, t_min=0.05):
    best = seat                             # the best seat seen so far
    while t > t_min:
        new = random.choice(neighbours(seat))
        delta = value(new) - value(seat)
        if delta > 0 or random.random() < math.exp(delta / t):
            seat = new
            if value(seat) > value(best):
                best = seat                 # remember a new best seat
        t = t * cooling
    return best

Explain the codeڕوونکردنەوەی کۆدەکە

Lineدێڕی 2

Start with the first seat as the best one.

یەکەم کورسی وەک باشترین دەست پێبکە.

Lineدێڕی 8-9

After every move, keep the better of the two.

دوای هەر جووڵەیەک، باشترەکەی هەردووکیان هەڵبگرە.

Replace the function in cinema_annealing.py with this one and run it again. The result can never be worse than before: if the search visits D7 and later wanders away while it is still warm, the copy in best keeps D7. It costs only one extra comparison per step.

ئەم لەبری ئەوەی ناو cinema_annealing.py دابنێ و دیسان کاری پێ بکە. ئەنجامەکە هەرگیز لە پێشوو خراپتر نابێت: ئەگەر گەڕانەکە سەردانی ⁦D7⁩ بکات و دواتر لە کاتێکدا هێشتا گەرمە لێی دوور بکەوێتەوە، کۆپییەکەی ناو best ⁦D7⁩ دەپارێزێت. تەنیا یەک بەراوردی زیادە لە هەر هەنگاوێکدا تێدەچێت.

cinema_annealing.py with this function⁦cinema_annealing.py⁩ بەم کردارەوە

start at C2 | view 6
hill climbing stops at C3 | view 8
simulated annealing, cooling 0.9: best seat D7 found 12 times out of 100
simulated annealing, cooling 0.99: best seat D7 found 81 times out of 100
simulated annealing, cooling 0.999: best seat D7 found 100 times out of 100

Same seed, so the same runs as before: 12 → 12, 73 → 81, 90 → 100. With slow cooling every run visits D7 at some point.

هەمان تۆو، کەواتە هەمان کارپێکردنەکانی پێشوو: ⁦12⁩ ← ⁦12⁩، ⁦73⁩ ← ⁦81⁩، ⁦90⁩ ← ⁦100⁩. بە ساردکردنەوەی هێواش هەموو کارپێکردنێک لە کاتێکدا سەردانی ⁦D7⁩ دەکات.

ExerciseڕاهێنانAnnealing for the delivery driverannealing بۆ شۆفێری گەیاندن

Describe simulated annealing for the delivery driver: what is a state, a neighbour, the value, and what does the temperature mean?

بۆ شۆفێری گەیاندن وەسف بکە: چییە، دراوسێ چییە، بەها چییە و چ واتایەکی هەیە؟

Show answerوەڵامەکە پیشان بدە

State: one complete delivery route (the order of the addresses).
Neighbour: the same route with one change, for example two addresses swapped or a different road between two stops.
Value: the total driving time (a cost: lower is better, so “better” means ΔE in the cost goes down).
Temperature: how willing the driver is to try a detour that looks slower. Early in the week (hot) he tries many; later (cold) he keeps to the fast route.

: ڕێگەیەکی تەواوی گەیاندن (ڕیزبەندیی ناونیشانەکان).
دراوسێ: هەمان ڕێگە بە یەک گۆڕانکاری، بۆ نموونە گۆڕینەوەی شوێنی دوو ناونیشان یان ڕێگەیەکی تر لە نێوان دوو وەستگەدا.
بەها: کۆی کاتی لێخوڕین (کۆستە: کەمتر باشترە، بۆیە «باشتر» واتە کۆستەکە کەم دەبێتەوە).
: شۆفێرەکە چەند ئامادەیە ڕێگەیەکی لادان تاقی بکاتەوە کە خاوتر دەردەکەوێت. سەرەتای هەفتە (گەرم) زۆریان تاقی دەکاتەوە؛ دواتر (سارد) بە ڕێگە خێراکەوە دەمێنێتەوە.

Summary and reviewکورتە و پێداچوونەوە

Hill climbing is efficient but incomplete; a random walk is complete but not efficient. Simulated annealing gets both.
The name imitates annealing: heating metal and cooling it slowly so it settles into a stable state (not changing its shape).
Rule: a better neighbour is always taken; a worse one with probability e^(ΔE/T).
A cooling schedule lowers T: hot = explore, cold = climb. Slow cooling finds the global maximum with probability near 1, but takes longer.
The cinema: hill climbing stops on a good seat; simulated annealing usually reaches the best seat.

کارایە بەڵام تەواو نییە؛ تەواوە بەڵام کارا نییە. هەردووکیانی دەست دەکەوێت.
ناوەکە لاسایی annealing دەکاتەوە: گەرمکردنی کانزا و ساردکردنەوەی بە هێواشی تاکو لە دۆخێکی جێگیردا ڕێک بێت (نەک گۆڕینی شێوەکەی).
یاسا: دراوسێی باشتر هەمیشە وەردەگیرێت؛ خراپتر بە e^(Δ⁦E/T⁩).
T دادەبەزێنێت: گەرم = گەڕان، سارد = سەرکەوتن. ساردکردنەوەی هێواش بە نزیک لە 1 دەدۆزێتەوە، بەڵام کاتی زیاتر دەبات.
سینەماکە: لەسەر کورسییەکی باش دەوەستێت؛ زۆربەی جار دەگاتە نایابترین کورسی.

Review questionsپرسیارەکانی پێداچوونەوە

What does the temperature T control?پلەی گەرمی T چی کۆنترۆڵ دەکات؟

How likely the search is to accept a worse move: high T, often; low T, almost never.

ئەوەی گەڕانەکە جووڵەیەکی خراپتر وەربگرێت: T ـی بەرز، زۆر جار؛ T ـی نزم، نزیکەی هەرگیز.

Why must the temperature fall slowly?بۆچی دەبێت پلەی گەرمی بە هێواشی دابەزێت؟

So the search has time to leave local maxima before it becomes too picky; cooling too fast makes it stop on a local maximum.

تاکو گەڕانەکە کاتی هەبێت بەجێ بهێڵێت پێش ئەوەی زۆر درەنگهەڵبژێر بێت؛ ساردکردنەوەی زۆر خێرا وای لێ دەکات لەسەر بوەستێت.

What does “simulated” mean in the name?«Simulated» لە ناوەکەدا چ واتایەکی هەیە؟

Imitated: the algorithm imitates the physical process of annealing metal.

لاساییکراوە: ئەلگۆریزمەکە لاسایی کارلێکی فیزیایی annealingی کانزا دەکاتەوە.

In the cinema example, what is the local maximum?لە نموونەی سینەماکەدا لووتکەی ناوخۆیی چییە؟

A good seat (C3 in our hall) that is better than all the seats next to it, while a better seat (D7) exists elsewhere.

کورسییەکی باش (⁦C3⁩ لە هۆڵەکەی ئێمەدا) کە لە هەموو کورسییەکانی تەنیشتی باشترە، لە کاتێکدا کورسییەکی باشتر ⁦(D7)⁩ لە شوێنێکی تر هەیە.

At T = 0.5, how likely is a move that is 1 worse?لە ⁦T = 0.5⁩دا جووڵەیەک کە 1 خراپترە چەند ئەگەری هەیە؟

e^(−1/0.5) = e^(−2) ≈ 0.14, about 14%.

e^⁦(−1/0.5) = e⁩^⁦(−2)⁩ ≈ ⁦0.14⁩، نزیکەی ⁦14%⁩.

Videoڤیدیۆ

Watch a videoسەیری ڤیدیۆیەک بکە

A video that viewers liked a lot and praised in their comments, chosen for this lesson.ڤیدیۆیەک کە بینەران زۆریان پێ خۆش بووە و لە کۆمێنتەکانیاندا ستایشیان کردووە، بۆ ئەم وانەیە هەڵبژێردراوە.

Harvard CS50’s Artificial Intelligence with Python – Full University CoursefreeCodeCamp.org · Englishئینگلیزی · 5.1M viewsبینین · 134K likesلایک · Partبەشی 6:03:51–6:14:51 (ofلە 11:51:22)
Harvard's CS50 AI lecturer explains each idea with clear pictures and Python code; each placement plays only the chapter that matches its screen.
مامۆستای کۆرسی ⁦CS50 AI⁩ـی زانکۆی Harvard هەر بیرۆکەیەک بە وێنەی ئاشکرا و کۆدی ڕوون دەکاتەوە؛ لە هەر شوێنێک تەنها ئەو بەشەی لێدەدرێت کە لەگەڵ ئەو شاشەیە دەگونجێت.
Plays 6:03:51–6:14:51: simulated annealing, the temperature, the probability e^(ΔE/T) of accepting a worse state, and the travelling salesman problem.
لە ⁦6:03:51⁩ تا ⁦6:14:51⁩ لێدەدرێت: ، ، `e^(ΔE/T)` بۆ وەرگرتنی خراپتر، هەروەها .

Lesson complete!وانەکە تەواو بوو!

Well done. Review the key terms, then go on to the next lesson.دەستخۆش. سەیرێکی زاراوە سەرەکییەکان بکەرەوە، پاشان بڕۆ بۆ وانەی داهاتوو.

Key termsزاراوە سەرەکییەکان

Next lessonوانەی داهاتوو

Building Tic-Tac-Toe in Pythonدروستکردنی یاریی ئێکس‌وئۆ بە Python

Related lecturesوانە پەیوەندیدارەکان

Search Problems: States, Actions, Goals and Costsکێشەکانی گەڕان: دۆخەکان، کردەوەکان، ئامانج و کۆست

References and further readingسەرچاوەکان و خوێندنەوەی زیاتر

This lecture is a first edition. The Kurdish text and terminology are waiting for review by Kurdish IT teachers.ئەم وانەیە چاپی یەکەمە. دەقە کوردییەکە و زاراوەکانی چاوەڕێی پێداچوونەوەی مامۆستایانی کوردی بواری IT ن.