بررسی اجمالی [ ویرایش ]

در دنیای طبیعی ، مورچه های برخی از گونه ها (در ابتدا) به طور تصادفی سرگردان می شوند و در هنگام گذر از مسیرهای فرمون ، هنگام پیدا کردن غذا به کلنی خود باز می گردند . اگر مورچه های دیگر چنین مسیری را پیدا کنند ، احتمالاً آنها به طور تصادفی سفر نمی کنند ، بلکه در عوض دنباله را دنبال می کنند ، در صورت پیدا کردن غذا ، بازگشت و تقویت آن را تقویت می کنند (به مکتب مربوط به مورچه ها مراجعه کنید ). [8]

اما با گذشت زمان ، دنباله فرمون شروع به تبخیر می کند ، بنابراین قدرت جذابیت آن را کاهش می دهد. هرچه زمان سفر مورچه ها به پایین مسیر و بازگشت مجدد بیشتر شود ، زمان بیشتری برای تبخیر فرومون ها وجود دارد. در مقایسه با آن ، یک مسیر کوتاه بیشتر مرتب طی می شود و بنابراین تراکم فرمون در مسیرهای کوتاه تر از مسیرهای طولانی تر بیشتر می شود. تبخیر فرمون همچنین از مزایای جلوگیری از همگرایی به محلول بهینه محلی برخوردار است. اگر به هیچ وجه تبخیر وجود نداشته باشد ، مسیرهای انتخاب شده توسط مورچه ها برای دیدن موارد بعدی به طرز بیش از حد جذاب هستند. در این حالت ، اکتشاف فضای راه حل محدود می شود. تأثیر تبخیر فرمون در سیستم های مورچه واقعی مشخص نیست ، اما در سیستم های مصنوعی بسیار مهم است. [9]

نتیجه کلی این است که وقتی یک مورچه مسیر خوبی (از جمله کوتاه) از کلنی به یک منبع غذایی پیدا کند ، سایر مورچه ها نیز به احتمال زیاد آن مسیر را دنبال می کنند و بازخورد مثبت در نهایت منجر به بسیاری از مورچه ها در یک مسیر واحد می شود. ایده الگوریتم کلونی مورچه ها این است که از این رفتار با "مورچه های شبیه سازی شده" که در اطراف گراف قدم می زنند ، تقلید کند و مشکل را حل کند.

شبکه های محیطی از اشیاء هوشمند [ ویرایش ]

مفاهیم جدید لازم است از آنجا که "هوش" دیگر متمرکز نیست ، اما می تواند در تمام اشیاء کوچک ریز پیدا شود. شناخته شده است که مفاهیم انسان شناسی منجر به تولید سیستم های IT می شوند که در آن پردازش داده ها ، واحدهای کنترل و نیروهای محاسبه متمرکز است. این واحدهای متمرکز به طور مداوم عملکرد خود را افزایش داده و قابل مقایسه با مغز انسان هستند. مدل مغز به دید نهایی رایانه ها تبدیل شده است. شبکه های محیطیاشیاء هوشمند و دیر یا زود ، نسل جدیدی از سیستمهای اطلاعاتی که حتی بیشتر گسترش یافته و مبتنی بر فناوری نانو هستند ، این مفهوم را به شدت تغییر می دهند. دستگاه های کوچک که می توانند با حشرات مقایسه شوند ، هوش بالایی از خود به خود اختصاص نمی دهند. در واقع ، هوش آنها می تواند نسبتاً محدود طبقه بندی شود. به عنوان مثال ، ادغام یک ماشین حساب با کارایی بالا با قدرت حل هر نوع مشکل ریاضی در یک بیوشیمی که در بدن انسان کاشته شده یا در یک برچسب هوشمند که برای ردیابی مقالات تجاری طراحی شده است ، غیرممکن است. با این حال ، به محض اتصال این اشیاء ، نوعی از هوش را می توان با کلونی از مورچه ها یا زنبورها مقایسه کرد. در مورد مشکلات خاص ،[10]

