الگوریتم های فراابتکاری (آموزش و کد متلب)

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

معرفی روش های حل مسائل بهینه سازی

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

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

این دسته از الگوریتم ها در طول زمان شکل گرفته و دستخوش تغییر و تحول شده اند. روند تاریخی تکامل (تبارشناسی) الگوریتم های فراابتکاری در شکل زیر نشان داده شده است.

معرفی الگوریتم ها فراابتکاری

الگوریتم های فراابتکاری برای حل مسائل بهینه سازی، را می توان به طور کلی به دو دستهی الگوریتم های تک جوابی' یا خط سير"، و الگوریتم های جعیت مبنا، طبقه بندی نمود. الگوریتم های تک جوابی یا خط سير، الگوریتم های حریصانه ، شبیه سازی تبریدی، جست و جوی ممنوع ، و الگوریتم هایی از این دست را شامل می شود. الگوریتم های جمعیت مبنا نیز الگوریتم هایی از قبیل الگوریتم ژنتیک، استراتژی های تکاملی ، اجتماع مورچه، جست و جوی پراکنده، ازدحام ذرات و الگوریتم های از این دست را در بر می گیرد. الگوریتم های جمعیت مبنا جمعیتی متشکل از چندین جواب را در ابتدای شروع الگوریتم یا در حین فرایند آن تولید نموده و خروجی آنها مجموعه ای از جواب های بهینه است. به طور کلی، الگوریتم های خط سیر، از قابلیت محاسباتی بالا، و کارآمدی (زمان حل مسئله) لازم برای حل مسائل بهینه سازی برخوردار بوده اما قادر به تولید مرز (حد) بهینه پارتو برای مسائل بهینه سازی چندهدفه نمی باشند. در ادامه به معرفی الگوریتم های جمعیت مینا و روند (خط سیر) به کار گرفته شده در مطالعه ی حاضر، پرداخته می شود.

معرفی الگوریتم شبیه سازی تبریدی (انجماد تدریجی)

الگوریتم شبیه سازی تبریدی، از الگوریتم توسعه داده شده توسط مترو پولیس و همکاران، در حوزهی مکانیک آماری، که برای تعیین حالت اتمها در یک سیستم ترمودینامیکی به کار برده می شود، اقتباس شده است بر مبنای الگوریتم پیشنهادی این محققان، کاربردهای دیگری توسط کریک پاتریک و همکاران در سال ۱۹۸۳ و توسط چرنیه (۱۹۸۵) در حل مسئلهی فروشنده ی دوره گرد مطرح شده است (1985 ,Cerny). مهم ترین ویژگی الگوریتم شبیه سازی تبریدی، توانایی آن در اجتناب از قرار گیری در بهینهای محلی می باشد (جلالی نائینی و همکاران، ۱۳۹۱). این الگوریتم از فرآیند خنک سازی تدریجی که انجماد نامیده می شود پیروی کرده تا انرژی وضعیت زمینهی یک ماده و یا ذره را تخمین بزند به بیان دیگر، انجماد تدریجی به فرآیندی اطلاق می شود که در آن به یک ماده تا دمای ذوب حرارت داده شده و سپس آن را تا رسیدن به خواص مطلوب تدريجا" خنک نمایند. در نهایت پس از دست یابی به شرایط مطلوب، ماده به یکباره سرد شده تا مولکولها در جای خود ثابت بمانند و پایداری ماده حاصل گردد (بشیری و کریمی، ۱۳۹۰). در فرآیند انجماد تدریجی، در هر تکرار، به هر یک از اتمهای مجموعه یک جابه جایی تصادفی بسیار کوچک اعمال و سپس تغییرات حاصله در انرژی آن (AE) محاسبه می شود، اگر این مقدار کم تر از صفر باشد، جابه جایی انجام شده پذیرفته شده و موقعیت جدید به دست آمده برای اتم در تکرار بعدی برای انجام شبیه سازی مورد استفاده قرار می گیرد. در حالتی که مقدار تغییرات انرژی بزرگ تر از صفر باشد، احتمال قبول موقعیت جديد اتم برابر در نظر گرفته می شود که در آن ka ثابت بولتزمن و T دمای محیط بر حسب کلوین است. در حالت اخیر برای رد یا قبول موقعیت جدید اتم می توان عددی تصادفی با توزیع یکنواخت در بازهی ۰ و ۱ تولید نمود. اگر این عدد تصادفی کوچکتر از (P AE باشد، آن گاه موقعیت جدید به دست آمده برای اتم، مورد قبول قرار گرفته و در غیر این صورت رد میشود. با تکرار این مراحل، می توان یک سیستم ترمودینامیکی را شبیه سازی نمود (مریخ بیات، ۱۳۹۰).

