نوع جهش را جهش خزنده مينامند.
2-1-2-11 حفظ بهترين كروموزومها
تا اينجا توليد جمعيت جديد خاتمه مييابد. اكنون براي آنكه بهترين كروموزوم نسل قبل را از دست ندهيم آنرا بهطور دستي در جاي بدترين كروموزوم نسل جديد قرار ميدهيم.
رهيافت ديگري براي حفظ بهترين كروموزوم ايناست كه جمعيت جديد و جمعيت قبلي را با هم در آميخته و سپس آنها را بر حسب برازندگيشان از بزرگ به كوچك طبقه بندي ميكنيم. سپس ppsz (برابر با تعداد جمعيت اولیه) كروموزوم اول جمعيت كه از همه برازندگيشان بيشتر است بهعنوان جمعيت جديد برميگزينيم.
در اين روش جمعيت با ميانگين برازندگي بالاتري تشكيل ميگردد و بهجاي انتقال بهترين كروموزوم و حذف بدترين كروموزوم دستهاي از بهترين كروموزومها جاي دستهاي از بدترين كروموزومها را ميگيرند. با اين عمل همگرايي به سمت عدد بهينه در اجراي الگوريتم سريعتر و زمان اجراي برنامه تا يافتن جواب مناسب كاهش مييابد.
2-1-2-12 تکرار تا زمان توقف
حال جمعيت جديدی توليد شده است كه ميانگين برازندگي آن از نسل قبلي بهتر است. با اين جمعيت، مجددا مراحل قبل را از گام چهارم تا يازدهم تكرار كرده و اين اعمال را آنقدر انجام ميدهيم تا به مقدار بهين دست پيدا كنيم.
2-2 روش شبیه سازی تبرید21SA
مقایسه ساختار پیچیده پیکربندی فضای جواب مسائل بهینه سازی سخت، با بعضی از پدیدههای فیزیکی توسط کرک پاتریک22 و همکارانش در انجمن IBM ، منجر به ارائهی پیشنهاد یک روش جدید تکراری (تکنیک انجماد تدریجی (شبیه سازی تبرید)) که توانایی خروج از بهینه محلی را داشت، گردید. همچنین اثر مشابهی در همان زمان توسط کرنی23 در سال 1985 منتشر گردید. آنها از الگوریتم انجماد تدریجی (SA) برای افراز بندی گرافها استفاده نمودند. SA بهدلیل سادگی و همچنین کارایی بالا در حل مسائل بهینه سازی ترکیبی، جایگاه ویژهای در بین تکنیکهای جستجو و هیوریستیکها در دهه 1980 بهدست آورد. این تکنیک بعدها به حوزه مسائل بهینهسازی پیوسته نیز توسعه داده شد.
2-2-1: مقایسه با پدیدههای فیزیکی
در طبیعت فرایند تغییر شکل منظم را بهصورت خودبهخود، زمانیکه دمای یک سیستم بهتدریج کاهش مییابد، میتوان دید. آرایش مولکولی یک جسم داغ که در ابتدا ساختاری غیر منظم داشته و دارای فاصله زیادی از همدیگر است، زمانیکه دمای آن بهآرامی کاهش پیدا میکند، به یک ساختار منظم و نزدیک به هم تغییر شکل پیدا میکند.
به دو صورت میتوان جسم را سرد کرد. در حالت اول، جسم بهسرعت سرد میگردد که در اینحالت میزان آنتروپی (یا فاصله بین مولکولها) از همدیگر کاهش مییابد ولی بهمقدار حداقلی، نخواهد رسید. در حالت دوم، جسم بهآرامی سرد میشود و مولکولها این فرصت را پیدا میکنند که کلیه فضاهای خالی را پر کرده و آرایش منظمتری را ایجاد نمایند. در این حالت میزان آنتروپی به حداقل خود خواهد رسید.
بهمنظور تولید یک ساختار کریستالی، ابتدا جسم به اندازه کافی دما داده میشود و سپس آن جسم به آرامی سرد میگردد. در طول فرایند کاهش دما، پس از هر مرحله کاهش، مدتی جسم در آن دما باقی میماند. این مرحله به آرامی ادامه پیدا میکند تا جسم به پایینترین دما رسانده شود که منجر به ایجاد یک حالت کریستالی در جسم خواهد شد. در صورتیکه در مرحلهای کاهش دما بهتندی، صورت گیرد، حالت غیر بلوری ایجاد خواهد شد.
الگوریتم شبیه سازی تبرید که انجماد تدریجی نیز نامیده میشود، از پدیده انجماد فیزیکی فوق الگو گرفته شده است. در این الگوریتم شبیه به پدیده آنیلینگ، از یک پارامتر دما برای کنترل الگوریتم در طول بهبود جواب مساله استفاده میگردد. جدول زیر مقایسهای بین یک سیستم فیزیکی با مسائل و الگوریتم های بهینه سازی را نمایش میدهد.
جدول 2-7: مقایسه بین یک مساله و الگوریتم بهینه سازی با یک سیستم فیزیکی
سیستم فیزیکی
مساله و الگوریتم بهینه سازی
وضعیت سیستم
جواب
موقعیتهای مولکولی
متغیرهای تصمیم
انرژی
تابع هدف
وضعیت پایدار
جواب بهینه سراسری
وضعیت نیمه پایدار
بهینه محلی
سرد کردن سریع
جستجوی محلی
دما
پارامتر کنترل
آنیلینگ با دقت
شبیه سازی تبرید

