الگوریتم ژنتیک^[۹]
این الگوریتم با جمعیتی از راهحلها آغاز میشود و در آن هر راهحل با یک کروموزوم نشان داده میشود. پس از کدگذاری تمامی راه حلها اپراتورهایی روی کروموزومها عمل کرده و جواب را تغییر داده تا جایی که جوابها به همگرایی برسند. ویژگی اصلی این الگوریتم این است که به جای تمرکز روی یک نقطه از فضای جستجو، روی جمعیتی از جوابها (کروموزومها) تمرکز دارد. با توجه به بکارگیری الگوریتم ژنتیک در این تحقیق، در ادامه به تشریح کاملتری از این الگوریتم خواهیم پرداخت.
روش تبرید شبیهسازیشده^[۱۰]
این الگوریتم، روشی تصادفی است که با جستجوی محلی، فضای حل را به صورت تصادفی و مؤثر جستجو میکند. این الگوریتم تلاش میکند در صورتی که حل در تکرارها به جواب بهتری دست نیابد، با پذیرش جوابهای بدتر که با احتمالی کاهشی همراه است از افتادن در دام بهینه محلی خودداری کند.
روش جستجوی ممنوعه^[۱۱]
این الگوریتم از یک نقطه یا راه حل شروع کرده و در اطراف آن نقطه به جستجوی همسایگی میپردازد. در بین همسایهها بهترین را انتخاب و به آن نقطه حرکت مینماید. این جستجو تا برآوردن معیار توقف ادامه مییابد.
الگوریتم مورچگان^[۱۲]
مسئله عمومی در این روش یافتن کوتاهترین مسیر بین دو رأس در یک گراف است. در ابتدا هر یال یک مقدار تصادفی به عنوان فرومون اولیه دریافت میکند و در طول اجرای الگوریتم غلظت فرومون^[۱۳] برخی از مسیرها (احتمال پذیرش مسیر) افزایش مییابد به طوریکه مسیرهای بهینه انتخاب شود.
شبکه های عصبی^[۱۴]
تحقیقات در این زمینه نشان داده است که مغز، اطلاعات را همانند الگو‌ها ذخیره می‌کند. فرایند ذخیره‌سازی اطلاعات به‌صورت الگو و تجزیه و تحلیل آن الگو‌، اساس روش نوین محاسباتی را تشکیل می‌دهند. این حوزه از دانش محاسباتی به هیچ وجه از روش‌های برنامه‌نویسی سنتی استفاده نمی‌کند و به‌جای آن از شبکه‌های بزرگی که به‌صورت موازی آرایش شده‌اند و تعلیم یافته‌اند، بهره می‌جوید.
الگوریتم جهش قورباغه^[۱۵]
در این الگوریتم یک جمعیت شامل دستهای قورباغه میباشد. این جمعیت (جواب) به زیرمجموعههایی تقسیم میشود. هر یک از زیر مجموعه ها به جستجوی محلی میپردازد. این فرایند و عمل جستجوی محلی تا زمانی ادامه مییابد که شرط همگرایی برآورده شود.
الگوریتم زنبور عسل^[۱۶]
در این الگوریتم با دریافت دامنه تغییرات هر یک از متغیرها و تحلیل حالت بیشمار تلفیق دامنهها با یکدیگر، حالت بهینه را بدست میآورد.
الگوریتم اجتماع پرندگان^[۱۷]
در طراحی روش های فراابتکاری، دو معیارمتناقض شامل کاوش در فضای جواب و تبعیت از بهترین راهحلهای پیدا شده باید درنظر گرفته شود. این روشها را میتوان برای مسائل ساده با ابعاد بزرگ یا با محدودیتهای زمان واقعی (مسائلی که نیاز به حل در همان زمان دارند) و یک مسئله سخت(Np-hard)، مسائل با توابع هدف یا محدودیتهای پیچیده، مدلهای غیرتحلیلی مسائل بهینه سازی و یا در شرایط غیرقطعی کاربرد دارد (فتاحی، ۱۳۹۰).

