ریاضیات

فهرست

• 1بررسی اجمالی
  • 1.1شبکه های محرمانه اشیاء هوشمند
  • 1.2سیستم فرومون مصنوعی
• 2فرمت های رایج
  • 2.1سیستم عامل مهاجم
  • 2.2 سیستمحداکثر مینیمم (MMAS)
  • 2.3سیستم کلون مورچه
  • 2.4سیستم مورچه بر اساس رتبه (ASrank)
  • 2.5مستعمره مورچه متعارف (COAC)
  • 2.6بهینه سازی مستعمرات مورچه
• 3همگرایی
• 4مثال شبه کد و فرمول
  • 4.1انتخاب لبه
  • 4.2به روز رسانی فرومون
• 5برنامه
  • 5.1برنامه ریزی مشکل
  • 5.2مشکل مسیریابی خودرو
  • 5.3تخصیص مشکل
  • 5.4تنظیم مشکل
  • 5.5مشکل اندازه اندازه دستگاه در طراحی فیزیکی نانوالکترونیک
  • 5.6بهینه سازی و سنتز آنتن
  • 5.7پردازش تصویر
  • 5.8برنامه های دیگر
• 6دشواری تعریف
• 7الگوریتم های Stigmergy
• 8روش های مرتبط
• 9تاریخچه
• 10منابع
• 11انتشارات (انتخاب شده)
• 12لینک خارجی

بررسی [ ویرایش ]

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

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

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

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

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

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

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

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

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

پسوندهای مشترک [ ویرایش ]

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

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

بهترین راه حل جهانی، فرومون را در هر تکرار همراه با دیگر مورچه ها نگه می دارد.

سیستم مگنوم مین (MMAS) [ ویرایش ]

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

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

این در بالا ارائه شده است. [25]

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

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

[ COAC ] [ ویرایش ]

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

روش طراحی متعارف و روش تنظیم سازگاری شعاع نیز می تواند به الگوریتم های بهینه سازی دیگر برای ارائه مزایای گسترده تر در حل مسائل عملی گسترش یابد. [26]

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

این یک شکل بازگشتی از سیستم مورچه است که دامنه جستجو را به چندین زیر دامنه تقسیم می کند و هدف را در این زیر دامنه ها حل می کند. [27] نتایج حاصل از تمام زیر دامنه ها مقایسه می شوند و بهترین آنها را برای سطح بعدی ارتقاء می دهند. Subdomains مربوط به نتایج انتخاب شده بیشتر تقسیم می شوند و روند تا زمانی که خروجی دقت مورد نظر به دست می آید، تکرار می شود. این روش بر روی مشکلات معکوس زمین شناسی معکوس آزمایش شده و به خوبی کار می کند. [28]

همگرایی [ ویرایش ]

برای برخی از نسخه های الگوریتم، می توان ثابت کرد که آن همگرا است (به عنوان مثال، قادر به یافتن بهینه مطلوب جهانی در زمان محدود است). اولین شواهد الگوریتم کلون همگرا در سال 2000، الگوریتم سیستم مورس مبتنی بر گراف، و سپس الگوریتم های ACS و MMAS ساخته شد. همانند بسیاری از متاوئیستوسئیستی ، سرعت تئوری سرعت همگرائی بسیار نزدیک است. در سال 2004 Zlochin و همکارانش [29] نشان دادند که الگوریتم های نوع COA می تواند روش های جذب شیب تصادفی ، بر روی آنتروپی متقاطع و برآورد الگوریتم توزیع را به دست آورد . آنها اینفراماسونری را به عنوان یک مدل مبتنی بر تحقیق پیشنهاد دادند"تجزیه و تحلیل عملکرد الگوریتم کلونی مستمر مورچه بر اساس پارامترهای مختلف آن، نشان دهنده حساسیت آن در همگرایی در تنظیم پارامتر است. [30]

مثال شبه کد و فرمول [ ویرایش ]

  روش  ACO_MetaHeuristic 
    در حالی که ( non_termination ) 
       generateSolutions () 
       daemonActions () 
       pheromoneUpdate () 
    پایان  در حالی که 
  روند پایان