k – Xi,k ≤ 1 i,j,k = 1,2,…,n and i≠ j≠k (2-33) ∑_(i,j є S and i ≠j )▒〖”X” _”i,j ” ≥1〗 (2-34) fi ≤ fj – Xj,i . ( dj + M) + M i, j = 1,2,…,n and i≠ j (2-35)
f1 = 0 (2-36)
“X” _”i,j ” є { 0 , 1} i, j = 1,2,…,n and i≠ j (2-37)
رابطه (2-31) شرط پیشنیازی را بیان میکند. رابطه (2-32) نشان میدهد که در شبکه فعالیتها دوری وجود ندارد. رابطه (2-33) خاصیت تراگذاری را در رابطه پیشنیازی نشان میدهد. یعنی اگر i پیشنیاز j باشد و j پیشنیاز k باشد انگاه i پیشنیاز k است. رابطه (2-34) محدودیت منابع را تضمین میکند. زمان اتمام هر فعالیت طبق روابط (2-35) و (2-36) محاسبه میشود. رابطه (2-37) مشخص میکند که متغیر تصمیمگیری دودویی است.
فصل سوم
الگوریتم بهینهسازی مبتنی بر آموزش یادگیری
3-1 مقدمه
یک الگوریتم، توصیفی از گام‌هایی است که به‌گونه‌ای مناسب‌تر در یک برنامه کامپیوتری پیادهسازی میشود تا تقریبی از یک نقطه بهینه یافت شود. طراحی یک الگوریتم می‌تواند چند هدف داشته باشد؛ از جمله دستیابی به نقطه بهینه محلی، دستیابی به نقطه بهینه سراسری، یافتن همه نقاط بهینه سراسری، یافتن همه نقاط بهینه سراسری و محلی [12].
الگوریتمهای ابتکاری مبتنی بر جمعیت طبیعی گونهای از الگوریتمها و یک زمینه تحقیقی هستند که پدیدههای مختلف طبیعی را شبیهسازی میکنند تا یک محدوده بزرگ و گسترده از مسایل را حل کنند. محققان الگوریتمهای متعددی که مبتنی بر پدیدههای طبیعی مختلفی هستند، پیشنهاد دادهاند. TLBO یکی از الگوریتمهای مبتنی بر جمعیت است که اخیرا معرفی شدهاست و فرایند آموزش و یادگیری در کلاس درس را شبیهسازی میکند. از ویژگیهای این الگوریتم این است که نیازی به پارامترهای کنترلی خاص الگوریتم ندارد و پارامترهای کنترلی عمومی مانند اندازه جمعیت و تعداد نسلها را شامل میگردد. برای بررسی بهتر کارایی الگوریتم TLBO مفهوم نخبهگرایی34 نیز در آن تاثیر داده شدهاست.
3-2 الگوریتمهای فراابتکاری
بهینهسازی ریاضی و محاسباتی در مسایل مهندسی با مقیاس بزرگ، سختیهای زیادی را با همراه دارد. به همین دلیل راهحلهای جایگزین و متناوب را بصورت مشارکتی ایجاد کردهاند. روشهای سنتی مانند برنامهنویسیخطی، برنامه نویسی پویا و … هستند که غالبا در این مسایل با شکست روبرو میشوند یا دارای پاسخهای بهینه محلی هستند. این مسایل دارای متغیرهای خیلی زیادی هستند و توابع هدف غیر خطی دارند. الگوریتمهای تقریب35 رسماً در دهه 1960 به منظور تولید جواب‌های نزدیک به بهینه36 معرفی شدند. این الگوریتمها برای آن دسته از مسائل بهینهسازی به‌کار میروند که با روش‌های محاسباتی، نمیتوان آنها را به صورت اثربخش حل کرد. با ارایه تئوری مسایل با زمان حل غیرچندجمله‌ای کامل37 در اوایل دهه 1970، این حوزه علمی مهم‌تر شد، زیرا نیاز به تولید جواب‌های نزدیک به بهینه برای مسائل با زمان حل غیرچندجملهای سخت38 به شدت احساس میشد. الگوریتمهای آن دهه، جواب نزدیک به بهینه در زمان کوتاه به یک مسئله می‌داد و برای سایر مسائل نیز به سختی جواب زیربهینه39 تولید میکرد[13]. روشهای تقریبی از تکنیکهای موسوم به ابتکاری استفاده میکنند. برخی منابع علمی، تکنیک‌های ابتکاری را به دو خانواده ابتکاریهای خاص40 و فراابتکاری‌ها تقسیم کردهاند[14]. ابتکاریهای خاص برای حل یک مسئله خاص و یا یک مصداق از آن طراحی میشوند، در حالیکه فراابتکاری‌ها الگوریتمهای با منظور عمومی41 هستند که قابل استفاده در تقریباٌ همه مسائل بهینهسازی هستند و معمولا هدف از آنها ترکیب روش‌های ابتکاری در چارچوبهای کلانتر به منظور کاوش کارا و اثربخش فضای جستجو می‌باشد. واژه متا هیوریستیک برای این الگوریتمها را اولین بار گلوور42 درسال 1986 به کاربرد که از ترکیب دو واژه یونانی متا و هیوریستیک ساخته شده است. پیشوند متا به معنای فراتر و هیوریستیک به معنای یافتن و مکاشفه است[15]. این الگوریتمها در دستههای مختلفی دستهبندی میشوند که بستگی به معیار مورد نظر مانند مبتنی بر جمعیت، مبتنی بر تکرار، معین و نامعین دارند. براساس پدیدههای طبیعی شبیهسازی شده بوسیله الگوریتمها، الگوریتمهای ابتکاری مبتنی بر جمعیت دو گروه مهم دارند: الگوریتمهای تکاملی43 و الگوریتمهای هوش جمعی44.
برخی الگوریتمهای تکاملی عبارتند از: الگوریتم ژنتیک[16]، استراتژی تکاملی[17]، برنامه نویسی تکاملی[18]، تکامل تفاضلی[19و20]، بهینهسازی کاوش باکتری[21]، ایمنی مصنوعی[22] و …. از میان همه اینها، الگوریتم ژنتیک بصورت گسترده در برنامههای کاربردی استفاده شدهاست. الگوریتم ژنتیک براساس تئوری بقا داروین و تئوری تکامل تدریجی موجودات زنده عمل میکند. استراتژی تکاملی بر این فرض بنا شده است که قوانین وراثتی در طول دوره تکامل بیولوژیکی با سرعت بیشتری تطابق پیدا میکنند و از تاثیر روالهای ژنتیک روی شکل ظاهری و الگوهای توارث پیروی میکند. برنامهنویسی تکاملی، پدیدههای تکاملی طبیعی در سطح الگوها45 را شبیهسازی میکند. الگوریتم بهینهسازی جستجوی غذای باکتری بوسیله رفتار اجتماعی یک دسته باکتری معده شبیهسازی شدهاست. الگوریتم ایمنی مصنوعی براساس سیستم ایمنی انسان عمل میکند.
برخی الگوریتمهای مبتنی بر هوش جمعی عبارتند از : الگوریتم بهینهسازی ازدحام ذرات[23]، الگوریتم ترکیبی جهش قورباغه[24]، الگوریتم بهینهسازی کلونی مورچگان[25]، الگوریتم کلونی زنبور عسل مصنوعی[26و27و28و29]. در کنار الگوریتمهای مبتنی بر هوش جمعی و الگوریتمهای تکاملی، الگوریتمهای دیگری نیز هستند که براساس پدیدههای طبیعی متفاوتی عمل میکنند. برخی از این الگوریتمها عبارتند از:
جستجوی هارمونی که براساس بهبود هماهنگی در پخش موسیقی عمل میکند[30].
الگوریتم جستجوی گرانشی که براساس نیروی کشش بین اجسام عمل میکند[31].
الگوریتم بهینهسازی مبتنی بر جغرافیا، که بر اساس مهاجرت از یک مکان به مکان دیگر و بر اساس تئوری زیست جغرافیا عمل میکند[32].
الگوریتم انفجار نارنجک[33].
تمام الگوریتمهای تکاملی و هوش جمعی، الگوریتمهای احتمالی هستند و نیازمند پارامترهای کنترلی عمومی نظیر اندازه جمعیت46، تعداد نسلها47، تعداد نخبهها48 و… هستند. علاوه بر پارامترهای کنترلی عمومی، این الگوریتمها نیاز به پارامترهای اختصاصی خود نیز دارند. مثلا الگوریتم ژنتیک از نرخ جهش49 و نرخ پوشش50 استفاده میکند. میزان مناسب بودن پارامترهای اختصاصی هر الگوریتم فاکتوری اساسی است و بر کارایی الگوریتم مربوطه تاثیر دارد. اگر پارامترهای اختصاصی الگوریتم مناسب نباشد، محاسبات الگوریتم افزایش مییابد یا باعث ایجاد پاسخهای بهینه محلی میگردد. در این پایان نامه الگوریتم فراابتکاري مبتنی بر آموزش – یادگیری (TLBO ) براي حل این مسئله استفاده شده است. در ادامه این الگوریتم را تشریح میکنیم.
3-3 الگوریتم مبتنی بر آموزش- یادگیری
TLBO یکی از الگوریتمهای مبتنی بر جمعیت است که اخیرا معرفی شدهاست و فرایند آموزش و یادگیری در کلاس درس را شبیهسازی میکند. TLBO بوسیلهRao و همکارانش در سال 2011 و 2012 پیشنهاد گردید و توسعه دادهشد[34و35و36و37و38]. از ویژگیهای این الگوریتم این است که نیازی به پارامترهای کنترلی خاص الگوریتم ندارد و پارامترهای کنترلی عمومی مانند اندازه جمعیت و تعداد نسلها را شامل میگردد. TLBO را می توان الگوریتم بدون پارامتر اختصاصی نیز نامید. الگوریتم مورد استفاده با بکارگیري عملگرهایی که براي مسئله زمانبندي پروژه تحت محدودیت منابع طراحی شدهاند، در چارچوب کلی الگوریتم خود، به حل مسئله میپردازد. برای بررسی بهتر کارایی الگوریتم TLBO مفهوم نخبهگرایی نیز در آن تاثیر داده شده است[39]. نخبهگرایی مکانیسمی برای باقی نگهداشتن بهترین افراد از نسلی به نسل دیگر است. با این روش، هرگز بهترین افراد پیدا شده در طول فرایند بهینهسازی از دست نخواهند رفت. نخبهسالاری را میتوان با قرار دادن یک یا بیشتر افراد نخبه در جمعیت نسل بعد، به انجام رساند.
این الگوریتم بر اساس تاثیر معلم (آموزش دهنده) بر فراگیران (یاد گیرندگان) بنا شده است. الگوریتم دو سبک پایهای یادگیری را توضیح میدهد. سبک اول از طریق معلم انجام میگیرد که بعنوان فاز معلم شناخته میشود و تعامل فراگیران با یکدیگر نیز سبک دوم یادگیری است که بعنوان فاز فراگیرنده شناخته میشود. در این الگوریتم بهینهسازی، گروهی از فراگیران بعنوان جمعیت مطرح شدهاند. موضوعات مختلفی که به فراگیران عرضه میشود، بعنوان متغیرهای مختلف طراحی مسئله بهینهسازی در نظرگرفته میشود. نتیجه یادگیری فراگیران مشابه مقدار تابع برازندگی51 مسئله بهینهسازی است. متغیرهای طراحی، پارامترهای درگیر در تابع هدف یک مسئله بهینهسازی معین هستند و بهترین مقدار برای تابع هدف، بهترین راه حل میباشد. در شکل 3-1 فلوچارت TLBO نمایش داده شده است[37]. همانگونه که اشاره شد عملکرد TLBO به دو قسمت تقسیم شده است: فاز آموزش دهنده52 و فاز فراگیر53. در ادامه به توصیف این دو فاز میپردازیم.
3-3-1 فاز معلم
در طول این فاز یک معلم سعی میکند که میانگین نتیجه کلاس را در موضوعی که بوسیله او آموزش داده میشود، طبق تواناییش افزایش دهد و آن را از مقدار M1 به سطح خودش یعنی TA برساند. ولی در عمل این تغییر ممکن نیست و معلم می تواند میانگین کلاس را از M1 بهM2 برساند که از M1 بهتر است ولی از سطح معلم کمتر است. حداکثر تعداد مجاز تکرار را با MAXIT مشخص می کنیم. در هربار تکرار مانند i، فرض میشود که m موضوع تدریس و n نفر فراگیر وجود دارند. m تعداد متغیرهای طراحی و n اندازه جمعیت است. Mj,i میانگین نتیجه فراگیران در تکرار i و در یک موضوع بخصوص مانند موضوع j است. (j=1,2,…,m) بهترین نتیجه کلی Xtotal-kbest,i که با توجه به همه موضوعات و بوسیله کل فراگیران بدست میآید را می توان بعنوان نتیجه بهترین فراگیر kbest یعنی معلم در نظر گرفت. فراگیران را با k=1,2,…n مشخص میکنیم. معمولا معلم بعنوان یک شخص در سطح بالایی آموخته است معرفی میشود که فراگیران را آموزش میدهد، بطوریکه نتیجه بهتری را کسب کنند. بهترین فراگیران شناسایی شده بوسیله الگوریتم، بعنوان معلم در نظر گرفته میشوند. تفاوت بین میانگین نتیجه یادگیری هر موضوع در حال حاضر با نتیجه متناظر معلم برای هر موضوع از رابطه (3-1) بدست می آید:
Difference_Meanj,k,i = ri ( Xj,kbest,i -TF M j,i ) (3-1)
Xj,kbest,i نتیجه بهترین فراگیر یعنی معلم، در موضوع j در تکرار i ام است. ri عددی تصادفی در محدوده [0,1] است. TF فاکتور آموزش است که تصمیمگیری در مورد تغییر مقدار میانگین را انجام میدهد. مقدار TF بصورت تصادفی با احتمال برابر بصورت زیر بدست میآید:
TF = round[ 1 + rand( 0,1) {2 -1} (3-2)
مقدار TF بین یک یا دو است. اگر یک باشد یعنی در سطح دانش، افزایشی رخ ندادهاست و اگر دو باشد یعنی دانش بطور کامل منتقل شده است. مقادیر بین یک و دو، میزان سطح انتقال دانش را نشان میدهند. TF پارامتر الگوریتم TLBO نیست. مقدار TF بعنوان ورودی الگوریتم داده نمیشود بلکه بصورت تصادفی

دسته بندی : No category

دیدگاهتان را بنویسید