بر اساس مراحل ارائه شده در شبیه سازی سیستم های ترمودینامیکی، فتاحی (۱۳۹۰)، اجزا یک مسئله ی بهینه سازی را بر فرآیند انجماد تدریجی منطبق می سازد، به طوریکه، راه حل (جواب)، متغیرهای تصمیم، تابع هدف، راه حل بهینهی سراسری، بهینهی محلی، جست و جوی محلی، پارامتر کنترل و شبیه سازی تبرید در مسئله ی بهینه سازی به ترتیب بر وضعیت سیستم، موقعیت های مولکولی، انرژی، وضعیت پایدار، وضعیت نیمه پایدار، سرد کردن سریع، دما، و انجماد با دقت در انجماد تدریجی منطبق می شود.

معرفی الگوریتم جست و جوی ممنوع

الگوریتم جست و جوی ممنوع الگوریتم جست وجوی محلی فراابتکاری است که برای حل مسائل بهینه سازی ترکیبیاتی توسط فرد گلاور در سال ۱۹۷۰ توسعه یافت (1986 ,Glover). این الگوریتم، الگوریتم جست و جوی متمرکز است که برای افزایش کارایی و جلوگیری از افتادن در تلهی بهینهی محلی از حافظه استفاده می کنند (جلالی نائینی، ۱۳۹۱). الگوریتم جست و جوی ممنوع، با جواب اولیه شروع می شود. اگر پاسخ انتخاب شده، مقدار تابع هدف (کیفیت جواب) را بهبود بخشیده و در فهرست ممنوع قرار نداشته باشند، جواب اولیه با این جواب جایگزین (تعویض می شده و به فهرست ممنوع اضافه می شود. در غیر این صورت، رو بهی الگوریتم ادامه یافته تا جواب تصادفی دیگری تولید شود. این عمل تا زمانی ادامه می یابد که معیار توقف که از پیش تعیین شد است، برآورده گردد

الگوریتم بهینه سازی علف های هرز

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

مهرابیان و لوکاس، در مقدمه معرفی الگوریتم پیشنهادی خود درباره شکل گیری ایده علفهای هرز این گونه توضیح می دهند:

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

معرفی روش های هیبریدسازی الگوریتم های فراابتکاری

هیبریدسازی به مفهوم ترکیب کردن و تلفیق نمودن الگوریتم های فراابتکاری برای افزایش کیفیت و دقت پاسخها، و کاهش زمان حل مسئله می باشد. هدف اصلی تلفیق الگوریتم های فراابتکاری، کشف قابلیت بهبود حل مسائل بهینه سازی از طریق همکاری الگوریتم های منفرد فراابتکاری است.

به طور کلی چهار ایده اصلی برای هیبرید سازی الگوریتم های فراابتکاری را معرفی می کند:

• تلفیق سطح پایین به طور تقویت کننده (LRH)
• تلفيق سطح پایین به طور گروهی (2LTH، 3)
• تلفیق سطح بالا به طور تقویت کننده (HRH)
• تلفیق سطح بالا به طور گروهی

منظور از تلفیق سطح پایین و بالا، به ترتیب، قرار دادن یک الگوریتم فراابتکاری در ساختار درونی یک الگوریتم تک جوابی (یا خط سير) (استفاه از یک الگوریتم فرا ابتکاری به جای یکی از توابع موجود در الگوریتم تک جوابی)؛ و استفاده از الگوریتم های فراابتکاری به صورت خود در بر دارنده بوده که در آنها ارتباطی مستقیم و درونی میان الگوریتم ها برقرار نمی شود، می باشد. معنای تلفیق تقویت کننده و گروهی نیز به ترتیب: به کارگیری متوالی الگوریتم های فراابتکاری بوده که خروجی یک الگوریتم به عنوان ورودی الگوریتم دیگر محسوب شده و عملکرد الگوریتم ها به طور اتصالی خواهد بود؛ و مدل های بهینه سازی همکارانه که در آن تعداد زیادی از الگوریتم های فراابتکاری به صورت موازی با یکدیگر جست و جوی فضای جواب را انجام می دهند، می باشد.

در الگوریتم های LRH یک الگوریتم فراابتکاری در ساختار یک الگوریتم تک جوابی مستقر می شود. این دسته از الگوریتم ها مورد استقبال محققان قرار نگرفته و تعداد کمی از الگوریتم های تلفیقی در این دسته قرار داده می شوند.

در الگوریتم های LTH، دو هدف مورد نظر طراحان است. اولین هدف افزایش قدرت جست و جوی الگوریتم و دومین هدف افزایش قدرت استخراج الگوریتم می باشد. برای حصول اطمینان از جست و جری بخش هایی از فضای پاسخ، ارتقا قدرت جست و جوی الگوریتم، و به منظور پالایش جواب ها برای دست یابی به جواب بهتر، ارتقا قدرت استخراج الگوریتم مورد نیاز است.

الگوریتم های جمعیت - مینا الگوریتم های قدرتمندی در جست و جوی فضای جواب بوده، اما در استخراج جواب ضعیف هستند. از طرف دیگر، الگوریتم های تک جوابی (خط سیر) در استخراج پاسخ به خوبی عمل کرده و در جست و جوی فضای جواب دچار نقصانند. به همین علت، اساس الگوریتم های LTH بر تلفيق الگوریتم های جمعیت مبنا و تک جوابی استوار است به طوری که ضعف های یکی توسط قوت های دیگری بر طرف گردد . این دسته از الگوریتم های هیبرید فراابتکاری دارای بهترین عملکرد در میان سایر الگوریتم های هیبرید هستند. به عنوان نمونه ای از الگوریتم های LTH، می توان به تحقیق انجام شده توسط بليره (۱۹۹۱)، جایگزینی عملگرهای الگوریتم ژنتیک با الگوریتم حریصانه و جست و جوی ممنوعه اشاره نمود. این شکل از تلفیق در ارتقا الگوریتم های جست و جوی پراکنده و اجتماع مورچگان مورد استفاد قرار گرفته است.

در الگوریتم های HRH الگوریتم های فراابتکاری به طور متوالی اجرا می شوند. الگوریتمهای تکاملی، برای مسائلی که دارای ساختار ظریف دو گانه بوده و به پاسخ های بهینه نزدیک هستند متناسب نخواهند بود. در عوض، نقطهی قرت الگوریتم های تکاملی در مکان یابی سریع فضاهای جست و جوی پیچیده و گسترده می باشد. هنگامی که الگوریتم تکاملی، در مناطق جست و جو قرار دارند، به کارگیری الگوریتم های جست و جوی محلی برای افزایش عملکرد ساختارهای تکامل یافته توسط الگوریتمهای تکاملی سودمند است. یکی از اشارات بنیادی در حل مسائل ظریف دو گانه (جداسازی گراف')، آن است که پس از گذشت زمان مشخصی از اجرای الگوریتم، جمعیت مورد بررسی، یکنواخت شده و مقدار تابع هدف برای این جمعیت کاهش یا افزایش محسوسی پیدا نمی کند. این امر نشان دهنده آن است که فرایند بهینه سازی در یک حوزهی جذب قرار گرفته، و احتمال خروج از آن بسیار ضعیف است. برای ارتقا استخراج پاسخ در این مسائل و خروج آن از حوزهی جذب، به تلفيق الگوریتم های جمعیت مبنا و خط سیر پرداخته می شود. به عنوان مثال، الگوریتم حریصانه برای تولید جواب اولیه مناسب برای الگوریتم ژنتیک استفاده شده و برای افزایش کیفیت استخراج جواب از الگوریتم جست و جری ممنوعه استفاده می شود. به طوری که خروجی الگوریتم حریصانه، به عنوان وردوی الگوریتم ژنتیک، و خروجی الگوریتم ژنتیک به عنوان ورودی الگوریتم جست و جوی ممنوعه استفاده می شود به عنوان نمونه ای از الگوریتم های HRH، می توان به تحقیق انجام شده توسط تلبی و همکاران (۱۹۹۴)، اشاره نمود که در آن الگوریتم جست و جوی ممنوعه برای ارتقا کیفیت استخراج پاسخهای تولید شده توسط الگوریتم ژنتیک به کار گرفته شده است.

جهت دانلود آموزش کامل الگوریتم های فراابتکاری به همراه کد متلب لینک زیر را کلیک کنید