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

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

فرایند طراحی و پیاده‌سازی الگوریتم‌های فرا ابتکاری دارای سه مرحله‌ی متوالی است که هر کدام از آن‌ها دارای گام‌های مختلفی هستند[۴۰]. در هر گام فعالیت‌هایی باید انجام شود تا آن گام کامل شود. مرحله‌ی یک آماده‌سازی است که در آن باید شناخت دقیقی از مسأله‌ای که می‌خواهیم حل کنیم به­دست آوریم و اهداف طراحی الگوریتم فرا ابتکاری برای آن باید با توجه به روش‌های حل موجود برای این مسأله، به طور واضح و شفاف مشخص شود. مرحله‌ی بعدی، ساخت نام دارد. مهم­ترین اهداف این مرحله انتخاب استراتژی حل، تعریف معیارهای اندازه گیری عملکرد و طراحی الگوریتم برای استراتژی حل انتخابی می‌باشد. آخرین مرحله پیاده‌سازی است که در آن تنظیم پارامترها، تحلیل عملکرد و در نهایت تدوین و تهیه گزارش نتایج باید انجام شود.
معیارهای مختلفی برای طبقه‌بندی این الگوریتم‌ها استفاده می­ شود که در ادامه چند نمونه ذکر می­ شود:

• • مبتنی بر یک جواب و مبتنی بر جمعیت : الگوریتم‌های مبتنی بر یک جواب در حین فرایند جستجو یک جواب را تغییر می‌دهند، در حالی که در الگوریتم‌های مبتنی بر جمعیت در حین جستجو، یک جمعیت از جواب‌ها در نظر گرفته می‌شوند. از الگوریتم‌های متداول فراابتکاری مبتنی بر جمعیت می‌توان الگوریتم‌های تکاملی (الگوریتم ژنتیک، برنامه‌ریزی ژنتیک، …)، بهینه‌سازی کلونی مورچگان،کلونی زنبورها، روش بهینه‌سازی ازدحام ذرات و الگوریتم رقابت استعماری و از الگوریتم‌های متداول فرا­ابتکاری مبتنی بر یک جواب می‌توان الگوریتم جستجوی ممنوعه و الگوریتم تبرید شبیه‌سازی شده را نام برد.

• • الهام گرفته شده از طبیعت و بدون الهام از طبیعت: بسیاری از الگوریتم‌های فرا­ابتکاری از طبیعت الهام گرفته شده‌اند. مانند الگوریتم خفاش یا کلونی مورچه ها، در این میان برخی از الگوریتم‌های فراابتکاری نیز از طبیعت الهام گرفته نشده­اند.

• • با حافظه و بدون حافظه: برخی از الگوریتم‌های فرا­ابتکاری فاقد حافظه می‌باشند به این معنا که این نوع الگوریتم‌ها از اطلاعات به دست آمده در حین جستجو استفاده نمی کنند (به طور مثال تبرید شبیه‌سازی شده). این در حالی است که در برخی از الگوریتم‌های فرا ابتکاری نظیر جستجوی ممنوعه از حافظه استفاده می‌کنند. این حافظه اطلاعات بدست آمده در حین جستجو را در خود ذخیره می‌کند.

• • قطعی و احتمالی: یک الگوریتم فرا ابتکاری قطعی نظیر جستجوی ممنوعه، مسآله را با بهره گرفتن از تصمیمات قطعی حل می‌کند. اما در الگوریتم‌های فرا ابتکاری احتمالی نظیر تبرید شبیه سازی شده، یک سری قوانین احتمالی در حین جستجو مورد استفاده قرار می‌گیرد.