الگوریتم ممتیک
الگوریتم ممتیک گونهای از الگوریتمهای تکاملی است که در آن جستجوهای ابتکاری محلی با الگوریتم ژنتیک ترکیب میشوند تا در زمان کمتر نتایج بهتری به دست آید ( کاتالیو و جیم، ۲۰۰۵ ).
الگوریتمهای ژنتیک برای شناسایی بخش وسیعی از فضای جستجو ایجاد میشوند، در حالی که جستجوی محلی میتواند حوزه نزدیک به هر پاسخ یافته شده توسط الگوریتم ژنتیک را (که به آن همسایگی گفته میشود) برای یافتن پاسخهای بهتر مورد جستجو قرار دهد. این که برای پیادهسازی یک الگوریتم ممتیک و در بخش ژنتیک آن از چه عملگرهایی و یا برای جستجوی محلی از کدام روش استفاده شود، نتایج اجرای بسیار متفاوتی خواهد داشت (جولا و خاتونناصری، ۲۰۰۷).
رنگآمیزی گراف
هر گراف شامل چندین راس یا گره است که با یک سری یال به یکدیگر متصل هستند. به دو راسی که با یک یال به یکدیگر متصل شدهاند راس مجاور یا همسایه گفته میشود. مساله رنگآمیزی گراف( GCP)، به این صورت است که با داشتن گراف G، حداقل تعداد رنگهای لازم برای رنگ آمیزی رئوس گراف را مییابد طوری که هیچ دو راس مجاوری همرنگ نباشند. حداقل تعداد رنگهای لازم برای این کار، عدد رنگی گراف نامیده میشود.
برای تبدیل مسئله جدول زمانبندی میتوان تدریسها را به عنوان گره در گراف در نظر گرفت و در صورتیکه دو تدریس از نظر همزمانی با یکدیگر غیرمجاز باشند بین آن دو گره یک یال رسم کرد. برای رنگآمیزی گراف تشکیل شده، دوره های زمانی به عنوان رنگ در نظر گرفته میشود و به گرهها (تدریسها)، هر کدام یک رنگ (زمان) الصاق میشود، به طوری که هیچ دو گره مجاوری دارای رنگ (بازه زمانی) مشابهی نباشند. رنگهای در نظر گرفته شده برای هر گره بایستی طوری باشد که محدودیتهای سخت را ارضا کند.
۲-۲-۴- معرفی الگوریتم ژنتیک
نظریه تکامل چارلز داروین که در سال ۱۸۵۹ ارائه گردید، جایگاه ویژهای را در مسائل بهینه سازی به خود اختصاص داد. این نظریه بر اساس تکامل بهترینها ارائه گردید و آن را میتوان به عنوان نقطه شروعی برای محاسبات تکاملی دانست. ایده محاسبات تکاملی اولین بار در سال ۱۹۶۰ توسط رچنبرگ که در زمینه استراتژیهای تکاملی تحقیق میکرد به وجود آمد. در سال ۱۹۷۵ پروفسور هلند این ایده را در کتاب خود با نام ” انطباق بین طبیعت و سیستمهای هوشمند” ارائه کرد (فتاحی، ۱۳۹۰). او ایده استفاده از تکامل طبیعی در حل مسائل بهینه سازی را شرح داد که پایهای برای الگوریتم ژنتیک محسوب میگردید. مشهورترین تکنیک در تحقیقات محاسبات تکاملی، الگوریتم ژنتیک است. در این الگوریتم فرض میگردد که هر موقعیت (نقطه) در رشته معرف یک ویژگی خاص از یک فرد(جواب) است و مقدار مشخص شده برای آن موقعیت، نشان دهنده نحوه بیان آن ویژگی در جواب است. این الگوریتم، یک تکنیک جستجو را برای یافتن راهحلهای نزدیک بهینه برای مسائل بهینه سازی ارائه مینماید.
الگوریتم ژنتیک با یک جمعیت اولیه از راهحلها شروع میگردد. هر راهحل از طریق یک کروموزوم که رشتهای از بیتها است و در واقع شکل کدشده یک جواب ممکن از مسئله مورد نظر میباشد، نمایش داده میشود. تمامی راهحلهای ممکن باید با بهره گرفتن از یک سیستم کدگذاری، تبدیل به کد شوند. سپس مجموعهای از اپراتورهای تولید مثل، باید تعیین گردند. اپراتورهای تولید مثل، مستقیماً روی کروموزومها عمل نموده و سپس کروموزومها تحت اپراتور جهش و رویه ترکیب قرار میگیرند. طراحی ساختار کدگذاری تأثیر زیادی روی عملکرد الگوریتم ژنتیک خواهد داشت.
جدول ۲-۱- مقایسه الگوریتم ژنتیک با سیستمهای طبیعی (مسعودیان و استکی، ۱۳۸۸)