الگوریتم مورچگان و پایان نامه

دانلود پایان نامه
Update the pheromone trail
Step 3: Return the best solution found.
پیکربندی الگوریتم پیشنهادی MOACO شامل مراحل زیر می باشد :
4-3-1-1- ساختن گراف مسئله
اولین قدم برای اجرای الگوریتم مورچگان تبدیل مسئله بهینه سازی به شکل یک گراف میباشد. در این پایان نامه از رویهی ساخت گراف برای زمانبندی ماشینهای موازی که در مقالهی آقای کنکین ترک و همکاران [61] بحث شده، استفاده شده است. گراف مورد استفاده در این تحقیق بصورت زیر تولید میگردد: کارها به شکل یک گره بزرگ ( بصورت یک خوشه از گره ها ) نمایش داده میشوند. هر گرهی بزرگ شامل گرههای کوچکی میباشند که نمایش دهنده ماشینهایی می باشد که کار موردنظر میتوانند روی آن ماشینها پردازش شوند. گرههای کوچک موجود در یک گرهی بزرگ به یکدیگر متصل نمیباشند ولی هر گرهی کوچک موجود در گرهی بزرگ به سایر گرههای کوچک موجود در گره های بزرگ دیگر متصل می باشند. به منظور تکمیل کار یک گرهی مجازی که بعنوان لانهی موچهها ( بعنوان نقطهی شروع و پایان یک تور مورچه ) میتواند باشد در نظر گرفته میشود. این گرهی مجازی به سایر گرههای کوچک دیگر متصل میباشد.
4-3-1-2- نحوهی ساختن پاسخ برای مسئله
برای ساختن یک پاسخ، مورچهها به هر گرهی بزرگ سفر میکنند و در هر گرهی بزرگ یکی از گرههای کوچک را ملاقات میکنند و در نهایت به گرهی مجازی برمیگردند. زمانیکه یک مورچه سفر خود را کامل میکند، ترتیب ملاقات هر گرهی بزرگ بیان کننده ترتیب پردازش کارها روی ماشینها میباشد. بعلاوه گرهی کوچکی که در هر گرهی بزرگ ملاقات میشود تعیین کنندهی ماشینی است که کار مورد نظر روی آن پردازش میشود. اگرچه بخاطر محدودیتهای پیشنیازی برخی از این پاسخها (سفرها) نشدنی هستند. از اینرو برای ایجاد سفرهای شدنی برای هر مورچه ما نیاز به یک ترتیب شدنی از ملاقات گرههای بزرگ را داریم. برای این منظور ابتدا برای هر مورچه بصورت تصادفی جایگشتی از اعداد یک تا تولید کنید و آنرا بنامید. سپس برای دستیابی به یک ترتیب شدنی از پردازش کارها با استفاده از الگوریتم اصلاحی مجموعه را اصلاح کنید و مجموعهی اصلاح شده را مجموعه بنامید.
شکل 7 مثالی از یک سفر شدنی را نمایش میدهد. برای این مثال، مثالی که در بخش تقاطع الگوریتم NSGA- مطرح شده است را در نظر بگیرید. فرض کنید که در نتیجه . بر مبنای توالی شدنی بدست آمده (مجموعه C)، مورچه می بایستی ابتدا به گرهی بزرگ 1 (کار شماره 1) و سپس به گرههای بزرگ 5،6،4،3،2 سفر کند. با توجه به شکل شماره 7 نتایج بدست آمده بدین صورت میباشد که روی ماشین 1 ابتدا کار 3و سپس کار 5 پردازش میشود. روی ماشین 2 ابتدا کار 1و سپس کار 6 پردازش میشود و نهایتاً روی ماشین 3 ابتدا کار 2و سپس کار 4 پردازش می شود.
شکل (4-7)- نمونه ای از یک سفر برای یک مورچه
شکل (4-7)- نمونه ای از یک سفر برای یک مورچه

این مطلب مشابه را هم بخوانید :   آنالیز واریانس و مورفومتری

در الگوریتم MOACO پیشنهادی ما فرض کردیم که مورچههای مصنوعی فرومونها را بجای اینکه روی مسیرها ترشح کنند، روی گرههای کوچک که در مسیر خود از آنها عبور میکنند ترشح میکنند. در هر مرحله از ساخت یک راهحل توسط مورچه ، طبق توالی شدنی بدست آمده کار را به ماشین به روشهای زیرتخصیص میدهد.
جاییکه یک عدد تصادفی بین و یک پارامتر است که در ابتدا توسط کاربر داده می شود. ماشینی است که از رابطه بالا بدست میآید و ماشینی است که طبق احتمال زیر بدست میآید.
جاییکه و میزان فرومونی است که در تکرار t بر روی گره بر مبنای هدف اول و هدف دوم برجای مانده است. پارامتری است که تعیین کننده اثر نسبی قدرت فرومون است و چون در این بخش از اطلاعات ابتکاری استفاده نشده است مقدار آن را یک در نظر میگیریم و مجموعهی ماشینهای است که میتوانند کار را پردازش کنند. ایجاد کننده اهمیت نسبی مختلف برای توابع هدف به منظور هدایت مورچهها برای جستجو در همهی مناطق موجود در لبهی پارتو میباشد. در نسخهی اصلی این الگوریتم مقدار از صفر تا یک بصورت خطی افزایش می یافت ولی در این تحقیق ما فرض کرده ایم که مقدار بصورت خطی از مقدار 0.3 به 0.7 افزایش می یابد که از رابطه زیر بدست می آید. اشکال عمدهای در نسخهی اول وجود دارد این است که در بعضی از مورچهها ضریب اثر یک هدف از هدف دیگر به مقدار بسیار زیادی بیشتر میباشد که این امر یک امری غیر منطقی به نظر میرسد و با توجه به آزمایشهایی که انجام دادهایم به نظر میرسد که برای مسئله مورد بررسی در این تحقیق بازهی [0.7 0.3] به پاسخ هایی مطلوبی دست مییابد.

در عبارت بالا جمعیت مورچهها و شماره مورچهها میباشد.
4-3-1-3- بروزرسانی فرومون ها
فرآیند بروزرسانی فرومون موجود در تمام گرههای توسط عبارات زیر صورت میگیرد :
جاییکه بیان کننده نرخ تبخیر و جمعیتی از مورچهها که در اولین لبهی نامغلوب قرار دارند و و مقدار فرومونی است که توسط مورچه kروی گره ترشح میشود که به صورت زیر میباشند :

در عبارات بالا یک عدد ثابت که معمولاً یک در نظر گرفته میشود و حل مربوط به مورچه میباشد. و به ترتیب مقادیر تابع هدف اول و تابع هدف دوم برای حل میباشند.
4-4- تنظیم پارامترهای کنترل کننده و کالیبراسیون الگوریتم ها