2-2-2- روش کار الگوریتم شبیه سازی تبرید
فرض کنید فضای جواب s یک مجموعه متناهی از تمام جوابها و f مقدار تابع هدف، برای هر یک از عناصر باشد. هدف، پیدا کردن یک جواب یا حالتی مانند iєs است بهطوریکه f(i) روی s کمینه باشد. تبرید شبیه سازی شده، شکلی از روشهای سنتی کاهشی برای بهینه سازی محلی یا جستجوی همسایگی است. الگوریتم کاهش با یک جواب اولیه شروع میکند و از بین همسایگیهای این جواب، آن را که جواب حاضر را بهبود دهد انتخاب میکند و این همسایگی جدید بهجای جواب اولیه قرار میگیرد. این فرآیند ادامه مییابد تا اینکه دیگر هیچ یک از همسایگیهای جواب جاری نتواند مقدار تابع هدف را بهبود بخشد. در این حالت جواب جاری یک بهینه محلی است.
یکی از راههایی که میتوان برای بهبود این روش استفاده کرد این است که الگوریتم را چندین  بار با جوابهای اولیه مختلف اجرا کنیم و در نهایت بهینه محلی را انتخاب کنیم. شبیه سازی تبرید  بهجای استفاده ازاین استراتژی، سعی میکند در یک بهینه محلی قرار نگیرد و بنابراین برای این کار، بعضی اوقات جوابهایی که مقدار تابع هدف را افزایش داده میپذیرد. قبول یا رد این جواب به دنباله ای از اعداد تصادفی وابسته به یک کنترل احتمالی بستگی دارد. بهعلاوه اجتناب از جواب بهینه محلی، به برنامه آنیلینگ (گرم کردن و سپس به تدریج سرد کردن)، انتخاب دمای اولیه، تعداد تکرارهای لازم در هر دما و مقدار کاهش دما در هر مرحله بستگی دارد که درادامه به آنها اشاره خواهد شد.
در واقع این الگوریتم بر مبنای دو قاعده از فیزیک آماری عمل میکند:
قاعده اول بر این اساس است که وقتی تعادل ترمودینامیکی به یک دمای مشخص رسید، احتمال یک سیستم فیزیکی برای داشتن یک سطح انرژی E، با فاکتور بالتزمن24، e^((-E)⁄(k_B T)) که در آن k_B  توزیع بالتزمن در دمای مربوطه می باشد، متناسب است. بر اساس این قاعده احتمال پذیرش جوابها در دماهای مختلف متفاوت بوده و متناسب با تابع معرفی شده میباشد.
قاعده دوم نحوه رسیدن به تعادل ترمودینامیکی در یک دمای مشخص را بیان میکند. بر اساس آن، در یک دمای مشخص، با استفاده از الگوریتم متروپلیس تکامل یک سیستم فیزیکی در رسیدن به تعادل ترمودینامیکی در دمای مشخص شبیه سازی میگردد. بر اساس این قاعده، برای یک جواب یا پیکرهبندی مشخص یک سری محدود از حرکت یا تغییرات ابتدایی در نظر گرفته میشود. اگر یک تغییر شکل منجر به کاهش تابع هدف یا انرژی گردد، آن تغییر شکل پذیرفته میشود و درصورتیکه این تغییر شکل منجر به افزایش تابع هدف یا انرژی به اندازه E∆ گردد، تغییر شکل با احتمال e^((-∆ E)⁄T) پذیرفته میشود. این پذیرش از طریق تولید یک عدد تصادفی با توزیع یکنواخت در فاصله بین ۰و۱ و مقایسه آن با تابع تعریف شده انجام میگردد. در صورتی که مقدار عدد بهدست آمده کوچکتر از تابع تعریف شده باشد، تغییر شکل پذیرفته میشود. هر جواب از روی جواب پذیرفته شده قبلی خود تولید میگردد و با تکرار تولید جوابها و پذیرش آنها با استفاده از قاعده متروپلیس، یک توالی از جوابها بهوجود میآید که زنجیره مارکف را بهوجود آوردهاند. پایان یافتن این زنجیره با طول محدود و کافی را میتوان به رسیدن یک سیستم فیزیکی به تعادل ترمودینامیکی در یک دمای مشخص تشبیه کرد.
قاعده متروپلیس بهصورت زیر عمل میکند: در دمای بالا و مراحل اولیهی الگوریتم، مقدار e^((-E)⁄( T)) نزدیک به یک بوده و درنتیجه، اکثر حرکتها (تغییر شکلها) پذیرفته میشود و الگوریتم، رفتاری شبیه به یک جستجوی تصادفی را خواهد داشت. در دماهای پایین و اواخر الگوریتم، مقدار e^((-E)⁄( T)) به صفر نزدیک شده و اکثر جوابهای بدتر ردشده و تنها جوابهای خوب پذیرفته میشوند. شانس جابهجایی یک جواب خوب با یک جواب بدتر، خروج الگوریتم از جواب بهینهی محلی را تضمین میکند و از طرفدیگر، کاهش احتمال پذیرش جواب بدتر با کاهش دما، موجب تضمین همگرایی SA است.
معمولا الگوریتم های بهبود دهنده، که با یک جواب اولیه شروع شده و در طی مراحلی بهبود داده میشوند، ممکن است بعد از چند تکرار در نقطه بهینه محلی قرار بگیرند، که گاهی اوقات نیز از ناحیه جواب نهایی خیلی دور است. فرق الگوریتم انجمادتدریجی با الگوریتم های بهینهسازی محلی در ایناست، که در الگوریتم بهینهسازی محلی، یک جواب در همسایگی جواب قبلی ایجاد میشود، اگر تابع هدف بهواسطه جواب جدید بهترشود، جواب جدید قبول شده و در غیراینصورت جواب جدید رد میگردد. این عمل ممکن است منجر به قرارگرفتن در نقطه بهینه محلی شده و دیگر نتواند از آن خارج شود. درحالیکه در روش تبرید شبیه سازی شده، از توقف در ناحیه بهینه محلی اجتناب کرده و بهطور گذرا از آن رد میشود. این حالت با پذیرفتن احتمالی جوابهای بد انجام میشود، تا از نقطه بهینه محلی خارج شود. این احتمال برابر است با 〖( e〗^((-∆f)⁄T) ) که T میزان درجه حرارت و ∆f میزان تغییر در تابع هدف میباشد. اگراین احتمال از یک عدد تصادفی یکنواخت بین [ 0 ,1] ، بیشتر باشد، جواب نامناسب هم پذیرفته میشود.

