۳- روش پیشنهادی

۳-۱- راه‌کارهای پیشنهادی
چون مسأله توالی هواپیما یک مسأله NP-سخت است، الگوریتمهای دقیق کارایی خود را بر روی این مسأله در ابعاد بالا از دست میدهند و نمیتوانند به جواب بهینه در یک‌زمان قابل‌قبول دست یابند. درنتیجه امروزه برای حل اینگونه مسائل از الگوریتمهای ابتکاری و فرا ابتکاری استفاده میشود. توجه به این نکته ضروری است که الگوریتمهای ابتکاری در یک‌زمان اندک به جواب زیر بهینه میرسند اما چون دارای ساختار خوبی برای فرار از نقاط بهینه محلی نیستند، معمولاً به جواب‌های باکیفیت همگرا نمیشوند. از طرف دیگر در چند دهه اخیر الگوریتمهایی پیشنهاد شدند که دارای ساختار تصادفی برای رسیدن به جواب مسأله هستند. این الگوریتمها که فرا ابتکاری نامیده میشوند، میتوانند تا حد امکان از بهینه‌های محلی فرار کنند و به جواب‌های بسیار خوبی همگرا شوند که یکی از این الگوریتم‌ها ICA میباشد.
۳-۲- الگوریتم تکاملی

۳-۲-۱ مقدمه

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

همان‌گونه که از شبه کد نیز معلوم است، الگوریتمهای تکاملی جزئی از الگوریتم‌های تولید – آزمایش^[۵۸] هستند.
الگوریتم تکاملی مبتنی بر جمعیت است.
الگوریتم تکاملی از ترکیب استفاده می‌کند تا اطلاعات گونه‌های بیشتری را در یک‌گونه خلاصه کند.
الگوریتم تکاملی اتفاقی است.
گونههای مختلف الگوریتم‌های تکاملی همگی از طرح کلی که ارائه شد، پیروی می‌کنند و فقط در جزئیات فنی متفاوت هستند.

۳-۲-۲-علت استفاده از الگوریتم‌های تکاملی

الگوریتمهای تکاملی در مقایسه با سایر الگوریتمهای بهینه‌سازی برتری‌هایی دارند که موجب شده است به‌طور گسترده مورداستفاده قرار بگیرند. به‌عنوان‌مثال، این الگوریتمها، نیاز به معرفی کامل مسأله ندارند و تنها با داشتن اطلاعات چندی در مورد تعریف مسأله میتوانند کار کنند. همچنین محدودیتی در مورد تابع شایستگی ندارند و لزومی ندارد که این تابع مثلاً مشتق‌پذیر باشد.
علاوه بر این موارد، چون الگوریتمهای تکاملی دارای جمعیتی از موجودات هستند و روی بخشهای مختلفی از جمعیت به‌طور موازی کار میکنند، احتمال کمتری برای قرار گرفتن در بهینههای محلی^[۵۹] دارند. این قابلیت الگوریتمهای تکاملی اجازه میدهد که کار بهینه‌سازی را به‌طور موازی روی چندین بخش جمعیت انجام داد. به‌عنوان نتیجه این ویژگی گفته میشود که الگوریتمهای تکاملی روی جمعیتها خوب عمل می‌کنند. این‌گونه جمعیتها دارای تعداد زیادی بهینههای محلی هستند. الگوریتمهای تکاملی در این بهینههای محلی گیر^[۶۰] نمیکنند و معمولاً میتوانند درنهایت به بهینه‌ترین جواب برسند.

۳-۲-۳- انواع الگوریتم‌های تکاملی

