• شبکه های عصبی^[۲۰]

تحقیقات در این زمینه نشان داده است که مغز، اطلاعات را همانند الگو‌ها ذخیره می‌کند. فرایند ذخیره‌سازی اطلاعات به صورت الگو و تجزیه و تحلیل آن الگو‌، اساس روش نوین محاسباتی را تشکیل می‌دهند. این حوزه از دانش محاسباتی به هیچ وجه از روش‌های برنامه‌نویسی سنتی استفاده نمی‌کند و به‌جای آن از شبکه های بزرگی که به صورت موازی آرایش شده‌اند و تعلیم یافته‌اند، بهره می‌جوید.

• الگوریتم جهش قورباغه^[۲۱]

در این الگوریتم یک جمعیت شامل دسته­ای قورباغه ‌می‌باشد. این جمعیت (جواب) به زیرمجموعه­هایی تقسیم می­ شود. هر یک از زیر مجموعه­ها به جستجوی محلی می ­پردازد. این فرایند و عمل جستجوی محلی تا زمانی ادامه می­یابد که شرط همگرایی برآورده شود.

• الگوریتم زنبور عسل^[۲۲]

در این الگوریتم با دریافت دامنه تغییرات هر یک از متغیرها و تحلیل حالت بی­شمار تلفیق دامنه­ها با یکدیگر، حالت بهینه را به دست ‌می‌آورد.

• الگوریتم اجتماع پرندگان^[۲۳]

در طراحی روش­های فراابتکاری، دو معیارمتناقض شامل کاوش در فضای جواب و تبعیت از بهترین راه ­حل­های پیدا شده باید درنظر گرفته شود. این روش­ها را ‌می‌توان برای مسائل ساده با ابعاد بزرگ یا با محدودیت­های زمان واقعی (مسائلی که نیاز به حل در همان زمان دارند) و یک مسئله سخت(Np-hard)، مسائل با توابع هدف یا محدودیت­های پیچیده، مدل­های غیر­تحلیلی مسائل بهینه­ سازی و یا در شرایط غیرقطعی کاربرد دارد (فتاحی، ۱۳۹۰).

• الگوریتم ممتیک

الگوریتم ممتیک گونه ­ای از الگوریتم­های تکاملی است که در آن جستجو­های ابتکاری محلی با الگوریتم ژنتیک ترکیب می­شوند تا در زمان کمتر نتایج بهتری به دست آید ( کاتالیو و جیم، ۲۰۰۵ ).

الگوریتم­های ژنتیک برای شناسایی بخش وسیعی از فضای جستجو ایجاد می­شوند، در حالی که جستجوی محلی می ­تواند حوزه نزدیک به هر پاسخ یافته شده توسط الگوریتم ژنتیک را (که به آن همسایگی گفته می­ شود) برای یافتن پاسخ­های بهتر مورد جستجو قرار دهد. این که برای پیاده ­سازی یک الگوریتم ممتیک و در بخش ژنتیک آن از چه عملگرهایی و یا برای جستجوی محلی از کدام روش استفاده شود، نتایج اجرای بسیار متفاوتی خواهد داشت (جولا و خاتون­ناصری، ۲۰۰۷).

• رنگ­آمیزی گراف

هر گراف شامل چندین رأس یا گره است که با یک سری یال به یکدیگر متصل هستند. به دو راسی که با یک یال به یکدیگر متصل ‌شده‌اند رأس مجاور یا همسایه گفته می­ شود. مسئله رنگ­آمیزی گراف( GCP)، ‌به این صورت است که با داشتن گراف G، حداقل تعداد رنگ­های لازم برای رنگ آمیزی رئوس گراف را می­یابد طوری که هیچ دو رأس مجاوری همرنگ نباشند. حداقل تعداد رنگ­های لازم برای این کار، عدد رنگی گراف نامیده می­ شود.

برای تبدیل مسئله جدول زمان­بندی ‌می‌توان تدریس­ها را به عنوان گره در گراف در نظر گرفت و در صورتی که دو تدریس از نظر هم­زمانی با یکدیگر غیرمجاز باشند بین آن دو گره یک یال رسم کرد. برای رنگ­آمیزی گراف تشکیل شده، دوره ­های زمانی به عنوان رنگ در نظر گرفته می­ شود و به گره­ ها (تدریس­ها)، هر کدام یک رنگ (زمان) الصاق می­ شود، به طوری که هیچ دو گره مجاوری دارای رنگ (بازه زمانی) مشابهی نباشند. رنگ­های در نظر گرفته شده برای هر گره بایستی طوری باشد که محدودیت­های سخت را ارضا کند.