طبیعت نمونه های مختلفی از چگونگی موجودات کوچک در صورتی که همه آنها از همان قانون اساسی پیروی کنند ، ارائه می دهد و می تواند شکلی از هوش جمعی را در سطح ماکروسکوپی ایجاد کند. مستعمرات حشرات اجتماعی کاملاً این مدل را نشان می دهند که تفاوت زیادی با جوامع بشری دارد. این مدل مبتنی بر همکاری واحدهای مستقل با رفتار ساده و غیرقابل پیش بینی است. [11]آنها برای انجام کارهای خاص از طریق محیط اطراف خود حرکت می کنند و فقط اطلاعات بسیار محدودی برای این کار دارند. به عنوان مثال ، مستعمره مورچه ها ویژگی های بی شماری را نشان می دهد که می تواند برای شبکه ای از اشیاء محیط نیز اعمال شود. مستعمرات مورچه ها از ظرفیت بسیار بالایی برای انطباق خود با تغییرات در محیط و همچنین قدرت عظیمی در مواجهه با موقعیت هایی که فرد در انجام یک کار مشخص ناتوان است ، برخوردار هستند. این نوع انعطاف پذیری همچنین برای شبکه های تلفن همراه اشیاء که به طور دائم در حال توسعه هستند بسیار مفید خواهد بود. بسته های اطلاعاتی که از رایانه به یک شیء دیجیتالی منتقل می شوند ، به همان روشی که مورچه ها انجام می دهند ، رفتار می کنند. آنها از طریق شبکه حرکت می کنند و از یک گره به نقطه دیگر با هدف رسیدن به مقصد نهایی خود در اسرع وقت عبور می کنند. [12]

سیستم فرمون مصنوعی [ ویرایش ]