الگوریتم‌های تکاملی زیرمجموعه‌ای از محاسبات تکاملی است و در شاخه هوش مصنوعی قرار می‌گیرد. الگوریتم‌های تکاملی شامل الگوریتم هایی جهت جستجو است که در آن‌ها عمل جستجو از چندین نقطه در فضای جواب میباشد. مسائل مهندسی و بهینه‌سازیای وجود دارند که راه‌حلهای عادی و متعارف برای آن‌ها چاره‌ساز نیستند؛ زیرا که یا تحلیلی برای آن‌ها وجود ندارد (حل تحلیلی بسیار مشکلی دارند) و یا پیچیدگی، متغیرها و پارامترهای بسیار مسأله، انبوه از راه‌حل‌ها و نه لزوماً جواب مسأله را پیش روی مهندس میگذارد که امکان محک و ارزیابی تمام راه‌حل‌ها به دلیل تعداد بسیار زیاد وجود ندارد. الگوریتم‌های تکامل‌پذیر روش‌هایی بر مبنای جستجوی تصادفی‌اند که از مدل‌سازی تکامل بیولوژیکی طبیعی الگوبرداری شده‌اند. آن‌ها بر روی پاسخ‌های ممکنی کار می‌کنند که از ویژگی برتری برخوردار و نیز بقای نسل بیشتری دارند، لذا تخمین نزدیک‌تری از پاسخ بهینه به دست می‌دهند.
در هر نسل دسته جدیدی از تخمین‌ها بر مبنای انتخاب اعضای با میزان برازندگی (شایستگی) بیشتر تولیدشده و آن‌ها مشابه آنچه در طبیعت رخ می‌دهد باهم تلفیق می‌شوند. این روند نتیجتاً تکامل افرادی را شامل می‌شود که نسبت به والدینشان در محیط سازگارترند، دقیقاً مشابه آنچه در مطابقت با طبیعت است. الگوریتم‌های تکامل‌پذیر بر روی جمعیت‌هایی از افراد به‌جای یک تک پاسخ کار می‌کنند، ازاین‌رو جستجو به‌صورت موازی می‌تواند صورت گیرد.
چنین الگوریتم تکاملیِ تک جامعه‌ای به‌اندازه کافی قوی است و در گستره وسیعی از مسائل کارآمد می‌باشد. بااین‌حال با ایجاد چندین زیر جامعه نتایج بهتری به دست خواهد آمد. هر زیر جامعه بر روی چندین نسل جدا از هم (نظیر الگوریتم تکاملی تک جامعه‌ای) شکل می‌گیرد و پیش از آن هیچ عضوی بین زیر جامعه‌ها جابجا نخواهد شد. الگوریتم تکاملی چند جامعه‌ای تحول گونه‌ها را نسبت به الگوریتم تکاملی تک جامعه‌ای با روشی مشابه‌تر به طبیعت مدل‌سازی می‌نماید. الگوریتم‌های تکاملی به‌طور اساسی با دیگر روش‌های بهینه‌سازی و جستجوی مرسوم قدیمی تفاوت دارند. برخی از این تفاوت‌ها عبارت‌اند از:
الگوریتم‌های تکامل‌پذیر تنها یک تک نقطه را جستجو نمی‌کنند بلکه جمعیتی از نقاط را به‌صورت موازی بررسی می‌نمایند،
الگوریتم‌های تکامل‌پذیر نیاز به اطلاعاتی ضمنی و دیگر دانش‌های مکمل ندارند؛ تنها تابع هدف و شایستگی مربوطه در جهت‌های جستجو تأثیرگذارند،
الگوریتم‌های تکامل‌پذیر از قوانین در حال تغییر احتمالی بهره می‌برند و نه موارد مشخص و معین،
استفاده از الگوریتم‌های تکامل‌پذیر به‌طورکلی خیلی سرراست است، زیرا هیچ‌گونه محدودیت‌هایی برای تعریف تابع هدف وجود ندارد.
الگوریتم‌های تکامل‌پذیر تعداد زیادی از پاسخ‌های قابل‌قبول را به دست می‌دهند و انتخاب پایانی بر عهده کاربر است. لذا در مواردی که مسأله موردنظر شامل یک پاسخ مفرد نیست، مثلاً خانواده‌ای از پاسخ‌های بهینه-پَرِتو، مشابه آنچه در بهینه‌سازی چندهدفه و مسائل زمان‌بندی وجود دارد، الگوریتم‌های تکاملی برای شناسایی این پاسخ‌های چندگانه به‌طور همزمان ذاتاً کارآمدند.