۲-۲-۴- معرفی الگوریتم ژنتیک

نظریه تکامل چارلز داروین که در سال ۱۸۵۹ ارائه گردید، جایگاه ویژه­ای را در مسائل بهینه­ سازی به خود اختصاص داد. این نظریه بر اساس تکامل بهترین­ها ارائه گردید و آن را ‌می‌توان به عنوان نقطه شروعی برای محاسبات تکاملی دانست. ایده محاسبات تکاملی اولین بار در سال ۱۹۶۰ توسط رچنبرگ که در زمینه استراتژی­ های تکاملی تحقیق می­کرد به وجود آمد. در سال ۱۹۷۵ پروفسور هلند این ایده را در کتاب خود با نام ” انطباق بین طبیعت و سیستم­های هوشمند” ارائه کرد (فتاحی، ۱۳۹۰). او ایده استفاده از تکامل طبیعی در حل مسائل بهینه­ سازی را شرح داد که پایه­ای برای الگوریتم ژنتیک محسوب می­گردید. مشهورترین تکنیک در تحقیقات محاسبات تکاملی، الگوریتم ژنتیک است. در این الگوریتم فرض می­گردد که هر موقعیت (نقطه) در رشته معرف یک ویژگی خاص از یک فرد(جواب) است و مقدار مشخص شده برای آن موقعیت، نشان­دهنده نحوه بیان آن ویژگی در جواب است. این الگوریتم، یک تکنیک جستجو را برای یافتن راه ­حل­های نزدیک بهینه برای مسائل بهینه­ سازی ارائه می­ نماید.

الگوریتم ژنتیک با یک جمعیت اولیه از راه ­حل­ها شروع می­گردد. هر راه ­حل از طریق یک کروموزوم که رشته­ای از بیت­ها است و در واقع شکل کد­شده یک جواب ممکن از مسئله مورد نظر ‌می‌باشد، نمایش داده می­ شود. تمامی راه ­حل­های ممکن باید با بهره گرفتن از یک سیستم کدگذاری، تبدیل به کد شوند. سپس مجموعه ­ای از اپراتورهای تولید مثل، باید تعیین گردند. اپراتورهای تولید مثل، مستقیماً روی کروموزوم­ها عمل نموده و سپس کروموزوم­ها تحت اپراتور جهش و رویه ترکیب قرار می­ گیرند. طراحی ساختار کدگذاری تأثیر زیادی روی عملکرد الگوریتم ژنتیک خواهد داشت.

جدول ۲-۱- مقایسه الگوریتم ژنتیک با سیستم­های طبیعی (مسعودیان و استکی، ۱۳۸۸)

سیستم­های طبیعی
الگوریتم ژنتیک

کروموزوم: بسته­های ژنی هستند که اطلاعات وراثتی را از نسلی به نسل دیگر انتقال می­ دهند.

کروموزوم: پاسخ­های ممکن مسئله که به صورت رشته­ های عددی رمزگذاری شده اند.

محیط: شرایط محیطی که جمعیت در آن قرار دارد و دیکته کننده نحوه تحول است.

تابع برازش: محک کیفیت یک کروموزوم که به صورت یک رابطه ریاضی درآمده که آن را تابع برازش می­نامند.

اصل انتخاب طبیعی: معیار بقای موجود زنده و تکثیر آن، سازش با محیط است.

تکثیر: هر رشته جمعیت را به عنوان متغیر تابع برازش در نظر گرفته و مقدار تابع برازش هر رشته محاسبه می­ شود. متناسب با مقدار تابع برازش، رشته­ های والدین برای تولید جمعیت جدید انتخاب می­ شود.

تقاطع: در نتیجه تقاطع یا تبادل قسمتی از کروموزوم­ها، مبادله ژن­های پیوسته صورت ‌می‌گیرد.

ادغام: رشته­ های جمعیت به صورت دو به دو مزدوج می­شوند. زوج رشته­ ها از یک نقطه قطع می­شوند. نیم بخش­های بین دو رشته تعویض می­شوند.

جهش: جانشین شدن ژنی به جای ژن دیگر یا در تغییرات ایجاد شده در DNA طول زنجیره ژن. گاهی قسمتی از یک ژن جانشین ژن دیگری می­ شود.

جهش: یک بیت از رشته عددی به صورت تصادفی انتخاب می­ شود و ‌دچار تغییر می­گردد.

تجدید نسل: ایجاد نسل­های جدید و تکامل موجودات

تجدید نسل: تکرار مراحل الگوریتم بعد از مرحله تکثیرتا حصول پاسخ بهینه یا رسیدن به حد توقف.