ارتباطات مبتنی بر فرمون یکی از موثرترین راههای ارتباطی است که به طور گسترده در طبیعت مشاهده می شود. فرمون توسط حشرات اجتماعی مانند زنبورها ، مورچه ها و موریانه ها استفاده می شود. هر دو برای ارتباطات میان عامل و عامل-ازدحام. به دلیل امکان پذیر بودن آن ، فرمون های مصنوعی در سیستم های روباتیک چند ربات و ازدحام پذیرفته شده اند. ارتباطات مبتنی بر فرمون با روشهای مختلفی مانند شیمیایی [13] [14] [15] یا فیزیکی (برچسب های RFID ، [16] نوری ، [17] [18] [19] [20] صدا [21] راه اجرا شد. . با این حال ، این پیاده سازی ها قادر به تکرار همه جنبه های فرومون ها نیستند که در طبیعت مشاهده می شود.

استفاده از نور پیش بینی شده در مقاله IEEE در سال 2007 توسط گارنیر ، سیمون و همكاران ارائه شد. [22] به عنوان یک آزمایش تجربی برای مطالعه ارتباطات مبتنی بر فرمون با روبات های میکرو خودمختار. مطالعه دیگری که یک روش ارتباطی فرمون جدید ، COSΦ ، [23] را برای یک سیستم روباتیک ازدحام پیشنهاد داده است ، بر محلی سازی دقیق و سریع بصری است. [24] این سیستم امکان شبیه سازی تعداد نامحدودی از فرمون های مختلف را فراهم می کند و نتیجه تعامل آنها به عنوان یک تصویر مقیاس خاکستری در صفحه LCD افقی که روبات ها روی آن قرار می گیرند ، فراهم می کند. به منظور نشان دادن روش ارتباط فرمون ، ربات خودمختار Colias به عنوان سکوی رباتیک ازدحام مستقر شد. [ نیاز به استناد ]

الگوریتم و فرمول ها [ ویرایش ]

در الگوریتم های بهینه سازی کلونی مورچه ها ، مورچه مصنوعی یک عامل محاسباتی ساده است که به دنبال راه حل های مناسب برای یک مسئله بهینه سازی معین است. برای استفاده از یک الگوریتم کلونی مورچه ها ، مشکل بهینه سازی باید به مشکل پیدا کردن کوتاهترین مسیر در یک نمودار وزنه تبدیل شود. در مرحله اول هر تکرار ، هر مورچه به صورت تصادفی یک محلول را می سازد ، یعنی ترتیب ترتیب لبه های نمودار را دنبال می کند. در مرحله دوم ، مسیرهای یافت شده توسط مورچه های مختلف مقایسه می شود. مرحله آخر شامل بروزرسانی سطح فرمون در هر لبه است.

روش ACO_MetaHeuristic است 
    در حالی که not_termination انجام می دهد
        generateSolutions ()
        daemonActions ()
        pheromoneUpdate ()
    تکرار
روش پایان

انتخاب لبه [ ویرایش ]

برای حرکت از طریق نمودار ، هر مورچه نیاز به ساختن راه حل دارد. برای انتخاب لبه بعدی در تور ، مورچه طول هر لبه موجود از موقعیت فعلی خود و همچنین سطح فرمون مربوطه را در نظر می گیرد. در هر مرحله از الگوریتم ، هر مورچه از یک حالت حرکت می کندایکس بیان کردن یمربوط به یک راه حل واسطه ای کامل تر. بنابراین ، هر مورچهک یک مجموعه را محاسبه می کند A_ {k} (x)از گسترش های ممکن به وضعیت فعلی آن در هر تکرار ، و به احتمال زیاد به یکی از این موارد منتقل می شود. برای مورچهک، امکانp_ {xy} ^ {k} حرکت از دولت ایکس بیان کردن یبستگی به ترکیب دو مقدار ، جذابیت دارد \ eta _ {xyاز حرکت، به عنوان برخی اکتشافی نشان دهنده محاسبه پیشینی مطلوبیت که حرکت و سطح دنباله دار\ tau _ {xyاز این حرکت ، نشان می دهد که در گذشته چقدر مهارت داشته است تا این حرکت خاص را انجام دهد. سطح دنباله دار نشان دهنده یک نشانه پسینی از مطلوبیت که حرکت کند.

به طور کلی ، کمورچه ها از دولت حرکت می کنند ایکس بیان کردن ی با احتمال

p_ {xy} ^ {k} = {\ frac {(\ tau _ {xy} ^ {\ alpha}) (\ eta _ {xy} ^ {\ beta})} {\ sum _ {z \ in \ mathrm {مجاز} _ {x}} (\ tau _ {xz} ^ {\ alpha}) (\ eta _ {xz} ^ {\ beta})}}

جایی که

\ tau _ {xy مقدار فرمون سپرده شده برای انتقال از دولت است ایکس به ی، \ آلفا  یک پارامتر برای کنترل تأثیر است \ tau _ {xy،\ eta _ {xy مطلوبیت انتقال دولت است xy( دانش پیشینی ، به طور معمول)1 / d _ {{xy}، جایی که د فاصله است) و \ بتا  ≥ 1 پارامتر برای کنترل نفوذ است \ eta _ {xy. \ tau _ {xz و \ eta _ {xz نشان دهنده سطح دنباله و جذابیت برای گذارهای دیگر ممکن است.

بروزرسانی فرمون [ ویرایش ]

معمولاً وقتی همه مورچه ها راه حل خود را به اتمام رسانده اند ، مسیرها به روز می شوند ، به ترتیب سطح مسیرهای مربوط به حرکاتی که بخشی از راه حلهای "خوب" یا "بد" بودند ، افزایش یا کاهش می یابد. نمونه ای از یک قانون به روزرسانی فرمون جهانی است

\ tau _ {xy} \ leftarrow (1- \ rho) \ tau _ {xy} + \ sum _ {k} \ Delta \ tau _ {xy} ^ {k}

جایی که\ tau _ {xy مقدار فرمون سپرده شده برای انتقال حالت است xy، .رو است ضریب تبخیر فرمون و\ دلتا \ تاو _ {xy} ^ {k} مقدار فرومون سپرده شده توسط کمورچه هفتم ، به طور معمول برای یک مشکل TSP (با حرکات مربوط به قوس نمودار) توسط

\ Delta \ tau _ {xy} ^ {k} = {\ آغاز {موارد} Q / L_ {k} & {\ mbox {اگر مورچه}} k {\ mbox {از منحنی}} xy {\ mbox {استفاده می کند تور}} \\ 0 & {\ mbox {در غیر این صورت}} \ پایان {موارد}}

جایی که L_ {k} هزینه آن است کتور مورچه ها (به طور معمول طول) وس ثابت است.

برنامه های افزودنی مشترک [ ویرایش ]

در اینجا برخی از محبوب ترین تغییرات الگوریتم های ACO آورده شده است.

سیستم مورچه  [ ویرایش ]

Ant System اولین الگوریتم ACO است. این الگوریتم مطابق با الگوی ارائه شده در بالا است. توسط دوریگو توسعه داده شده است. [25]

سیستم کلونی مورچه (ACS) [ ویرایش ]

در الگوریتم سیستم کلونی مورچه ها ، سیستم مورچه اصلی در سه جنبه اصلاح شده است: (i) انتخاب لبه به سمت بهره برداری مغرضانه است (یعنی به نفع احتمال انتخاب کوتاهترین لبه ها با مقدار زیادی فرمون). (ب) در حین ساختن یک راه حل ، مورچه ها با استفاده از یک قانون به روزرسانی فرمون محلی ، سطح فرمون لبه های مورد نظر خود را تغییر می دهند. (iii) در پایان هر تکرار ، تنها بهترین مورچه مجاز است با استفاده از یک قانون به روزرسانی فرمون جهانی اصلاح شده ، مسیرهای موجود را به روز کنید. [26]

سیستم مورچه های نخبه گرا [ ویرایش ]

در این الگوریتم ، بهترین راه حل جهانی فرمون را در دنباله خود بعد از هر تکرار (حتی اگر این دنباله تجدید نظر نشده است) به همراه سایر مورچه ها رسوب می کند.

سیستم مورچه

Max-Min (MMAS) [ ویرایش ]

این الگوریتم حداکثر و کمترین مقدار فرمون را در هر دنباله کنترل می کند. فقط بهترین تور جهانی یا تکرار بهترین تور مجاز به اضافه کردن فرمون به دنباله آن است. برای جلوگیری از رکود الگوریتم جستجو ، دامنه مقادیر احتمالی فرمون در هر دنباله محدود به یک فاصله زمانی [τ حداکثر ، τ دقیقه ] است. تمام لبه ها به τ حداکثر برای مجبور کردن اکتشاف بالاتر از محلول ها اولیه می شوند. در هنگام نزدیک شدن به رکود مسیرها به حداکثر می رسند. [27]

سیستم مورچه ای مبتنی بر رتبه (ASrank) [ ویرایش ]

همه راه حل ها با توجه به طول آنها رتبه بندی می شوند. فقط تعداد مشخصی از بهترین مورچه ها در این تکرار مجاز به روزرسانی آزمایش های خود هستند. مقدار فرمون سپرده شده برای هر محلول وزن می شود ، به گونه ای که محلول هایی با مسیری کوتاه تر فرمون بیشتری را نسبت به محلول های دارای مسیری طولانی تر به دست می آورند.

مستعمره مورچه ارتوگونال مداوم (COAC) [ ویرایش ]

مکانیسم رسوب فرمون COAC این است که مورچه ها را قادر به جستجوی راه حل های مشترک و موثر می کند. با استفاده از یک روش طراحی متعامد ، مورچه ها در دامنه عملی می توانند با انتخاب و جستجوی پیشرفته جهانی ، مناطق منتخب خود را به سرعت و کارآمد کشف کنند. روش طراحی متعامد و روش تنظیم شعاع تطبیقی ​​نیز می تواند به سایر الگوریتم های بهینه سازی برای ارائه مزایای گسترده تر در حل مشکلات عملی گسترش یابد. [28]

بهینه سازی کلونی مورچه بازگشتی [ ویرایش ]

این یک نوع بازگشتی سیستم مورچه است که کل حوزه جستجو را به چندین زیر دامنه تقسیم می کند و هدف را در این زیر دامنه ها حل می کند. [29] نتایج حاصل از کلیه زیر دامنه ها مقایسه می شود و بهترین تعداد کمی از آنها برای سطح بعدی ارتقا می یابد. زیر دامنه های مربوط به نتایج انتخابی بیشتر تقسیم می شوند و تا زمانی که خروجی از دقت مطلوب حاصل نشود ، این روند تکرار می شود. این روش بر روی مشکلات وارونگی ژئوفیزیکی بدحال آزمایش شده است و به خوبی کار می کند. [30]

منبع

https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms