معرفی روش های اصلاح شده در بهینه سازی کولونی مورچه ها

معرفی روش های اصلاح شده در بهینه سازی کولونی مورچه ها

اسلاید 1: بنام خدا

اسلاید 2: معرفي روشهاي اصلاح شده در بهينه سازي کولوني مورچه ها و پيشنهاد يک local optimization

اسلاید 3: معرفی مسئله TSP روش هاي متفاوت بهينه سازي هوشمند بهينه سازي کولوني مورچه ها سير تحولي و تکاملي اين الگوريتم ACS MACS GMACS Local optimization ها محدودیت هاپیشنهاد یک local optimization مقایسه و نتیجه گیری

اسلاید 4: در مسائل بهينه سازي با تعداد زياد پارامتر، روش هاي قديمي کارايي چنداني ندارند وقت هزينه زياد بررسي تمامي فضاي جواب تقريبا غير ممکن است بنابراین از روش هاي ديگري استفاده شود که به صورت هوشمند گستره فضاي جستجو را کاهش دهند.الگوبرداري از سيستم ها و فرايند هاي طبيعي و بيولوژيک در انجام چنين فرايند هايي موفق تر عمل مي کنند.ازجمله به الگوريتم هاي ژنتيکي، شبکه هاي عصبي و بهينه سازي کولوني مورچه ها (Ant Colony Optimization=ACO) می توان اشاره کرد .

اسلاید 5: مسئله TSPحل اين مسئله، مخصوصا وقتي تعداد شهرها زياد باشد، با روشهاي تحليلي ممکن نيست. TSPدر مختصات دو و سه بعدی و ATSPمسائل Eil51 وKroa100http://www.iwr.unihelderberg.de/iwr/comopt/sof/TSPLIB95/TSPLIB.html

اسلاید 6: مفاهيم مربوط به ACS

اسلاید 7: ACS توسط M. Dorigo و L.M.Gambardella برای اولين بار مطرح شد. مشاهده شده است که مورچه ها معمولا بعد از گذشت مدت زماني، کوتاه ترين مسير را براي دستيابي به غذا مي يابند و به صورت دسته جمعي از اين مسير استفاده مي کنند. مکانيزم حاکم بر رفتار آنها به اين صورت است که هر مورچه به سمت هدف مورد نظر (غذا) حرکت مي کند و در مسير حرکت خود ماده اي به نام فرمون(pheromone) بر جاي مي گذارد. ضمنا فرمون به جاي مانده در مسير با نرخ ثابتي تبخير مي شود و مورچه هاي ديگر را به سمت خود جذب مي کند.

اسلاید 8: به طور همزمان تعداد زيادي مورچه به اين کار پرداخته و مسير هاي مختلف را آزمايش مي کنند. بنابراين مورچه ها به مسيري همگرا خواهند شد که فرمون در آن از غلظت بيشتري برخوردار است.

اسلاید 9: در ابتدا که فرموني وجود ندارد مورچه ها در دو راهي ها هيچ رجحاني براي انتخاب يک مسير خاص ندارند

اسلاید 10: با توجه به احتمالات، به طور متوسط تعداد مورچه هايي که در هر يک از دو جهت به راه خود ادامه مي دهند، مساوي است.

اسلاید 11: اما به دليل تبخير، باگذشت زمان مسيرهاي کوتاه تر، حاوي فرمون بيشتري خواهند بود و بيشتر مورچه ها به سمت مسير هاي کوتاه تر جذب مي شوند.

اسلاید 12: در واقع مورچه هاAgent هاي ساده اي هستند که با ارتباط فرموني خود يک حافظه گسترده (distributed) ايجاد مي کنند و با بهره گيري از فرمون و اين حافظه، جواب مسئله را به صورت شراکتي به دست مي آورند.

اسلاید 13: ما مسئله هاي TSP متقارن در مختصات دو بعدي را مورد بررسي قرار داده ايم. ابتدا تعداد شهرها را مشخص مي کنيم، هرشهر با يک جفت مرتب ( xi , yi ) نشان داده مي شود. d(r,s) فاصله اقليدسي بين دو شهر r و s مي باشد. حال تعداد مشخصي مورچه را به طور تصادفي در شهر هاي موجود قرار مي دهيم و مورچه ها طبق قانون حرکتي که در زير توضيح داده مي شود، شهر بعدي را انتخاب مي کنند. در اين انتخاب دو معيار به طور همزمان مد نظر قرار مي گيرند:1. فاصله تا شهر بعدي2. مقدار فرمون در مسير منتهي به شهر بعدي

اسلاید 14: در ابتداي الگوريتم فرمون موجود در تمامي مسيرها برابر فرض شده ومقداري در بازه [0,1] به آن اختصاص داده مي شود. سپس شهر مقصد يا شهرs با توجه به معيارهاي بالا، از فرمول زير محاسبه مي شود:

اسلاید 15: بنابراين با فرض اينکه در لحظه فعلي مورچه k ام در شهر rقرار دارد و s يکي از شهر هايي است که مورچه k ام از آن عبور نکردهاست، احتمال انتخاب شهر s به عنوان شهر بعدي از رابطه زير محاسبه مي شود:

اسلاید 16: وجود S2 تا حدي به الگوريتم حالت تصادفي تزريق مي کند و بدون وجود S2احتمال همگرايي الگوريتم به مينيمم موضعي بالا خواهد بود چرا که استفاده از S2 فضاي جستجو را گسترش مي دهد و به الگوريتم کمک مي کند که تا حدي از دام مينيمم موضعي برهد. براي بدست آوردن جواب بهينه، مقادير پارامتر ها بايد به نحو مناسبي انتخاب شوند. مقادير مناسب تاحد زيادي وابسته به مسئله خواهند بود اما طبق نتايج شبيه سازي هاي انجام شده مقادير q0 = 0.9 و β = 6 منجر به نتايج مناسبتري شدند.

اسلاید 17: با حرکت مورچه ها مقدار فرمون در مسير هاي پيموده شده، در دو مرحله تغيير مي کند: 1- Global updating 2- Local updating

اسلاید 18: Global updatingهر بارکه همه مورچه ها به شهري که سفر خود را ازآنجا آغاز کرده بودند، بازگشتند (تمامtour ها به پايان رسيدند) طول مسير ها را بدست مي آوريم و مسير هر کدام از مورچه ها را که کوتاه تر از بقيه بود، انتخاب مي کنيم. به منظور انجام global updating ابتدا فرمون تمامي مسير ها را به يک نسبت کم مي کنيم (در بحث حاضر در اين مرحله مقدار فرمون تمامي مسير ها در 0.9 ضرب شده است.) و مقداري فرمون به تمام edge هايي که عضو بهترين مسير هستند اضافه مي کنيم. مقدار فرموني که بايد به edge هاي مسير بهينه افزوده شود،r,s) )pheromoneΔ، با عکس طول کوتاه ترين مسير برابرخواهد بود.

اسلاید 19: پارامتر α تضعيف فرمون (تبخير) در مرحله global updating مي باشد و طول کوتاه ترين مسير طي شده تا اين مرحله از الگوريتم مي باشد.

اسلاید 20: Local updatingبراي اينکه علاوه بر بهترين مورچه به ديگر مورچه ها هم اهميت قايل شويم و بتوانيم از اطلاعات با ارزش مسير آنها استفاده کنيم local updating را طراحي مي کنيم يعني هرگاه يک مورچه از شهري به شهر ديگر مي رود، بايد در مسير پيموده شده مقداري فرمون طبق فرمول زير تزريق شود و در عين حال به طور همزمان بايد عمل تبخير نيز اعمال شود. ρ براي شبيه سازي تبخير مورد استفاده قرار مي گيرد. درصورتي که مورچه اي از edge اي عبور کند، فرمون آن edge افزايش مي يابد.

