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

الگوریتم های فراابتکاری یکی از ابزارهایی است که در یکی دو دهه گذشته بسیاری از محققین بر روی آن تمرکز کرده اند. بر اساس بررسی های انجام شده تا کنون بیش از 130 الگوریتم فراابتکاری ارائه شده است که بیشتر آنها از الگویی یکسان پیروی می کنند. شناسایی انواع الگوریتم های فراابتکاری به ما کمک خواهد کرد تا بهترین الگوریتم مورد نظر را برای تحقیق خود انتخاب کنیم. در یک شمای کلی میتوان انواع الگوریتم های متاهیوریستیک را به صورت زیر دسته بندی نمود. در شکل زیر یک دسته بندی از انواع روش های فراابتکاری ارائه شده است.

مطابق این شکل، روش های فراابتکاری به دو دسته تقسیم می شود. دسته اول روش هایی هستند که مبتنی بر جستجوی محلی هستند. در این روش ها، هر هر تکرار تنها 1 جواب تولید می شود و تلاش می شود تا بیشترین بهبود در این جواب ایجاد شود. الگوریتم های شبیه سازی تبرید، جستجوی همسایکی متغیر VNS و جستجوی ممنوع از مهم ترین روش های فراابتکاری این دسته هستد.

نوع دیگر روش های فرااتبکاری شامل الگوریتم هایی می شود که در آن در هر تکرار تعداد زیادی جواب تولید می شود. در هر تکرار این جواب ها اصلاح شده و جواب های جدیدی تولید می شود. در این الگوریتم ها برخلاف دسته اول، تمرکز زیادی بر جستجوی محلی وجود ندارد، تنها سعی می شود تا با ایجاد جواب های متعدد و غیر یکسان با یکدیگر، بهترین جواب ممکن پیدا شود. از مهمترین این روش ها می توان به جستجوی پراکندگی SS، الگوریتم ژنتیک، الگوریتم ایمنی مصنوعی AIS، الگوریتم کلونی مورچگان ACO و …. اشاره کرد.

در انواع الگوریتم های فراابتکاری روش های مختلفی برای نمایش یک جواب وجود دارد. نمایش جواب به معنای ارائه یک سیستم کد گذاری می باشد. در انواع الگوریتم های متاهیوریستیک مختلف بسته به ویژگی های آن الگوریتم بایستی روش مختلفی برای نمایش جواب انتخاب نمود

• انواع روش های کدگذاری

نوع اول نحوه نمایش جواب ها، حالت باینری است. در این نوع سیستم کد گذاری فقط از اعداد 0 و 1 استفاده می شود. این روش زمانی کارامد است که متغیرهای تصمیم در مسئله بهینه سازی فقط از نوع باینری باشند مثل مسائل مربوط به مکان یابی . نوع دوم سیستم های کد گذاری، کد گذاری جایگشتی می باشد. که هر جواب به صورت یک ترتیب از n عدد مختلف می باشد. این نوع کد گذاری زمانی مفید است که تصمیم گیری ما در خصوص ترتیب انجام کاری باشد. مانند مسائل مربوط به زمان بندی تولید و یا و یا مسائل مسیریابی وسایل نقلیه .

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

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

در ادامه به آموزش یکی از ساده ترین الگوریتم های فراابتکاری به نام الگوریتم شبیه سازی تبرید (شبیه سازی انجماد) می پردازیم.

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

الگوریتم متاهیوریستیک شبیه سازی انجام اولین بار توسط کریک پاتریک برای حل مسائل بهینه سازی در ۱۹۸۳ توسعه داده شد.این الگوریتم الهام گرفته از فرایند انجماد تدریجی در فیزیک (رفتار اتم ها در مجاورت گرما) است. به عبارتی دیگر، سرد شدن تدریجی مواد پس از ذوب کردن آن ها یک ایده اصلی برای بهینه سازی مسائل ریاضی در نظر گرفته شده است. در این روش بیان می شود که برای تولید یک ساختار کریستالی، ابتدا باید جسم به اندازه کافی دما داده شود و سپس آن جسم به آرامی سرد می گردد.

لذا الگوریتم SA بر این اساس پایه ریزی شده است که یک الگوریتم مبتنی بر جستجوی محلی است که توانایی خروج از بهینه محلی را دارد. از همهترین ویژگی های این الگوریتم می توان به موارد زیر اشاره نمود

 • پذیرش تصادفی: حرکت های بهتر همواره و حرکت های بدتر به طور تصادفی پذیرفته می شوند

• گوناگون گرا در ابتدای جستجو و تغییر تمرکز از گوناگونی به تشدیدگرا به صورت تدریجی

• گوناگونی گرایی بالا: احتمال بیشتر برای پذیرش جواب های بدتر

• پارامتر کنترل مکانیزم پذیرش: دما

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

در الگوریتم SA،  اصل تعادل ترمودینامیک مورد استفاده قرار می گیرد که بیان می کند، احتمال یک سیستم فیزیکی برای داشتن یک سطح انرژی E با فاکتور بالتزمن که در آن k توزیع بالتزمن در دمای مربوطه می باشد، متناسب است.

•با الهام از این اصل، احتمال پذیرش جواب های بدتر

ΔC  اختلاف بین تابع هدف دو جواب، T دمای کنونی

• احتمال پذیرش: تولید یک عدد تصادفی بین ۰ و۱

• میزان احتمال پذیرش بستگی هم به میزان تفاوت مقادیر تابع هدف دو جواب و هم دما دارد.

در نهایت می توان سودکد الگوریتم متاهیوریستیک شبیه سازی بترید را به صورت زیر ارائه نمود

حل یک مثال واقعی با الگوریتم های متاهیوریستیک

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

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

• هدف: تعیین برنامه تولید شرکت به نحوی که بیشترین سود را داشته باشد.

• پارامترها

• متغیر تصمیم

• مدل ریاضی

کد گذاری

• متغیرها:  X و  Y

• رویه نمایش جواب:

• نمایش این متغیرها با اعداد باینری (فرض کنید این حداکثر مقدار تولید ۵۰ است)

• معادل عدد ۵۰: ۱۱۰۰۱۰

• در نتیجه به جای هر متغیر، ۶ عدد باینری جایگزین می شود.

با در نظر گرفتن چنین طراحی کد گذاری، می توان انواع الگوریتم های فراابتکاری را برای بهینه سازی مدل ریاضی ترکیب تولید استفاده نمود. لذا می توان اصلی ترین گام در پیاده سازی الگوریتم های فراابتکاری را تبدیل متغیرهای تصمیم مدل ریاضی به یک سیستم کد گذاری مناسب دانست.

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

matlabanalysis2012@gmail.com