جمعیت^[۱۱۵]: مجموعه‌ای از کروموزوم‌ها را یک جمعیت می‌گویند.
نسل^[۱۱۶]: هر تکرار از الگوریتم را یک نسل می‌گویند.
۶ - ساختار کلی الگوریتم ژنتیک
ساختار کلی یک الگوریتم ژنتیک را می‌توان به صورت ذیل تصور کرد.
ابتدا پیش از هر چیز باید مکانیسمی برای تبدیل هر جواب مساله به یک کروموزوم تعریف کرد. پس از آن یک مجموعه از کروموزوم‌ها که در حقیقت مجموعه‌ای از جواب‌های مساله هستند به عنوان یک جمعیت آغازین^[۱۱۷] تهیه می‌گردند. این مجموعه که اندازه آن دلخواه است و توسط کاربر تعریف می‌شود اغلب به صورت تصادفی ایجاد می‌گردد.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

بعد از این مرحله باید با بکارگیری عملیات ژنتیک^[۱۱۸] اقدام به ایجاد کروموزوم‌های جدید موسوم به نوزاد^[۱۱۹]نمود. این عملیات به دو گونه عمده تقاطعی و جهشی تقسیم‌بندی می‌شوند. همچنین برای گزینش کروموزوم‌هایی که باید نقش والدین را بازی کنند دو مفهوم نرخ تقاطعی^[۱۲۰] و نرخ­جهشی^[۱۲۱] کاربرد فراوان دارند که این دو نیز پیش از شروع الگوریتم توسط کاربر تعیین می‌شوند.
بعد از تولید یکسری کروموزوم جدید یا اولاد باید با بهره گرفتن از عمل تحول^[۱۲۲] اقدام به انتخاب^[۱۲۳]برازنده‌ترین کروموزوم‌ها نمود. این فرایند که در فرایند انتخاب نمود می‌یابد گلچین‌کردن کروموزوم‌های برازنده در میان والدین و اولاد است به طوریکه تعداد کروموزوم‌های منتخب برابر با اندازه جمعیت اولیه باشد. فرایند انتخاب مبتنی بر مقدار برازندگی^[۱۲۴] هر رشته است. در حقیقت فرایند ارزیابی^[۱۲۵] محوری‌ترین بحث در فرایند انتخاب است.
تا بدین مرحله یک تکرار یا یک نسل از الگوریتم طی شده است. الگوریتم بعد از طی چندین نسل به تدریج به سمت جواب بهینه همگرا می‌شود. شرط توقف مساله نیز طی‌کردن تعداد معینی تکرار است که پیش از آغاز الگوریتم توسط کاربر تعیین می‌شود.
ساختار کلی یک الگوریتم ژنتیک را می‌توان به صورت ذیل بیان کرد ]۳۷[:
Procedure: Genetic Algorithm
Step 1: Set t:=0
Step 2: Generate initial population, p(t).
Step 3: Evaluate p(t) to creat fitness values
Step 4: While (not termination cordination) do:
Step 5: Recombine p(t) to yield c(t), selecting from p(t) according to the fitness values.
Step 6: Evaluate c(t)
Step 7: Generate p(t+1) from p(t) and c(t)
Step 8: Set t:=t+1
Step 9: End.
Step 10: Stop
P(t)= والدین نسل t
C(t)= نوزاد نسل t

۵-۳ : الگوریتم فراابتکاری شبیه­سازی تبرید

هدف رویکرد شبیه­سازی تبرید اجتناب از بهینه های موضعی با بهره گرفتن از تغییرات دما و استراتژی پذیرش جواب­های غیربهبود دهنده (جستجوی up/down-hill) در یک محیط گسسته می­باشد. رویکرد شبیه­سازی تبرید دارای مزایای برجسته متعددی نسبت به سایر رویکردهای فراابتکاری است که عبارتند از:
وابستگی زیادی به نقطه­ی اولیه ندارد.
قابلیت فرار از بهینه­های موضعی را دارد.
از لحاظ برنامه­نویسی و اجرا ساده است.
ثابت شده است که زمان محاسباتی آن دارای حد بالایی از نوع چندجمله­ای معین برحسب ابعاد مسأله است]۴۹[.
اساس تئوریک شبیه­سازی تبرید بر مبنای توزیع بولتزمن استوار است. برطبق توزیع بولتزمن، احتمال قرار گرفتن یک سیستم فرضی در وضعیت X=[x_ij] طبق توزیع زیر تعیین می­ شود.
(۱-۴)
بطوری­که T مبین دمای جاری سیستم و E(X) مشابه رابطه (۴-۳) برابر سطح انرژی سیستم در وضعیت X می باشد. به Zتابع پارتیشن گفته می­ شود. در الگوریتم شبیه­سازی تبرید ، برطبق قاعده تصمیم ­گیری متروپلیس ]۴۹[، احتمال تغییر وضعیت سیستم از X به X مادامی که دمای سیستم در حال کاهش باشد، بصورت رابطه زیر محاسبه می­گردد.
(۲-۴)
بطوری­که  یک عدد ثابت دلخواه می­باشد. رابطه فوق بیان می­ کند که اگر سطح انرژی سیستم در وضعیت X کمتر از X باشد، آنگاه حتماً سیستم از X به X تغییر وضعیت خواهد داد در غیراین­صورت با احتمال معین  این تغییر وضعیت صورت خواهد گرفت.
که این احتمال به دمای جاری سیستم و اختلاف سطح انرژی بین دو وضعیت،  ، بستگی دارد. بنابراین، نکته حائز اهمیت آن است که دمای اولیه سیستم چقدر بوده و دما با چه نرخی کاهش پیدا کند. کارایی شبیه سازی تبرید به مقدار زیادی به نرخ کاهش دما یا اصطلاحاً زمان­بندی سرمایش^[۱۲۶] و همچنین دمای اولیه وابسته است ]۱۴[. هدف صرف زمان بیشتر در نزدیکی دمای بحرانی T_c است. منظور از دمای بحرانی، دمایی است که در آن دست­یابی به بهینه سراسری محسوس­تر است، یعنی فرار از بهینه موضعی بطور معناداری سخت یا طولانی­تر می­ شود. برای T>>T_c رفتار شبیه سازی تبرید تقریباً بصورت تصادفی است، در حالی­که برای T<<T_c ، شبیه­سازی تبرید به یک بهینه موضعی همگرا یا اصطلاحاً فریز^[۱۲۷] خواهد شد. رویه متداول بدین­ترتیب است که الگوریتم از یک دمای اولیه، T₀، نسبتاً بالا فرایند خود را آغاز کرده و در هر تکرار الگوریتم، مقدار دما به آهستگی و تا رسیدن به یک دمای نهایی T_f کاهش خواهد یافت. دامنه کاهش دما عمدتاً بگونه­ای تعیین می­گردد که رابطه T₀/T_f=2 برقرار باشد ]۳۹[. تاکنون تحقیقات زیادی در زمینه زمان­بندی دما در شبیه­سازی تبرید انجام و پیشنهادات فراوانی نیز ارائه شده است. اولین و متداول­ترین قاعده به هنگام سازی دما که توسط کیرک پاتریک^[۱۲۸]]۴۹[ . پیشنهاد شد، بصورت زیر می­باشد. این قاعده بعدها مبنای بسیاری از قواعد دیگر به هنگام­سازی دما قرار گرفت.
 (۳-۴)
بطوری­که k شمارنده انتقالات دما می­باشد. همچنین T_k برابر دمای سیستم در تکرار kام و نیز معرف ضریب یا نرخ کاهش دما می­باشد که عمدتاً مقدار آن بین ۸/۰ تا ۹۹/۰ اختیار می­گردد. مقادیر بالای مبین کاهش آهسته دما و در نتیجه جستجوی بهتر همسایگی­ها می­باشد. ولی زمان حل را افزایش می­دهد. برعکس مقادیر کمتر مبین کاهش سریع دما و در نتیجه جستجوی سریع­تر همسایگی­ها می­باشد که منجر به همگرایی زودرس الگوریتم خواهد شد. یکی دیگر از قواعد کارا برای به هنگام سازی دما توسط گاتزمن^[۱۲۹] پیشنهاد شد ]۳۹[. این قاعده بصورت زیر است.
(۴-۴)
بطوری­که N برابر اندازه یا ابعاد مسأله و پارامتر معرف ثابت واپاشی یا اضمحلال^[۱۳۰] است که مقدار آن بصورت زیر محاسبه می­گردد.

که درآن K برابر حداکثر تعداد انتقالات یا کاهش دما (یعنی حداکثر مقدار شمارنده k) است که به عنوان معیار توقف الگوریتم بکار می­رود. یکی دیگر از پارامترهای اساسی در شبیه سازی تبرید ، تعداد جواب­های پذیرفته شده در هر دما، N، می­باشد. این پارامتر حجم جستجوی همسایگی جواب­ها را در هر دما کنترل می­ کند. با کاهش دما، اندازه همسایگی نیز کاهش می­یابد زیرا احتمال پذیرش جواب­های غیربهبود دهنده نیز در حال کاهش است. بنابراین مقدار N باید به اندازه­ای بزرگ باشد که موجب جستجوی مؤثر همسایگی شده و حدالمقدور به جواب­های بهتری که ممکن است در همسایگی وجود داشته باشند، دست یابد. از طرف دیگر مقدار N نباید آنقدر بزرگ باشد تا موجب جستجوی غیرمؤثر و ناکارا شده و زمان حل را افزایش دهد. اگر الگوریتم نتواند بیش از این در دمای جاری به جواب بهتری دست یابد، اصطلاحاً می گوییم سیستم در دمای جاری به تعادل^[۱۳۱] رسیده است و نیاز به بهنگام سازی دما می­باشد. بصورت تجربی، در بسیاری از تحقیقات مقدار N حدود ۱۰۰ در نظر گرفته شده است ]۹۰[.
یکی دیگر از نکات اساسی در شبیه سازی تبرید، استراتژی جستجوی همسایگی است. این امر می ­تواند با توجه به ماهیت مسأله، بسیار پیچیده باشد. چگونگی حرکت از نقطه­ای به نقطه دیگر (move) بستگی به ساختار عملگرهای طراحی شده دارد. دستیابی به نقاط کشف نشده فضای جواب و همچنین جستجوی دقیق همسایگی نقاط(Exploitation)، منوط به طراحی عملگرهای کارا و مؤثر می­باشد. این کار در بسیاری از مسایل پیچیده بهینه­سازی با متغیرهای تصمیم متنوع و محدودیت­های متعدد، امری دشوار است، تا آنجائی­که ممکن است بسیاری از رویکردهای فراابتکاری عملاً کارایی خود را از دست بدهند ]۹۰[.
شکل (۸-۳) فلوچارت یک شبیه سازی تبرید کلاسیک را نشان می­دهد. همان­طورکه در شکل (۸-۳) نشان داده شده است، الگوریتم شبیه­سازی تبرید از دو حلقه داخلی^[۱۳۲] و خارجی^[۱۳۳] تشکیل شده است. وظیفه حلقه داخلی کنترل دست­یابی به تعادل در هر دما است. همچنین وظیفه حلقه خارجی بهنگام سازی دما می­باشد. حلقه تصمیم ­گیری متروپلیس (احتمال پذیرش جواب­های غیربهبود دهنده) در درون حلقه داخلی تعبیه شده است. برطبق این حلقه تصمیم ­گیری، اگر جواب اخیراً تولید شده یعنی X^new نتواند تابع هدف را نسبت به جواب فعلی یعنی Xⁿ بیشتر بهبود دهد یعنی E = E(X^new)- E(Xⁿ)>0 ، آنگاه با احتمال  جواب X^new پذیرفته خواهد شد؛ بطوری­که y یک عدد تصادفی یکنواخت پیوسته در بازه [۰ ,۱] می­باشد. بنابراین احتمال پذیرش جواب غیربهبود دهنده به تغییرات مقدار تابع زیان، E، و دمای جاری بستگی خواهد داشت. همان­طورکه در شکل (۸-۳)، n شمارنده حلقه داخلی و k شمارنده حلقه خارجی است. همچنین E( ) معرف تابع لاگرانژین مشابه رابطه (۴-۲) می­باشد ]۹۰[.
شکل ۹-۳: فلوچارت یک شبیه سازی تبرید کلاسیک ]۹۰[
پارامترهای T₀، T_f،N ،Kو را از دریافت کنید
قرار دهید n = ۰ و k = ۰
جواب اولیه X⁰ را تولید کرده و مقدار X⁰)E( را محاسبه کنید
با بهره گرفتن از یک عملگر مناسب، جواب همسایگی X^new را تولید کرده و X^new)E( را محاسبه کنید
E(X^new)- E(Xⁿ)< 0
قرار دهید n = n+1 و Xⁿ =X^new
بله