اسلاید 21: مقدارΔpheromone ، با روشهاي مختلفي مقدار دهي مي شودروش Q-learning مخصوص حالتي است که الگوريتم ميزان تزريقي را خودش ياد مي گيرد .اطلاعات بيشتر در مرجع[2] آمده است. در اين روش مقدار فرمون تزريقي برابر خواهد بود با: ضريب γ در آن مقداري ثابت و در بازه [0,1] است .2روش ديگر آن است که Δpheromone را مساوي (مقدار ثابت) قرار دهيم. .3روش سوم مساوي قرار دادن آن با صفر مي باشد(حذف local updating(.

اسلاید 22: طبق شبيه سازي هاي انجام شده روشهاي اول و دوم هر دو نتايج خيلي بهتري نسبت به روش سوم بدست مي دهند چرا که حذف کردنlocal updating باعث مي شود الگوريتم خيلي سريع به مينيمم موضعي همگرا شود.

اسلاید 23: الگوريتم هاي اصلاح شده

اسلاید 24: MACS ( Multiple Ant Colony System) در اين روش از ايده کولوني هاي موازي استفاده شده است و سعي در جلوگيري از همگرايي به مينيمم هاي موضعي دارد. روش ACO از فيدبک مثبت استفاده مي کند اما در MACS مي توان با تغيير پارامتر ها، فيدبک منفي را هم وارد الگوريتم کرد. در اين روش M کولوني مورچه داريم که در هرکدام m مورچه موجود مي باشد و (h,k) مورچه k ام است که به کولوني h ام تعلق دارد. در زمان t، Mm مورچه بين شهر ها در حال حرکت مي باشند. هر مورچه در بازه زماني[t,t+1] ، از شهر i به شهر j مي رود.

اسلاید 25:

اسلاید 26: نحوه انتخاب شهر j در زير توضيح داده مي شود: اگر را ميزان فرمون edge(i,j) در کولوني h ام در زمان t بگيريم و ضريب تبخير و طول tour طي شده توسط مورچه ي (h,k) باشد، بعد از n بازه ي زماني ميزان فرمون بين شهرهاي و j در کولوني h ام برابر است با :

اسلاید 27: در واقع در اين الگوريتم local updating نقش موثرتري را ايفا مي کند چرا که به دليل تعدد کولوني ها، تعداد ant ها بالا رفته و فضاي جستجو وسيع تر شده است و در واقع احتمال از دست دادن مسير هاي مناسب در اثر به دام افتادن در مينيمم هاي موضعي، بسيار پايين مي آيد.

اسلاید 28: π ميزان تمايل به انتخاب شهر j است(که در اثر ارتباط بين کولوني ها شکل مي گيرد.) α ميزان تاثير کولوني lبر h را نشان مي دهد، يعني اگر مثبت باشد، کولوني l برh روي کولوني تاثير مثبت خواهد داشت (افزايش فرمون) و اگر منفي باشد، فيدبک منفي ايجاد خواهد شد(کاهش فرمون) و اگر صفر باشد، کولوني l بر کولوني h تاثيري نخواهد داشت. Cپارامتر باياس است و هميشه ميزا ن ثابتي از تمايل را در کولوني باياس مي کند. d هم طول edge(i,j) است.

اسلاید 29: پس قانون احتمال براي انتخاب شهر مقصد به صورت زير در مي آيد:

اسلاید 30: GMACS (Genetically Modified ACS):بررسي ها در جهت کشف روابط ميان پارامترها با هم و تاثير آنها بر سرعت همگرايي، منجر به استفاده از GMACS شد. استفاده از الگوريتم ژنتيکي باعث مي شود که مقدار پارامتر ها بهبود يابد و مسير هاي کوتاه تر توسط مورچه ها ايجاد شود.

اسلاید 31: ارزش هر مورچه برابر است با تفاضل طول مسيري که آن مورچه در تکرار قبلي طي کرده و بهترين طول بدست آمده توسط مورچه هاي ديگر. fitness function براي هر مورچه برابر است با ارزش هر مورچه، تقسيم بر متوسط ارزش در ميان جمعيت مورچه ها.mating Crossovermutation

اسلاید 32: راه حل پيشنهادي براي تصحيح مسير هاي متقاطع

اسلاید 33: به سادگي اثبات ميشود که در جواب بهينه مسئلهTSP، هيچ برخوردي ميان edge ها وجود نخواهد داشت داريم aa+bb >ab+ba

اسلاید 34: بــااعمال روش ACO به مسئله TSP و بررسي iteration هاي مختلف مشاهده مي شود که تقريبا درتمامي مراحل بين بعضي edge ها، تقاطع وجود دارد که باعث مي شود سرعت همگرايي کاهش يابد و يا در اغلب موارد در مينيمم موضعي به دام بيفتد. مشکل اصلي در اين ارتباط که با احتمال بالا رخ مي دهد اين است که مسير انتهايي که بين آخرين شهر و اولين شهر وجود دارد، باعث ايجاد تقاطع مي شود.

اسلاید 35: روشی که مورد استفاده قرار مي گيرد روش opt-2 است. در opt-2 هر edge اي با همه edge هاي ديگر مورد مقايسه قرار مي گيرد. در هر مقايسه دو edge مورد مقايسه حذف مي شوند در نتيجه مسير کلي جواب به دو مسيرک جدا از هم تقسيم مي شود. به دوطريق مي توان اين مسيرک ها را به يکديگر وصل کرد تا مسير بسته شود. هر بار با امتحان هر دو شيوه اتصال، آرايشي انتخاب مي شود که طول کمتري را بدست دهد.

اسلاید 36: در روش پيشنهادي در اين مقاله اولا با اجراي يک الگوريتم خاص فقط مسير هايي را مورد بررسي قرار مي دهيم که با هم تقاطع داشته باشند. ثانيا با تقسيم صفحه به Set (مجموعه) هاي مختلف وبررسي تقاطع در هر يک از مجموعه ها، سرعت عملياتي را افزايش مي دهيم .

اسلاید 37: اين الگوريتم را با شکل ساده زير توضيح مي دهيم.

اسلاید 38:

اسلاید 39: نتایج مربوط به مسائل eil51 و kroa100 را در زیر می بینیم:

اسلاید 40: بنابراین اين روش با قرار دادن شهرها در چندين مجموعه و جلوگيري از مقايسه هاي اضافي که در انجام مي گيرد،در بحثهای realtime سرعت بالاتري نسبت به آن دارد.

اسلاید 41: با تشکر از حوصله شما بزرگواران امير حسين تمجيدي علي اکبر آقامحمديگروه کنترل دانشکده برق وکامپيوتر دانشگاه تبريز