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

برخی الگوریتم­های تکاملی عبارتند از: الگوریتم ژنتیک[۱۶]، استراتژی تکاملی[۱۷]، برنامه نویسی تکاملی[۱۸]، تکامل تفاضلی[۱۹و۲۰]، بهینه­سازی کاوش باکتری[۲۱]، ایمنی مصنوعی[۲۲] و …. از میان همه این­ها، الگوریتم ژنتیک بصورت گسترده در برنامه ­های کاربردی استفاده شده­است. الگوریتم ژنتیک براساس تئوری بقا داروین و تئوری تکامل تدریجی موجودات زنده عمل می­ کند. استراتژی تکاملی بر این فرض بنا شده است که قوانین وراثتی در طول دوره تکامل بیولوژیکی با سرعت بیشتری تطابق پیدا می­ کنند و از تاثیر روالهای ژنتیک روی شکل ظاهری و الگوهای توارث پیروی می­ کند. برنامه­نویسی تکاملی، پدیده ­های تکاملی طبیعی در سطح الگوها^[۴۵] را شبیه­سازی می­ کند. الگوریتم بهینه­سازی جستجوی غذای باکتری بوسیله رفتار اجتماعی یک دسته باکتری معده شبیه­سازی شده­است. الگوریتم ایمنی مصنوعی براساس سیستم ایمنی انسان عمل می­ کند.
برخی الگوریتم­های مبتنی بر هوش جمعی عبارتند از : الگوریتم بهینه­سازی ازدحام ذرات[۲۳]، الگوریتم ترکیبی جهش قورباغه[۲۴]، الگوریتم بهینه­سازی کلونی مورچگان[۲۵]، الگوریتم کلونی زنبور عسل مصنوعی[۲۶و۲۷و۲۸و۲۹]. در کنار الگوریتم­های مبتنی بر هوش جمعی و الگوریتم­های تکاملی، الگوریتم­های دیگری نیز هستند که براساس پدیده ­های طبیعی متفاوتی عمل می­ کنند. برخی از این الگوریتم­ها عبارتند از:

• • جستجوی هارمونی که براساس بهبود هماهنگی در پخش موسیقی عمل می­ کند[۳۰].

• • الگوریتم جستجوی گرانشی که براساس نیروی کشش بین اجسام عمل می­ کند[۳۱].

• • الگوریتم بهینه­سازی مبتنی بر جغرافیا، که بر اساس مهاجرت از یک مکان به مکان دیگر و بر اساس تئوری زیست جغرافیا عمل می­ کند[۳۲].

• • الگوریتم انفجار نارنجک[۳۳].