2-2-3 : همگرایی الگوریتم انجماد تدریجی
بسیاری از محققین همگرایی الگوریتم شبیه سازی تبرید را بررسی نمودهاند و بعضی از آنها بهدنبال ارائهی یک مدل کلی برای تحلیل روشهای تصادفی در یافتن بهینه سراسری از مسائل بهینهسازی بودهاند. دستاوردهای اصلی آنها عبارتند از: در شرایط اطمینان، احتمالا الگوریتم شبیهسازی تبرید به سمت بهینه سراسری همگرا خواهد بود و بهعبارت دیگر، الگوریتم شبیه سازی تبرید، امکان رسیدن به نقطهای نزدیک به بهینه سراسری را خواهد داشت. این نتیجه، بهنوبهی خود، از اهمیت بهسزایی برخوردار بود. زیرا این نتیجه، موجب تمایز این الگوریتم نسبت به سایر الگوریتمهای مشابه که هنوز همگرایی آنها تضمین نشده بود، میگشت.
قبل از دادن یک طرح کلی پیشنهاد اکتشافی مبتنی بر SA برخی از نمادهای اضافی را معرفی میکنیم.
maxit: تعداد تکرارها تا زمان توقف الگوریتم
ilit: حداکثر تعداد تکرارها در هر دما
α: نرخ خنک کننده یا کاهش دما
temp_0: دمای اولیه
ffv: مقدار تابع تناسب
2-2-4 طرح کلی از SA پیشنهادی
مرحله 1: تولید تصادفی جمعیت اولیه از جوابها با اندازه از پیش تعیین شده ومحاسبه ffv برای هریک و بهترین مقدار آنرا ffv_0 مینامیم و قرار میدهیم solution=ffv_0 و bv(best value)=ffv_0
مرحله 2: تعیین پارامترهای اولیه
2-1: مقداردهی اولیه پارامترهای تبرید تدریجی ilit, maxit, α, temp_0
2-2: مقداردهی شمارشگر تکرار iter=0
مرحله 3: برنامه تبرید تدریجی
3-1: مقدار دهی اولیه حلقه داخلی il=0
3-2: رسیدن به تعادل در هر دما، اجرای حلقه داخلی تا زمانیکه شرایط 3-2-5 صدق کند
3-2-1: il=il+1
3-2-2: ایجاد یک جواب مجاور که در شرایط مدل صدق کند. محاسبه ffv مربوطه و نامگذاری آن بهعنوان ffv_il
3-2-3: ε=〖ffv〗_il-〖ffv〗_(il-1)
3-2-4: اگر(ε≥0 )
جواب جدید را قبول کن و ffv_il solution= و bv=ffv_il
درغیر اینصورت اگر (random(0,1)≤exp⁡((-ε)/temp_iter ))
جواب جدید را قبول کن و ffv_il solution=
در غیر اینصورت جواب جدید را ردکن و solution=ffv_(il-1)
3-2-5: اگر (il=ilit)
حلقه داخلی را خاتمه بده و برو به مرحله 3-3
در غیراینصورت حلقه داخلی را ادامه بده و برو به مرحله 3-2
3-3: temp_(iter+1)= temp_iter*α
3-4: iter=iter+1
3-5: اگر iter=maxit
برو به مرحله 3
درغیر اینصورت برو به مرحله 4
مرحله4:bv و solution را چاپ و توقف کن.

2-2-5 : اجزای

دسته بندی : No category

دیدگاهتان را بنویسید