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