تمام الگوریتم­های تکاملی و هوش جمعی، الگوریتم­های احتمالی هستند و نیازمند پارامترهای کنترلی عمومی نظیر اندازه جمعیت^[۴۶]، تعداد نسل­ها^[۴۷]، تعداد نخبه­ها^[۴۸] و… هستند. علاوه بر پارامترهای کنترلی عمومی، این الگوریتم­ها نیاز به پارامترهای اختصاصی خود نیز دارند. مثلا الگوریتم ژنتیک از نرخ جهش^[۴۹] و نرخ پوشش^[۵۰] استفاده می­ کند. میزان مناسب بودن پارامترهای اختصاصی هر الگوریتم فاکتوری اساسی است و بر کارایی الگوریتم مربوطه تاثیر دارد. اگر پارامترهای اختصاصی الگوریتم مناسب نباشد، محاسبات الگوریتم افزایش می­یابد یا باعث ایجاد پاسخ­های بهینه محلی می­گردد. در این پایان نامه الگوریتم فراابتکاری مبتنی بر آموزش – یادگیری (TLBO ) برای حل این مسئله استفاده شده است. در ادامه این الگوریتم را تشریح می­کنیم.
۳-۳ الگوریتم مبتنی بر آموزش- یادگیری
TLBO یکی از الگوریتم­های مبتنی بر جمعیت است که اخیرا معرفی شده­است و فرایند آموزش و یادگیری در کلاس درس را شبیه­سازی می­ کند. TLBO بوسیلهRao و همکارانش در سال ۲۰۱۱ و ۲۰۱۲ پیشنهاد گردید و توسعه داده­شد[۳۴و۳۵و۳۶و۳۷و۳۸]. از ویژگی­های این الگوریتم این است که نیازی به پارامترهای کنترلی خاص الگوریتم ندارد و پارامترهای کنترلی عمومی مانند اندازه جمعیت و تعداد نسل­ها را شامل می­گردد. TLBO را می توان الگوریتم بدون پارامتر اختصاصی نیز نامید. الگوریتم مورد استفاده با بکارگیری عملگرهایی که برای مسئله زمانبندی پروژه تحت محدودیت منابع طراحی شده ­اند، در چارچوب کلی الگوریتم خود، به حل مسئله می ­پردازد. برای بررسی بهتر کارایی الگوریتم TLBO مفهوم نخبه­گرایی نیز در آن تاثیر داده شده است[۳۹]. نخبه­گرایی مکانیسمی برای باقی نگه­داشتن بهترین افراد از نسلی به نسل دیگر است. با این روش، هرگز بهترین افراد پیدا شده در طول فرایند بهینه­سازی از دست نخواهند رفت. نخبه­سالاری را می­توان با قرار دادن یک یا بیشتر افراد نخبه در جمعیت نسل بعد، به انجام رساند.
این الگوریتم بر اساس تاثیر معلم (آموزش دهنده) بر فراگیران (یاد گیرندگان) بنا شده است. الگوریتم دو سبک پایه­ای یادگیری را توضیح می­دهد. سبک اول از طریق معلم انجام می­گیرد که بعنوان فاز معلم شناخته می­ شود و تعامل فراگیران با یکدیگر نیز سبک دوم یادگیری است که بعنوان فاز فراگیرنده شناخته می­ شود. در این الگوریتم بهینه­سازی، گروهی از فراگیران بعنوان جمعیت مطرح شده ­اند. موضوعات مختلفی که به فراگیران عرضه می­ شود، بعنوان متغیرهای مختلف طراحی مسئله بهینه­سازی در نظرگرفته می­ شود. نتیجه یادگیری فراگیران مشابه مقدار تابع برازندگی^[۵۱] مسئله بهینه­سازی است. متغیرهای طراحی، پارامترهای درگیر در تابع هدف یک مسئله بهینه­سازی معین هستند و بهترین مقدار برای تابع هدف، بهترین راه حل می­باشد. در شکل ۳-۱ فلوچارت TLBO نمایش داده شده است[۳۷]. همانگونه که اشاره شد عملکرد TLBO به دو قسمت تقسیم شده است: فاز آموزش دهنده^[۵۲] و فاز فراگیر^[۵۳]. در ادامه به توصیف این دو فاز می­پردازیم.
۳-۳-۱ فاز معلم
در طول این فاز یک معلم سعی می­ کند که میانگین نتیجه کلاس را در موضوعی که بوسیله او آموزش داده می­ شود، طبق تواناییش افزایش دهد و آن را از مقدار M₁ به سطح خودش یعنی T_A برساند. ولی در عمل این تغییر ممکن نیست و معلم می تواند میانگین کلاس را از M₁ بهM₂ برساند که از M₁ بهتر است ولی از سطح معلم کمتر است. حداکثر تعداد مجاز تکرار را با MAXIT مشخص می کنیم. در هربار تکرار مانند i، فرض می­ شود که m موضوع تدریس و n نفر فراگیر وجود دارند. m تعداد متغیرهای طراحی و n اندازه جمعیت است. M_j,i میانگین نتیجه فراگیران در تکرار i و در یک موضوع بخصوص مانند موضوع j است. (j=1,2,…,m) بهترین نتیجه کلی X_{total-kbest,i} که با توجه به همه موضوعات و بوسیله کل فراگیران بدست می ­آید را می توان بعنوان نتیجه بهترین فراگیر kbest یعنی معلم در نظر گرفت. فراگیران را با k=1,2,…n مشخص می­کنیم. معمولا معلم بعنوان یک شخص در سطح بالایی آموخته است معرفی می­ شود که فراگیران را آموزش می­دهد، بطوریکه نتیجه بهتری را کسب کنند. بهترین فراگیران شناسایی شده بوسیله الگوریتم، بعنوان معلم در نظر گرفته می­شوند. تفاوت بین میانگین نتیجه یادگیری هر موضوع در حال حاضر با نتیجه متناظر معلم برای هر موضوع از رابطه (۳-۱) بدست می آید:
Difference_Mean_j,k,i = r_i ( X_j,kbest,i -T_F M _j,i ) (۳-۱)
X_j,kbest,i نتیجه بهترین فراگیر یعنی معلم، در موضوع j در تکرار i ام است. r_i عددی تصادفی در محدوده [۰,۱] است. T_F فاکتور آموزش است که تصمیم ­گیری در مورد تغییر مقدار میانگین را انجام می­دهد. مقدار T_F بصورت تصادفی با احتمال برابر بصورت زیر بدست می ­آید:
T_F = round[ 1 + rand( 0,1) {2 -1} (3-2)
مقدار T_F بین یک یا دو است. اگر یک باشد یعنی در سطح دانش، افزایشی رخ نداده­است و اگر دو باشد یعنی دانش بطور کامل منتقل شده است. مقادیر بین یک و دو، میزان سطح انتقال دانش را نشان می­ دهند. T_F پارامتر الگوریتم TLBO نیست. مقدار T_F بعنوان ورودی الگوریتم داده نمی­ شود بلکه بصورت تصادفی بوسیله الگوریتم بدست می ­آید. پس از انجام آزمایش­های زیادی روی توابع و مسایل مختلف، این نتیجه بدست آمده­است که الگوریتم زمانی بهتر عمل می­ کند که مقدار T_F بین ۱ و ۲ باشد[۳۶]. برای ساده­سازی الگوریتم مقدار T_F یک یا دو در نظر گرفته می­ شود. یک یا دو بودن نیز بستگی به گرد کردن معیار داده شده در فرمول T_F دارد. براساس Difference_Mean _j,k,i، پاسخ موجود در فاز معلم، بصورت زیر به روز رسانی می­ شود:
X‘_j,k,i = X_{j,k,I +} Difference_Mean_j,k,i (۳-۳)
X‘_j,k,i به روز شده مقدار X_j,k,i است. X‘_j,k,i در صورتی پذیرش می­گردد که مقدار تابع هدف بهتری را نتیجه بدهد. تمام مقادیر قابل قبول تابع در پایان فاز معلم نگهداری می­ شود و این مقادیر، ورودی فاز فراگیر قرار داده می­شوند. فاز فراگیر وابسته به فاز معلم است.
۳-۳-۲ فاز فراگیر
فراگیران دانش خودشان را از طریق تعامل بین خودشان افزایش می­ دهند. یک فراگیر بصورت تصادفی با دیگر فراگیری تعامل می­ کند تا دانشش را افزایش دهد. یک فراگیر مطالب جدید را در صورتی خواهد آموخت که دیگر فراگیران دانش بیشتری از او داشته باشند. فرایند یادگیری در این مرحله نیز شبیه مرحله قبل است ولی روابطش متفاوت است. با توجه با اندازه جمعیت n، فرایند یادگیری در این فاز در ادامه آمده­است. اگر فراگیر فعلی P باشد، بصورت تصادفی فراگیر Q را انتخاب می­کنیم بطوریکه
X‘_totoal-P,i ≠ X‘_total-Q,i (۳-۴)
X“_j,P,i را بصورت زیر بدست می­آوریم:
If X‘_totoal-P,i < X‘_total-Q,i X“_{j,P,i =} X’_{j,P,i +} r_i ( X’_j,P,i - X’_j,Q,i ) (۳-۵)
If X ‘ _totoal-P,i > X ‘ _total-Q,i X “ _{j,P,i =} X’ _{j,P,i +} r_i ( X’ _j,Q,i - X’ _j,P,i) (۳-۶)
در صورتیکه مقدار تابع هدف برای X“_j,P,i بهتر باشد، X” پذیرش می­ شود و جایگزین مقدار قبلی می­ شود.
۳-۳-۳ الگوریتم TLBO نخبه سالارانه^[۵۴]
الگوریتم TLBO اولیه که بوسیله Rao و دیگران در سالهای ۲۰۱۱و ۲۰۱۲ بیان گردید رویکرد نخبه­گرایی در آن مطرح نبود و فقط دو پارامتر کنترلی عمومی اندازه جمعیت و تعداد نسل ها را شامل می­شد. همچنین تاثیر این پارامترها برکارایی الگوریتم بصورت جزیی بررسی گردیده­است. با وارد کردن مفهوم نخبه گرایی در الگوریتم TLBO تاثیر پارامترها در اکتشاف و ظرفیت اکتشاف را می­توان شناسایی کرد. فلوچارت TLBO با رویکرد نخبه­گرایانه در شکل ۳-۲ نمایش داده شده­است[۳۹]. محققان مفهوم نخبه­سالاری را در غالب الگوریتم­های تکاملی و هوش جمعی استفاده کرده ­اند. در هر نسل پاسخ­های بدتر با پاسخ­های نخبه جایگزین می­گردند. در TLBO پس از جایگزینی پاسخ­های بهتر بجای پاسخ­های بدتر در پایان فاز فراگیر، اگر پاسخ­های تکراری وجود داشت لازم است تا این پاسخ­های تکراری تغییر کنند تا الگوریتم در دام پاسخ­های بهینه محلی نیفتد. یک روش برای رفع پاسخ­های تکراری به این صورت است که پاسخ­های تکراری بوسیله جهش روی اندازه­ های (ابعاد) انتخابی تصادفی پاسخ­های تکراری، تغییر داده می­شوند. این کار قبل از اجرای نسل بعد انجام می­گیرد. در رویکرد نخبه­گرایی، پارامتر کنترلی اندازه نخبه نیز به پارامترها افزوده می­ شود.