الگوریتم­های فرا­ابتکاری در حل بسیاری از مسائل بهینه‌سازی در حوزه‌های مختلف کاربرد دارند. در ادامه به ­طور اجمالی چند نمونه از این الگوریتم­ها به اختصار معرفی می­گردد. پس از آن به تفصیل الگوریتــم خفاش که یک الگوریتم فرا­ابتکاری می­باشد و هم­چنین اساس کار این رساله بر آن بنا گردیده است، مورد بررسی قرار خواهد گرفت.
۳-۳-۱- بهینه سازی توده­ی ذرات
بهینه سازی توده­ی ذرات به وسیله­ کندی و ابرهارت ارائه شده است [۴۱] . این روش ، از رفتارهای هوشمند پرندگان در یافتن غذا الگو برداری شده است . مانند الگوریتم­های هوش جمعی دیگر، PSO از مجموعه ­ای از جواب­های ممکن استفاده می­ کند و تا زمانی که از روی این جواب­ها یک جواب بهینه به دست آید یا معیار خاتمه برآورده شود ، الگوریتم ادامه می­یابد. در این الگوریتم هر جواب ممکن به وسیله­ یک ذره نشان داده می شود و یک توده­ی ذرات، مجموعه ­ای از ذرات می­باشد . مسئولیت تکامل توده به یک ناحیه­ی بهینه بر عهده­ تساوی سرعت می­باشد. این تساوی دربرگیرنده­ی سه مؤلفه می­باشد : مؤلفه­ی ضریب سرعت ، مؤلفه­ی فردی ((p_i و مؤلفه­ی اجتماعی (P_g). کل روش را می­توان به صورت یک الگوریتم رفتاری توزیع شده در نظر گرفت که یک جستجوی چند بعدی را انجام می­دهد.
در شبیه سازی، رفتار هر ذره به وسیله­ بهترین ذره­ی محلی یا بهترین ذره­ی سراسری تحت تأثیر قرار می­گیرد. یک ویژگی جالب در PSO این است که به ذرات اجازه داده می­ شود تا از تجربه قبلی خود استفاده کنند . این الگوریتم به طور موفق بر روی بازه­ی وسیعی از کاربردها اعمال شده است .
ابتدا ، تمامی ذرات به طور تصادفی در فضای جستجو مقدار دهی اولیه می­شوند . هم­چنین موقعیت­های اولیه­ p_i هر ذره نیز مقدار دهی اولیه می­شوند. سپس بهترین ذره­ی موجود در توده شناسایی شده و به جواب p_g انتساب داده می شود. پس از آن، توده­ی ذرات تا زمانی که معیار خاتمه به دست آید، در فضای جستجو پرواز می­ کند. پرواز، شامل اعمال کردن تساوی سرعت بر روی هر ذره است که سبب می­ شود موقعیت و برازندگی هر ذره تغییر کند. برازندگی به دست آمده توسط هر ذره با برازندگی به دست آمده از طریق بهترین موقعیت قبلی آن یعنی موقعیت p_i مقایسه می­ شود. اگر موقعیت جدید دارای برازندگی بهتری نسبت به برازندگی بهترین موقعیت قبلی باشد، در این صورت موقعیت جدید جایگزین p_i خواهد شد. هم­چنین، اگر بهترین موقعیت جدید ذرات دارای برازندگی بهتری نسبت به برازندگی بهترین موقعیت توده یعنی موقعیت p_g باشد، در این صورت بهترین موقعیت جدید جایگزین p_g خواهد شد. الگوریتم PSO دارای ساختار ساده­ای است و تعداد معدودی پارامتر در آن وجود دارد. الگوریتم حاصل برای محاسبه­ی موقیت بعدی ذره به صورت زیر بیان می شود :
v_t+1= v _t+ _۱ ۱(p_i - x_i)+ _۲۲ (p _g- x_i) (3-2)
x_t+1= x _t+ v_t+1
که در آن ثابت های _۲و_۱، توازن بین تأثیر یافته­های اشخاص یا دانش فردی (_۱) و یافته­های کل گروه (یا دانش جمعی_۲) (که هر دو در آغاز پیدایش این الگوریتم مقدار ۲ می­گرفتند) و _۲ و_۱ اعداد تصادفی با توزیع یکنواخت و دارای کران بالای _max ، پارامترهای الگوریتم می­باشند. توجه نمائید که پرانتزها باعث شتاب ذرات به طرف بهترین یافته های قبلی در فضا می گردند. برای یک فضای n – بعدی، سرعت ذرات در هر بعد محاسبه و سپس در یک بردار نهایی برای به روز کردن وضعیت ذره قرار می­گیرند. این تکنیک برای تعدادی از کاربرد­ها و مسائل پایه­ای مورد استفاده قرار گرفت که در اجرا بسیار جالب عمل می­کردند. در واقع، این روش­ها از تحریک پدیده ­های طبیعی و گروه بندی های اجتماعی برای بهینه سازی توابع مختلط که کاربرد وسیعی در صنعت دارند، الهام گرفته شده اند .
۳-۳-۲- الگوریتم جفت گیری زنبور عسل
جفت­گیری زنبورهای عسل به­عنوان یک روش عمومی برپایه رفتار حشرات جهت بهینه­سازی مورد استفاده قرار می­گیرد؛ که در واقع از فرایند جفت­گیری زنبورهای واقعی الهام گرفته است. یک کندو، دارای یک ملکه، صدها زنبور نر و حدود ده­ها هزار زنبور کارگر می­باشد. نقش اصلی ملکه تولید مثل و تخم­گذاری می­باشد. زنبورهای نر به عنوان پدر کندو ایفای نقش می­نمایند. زنبـورهای کارگر وظیفه بچه­داری و در برخی موارد تخم­گذاری را بر عهده دارند. تخم­های بارور به تولید ملکه و زنبورهای کارگر منجر می­ شود و در مقابل تخم­های نابارور، زنبورهای نر را تولید می­ کند.
زمان جفت­گیری ملکه با سرعت مشخصی از کندو خارج می­ شود؛ زنبورهای نر ملکه را تعقیب می­ کنند و آن­هایی که به ملکه می­رسند موفق به جفت­گیری با ملکه می­شوند، ولی بعد از عمل جفت­گیری می­میرند. ملکه تا زمانی که حجم محفظه اسپرم گنجایش داشته باشد به پرواز ادامه می­دهد؛ همین که حجم آن به اندازه مورد نظر رسید، در صورتی­که انرژی پرواز داشته باشد، به کنـدو بازمی­گردد. احتمال توانـایی جفت­گیری هر زنبـور نر با فرمول زیر شبیه­سازی می­گردد:
(۳-۳)
، عبارت است از احتمال اضافه شدن اسپرم زنبور نرِ  به حجم محفظه­ی اسپرم ملکه  و یا احتمال یک جفت­گیری موفق می­باشد.  قدر مطلق اختلاف بین تابع هدف زنبور نر  و تابع هدف ملکه  می­باشد.  سرعت ملکه در لحظه  می­باشد. این بدان معنا است که در ابتدای پرواز، که سرعت ملکه جهت جفت­گیری زیاد است و چنانچه تابع برازش زنبور نر نیز مناسب باشد، به­ طوری­که به مقدار تابع برازش ملکه نزدیک گردد آنگاه احتمال جفت­گیری مناسب زیاد است. به تدریج، سرعت و انرژی ملکه کاهش می­یابد. این موضوع با فرمول زیر نشان داده می­ شود:
(۳-۴)
مراحل اجرای این الگوریتم در زیر آورده شده است:
در شروع پرواز، ملکه، که همان جواب برتر می­باشد، زنبورهای نر را به طور تصادفی جهت تولید بچه­های جدید، انتخاب می­نماید.
بچه زنبورهای جدید با جابجایی ژن­های نر با ژن­های ملکه ایجاد می­شوند.
از زنبورهای کارگر جهت ارتقاء نسل استفاده می­گردد.
تابع برازش زنبور کارگر با توجه به میزان پیشرفت در نسل زنبورها مرتب می­گردد.
بچه زنبورهای برتر در حین انجام این فرایند در صورت برتری نسبت به ملکه، جایگزین آن می­شوند[۴۲].
۳-۳-۳- الگوریتم مورچگان
یک آزمایش بیولوژیکی معروف به نام آزمایش پل دو­گانه منبع مؤثری برای طرح اولین الگوریتم ACO بود. آزمایش پل دو طرفه برای بررسی تأثیر ردپای فرومون و رفتار حاصله مورچه­ها طراحی شده بود. در این آزمایش، یک پل دوطرفه با دو شاخه دارای طول­های متفاوت لانه این مورچه­ها را به یک منبع غذایی متصل می کرد (شکل ۳-۴). شاخه­ بلند این پل دو برابر شاخه کوتاه­تر آن بود. در حین اجرای این آزمایش چنین کشف شد که بعد از چند دقیقه تقریباً اکثر مورچه ها از شاخه­ کوتاه­تر پل استفاده می­ کنند. شرح و توضیح این رفتار به این واقعیت مربوط می شود، که مورچه­ها فرومون را در طول مسیرشان به جای می گذارند. احتمالاً مورچه­هایی که به طور تصادفی واتفاقی شاخه­ کوتاه­تر پل را انتخاب می­ کنند، زودتر به منبع غذایی می­رسند. وقتی که آن­ها به لانه بر­می­گردند، اثر فرومون بر روی شاخه­ کوتاه­تر را بو­ می­ کنند. بنابراین، عبور از این شاخه را ترجیح می­ دهند. فرومون بر روی شاخه­ کوتاه­تر، سریع­تر از شاخه­ درازتر جمع و انباشته می­ شود و بنابراین، بعد از مدت زمان کمی غلظت و تراکم فرومون بر روی شاخه­ کوتاه­تر بیشتر شده و تقریباً اکثر مورچه­ها شاخه­ کوتاه­تر را انتخاب می­ کنند. . به این ترتیب، با گذشت زمان میزان ماده­ شیمیایی در مسیر درست بیشتر و در مسیر نامناسب به کلی از بین می­رود و تعداد مورچه­هایی که جذب مسیر مستقیم می­شوند، افزایش می­یابد و جستجو در سایر مسیرها متوقف می­گردد.

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