بسم الله الرحمن الرحیم
ربابه خشنودی
معصومه عباس زاده
خانم مهندس لنگری
Ant colony optimization
بهینه سازی الگوریتمهای اجتماع مورچگان
مقدمه:
یکی از مسائلی که به وسیله ی زیست شنا سان مورد مطالعه قرار گرفته است درک این موضوع است که چگونه موجودات تقریبا کور مانند مورچه ها کوتاه ترین مسیر را از لانه ی خود تا منبع غذا و بر عکس پیدا می کنند.آنها پی بردند که یک رسانه برای ابلاغ اطلاعات بین تک تک مورچه ها مورد استفاده قرار می گیرد و برای تصمیم گیری درمورد اینکه کدام مسیر را انتخاب کنند به کار می رود که آن رسانه بو(اثر) ماده ای به نام فرومون.
الگوریتمهای لانه ی مورچه از جمله روشهای مکاشفه ای هستند که برای حل مسایل بهینه سازی سخت پیشنهاد شده اند.
این الگوریتم ها در آغاز از رفتارهای اجتماعی پشت سرهم قرار گرفتن و تعقیب کردن الهام گرفته شد، که در جامعه ی مورچگان مشاهده گردید. یک اجتماع از عامل های ساده (مورچه ها) به طور غیر مستقیم از طریق تغییرات پویای (دینامیکی) محیط ارتباط برقرار می کنند (رد پاهایی از فرومون) و بنابراین بر اساس تجربه ی اجتماعی آنها، یک راه حل برای یک مسئله ارائه می دهند.
در این مطالعه مدل کاوش مورچه ها Meta-Heurestic انتخاب شده است و درابتدا به مطالعه الگوریتمهای ساده سپس سیستم AS (ant system) و سیستمACS (ant colony system) و MMAS(max-min ant system) شرح داده می شود.
رفتار طبیعی مورچه:
یک مورچه در حال حرکت مقداری فرومون دراندازه های گوناگون از خود بر روی زمین باقی می گذارد و بدین ترتیب مسیر را به وسیله ی بوی این ماده مشخص
می سازد. هنگامی که یک مورچه به طور تصادفی و تنها حرکت میکند با روبه رو شدن با مسیری که توسط مورچه یا مورچه های قبلی انتخاب شده و دارای بوی فرومون است به احتمال زیاد آن را انتخاب می کند و با فرومونی که خود بر جای می گذارد بوی آن را در مسیر مذکور تقویت می نماید.
وقتی رفتار جمعی پدید میآید، گونه ای از رفتار خود تقویتی است، یعنی هرچه مورچه ها بو(اثر) ماده ی مذکور را دنبال کنند آن بو برای مورچه های پیرو آنها جذاب تر خواهد بود. فرایند گفته شده به وسیله ی یک حلقه توصیف می شود، یعنی احتمال اینکه یک مورچه یک مسیر را انتخاب کند متناسب باتعداد مورچه هایی که قبلا آن مسیر را انتخاب کرده اند ،افزایش مییابد.
ایده این است که اگر در یک نقطه معین یک مورچه مجبور است از بین مسیرهای مختلف یکی را انتخاب کند، مسیرهایی را که توسط مورچه های قبلی بیش تر انتخاب شده اند، به عبارت دیگر سطح بوی آنها بالاتر است، با احتمال بیشتری انتخاب خواهد کرد. به علاوه سطح فرمون بالاتر معادل مسیرهای کوتاهتر خواهد بود.
الگوریتم های مورچه های مصنوعی به طور افزایشی با اضافه کردن به جا و مناسب مولفه های راه حل تعریف شده به راه حل جزئی مورد نظر، راه حلهایی را می سازند.
مسیرها و غذایابی
در تصویر بالا مسیرهای متفاوت برای غذایابی دیده می شود.و تعداد مورچه ها و A و B مسیرهای در زمان t جستجو برای یافتن مسیر آغاز و در زمان t+1، مسیر پیدا شده و فرمول مورد استفاده :
رابطه:1-1
cکمیتی غیر اکتشافی برای مقدار جذب فرمون است و تحت تاثیر فرمون ذخیره شده در فرآیند است.و باتعداد مورچه ها نسبت مستقیم دارد.در اثر تجربه مقدار برای a=2 و c=20 است.
اگر پس مسیر A بهتر از B است.
اگر دو مسیر یکسان باشند مسیر بصورت تصادفی و تعداد مورچه ها یکسان باشد در بیشتر موارد مسیر کوتاهتر بعد از مدتی پیدا می شودو مقدار فرمون مسیر کوتاهتر بیشتر از مسیر دیگر است.
Let r~U(0,1)
For each potential path A do
Calculate Pa using e.g. ,1-1
If r<=Pa then
Follow path A;
Breack ;
End
End
الگوریتم اولیه :
بهینه سازی کلونی مورچه ساده SACO
برای انجام این کار، مورچه های مصنوعی یک گام برداری تصادفی را روی گراف همبند کامل G=(C,L) انجام می دهند، که راسهای آن مولفه های راه حل C و مجموعهء L ، اتصالات است.این گراف، گراف ساخت نام دارد.
وقتی یک مسئله CO دارای محدودیت را در نظر می گیریم، محدودیتهای مسئله در رویه سازندهء مورچه ها ساخته می شوند به نحوی که در هر مرحله از فرایند ساخت فقط مولفه هایی از راه حل که عملی هستند می توانند به راه حل جزئی فعلی اضافه شوند. به علاوه مولفه ها و اتصالات به ترتیب می توانند با مقدار اکتشافی متناظر گردند.
این مقادیر برای تصمیمات احتمالی مورچه ها در مورد چگونگی حرکت در گراف ساخت استفاده می گردند.احتمالات مربوط به گراف ساخت، احتمالات انتقال نامیده می شود.
بعد از مقدار دهی اولیه به مقادیر فرومون ، در هر مرحله ، هر مورچه یک راه حل را می سازد. سپس این راه حلها برای به روزرسانی مقادیر فرومون استفاده می گردند
در ابتدا، کلیهء مقادیر فرومون با یک مقدار کوچک مشابه مقداردهی می شوند. در فاز ساخت، یک مورچه با افزودن مولفه هایی به راه حل جزئی فعلی ، به تدریج یک راه حل را ایجاد می کند.اگر هیچ نودی وجود نداشته باشد و در غیر اینصورت فرآیند انجام و به انتها می رسد.ودر صورت افتادن در حلقه باید ان مسیر حذف و دوباره عملیات انجام گردد. وحلقه ها از بین می رود.
وبرای هر مسیر پیموده شده برای K مورچه :
و این بدین معنی است که تعداد عبور ومرور برای هر مسیر طی شده بصورت معمولی باشد در هر بار مقدار F(xk(t)) فرمون بدست می آید و اگر برای همه یکسان باشد بنابراین تنها مسیری متفاوت خواهد بود که کوتاهتر باشد.و همچنین مقدار کاهش فرمون F(xk(t))/1 خواهد بود.
بنا براین مقدار طول مسیرها مقدار F را کاهش داده و مورچه ها مجبور می شوند مسیر کوتاهتر را پیدا نموده وتغییر مسیر دهند در این الگوریتم 2 مقدار داریم:
مقادیر ضمنی :
رفتار مورچه ها در طول مسیر متفاوت تحت تاثیر بقیه مورچه ها قرار دارد.
مقادیر صریح:
مقادیر فرمون تولید شده متناسب با مقدار فرمون محیط است.
در الگوریتم باید شدت تکرار مقدار فرمون قبل از استحکام مسیرهای جدید برای انها محاسبه شود. با
در مقادیر بالا فرمون بسرعت رشد می کند و اگر کم شود نرخ رشد کاهش می یابد الفا =1 باشد جستجو کاملا تصادفی خواهد بود.
برای مورچه ها انتخاب مسیر بعدی وابسته به اطلاعاتی است که مورچه های دیگر از طریق فرمون بجا گذاشته اند بنابراین در یک محیط محلی انتخاب مسیر بعدی تصادفی نخواهد بود.
Ant system
در مطالعه الگوریتم ACO تصمیم گیری برای طول مسیر بود که با افزایش طول مسیر کارایی آن پایین می آمد وبنابراین تغییراتی نیز برای اضافه شدن اطلاعات(فرمون) و اکتشاف لینکهاو حافظه برای هر دوره و بروز رسانی لینکها داشته باشیم.
Ant system اولین الگوریتم پیشرفته بوسیله دوریگو مورد مطالعه قرار گرفت و این پیشرفت روی SACO ،بوسیله تغییرات دراطلاعات وتغییرات در اکتشاف لینکها و اضافه نمودن حافظه می باشد.
در AS تغییرات نود I به j بصورت:
اولویت اثردر محاسبه هیوریستیک به هنگام حرکت از نود I به j در مقدار اثرگذار بوده ومقدار کم میگردد.
مقدار تمرکز فرمون در هنگام حرکت باید نگهداری شود.
پس پارامترهای و در حفظ شده و باالگوریتم اکتشافی GREEDY مقدارآنها محاسبه می گردد.
مسائلی که درآنها هزینه و یا فاصله کمینه مورد نیاز است با محاسبه می شوند.
وبرای طی نشدن مسیری خاص می توان یک لیست ممنوع تولید کرد(حلقه مانع که نباید توسط مورچه ها طی شود )ومورچه در هنگام دیدن یک نود جدید آن را با لیست ممنوع مقایسه وسپس تصمیم می گیرد که انرا طی کند یا نه؟
و فرمول محاسبه حلقه مانع:
برای تشخیص سیکل:
در چرخه پیاده سازی شده فرمون با مقدار Q در توابع اصلی بروز رسانی میشود و Q مقدار مثبت است. اگر سیکلی وجود دارد مقدار فرمون را بروز برسان
برای آنکه بتوانیم تراکم مورچه ها را در سیکل محاسبه کنیم.
فرمون در مسیر با تراکم بالا محاسبه می گرددو برای کمیت مورچه ها نیز چون اطلاعات بصورت محلی ذخیره می گردند باید بروز زسانی شوند .
در این الگوریتم تمامی مکانها به مورچه ها اعلام گردید و جایگاه مورچه ها نیز بصورت تصادفی قرار گرفت و کوتاهترین مسیر نیز اعلام شد.
تفاوت ACS با AS :
1)افزایش مسیرهای متفاوت برای پیمودن
2)در مسیرها فرمون متفاوت تولید می گردد.
3)مکان فرمون محلی بروز می شود.
4)لیست کاندید برای هر نود تعریف می شود.
در ACS قانون افزایشی موجب انجام پردازش تصادفی متناسب با مسیر می شود.توانایی اکتشاف واستخراج نودها بالا می رود.K مورچه در مکان نود جاری هستند پس به نود بعدی حرکت می کنند.
ACS نزدیکترین همسایگی را نیز پیدا میکند و شرایط نودها در اولین برخورد قرار می دهد.در لیست شرایط بوسیله کاهش فاصله نود بعدی را انتخاب می کند و اگر لیست کاندید خالی بود نود بعدی انتخاب می گردد.و شرایط جدید باید نزدیکترین شرایط به قبلی باشد.
الگوریتم MAX-MIN
سیستم مورچه برای مسائل پیچیده ایستا استفاده می شود که ایستایی در اینجا برای همه مورچه ها ،مسیر یکسان را تعریف می کند و در هنگام استخراج واکتشاف مقدار فرومون بالا می رود .
(استاتزل و هاس) سیستم مورچه max-min را نا م MMAS برای حل مسئله ارائه دادند و تفاوت آن با AS شدت فرومون تطبیق داده شده در فاصله محدود است که مقدار بهترین فرومون با بیشترین مقدار را تایید می کند و در آن از مکانیسم هموار سازی فرومون استفاده می گردد.
ایستایی در نقطه تمرکز فرومون ti,j در بیشترین مقدار و بهترین تکرار مسیر با فاکتور شاخه لاندا با مقدار 0.05 وچون به وسیله تعداد لینک های نود تعریف می شود ،در نقطه ایستایی کاهش می یابد .
خروجی الگوریتم max-min تغییر رنج برای همه ti,j گسترش می دهد. و در این نسخه tmin , tmax پارامترهای استاتیک وابسته هستندو مقدار جدید برای تابع فرومون تمرکز یافته در مقادیر بالاست.
همچنین به رشد سریع فرومون و بهترین همگرایی کمک می کندو کاهش تغییرات در لینکهای پایین تئوری کاهش توانایی نامیده می شود.
فرایند جستجوی سراسری در الگوریتم های بعدی مورد استفاده قرار می گیرد.
الگوریتم اصلی در این بازی بروی رفتار کلونی مورچه ها [Derigo] پیاده سازی شده و در آن از استراتژی فعال استفاده شده است.این بازی بروی ماتریسی M*N قرار گرفته و مکانی که هر مهره اشغال میکند بروی هر نقطه از ماتریس،ممکن است بمبی قرار داده شده باشد و این بازی دارای سطوح متفاوت است.و با دلفی 2006 نوشته شده و از الگوریتمهای ژنتیک چند عامله در آن استفاده شده است.
انواع استراتژیها :
الف)وابسته: وابسته به بازیکنهایی که با یکدیگر برای رسیدن به هدف مشترک کار می کنند.
ب)رقابتی: رقابت بین بازیکنهایی که برای بدست آوردن هدف مبارزه می کنند.
ج)ترکیبی: که درآنها هدف مشترک و بایکدیگر نیز مبارزه می کنند.
در بیشتر استراتژیها در بازیهای مقایسه ای از روش minimax و هرس alpha-beta برای ساختن درخت جستجو استفاده می شود.
تشریح بازی :
در این بازیها مثل شطرنج ،چکرز و اتلو که دارای عامل سودمندی نیز هستند تغییرات و هدفها برای طرفین کاملا مشخص است.و طرفین بازی به تمام قوانین آشنا هستند ودر بازیهای ورق مثل پوکر و یا تخته نرد احتمال و شانس نیز دخالت دارد.
در بازی رقابتی goیک صفحه شطرنجی ساده 19*19 اما با حرکات وتکنیکهای کاملا پیشرفته از منابع بیشتری مانند الگوریتمهای ژنتیک وفازی عصبی نیز باید استفاده نمود .
بعنوان مثال استراتژی اصلی[Lujan2004] از شبکه های عصبی برای یادگیری بازی go بوده است.
در این بررسی 2نوع از توابع با استفاده ازالگوریتمهای اتاماتای یادگیر وانالیز ژنتیک بهره بردندو دران انواع پیچیدگی برای بازیکنان ارزیابی شده وهربازیکن بهترین استراتژی را پی می گیرد.
یک راه حل دیگردربازیهای چند عامله که دارای هدف مشترک ،در مقاله [Parker1998] نشان داده شده که گروهی از مورچه های وابسته به یک محل با حرکت شبکه ای در محلهایی که امیدی به افزایش متغیرهای لبه گذاری وجود ندارد را با فرمون مخصوص مشخص می کنند.
هدف بازی در تکنیکهای هوش مصنوعی در جدولی در انتها آورده شده است که الگوریتم اصلی آن برای کلونیهای جمعی مورچگان در بازی animat و پیدا کردن بمبها در شبکه ای که هر animat دارد و هر مورچه انواع متفاوت فرمون را تولید می کند تا جای بمبها در ماتریس بازی شناخته شود.
بازی animat:
این بازی با ماتریس M*N است و بمبها و animatها در آن شرکت دارند.
در مربع شروع یک یا دو راه توسط animatانتخاب می شود و تاجائیکه یک animatدیگر از ماتریس بیرون بیایدو سپس آنها باید بمبها را پیدا کنند در ماتریس هر animat خودش یک کلونی است و پخش آنها بصورت تصادفی است و پخش مانع نیز بصورت
Grid (I,j) = abstacle if and only if (I,j mod 2=0)
Animatها در شبکه بصورت افقی یا عمودی حرکت می کنند و مسیر بصورت N,S,E,w و با شرایط زیر است :
1)if (I mod 4=0) then direction=N
Else direction=S
2)if (j mod 4=0) then direction=W
Else direction=E
مسیر نادرست : مسیری است که به یک مانع یا خارج از صفحه انتقال می یابد و باید حذف شود.
سطوح متفاوت در بازی بیشترین حرکات اصلی را برای پیدا کردن بمبها بصورت زیر تعریف
می کند:
سطح مبتدی: کمتر از 2*(M*N) حرکت.
سطح متوسط: کمتر از (M*N) حرکت.
سطح پیشرفته: کمتر از (M*N)/2 حرکت.
پشت زمینه:
نظریه ACO در طبیعت استراتژی محیطهای چند عامله است.سیستم جستجوی ACO بروی فرمون بنا شده است که توسط مورچگان در مسیر ترشح شده و راهنما برای دیگر مورچگان است
انواع متفاوت فرمون پیامهای متفاوت (غذا،خطر و….)را اعلام می دارند واین فرمون تبخیرمی شود.
چگونگی کوتاهترین مسیر برای پیدا کردن غذا را موجب می شود.
از این استراتژی برای حل مسائل از قبیل TSP وNP و مسیر یابی در شبکه ها استفاده می شود.
پیاده سازی:
بیشترین مقدار تغییرات فرمون در خانه های مجاور به فاصله بین نودها و مقدار فرمون بستگی دارد.
در بازی animatفاصله بین نودها همواره 1 است پس وابستگی فرمون 1خواهد شد مقدار فرمون عددی تصادفی فرض می شود که با بالا رفتن زمان ،کاهش می یابد.
مقدار افزایش فرمون ترشح شده توسط مورچه درهرمسیر متناسب با عکس مقداردر طول مسیر است.
هر مورچه برای پیدا کردن هدف(پیدا کردن بمب) تلاش می کندو بعد از پیدا کردن اولین بمب مورچه ها بلافاصله جابجا می شوند
در موقعیتی که بمب پیدا شده و دوباره شروع به حرکت می کنند تا هنگامیکه بمبها را به بیشترین تعداد در ماتریس برسانند.
در هر آغاز ،مسیرها با ادامه دادن تقویت می شوند.
هر مسیر که تقویت شده است باید محکمترین و کوتاهترین باشد.تا مورچه ها در برگشت از آن استفاده کنند.
در هر حال ،تنوع تصمیم گیری در مسیر ها با مورچه های متفاوت از کلونیهای متفاوت باید سنجش واندازه گیری شوند.
تصمیم در هر مورد برای مورچه ها Xa,Xb (از کلونی aبه b) در یک زمان لایه های متفاوتی از فرمون را می سازند و پیدا کردن لایه L1برای بمب در سطح L1 و L2برای بمب سطح L2خواهد بود.
بعبارت دیگر ،فرمون تولید شده در لایهI ام برای بمب Iام خواهد بود.
نتیجه دیگر اینکه وقتی چندین animat مورد استفاده قرار می گیرند در یک مسیر
نمی تواند با animatدیگر ترکیب شوند پس باید در مسیر یکسان نوع فرمون هر animat با نوع فرمون animat دیگر تفاوت داشته باشد بنابراین دیگر این animat ها بایکدیگر اشتباه گرفته نمی شوندواین مکانیسم برای بمبها در مسیر نیز استفاده می شود.
نتایج:
برای تست الگوریتم 1200حالت تجربه وجود دارد که 600حالت برای هرشبکه در اندازه (11*11)و…(15*15)و اندازه هرشبکه 200 حالت تجربه که با 3و4و5 animat انجام گرفته است.
شکل 2 پیکربندی را برای 3، animat و10%از بمبها بصورت تصادفی نشان می دهد.
شکل بعدی حرکت پیدا شده برای هر animat وپیدا کردن بمبها در ماتریس را نشان میدهد.
ونتیجه19 حرکت برای هر animat است.
انعکاس نتایج این الگوریتم برای تولید استراتژی در سطوح مختلف نمایش داده شده است واین محاسبات قابل قبول می باشدو مارا برای حل مسائل پیچیده غیر کلاسیک کمک می نماید.
با تشکر از همراهیتان