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

دانلود پایان نامه
شکل (4-6)- مثالی از عملگر جهش پیشنهادی
شکل (4-6)- مثالی از عملگر جهش پیشنهادی

4-3- الگوریتم بهینه سازی کلونی مورچگان
الگوریتم بهینه سازی مورچگان (ACO) یک الگوریتم فراابتکاری است که از رفتار مورچگان در طبیعت الهام گرفته شده است. مورچگان و حشرات دیگری که در یک کلونی زندگی میکنند، از قبیل زنبورها و موریانهها، میتوانند به عنوان یک سیستم توزیع دیده شوند و همچنین رفتار آنها ارائه دهندهی یک زندگی با سازمان اجتماعی سطح بالا میباشد. بطور مثال در مورچگان فرآیند پیدا کردن منبع غذایی جدید و در پی آن یافتن کوتاهترین مسیر بین لانه و منبع غذایی کاری کاملاً اجتماعی است بطوریکه هیچ کدام از مورچه ها به تنهایی نمیتوانند به این امر دست پیدا کنند.
این الگوریتم اولین بار توسط دوریگو [82] برای حل مسئله فروشنده دورهگرد معرفی شده است. این الگوریتم بر مبنای توانایی مورچگان برای یافتن کوتاهترین مسیر بین لانه و منبع غذایی میباشد. حال سوالی که در این بخش پیش میآید این است که مورچگان که موجوداتی نابینا هستند، چگونه میتوانند کوتاهترین مسیر را از کلونیشان تا منبع غذایی پیدا کنند. همانطور که قبلاً گفته شده، مورچگان موجوداتی هستند که در کلونیها زندگی میکنند. بعد از مشاهده کامل رفتار مورچگان و به عمل آمدن بررسیهای علمی لازم نتیجه حاصل بر این است که تمامی مورچگان در هنگام راه رفتن از خود ماده ای بنام فرمون ترشح میکنند. میزان ترشح این ماده کاملاً معین است و نیز بعد از مدت زمانی تبخیر میشود. مورچگان قادر به تشخیص وجود فرمون از طریق حس بویایی خود هستند. همین نشان دهندهی این است که مورچگان جمعیتی هوشمند هستند چرا که از طریق حسگرهایشان که قوهی بویایی آنهاست، قادر به درک محیطشان هستند و بین دو مسیری که یکی از آن مسیرها دارای فرمون و دیگری فاقد فرومون است مسیری را انتخاب میکنند که دارای فرمون است. مورچگان در مقام انتخاب دو مسیری که هر دو دارای میزانی فرمون باشند همیشه مسیری را انتخاب میکنند که مقدار غلظت فرمون در آن مسیر بیشتر است. در نظر بگیرید بین آشیانهی مورچگان و یک منبع غذایی دو مسیر وجود داشته باشد، یکی از مسیرها از دیگری کوتاهتر باشد. یکی از مورچهها از مسیر کوتاهتر برود و مورچه دیگر از مسیر بلندتر و این انتخابها کاملاً بصورت تصادفی است. هر دو مورچه هم اثر فرمون خود را در مسیر بر جای میگذارند. مسلماً مورچهای که مسیر کوتاهتر را رفته است زودتر به مقصد یعنی مبنع غذایی میرسد و مقداری غذا برداشته و به سمت آشیانه باز میگردد وقتی به آشیانه رسید، غذا را در آشیانه قرار داده و دوباره به طرف منبع غذایی میرود. اما آن مورچهای که مسیر طولانیتر را رفته است ممکن است هنوز در مسیر رفتن به سمت منبع غذایی باشد، لذا حتما دیرتر از مورچهی مسیر کوتاهتر به آشیانه باز میگردد. پس مسیر کوتاهتر میزان فرمون بیشتری در خود خواهد داشت و مورچگان دیگری که به دنبال مسیری جهت یافتن منبع غذایی هستند مسیر کوتاهتر را انتخاب میکنند چون غلظت فرمون در آن مسیر بیشتر است. به همین ترتیب بعد از گذشت مدت زمانی تقریباً اکثر مورچگان از مسیر کوتاهتر میروند. پس مورچگان براحتی کوتاهترین مسیر بین آشیانه و منبع غذایی را پیدا میکنند. اثر فرمون بعد از مدت زمان معینی تبخیر میشود و این امر باعث پویایی این روند خواهد شد، چون ممکن است مسیرهای کوتاهتر دیگری نیز وجود داشته باشند. قابلیتهای مورچگان فقط به پیدا کردن مسیر کوتاهتر محدود نمیشود، بلکه مورچگان قادرند در مواقعی که مشکلات یا موانعی در مسیر پدیدار میشود نیز کوتاهترین مسیر موجود را پیدا کنند.
الگوریتم ACO، یک الگوریتم تکرار شونده است بطوریکه مسئله بهینهسازی را بصورت یک گراف که دارای گرههای بهم متصل هستند نمایش میدهد و هر پاسخ برای مسئله بصورت یک توالی مرتب شده از گرههای بهم متصل میباشد. در هر تکرار، مورچهها فضای جواب را با حرکت احتمالی از یک گره به گره دیگر جستجو میکنند. این تصمیم ( حرکت از یک گره به گره بعدی ) از طریق قانون انتقال تعیین میگردد، در این قانون مقدار فرمون ذخیره شده بین جفت گرههای بهم متصل شده و همینطور اطلاعات ابتکاری که نشان دهنده حرکت ترجیحی از یک گره به گره بعدی طبق اطلاعات اولیه از مسئله میباشد در نظرگرفته میشود. در هر مرحله بعد از اینکه مورچهها حلهای خود را ساختند، مقدار تابع هدف مربوط به هر حل محاسبه میشود، در مرحله بعدی میبایستی میزان فرومونی که هر مورچه در مسیر حرکت خود ترشح کرده است مشخص گردد که معمولاً این مقدار به مقدار تابع هدف مربوط به حلی که آن مورچه ساخته است بستگی دارد. علاوه بر این، در پایان هر تکرار، میزان فرمون موجود در هر مسیر توسط فاکتوری به نام نرخ تبخیر کاهش می یابد. این امر به منظور جلوگیری از ماندن حل در یک بهینه محلی و تشویق الگوریتم برای یافتن حلهای جدید میباشد.
اولین الگوریتم ACO پیشنهاد شده در ادبیات موضوع، سیستم مورچگان AS نام دارد که در آن میزان فرومونی که بین دو گره و ترشح میشود بصورت زیر میباشد :
جاییکه نرخ تبخیر ، تعداد مورچه ها و مقدار فرومونی است که بین گره های و توسط مورچه ترشح میشود. که این مقدار وابسته به کیفیت حل تولید شده توسط هر مورچه میباشد. و قانون انتقال توسط احتمال اینکه مورچه گره را بعد از گره ملاقات کند، مشخص میگردد. این احتمال از رابطه زیر قابل محاسبه میباشد:
جاییکه تابع ابتکاری است که تعیین کننده میزان تمایل مورچه برای حرکت از گره به میباشد. و به ترتیب تعیین کننده میزان تاثیر اطلاعات ابتکاری و فرومون موجود در مسیر برای انتخاب گره بعدی میباشند.
شش سال بعد دوریگو و گامباردلا [83] نسخهی دیگری از این الگوریتم به نام سیستم کلونی مورچگان (ACS) معرفی کردند که نسبت به نسخهی قبلی عملکرد بهتری داشت. در ACS از رویههای متفاوتی برای بروزرسانی محلی و کلی فرومونها و همینطور در احتمال انتخاب استفاده شده است.
نسخههای متفاوت دیگری از این الگوریتم تا به امروز معرفی شده اند، از قبیل سیستم مورچگان نخبه [84]، سیستم مورچگان بر مبنای رتبه [85] و سیستم مورچگان مینیمم- ماکزیمم [86].
4-3-1- نسخه چند هدفه الگوریتم بهینه سازی مورچگان (MOACO)
با توجه به موفقیتی که الگوریتم مورچگان در حل مسائل تک هدفه بدست آورده است، محققان زیادی به استفاده از این الگوریتم برای حل مسائل چند هدفه علاقمند شدهاند و الگوریتمهای متنوعی را با اصلاح رویه الگوریتمهای AS و ACS طراحی نمودند. بدلیل سرعت بالایی که الگوریتم ACO در ساختن پاسخهای شدنی دارد، از این الگوریتم بعنوان یک ابزار جایگزین روشهای دقیق برای حل مسائل چندهدفه استفاده شده است. به نظر میرسد که الگوریتم بهینه سازی مورچگان برای حل مسائل بهینه سازی چندهدفه بدلیل سرعت بالای آن در تولید حلها که منجر به پیدا کردن حلهای نامغلوب بیشتری میشود، مناسب میباشد. ایردی و همکارانش [87] یک الگوریتم ACO چند هدفه برمبنای AS برای مسئله مسیریابی خودرو دو معیاره توسعه دادند. آن ها برای هر تابع هدف یک نوع اثر فرومون و یک نوع اطلاعات ابتکاری را در نظر گرفتند. آنها به منظور هدایت مورچهها برای جستجو در فضاهای مختلف جواب، پارامتری که با شماره مورچهها تغییر میکند را تعریف کردند. این پارامتر بعنوان یک فاکتور وزنی در قانون انتقال هم برای فرومونها و هم برای اطلاعات ابتکاری استفاده میشود. دورنر و همکارانش [88] یک الگوریتم ACO چند هدفه برمبنای ACS برای مسئله انتخاب پورتفولیو چندهدفه توسعه دادند. آنها به اندازه تعداد اهداف ماتریس فرومون درنظر گرفتند و همینطور یک اطلاعات ابتکاری ترکیبی برای این مسئله در این مدل درنظر گرفتند. آنها از دو روش ماکزیمم انتخاب و روش احتمالی برای انتخاب گره بعدی استفاده کردند. در پایان هر تکرار علاوه بر اینکه هر مورچه برروزرسانی محلی فرومون را انجام میدهد، بهترین مورچه و دومین بهترین مورچه بروزرسانی کلی فرومون را نیز انجام میدهند. الگوریتم سیستم کلونی مورچگان چندتایی توسط باران و چیرر [89] برای مسئله مسیر یابی خودرو دو هدفه با پنجره زمانی پیشنهاد شده است. در این الگوریتم از یک ماتریس فرومون و دو نوع اطلاعات ابتکاری، یکی برای هر تابع هدف، استفاده شده است. و همینطور برای قانون انتقال در این الگوریتم از دو روش ماکزیمم انتخاب و روش احتمالی استفاده شده است. آن ها به منظور هدایت مورچه ها برای جستجو در فضاهای مختلف جواب، پارامتری که با شماره مورچهها تغییر میکند را تعریف کردند. این پارامتر بعنوان یک فاکتور وزنی در قانون انتقال برای ماتریسهای اطلاعات ابتکاری استفاده می شود. دورنر و همکارانش [90] الگوریتم COMPETants را برای مسئله دو هدفه حمل و نقل پیشنهاد دادند. این مدل بر مبنای الگوریتم سیستم مورچگان بر مبنای رتبه عمل میکند. در این مدل از دو کلونی مورچه، دو ماتریس فرومون و دو ماتریس اطلاعات ابتکاری، یکی برای هر هدف، استفاده شده است. نکته قابلتوجه در این الگوریتم این است که تعداد مورچهها در هر کلونی ثابت نمیباشد و تعداد مورچه ها در هر کلونی وابسته به کیفیت پاسخهایی است که هر کلونی در تکرار قبلی بدست آوردهاند. در این الگوریتم در هر کلونی تعدای از بهترین مورچهها که آنها را مورچگان جاسوس نامیدهاند که اطلاعات ابتکاری و ماتریسهای فرومون مربوط به کلونیها را در بخش قانون انتقال با هم ترکیب میکنند. این امر به دلیل جستجو در قسمتهای مرکزی لبهی پارتو می باشد. گارسیا مارتینز و همکارانش [91] در سال 2007 میلادی به طبقهبندی و مروری کامل بر روی الگوریتمهای مورچگان چندهدفه موجود در ادبیات پرداختهاند و عملکرد آنها را برای حل مسئله فروشنده دورهگرد در مقابل الگوریتم ژنتیک چند هدفه بررسی کردند. علاقهمندان برای دستیابی به تمامی الگوریتمهای مورچگان چند هدفه که تا به امروز توسط محققان پیشنهاد شده است میتوانند به کتاب اس آنجلو و جی سی باربوسا [92] مراجعه فرمایید. این کتاب که در سال 2011 میلادی به چاپ رسیده است به بررسی کامل نحوه فرموله سازی این الگوریتم ها پرداخته است. با توجه به مرور ادبیات انجام شده الگوریتم های مورچگان چند هدفه را می توان به سه دسته کلی تقسیم کرد:
الگوریتم هایی با بکارگیری چندین کلونی، یکی برای هر یک از اهداف.
الگوریتم هایی که چندین نوع اثر فرمون، یکی برای هر یک از اهداف بکار می برند.
الگوریتم هایی که چندین نوع اطلاعات ابتکاری، یکی برای هر یک از اهداف بکار می برند.
الگوریتم پیشنهادی ما در این پایاننامه در گروه دوم قرار میگیرد. این الگوریتم که BicriterionAnt نامیده میشود توسط ایردی و همکاران [87] پیشنهاد شده است. در این الگوریتم از یک کلونی مورچهها و چندین اثر فرومون ( به اندازه تعداد اهداف) استفاده می شود. برای مثال، زمانیکه دو تابع هدف داشته باشیم آنگاه دو ماتریس فرومون و خواهیم داشت. در نسخهی اصلی این الگوریتم در هر تکرار فقط مورچههایی که در اولین لبهی نامغلوب قرار دارند میتوانند در بروزرسانی ماتریسهای فرومون شرکت کنند و مقدار فرومونی که میتوانند ترشح کنند به میزان می باشد، جاییکه تعداد مورچههای موجود در اولین لبهی نامغلوب جاری میباشد. اما در این روش ماتریس فرومونها هر دو به یک مقدار و بدون در نظر گرفتن مقادیر تابع هدف بروزرسانی میشوند. به همین دلیل ما در این پایان نامه از روشی برای بروزرسانی فرومون استفاده کرده ایم که مقادیر تابع هدف مورچههایی که در اولین لبهی نامغلوب قرار دارند مورد توجه قرار بگیرند. مراحل اصلی برای یک الگوریتم استاندارد ACO در یک مسئله بهینه سازی چند هدفه بصورت زیر می باشد.
Step 1: Initialize the pheromone trails and parameters:
Step 2: While termination condition is not met do the following:
Construct ant solution and evaluate the solutions
Apply the fast non-dominated sorting procedure and update Pareto optimal front