به نام خدا
الگوریتم کلونی مورچه و زنبور عسل
Ant Colony Optimization Algorithm ( ACO )
پروسهٔ پیدا کردن کوتاه ترین مسیر توسط مورچه ها، ویژگی های بسیار جالبی دارد، اول از همه قابلیت تعمیم زیاد و خود- سازمانده بودن آن است. در ضمن هیچ مکانیزم کنترل مرکزی ای وجود ندارد. ویژگی دوم قدرت زیاد آن است. سیستم شامل تعداد زیادی از عواملی است که به تنهایی بی اهمیت هستند بنابراین حتی تلفات یک عامل مهم، تاثیر زیادی روی کارایی سیستم ندارد. سومین ویژگی این است که، پروسه یک فرایند تطبیقی است. از آنجا که رفتار هیچ کدام از مورچه ها معین نیست و تعدادی از مورچه ها همچنان مسیر طولانی تر را انتخاب می کنند، سیستم می تواند خود را با تغییرات محیط منطبق کند و ویژگی آخر اینکه این پروسه قابل توسعه است و می تواند به اندازهٔ دلخواه بزرگ شود. همین ویژگی ها الهام بخش طراحی الگوریتم هایی شده اند که در مسائلی که نیازمند این ویژگی ها هستند کاربرد دارند. اولین الگوریتمی که بر این اساس معرفی شد، الگوریتم ABC بود. چند نمونه دیگر از این الگوریتم ها عبارتند از: AntNet,ARA,PERA,AntHocNet.
الگوریتم
در پایین تعدادی از انواع شناخته شده از الگوریتم بهینه سازی مورچگان را معرفی می کنیم:
۱- سیستم مورچه نخبگان: در این روش بهترین راه حل کلی در هر تکرار فرمون آزاد می کند. همچنین این روش برای تمام مورچه های مصنوعی باید انجام شود.
۲- سیستم مورچه ماکسیموم – مینیمم: یک مقدار کمینه و بیشینه برای فرمون تعیین کرده و فقط در هر مرحله بهترین جواب این مقدار را آزاد می کند و تمام گره های مجاور ان به مقدار فرمون بیشینهمقدار دهی اولیه می شوند.
۳- سیستم کلونی مورچه: که در بالا توضیحات کافی داده شده است.
۴- سیستم مورچه بر اساس رتبه: تمام راه حل های بدست آماده بر اساس طول جواب رتبه بندی می شوند و بر اساس همین رتبه بندی مقدار فرمون آزاد سازی شده توسط آنها مشخص خواهد شد و راه حل با طول کمتر از راه حل دیگر با طول بیشتر مقدار فرمون بیشتری آزاد می کند.
۵ – سیستم مورچه متعامد مداوم: در این روش مکانیزم تولید فرمون به مورچه اجازه می دهد تا برای رسیدن به جواب بهتر و مشترک با بقیه مورچه ها جستجو انجام دهد با استفاده از روش طراحی متعامد مورچه می تواند در دامنه تعریف شده خود به صورت مداوم برای بدست آوردن بهترین جواب جستجو کند که این عمل به هدف رسیدن به جواب بهینه و صحیح ما را نزدیک می کند. روش طراحی متعامد می تواند به دیگر روش های جستجو دیگر گسترش پیدا کنند تا به مزیت های این روش های جستجو اضافه کند.
انواع مختلف الگوریتم بهینه سازی مورچگان
مقدمه
طبیعت منبع الهام و الگو گرفتن برای بسیاری از تحقیقات و پیشرفت های علمی بوده است
به عنوان مثال:
الگوریتم های ژنتیک Genetic Algorithms
شبکه های عصبی Neural Networks
سیستم های خودسازمان ده Self-organizing Systems
الگوریتمهای ژنتیک که با استفادهاز ایده تکاملی داروینی و انتخاب طبیعی مطرح شده، روش بسیار خوبی برای یافتن مسائل بهینه سازیست. ایده تکاملی داروینی بیانگر این مطلب است که هر نسل نسبت به نسل قبل دارای تکامل است و آنچه در طبیعت رخ می دهد حاصل میلیون ها سال تکامل نسل به نسل موجوداتی مثل مورچه است.
همان طور که می دانیم مسئله یافتن کوتاهترین مسیر، یک مسئله بهینه سازیست که گاه حل آن بسیار دشوار است و گاه نیز بسیار زمانبر. برای مثال مسئله فروشنده دوره گرد را نیز می توان مطرح کرد. در این روش(ACo)، مورچه های مصنوعی به وسیلهٔ حرکت بر روی نمودار مسئله و با باقی گذاشتن نشانه هایی بر روی نمودار، همچون مورچه های واقعی که در مسیر حرکت خود نشانه های باقی می گذارند، باعث می شوند که مورچه های مصنوعی بعدی بتوانند راه حل های بهتری را برای مسئله فراهم نمایند. همچنین در این روش می توان توسط مسائل محاسباتی-عددی بر مبنای علم احتمالات بهترین مسیر را در یک نمودار یافت.
300pxاین
روش که از رفتار مورچه ها در یافتن مسیر بین محل لانه و غذا الهام گرفته شده؛ اولین بار در ۱۹۹۲ توسط مارکو دوریگو (Marco Dorigo) در پایان نامهٔ دکترایش مطرح شد.
بهینه سازی گروه مورچه ها یا ACO
Emergence
Emergence یا ظهور وقتی اتفاق می افتد که تعدادی عوامل ساده مرتبط با هم به گونه ای هماهنگ عمل می کنند که منجر به رفتار هوشمند پیچیده ای می شود.
این یک فرایند از پایین به بالا است: Emergence از متن جمعیت عوامل شروع می شود . عوامل موجود در یک سطح منجر به بروز رفتار یا ویژگی در سطح بالاتر می شوند.
هیچگونه رهبری و مدیریتی در آن صورت نمی گیرد.
Emergence در سیستم های متعددی اتفاق می افتد: زندگی جمعی حیوانات و خاصا بعضی از حشرات، مغز انسان، سیستم دفاعی بدن انسان،رفتارهای اجتماعی انسان ها، سیتم شهرسازی و زندگی شهری انسان و…..
کلونی مورچه ها و به طور کلی جوامع حشرات اجتماعی ،سیستم های گسترده ای هستند که علی رغم سادگی ، ساختار اجتماعی کاملاٌ سازمان یافته ای را عرضه می کنند . از طریق این سازماندهی کلونی مورچگان می تواند وظایف پیچیده ای را انجام دهد که در برخی موارد فراتر از توانایی های یک مورچه است
مقدمه
حوزه الگوریتم های مورچه مدل هایی را مطالعه می کند که از مطالعات رفتارهای واقعی مورچه ها ناشی می شود و از این مدل ها به عنوان منبع انگیزشی برای طراحی الگوریتم های جدید به منظور حل مسائل بهینه سازی و مسائل کنترل توزیع شده (Distributed control) استفاده می کند
آذوقه جویی، تقسیم کار و مشارکت در حمل و نقل ، مثال هایی از این موارد هستند
الهام از طبیعت
یکی از موفق ترین مثال های الگوریتم های مورچه به بهینه سازی از طریق کلونی مورچه یا ACO شهرت دارد
ACO که برای حل مسائل بهینه سازی گسسته کاربرد دارد، از رفتار جمع آوری آذوقه مورچه ها الهام گرفته شده است
قوه بینایی بسیاری از گونه های مورچه بسیار ابتدایی و محدود است و حتی برخی از انواع آن ها کاملاً نابینا هستند اما کوتاه ترین مسیر رفت و برگشت از خانه تا غذا را پیدا می کنند
در حقیقت نتیجه تحقیقات اخیر در مورد رفتار مورچه ها این بود که بیشترین ارتباط بین مورچه ها و یا میان هریک از آن ها و محیط اطرافشان ، با استفاده از مواد شیمیایی تولید شده توسط مورچه ها به نام فرمون (Pheromone) صورت می گیرد
واژه استیگمرجی توسط گراس برای تشریح نوعی ارتباط غیر مستقیم از طریق تغییراتی که روی محیط اطراف گذاشته می شود استفاده می گردد، معرفی شد. وی این رفتار را از روی موریانه های کارگر مشاهده کرد
رفتار کاوشگرایانه مورچه ها و بهینه سازی
الگوریتم مورچگان اولین بار در سال 1991 توسط مارکو دوریگو (Dorigo) برای حل مسائل بهینه سازی مشکلی مانند مساله فروشنده دوره گرد Traveling) (Sales Person ارائه شد
رفتار باقی گذاردن و تعقیب رد پا (Trail Pheromone) که مورچه از مواد شیمیایی به جا مانده از سایر مورچه ها تاثیر می گیرد، منشا پیدایش ACO شد
تاریخچه
بلورهای برف : تشکیل الگوهای پیچیده متقارن مثال از ظهور در یک سیستم فیزیکی است.
تنگه گارنی در ارمنستان به عنوان مثال از ساختار طبیعی ظهور است.
تپه های تولید شده توسط یک کلنی موریانه : یک مثال کلاسیک از ظهور در طبیعت
Giant's Causewayدر ایرلند شمالی به عنوان مثال از یک ساختار پیچیده اورژانس ایجاد شده توسط فرآیندهای طبیعی است
الگوهای موج یک تپه شن و ماسه ایجاد شده توسط باد یا آب به عنوان مثال از ساختار ظهور در طبیعت.
Swarm Intelligence
یا هوشمندی توده ای تعامل جزئی تعداد زیادی عوامل ساده برای حصول یک هدف کلی است
خصوصیات هوش جمعی عبارتند از:
عوامل ساده اند
عوامل به صورت غیرمستقیم با هم ارتباط برقرار می کنند
رفتار کلی پیچیده از رفتارهای جزئی ساده عوامل حاصل می شود
این رفتارها پایدارند
تک تک عوامل در حصول نتیجه کلی بی تاثیرند
مثال از هوشمندی توده ای : تمیزکاری لانه مورچه ها
مورچه ها آشغال ها ویا غذای پراکنده درسطح لانه را جمع آوری و در یک یا چند جا کپه می کنند
این کار به این ترتیب عملی می شود:
هر مورچه شروع به گردش به صورت دلخواه و بی هدف در سطح لانه می کند
اگر مورچه به یک تکه آشغال برخورد کرد آن را بر می دارد
مورچه به گردش تصادفی خود ادامه می دهد
اگر مورچه به یک تکه آشغال دیگررسید تکه قبلی را در کنار آن قرار می دهد
و باز به گردش خود ادامه می دهد
بعد از مدتی مشاهده می شود که آشغال ها در گوشه کنار لانه کپه شده اند.
مثال از هوشمندی توده ای : لانه سازی موریانه ها
موریانه ها برای ساخت لانه سه فعالیت مشخص از خود بروز می دهند.
در ابتدا صدها موریانه به صورت تصادفی به این طرف و آن طرف حرکت می کنند. هر موریانه به محض رسیدن به فضایی که کمی بالاتر از سطح زمین قرار دارد شروع به ترشح بزاق می کنند و خاک را به بزاق خود آغشته می کنند. به این ترتیب گلوله های کوچک خاکی با بزاق خود درست می کنند. علیرغم خصلت کاملا تصادفی این رفتار، نتیجه تا حدی منظم است.
در پایان این مرحله در منطقه ای محدود تپه های بسیار کوچک مینیاتوری از این گلوله های خاکی آغشته به بزاق شکل می گیرد.پس از این، همه تپه های مینیاتوری باعث می شوند تا موریانه ها رفتار دیگری از خود بروز دهند. در واقع این تپه ها به صورت نوعی نشانه برای موریانه ها عمل می کنند. هر موریانه به محض رسیدن به این تپه ها با انرژی بسیار بالایی شروع به تولید گلوله های خاکی بابزاق خود می کند. این کار باعث تبدیل شدن تپه های مینیاتوری به نوعی ستون می شود. این رفتار ادامه می یابد تا زمانی که ارتفاع هر ستون به حد معینی برسد
در این صورت موریانه ها رفتار سومی از خود نشان می دهند. اگر در نزدیکی ستون فعلی ستون دیگری نباشد بلافاصله آن ستون را رها می کنند در غیر این صورت یعنی در حالتی که در نزدیکی این ستون تعداد قابل ملاحظه ای ستون دیگر باشد، موریانه ها شروع به وصل کردن ستونهاو ساختن لانه می کنند.
Stigmergy
stigmergy شکلی از کنترل توزیع شده برمبنای ارتباط غیر مستقیم بین عاملها که محیط را به طور محلی تغییر می دهد و به این تغییرات واکنش نشان می دهد و این عمل به فاز همکاری سراسری عملیات عاملها منجر می گردد.
تفاوت هوشمندی توده ای و هوشمندی اجتماعی
در هوشمندی اجتماعی عناصر میزانی از هوشمندی را دارا هستند
سطح هوشمندی عامل ها متفاوت است.
در هوشمندی اجتماعی ارتباط مستقیم بین عامل ها وجود دارد.
در هوشمندی اجتماعی براساس یک طرح از پیش تعیین شده عمل می شود.
خصوصیات مورچه ها
مورچه ها حشراتی اجتماعی هستند که در کلونی ها زندگی می کنند
رفتار آنها بیشتر در جهت بقاء کلونی است تا درجهت بقاء یک جزء از آن.
مورچه ها توانایی دیدن و شنیدن را ندارند و فقط از حس بویایی استفاده می کنند مورچه ها صدا نیز ندارند ولی با استفاده از حس بویایی می توانند اطلاعات را منتقل کنند
مورچه ها از خود موادی را به جا می گذارند که بوی خاصی دارند به این مواد pheromone گفته می شود
مورچه ها pheromone به جا مانده از سایر مورچه ها را حس می کنند.
مورچه ها شدت بوی pheromone را نیز تشخیص می دهند.
مورچه ها و یافتن کوتاهترین مسیر
دو مورچه به صورت تصادفی شروع به یافتن غذا میکنند .
هر دو در نهایت غذا را می یابند .
مورچه ای که مسیر کوتاهتر را طی کرده اول غذا را پیدا میکند .
هر مورچه ردی از فرومون بجا می گذارد
مورچه ای که غذا را یافته روی رد قبلی به خانه برمیگردد .
یافتن کوتاهترین مسیر
مورچه ای که مسیر کوتاهتر را پیموده اول به خانه می رسد .
یافتن کوتاهترین مسیر
حاله مورچه سومی به دنبال غذا میگردد .
مورچه سوم میتواند آثار مورچه های قبلی را تشخیص دهد .
مورچه سوم میتواند به جای انتخاب یک مسیر جدید رد مورچه های قبلی را دنبال کند.
به احتمال بیشتر ردی را دنبال میکند که میزان فرومون بیشتری دارد.
یافتن کوتاهترین مسیر
مسیر کوتاهتر به مرور تقویت میشود .
در نهایت مسیر کوتاهتر توسط اغلب مورجه ها برگزیده میشود .
الگوریتم تصادفی ساده Simple Stochastic Algorithm
وقتی یک مورچه شروع به حرکت می کند:
با احتمال کوچکی یک مسیر جدید را شروع می کند.
با احتمال بیشتری یکی از مسیرهای موجود دارای pheromone را انتخاب می کند.
ولی در انتخاب مسیرهای موجود هر چه شدت pheromone یک مسیربیشتر باشد احتمال انتخاب آن نیز بالاتر خواهد بود.
چرا مسیرهای تازه؟
مورچه های قبلی الزاما کوتاه ترین مسیررا انتخاب نکرده اند
انتخاب مسیرهای جدید می تواند منجر به یافتن مسیرهای کوتاه تر بشود
در نهایت این منتهی به یافتن کوتاه ترین مسیر می شود
pheromone تبخیر و محو تدریجی
Pheromone به تدریج تبخیر می شود.
این یکی از ضروریات پویا بودن الگوریتم است.
انتقال از مسیرهای کوتاه به مسیرهای کوتاه تر بدون تبخیر pheromone در مسیرهای قدیمی امکان پذیر نخواهد بود.
الگوریتم وفقی Adaptive algorithms
الگوریتم به صورت وفقی عمل می کند.
علت این امر احتمال شروع مسیرهای تازه
و تبخیر تدریجی در مسیرهای قبلی است.
مقابله با خرابی و تغییرات مسیر
الگوریتم به دلیل رفتار پویا و وفقی می تواند در صورت وقوع خرابی در مسیر با یافتن مسیر جایگزین با آن مقابله کند.
همچنین اگر تغییر در مسیر ایجاد شود الگوریتم خود را با تغییرات هماهنگ می کند.
برای مثال اگر سنگی در مسیر مورچه ها قرار داده شود مورچه ها آن را دور زده و مسیر کوتاه جدیدی را در کنار آن پیدا می کنند.
اثر جانبی
مورچه ها در بین غذاهای موجود در محیط اطراف لانه ابتدا نزدیک ترین آنها را منتقل می کنند.
این یک اثر جانبی الگوریتم است
این پدیده می تواند کاربردهای زیادی داشته باشد
استفاده از بهینه سازی کلونی مورچه ها در مسئله فروشنده دوره گرد
تعدادی شهر داریم و هزینه رفتن مستقیم از یکی به دیگری را می دانیم. مطلوب است کم هزینه ترین مسیری که از یک شهر شروع شود و از تمامی شهرها دقیقاٌ یکبار عبور کند و به شهر شروع بازگردد.
تعداد کل راه حل ها برابر است با برای2 n> که n تعداد شهرها است.
مثلاً برای یک نظریه گراف کامل با 30 راس تعداد
دور همیلتونی مختلف با شروع و پایان از یک راس خاص وجود دارد، که باید بررسی شود. حتی اگر برای هر دور پیدا شده در محاسبه مسافت کل به یک میکروثانیه زمان احتیاج باشد ، برای30 راس تقریباً
سال نیاز داریم.
Travelling salesman problem
الگوریتم ارائه شده توسط Marco Dorigo سال 1996
در فاز یک M مورچه حافظه دار ایجاد میشود .
این مورچه ها به صورت تصادفی روی N گره قرار میگیرند .
در هرگره مقدار اولیه فرومون وجود دارد .
در فاز دو مراحل زیر به صورت موازی انجام میشود .
مورچه قرار گرفته در گره r برای انتخاب شهر s در حرکت بعدی از رابطه (1) استفاده میکند (قانون تبدیل حالت)
پس از اینکه مورچه ها مسیر احتمالی خود را ایجاد کردند به شهر مبدا برمیگردند .در این مرحله به روز رسانی فرومون ها با استفاده از فرمول زیر :
مسیر یابی شبکه های کامپیوتری با استفاده از ACO
اطلاعات بر روی شبکه بصورت بسته های اطلاعاتی کوچکی( Packet )منتقل می شوند.
هر یک از این بسته ها بر روی شبکه در طی مسیر از مبدا تا مقصد باید از گره های زیادی که مسیریاب (Router ) نام دارند عبور کنند.
در داخل هر مسیریاب جدولی قرار دارد تا بهترین و کوتاهترین مسیر بعدی تا مقصد از طریق آن مشخص می شود، بنابر این بسته های اطلاعاتی حین گذر ازمسیریاب ها با توجه به محتویات این جداول عبور داده می شوند.
روشی بنام ACR : Ant Colony Routing پیشنهاد شده که بر اساس ایده کلونی مورچه به بهینه سازی جدول می پردازد و در واقع به هر مسیری با توجه به بهینگی آن امتیاز می دهد.
استفاده از ACR به این منظور دارای برتری نسبت به سایر روش هاست که با طبیعت دینامیک شبکه سازگاری دارد، زیرا به عنوان مثال ممکن است مسیری پر ترافیک شود یا حتی مسیر یابی از کارافتاده باشد و بدلیل انعطاف پذیری که ACO در برابر این تغییرات دارد همواره بهترین راه حل بعدی را در دسترس قرار می دهد.
یکی از آزمایشات درخشانی که توسط دنوبورگ و همکارانش طراحی و اجرا شد ، اتصال لانه گونه ای از مورچه های آرژانتینی به نام آی .هیومیلی توسط یک پل دوراهه به منبع آذوقه بود
ان ها آزمایشات خود را با طول پل های مساوی و نامساوی انجام دادند
آزمایشات پل دو راهه
پل های مساوی
نتیجه این بود که تمام مورچه ها به سمت یک شاخه همگرا می شوند
این مسئله بدین علت رخ می دهد که در ابتدای آزمایش در هیچ یک از پل ها فرومونی وجود ندارد بنابراین مورچه ها با احتمال تقریباً برابر هر دو پل را انتخاب می کنند
اما به دلیل نوسانات تصادفی ، تعداد بیشتری مورچه ها یکی از شاخه ها را بیشتر از دیگری برمی گزینند
نتایج آزمایش پل های مساوی(آزمایش اول)
پل های نامساوی
در بیشتر آزمایشات مورچه ها پس از گذشت مدتی شاخه کوتاه تر را انتخاب کردند
با توجه به مقدار فرمون بیشتری که در شاخه کوتاه تر وجود دارد شاخه کوتاه تر را برمی گزینند
بنابراین فرمون به دلیل فرایند اتوکاتالیزور( بازخورد مثبت) روی شاخه کوتاه تر که توسط همه مورچه ها انتخاب می شود سریع تر انباشته می گردد
نتایج ازمایش پل های نامساوی(آزمایش دوم)
الف. آزمایش پل با مسیرهای با طول متفاوت ب. عبور مورچه های بیشتر از مسیرهای کوتاه تر
ب
الف
نکته
به طور جالب توجهی مشاهده می شود که حتی زمانی که طول شاخه بلند تر دو برابر شاخه کوتاه تر است ، تمام مورچه ها از مسیر کوتاه تر استفاده نمی کنند. بلکه درصد کمی ( مثلاً 10%) از مورچه ها ممکن است از شاخه بلند تر بگذرند. این عمل مورچه ها کشف مسیر نامیده می شود
نکته
جالب است بدانیم که وقتی مسیر جدید و کوتاه تری بین لانه و آذوقه پس از مدتی در اختیار کلونی مورچه قرر داده شود با گذشت زمان باز هم مورچه ها شاخه کوتاه تر را انتخاب می کنند چون تبخیر کند فرمون به کلونی مورچه ها اجازه می دهد تا مسیر نیمه بهینه ای که به سمت ان همگرا شده اند را فراموش و مسیر جدید و کوتاه تر را کشف کنند
دنوبورگ و همکارانش ، یک مدل ساده احتمالی برای نحوه عملکرد کلونی مورچه ها مطابق آنچه در آزمایش پل دو راهه مشاهده شد را ارائه کردند که با استفاده از شبیه سازی مورد ارزیابی قرار گرفت
یک مدل احتمالی
احتمال این که مورچه ای در لحظه t به نقطه تصمیم iϵ{1,2}
برسد و شاخه aϵ{s,l}را انتخاب کند به طوری که s وl به ترتیب بیانگر شاخه های کوتاه و بلند باشند، تابعی از مقدار کل فرمون یعنی روی هر شاخه است که این مقدار با تعداد مورچه هایی که تا زمان t از آن شاخه عبور کرده اند، متناسب است
مقادیر بزرگ پارامتر α باعث تاکید زیاد روی مسیرهای تصادفی اولیه و نوسانات تصادفی می شود و به بروز رفتارهای بد از سوی الگوریتم می انجامد . اما معادله بالا با در نظر گرفتن مقدار 2 از طریق آزمایش بدست آمده است
ادامه
در ACO مورچه های مصنوعی فرایندها (زیر برنامه های) کامپیوتری هستند که بصورت احتمالی راه حل های مختلف مسئله را می سازند.
آزمایشات پل دوراهه نشان می دهند که کلونی مورچه ها توانایی بالقوه ای برای بهینه سازی دارند
به طرز جالب توجهی با الهام گرفتن از آزمایشات پل دو راهه ، امکان طراحی مورچه های مصنوعی که با حرکت روی یک گراف مشابه پل دوراهه، کوتاه ترین مسیر بین دو گره متناظر با لانه و منبع آذوقه را می یابند وجود دارد.
به سمت مورچه های مصنوعی
ابزارهای مورچه های مصنوعی
ردپای فرومونی مصنوعی
این مقادیر در طی مراحل یافتن راه حل، بصورت پویا تغییر می کنند تا منعکس کننده نتایج بدست آمده توسط مورچه های مصنوعی باشند
اطلاعات ابتکاری (Heuristic Information)
این اطلاعات مرتبط با ساختار مسئله مورد نظر، برای حل مسئله بکار می روند.
الگوریتم های متفاوت به روشهای گوناگون از این ابزارها استفاده می کنند…
مورچه های مصنوعی و حرکت روی گراف
A
B
C
D
E
F
الگوریتم های ACO
تنظیمات پارامتر برای الگوریتم های ACO فاقد جستجوی محلی
جستجوی محلی رویکردی کلی برای یافتن جواب هاب یا کیفیت بالا برای مسائل بهینه سازی ترکیبی دشوار در یک زمان منطقی است
این روش بر پایه کاوش و جستجوی مکرر همسایه های جواب ها است و سعی دارد که از طریق تغییرات محلی ، جواب فعلی را بهبود بخشد
وقتی الگوریتم های ACO برای حل TSP به کار می روند بهترین عملکرد زمانی است که الگوریتمACO از یک بهینه ساز محلی برای بهبود دادن جواب های ساخته شده مورچه استفاده کند
جستجوی محلی چیست؟
این مشکل بوجود خواهد آمد که مورچه ها در حین ایجاد جواب ، ممکن است حلقه ایجاد کنند
به دلیل مکانیزم به روز آوری رد فرمون هنگام رفت ، حلقه ها بیشتر و بیشتر برای مورچه ها جذاب می شوند و مورچه ها در دام آن ها گیر می افتند و مکانیزم ساده تری که در شرایط پل دوراهه مورچه ها را مجبور می ساخت ، کوتاه ترین مسیررا با احتمال بالایی انتخاب کنند دیگر کار نمی کند
سیستم درصورتی می تواند کوتاه ترین مسیر را پیدا کند که به روزآوری رد فرمون در هر دو مسیر رفت و برگشت انجام شود
نکته
بنابراین لازم است ، توانایی ها و قابلیت های مورچه های مصنوعی را به صورتی افزایش دهیم تا درحالی که اکثر ویژگی های مهم مورچه طبیعی حفظ می شوند، مورچه های مصنوعی قادر گردند مسائل مسیر حداقل هزینه را برای تمام گراف ها حل کنند
یعنی به مورچه های مصنوعی نوعی حافظه محدود داده شود تا بتوانند در آن حافظه، بخش هایی از مسیر را که تا به حال طی کرده اند و همچنین هزینه مربوطه را ذخیره کنند
نکته
حافظه جواب های شدنی می سازد (محدودیت ها را در نظر می گیرد) ، مقادیر ابتکاری را محاسبه می کند و مسیر بازگشت مورچه ها را رد یابی می کند
هر مورچه یک وضعیت آغازین (x) و یک یا چند شرط توقف (e) دارد
مثال هایی از شرط توقف می تواند رسیدن به تعداد تکرار مشخص ، اجرا شدن برنامه تا زمان مشخص ، بدست امدن جواب بهتر تا یک تعداد مشخص باشد.
نکته
با استفاده از این حافظه، مورچه ها می توانند رفتارهای مفیدی را از خود نشان دهند. این رفتار ها به قرار زیر است :
1- متمایل شدن ساختارجواب به سمت قسمت هایی که رد فرمون بیشتری دارند ، بدون به روزآوری رد فرمون در مسیر رفت
2- قطعی شدن مسیر بازگشت با حذف حلقه ها و به روزآوری فرمون
3- ارزیابی کیفیت جواب های تولید شده و استفاده از کیفیت جواب ها در تعیین مقدار فرمون به جا مانده در مسیرها
در حالت ساده مسیریابی حداقل هزینه ، تخمین کیفیت جواب می تواند در هنگام تولید جواب نیز توسط مورچه ها انجام شود، در صورتی که این دو کار لزوماً نمی تواند برای همه مسائل همزمان انجام شود. زیرا در تمام مسائل ارزیابی قسمت هایی از جواب ها مقدور نیست.
ادامه
مورچه ها گره هایی که هنگام رفت از آن ها عبور کرده اند و هزینه کمان های طی شده (در صورتی که گراف دارای وزن باشد) را به خاطر می سپارند
بنابراین آن ها می توانند هزینه جواب هایی را که تولید کرده اند، ارزیابی کنند و این ارزیابی را برای تنظیم میزان فرمونی که در مسیر بازگشتشان از خود به جای می گذارند به کار می برند
به روزآوری براساس تابعی از کیفیت جواب به دست آمده ، می تواند مورچه های بعدی را با قدرت بیشتری به سمت جواب های بهتر هدایت کند
به روزآوری فرمون براساس کیفیت جواب ها
درحقیقت با اجازه دادن به مورچه ها به منظور انباشت مقدار فرمون بیشتر روی مسیرهای کوتاه ، مسیریابی مورچه ها سریع تر به سمت بهترین جواب ها متمایل خواهد شد
مورچه های لسیونایگر که از سمت منابع غذایی ارزشمند بازمی گردند، تمایل دارند، فرمون بیشتری نسبت به مورچه هایی که از منابع ضعیف تری باز می گردند از خود به جای گذارند
ادامه
در ابتدای فرایند جستجو ، مقدار فرمون ثابتی (مثلاً برابر یک برای تمامی مقادیرi وj متعلق به A ) به تمامی کمان ها اختصاص داده می شود . هنگامی که مورچه K ام در گره iام قرار گیرد ، برای محاسبه احتمال انتخاب گره j ام به عنوان گره بعدی مسیرش ، از رد فرمون استفاده می کند
رفتار جستجوی مسیر مورچه ها
رفتار مورچه ها با در نظر گرفتن هر دو ابزار
مورچه ها قبل از بازگشت حلقه هایی که خود در مسیر رفت بوجود آورده اند را از حافظه خود پاک می کنند
برای گره ای که در موقعیت iام قرار دارد و تشخیص که اینکه این گره در حلقه واقع شده است یا نه بدین صورت عمل می شود :مسیر از گره مقصد تا جایی که اولین بار گره iام در موقعیتی مانند j پدیدار گردد ، بررسی می شود . (هموارهj ≥ i است زیرا فرایند بررسی امکان دارد نهایتاً در موقعیت i متوقف شود ) اگر j>i شود مسیر فرعی که از موقعیت i+1 تا j ادامه دارد، نشان دهنده یک حلقه است و می تواند حذف شود
مسیر یابی مجدد و به روزآوری فرمون
فرایند حذف حلقه ، الزاماً طولانی ترین حلقه را حذف نمی کند
مسیر یابی مجدد و به روزآوری فرمون
تبخیر فرمون در یافتن کوتاه ترین مسیر توسط مورچه های واقعی نقش مهمی بازی نمی کند . اما حقیقت این است که در مورد مورچه های مصنوعی به نظر می رسد تبخیر فرمون نقش مهمی ایفا کند زیرا مسائل بهینه سازی که مورچه های مصنوعی درگیر حل آن ها هستند از مسائلی که مورچه های واقعی می توانند حل کنند بسیار پیچیده ترند
تبخیر رد فرمون را می توان به عنوان مکانیزم اکتشافی در نظر گرفت که از همگرایی سریع همه مورچه به سمت یک مسیر زیر بهینه جلوگیری می کند
مکانیزمی شبیه تبخیر که به فراموش شدن خطاها و یا انتخاب های ضعیفی که قبلاً صورت گرفته می انجامد، باعث بهبود مستمر در ساختار حل مسئله آموخته شده می شود و به نظر می رسد که این مکانیزم، برای مورچه های مصنوعی ضروری باشد
تبخیر رد فرمون
فرایند تبخیر، رد فرمون را با سرعت نمایی کاهش می دهد. درS-ACO تبخیر فرمون همزمان با باقی گذاشتن فرمون توسط مورچه ها انجام می شود
رد فرمون طبق معادله زیر از روی تمام کمان ها تبخیر می شود:
به طوری که ρ∈(0,1] یک پارامتر است
ادامه
افزایش تعداد مورچه ها تخمین بهتری از میانگین رفتار مورچه هاست
درصد آزمایشاتی که در آن ها S-ACO به طولانی ترین مسیر همگرا شده است (نتایج 100 بار آزمایش مستقل برای مقادیر متفاوت m و p=0 و (α=2
M تعداد مورچه استفاده شده در آزمایش
تعداد مورچه ها و نوع به روزآوری فرمون (آزمایشاتی با پل دو راهه)
الگوریتم های دقیق سعی دارند جواب های بهینه را بیابند و علاوه بر ان بهینگی خود را اثبات کنند. برای بسیاری از مسائل چندجمله ای غیر قطعی سخت (nondeterministic polynominal hard problems)، عملکرد الگوریتم های دقیق رضایت بخش نیست و کاربرد آن ها به مثال های کوچک محدود می شود
الگوریتم های تقریبی ، بهینگی را با کارایی مبادله می کند و مزیت ان ها این است که در عمل جواب های نسبتاً مناسب را در زمان بسیار کوتاه می یابند
به یک فراابتکاری می توان به عنوان یک چارچوب الگوریتمیک عمومی نگریست که با اندک تغییر و تعدیل لازم برای تطبیق با یک مساله خاص ، می تواند برای حل مسائل بهینه سازی گوناگونی به کار رود
تفاوت الگوریتم ها
ACO یک فراابتکاری سازنده برپایه جمعیت است که از نوعی حافظه غیر مستقیم که از عملکرد های قبلی بدست می آید ، استفاده می نماید
ترکیب این خصوصیات در هیچ یک از سایر فراابتکاری ها یافته نمی شود
فراابتکاری کلونی مورچه
الگوریتم های بهینه سازی از طریق کلونی مورچه ، برای هر دو نوع مسائل ایستا و پویا بهینه سازی ترکیبی قابل کاربرد هستند و از برهمکنش سه رویکرد اصلی: جواب ساخته شده توسط مورچه ها، به روزآوری رد فرمون و اعمال خارق العاده تشکیل می شود
مسئله فروشنده دوره گرد از جمله مسائل ایستاست
مسائل مسیریابی شبکه که در آن داده های ترافیک و موقعیت مکانی (شکل و ظاهر) شبکه در طول زمان قابل تغییر است از جمله مسائل پویاست
فراابتکاری کلونی مورچه
فرایند اعمال خارق العاده برای متمرکز کردن فعالیت هایی که توسط یک دسته از مورچه ها به تنهایی قابل اجرا نیستند، به کار می روند
مثال هایی از این نوع فرایند عبارتند از: فعال سازی فرایند بهینه سازی محلی و یا جمع آوری اطلاعات کلی که برای اخذ تصمیماتی به کار می رود مبنی بر اینکه آیا لازم است به منظور منحرف ساختن فرایند جستجو از یک منطقه غیر محلی، روی مسیرها فرومون اضافی باقی گذاشته شود یا نه
مثلاً به مورچه هایی که بهترین جواب را در چرخش الگوریتم تولید کرده اند اجازه داده می شود تا فرمون اضافی را از خود روی گره ها یا کمان ها باقی بگذارند
فرایند اعمال خارق العاده
استفاده از کلونی مورچه ها برای
بررسی اثر تغییر طول مسیر ها و
افزایش فراگیر بودن الگوریتم و
کاهش وابستگی الگوریتم به پارامترهای اولیه
اهمیت دارد
اهمیت
کاربرد
کاربرد
کاربرد
فراابتکاریACO برای اولین بار در مقالاتی توسط دورجیو و دیکارو (1999) و کارو، گامباردلا و دورجیو دی (1999) تشریح شد
اولین فراابتکاری که در چارچوب فراابتکاری ACO قرار گرفت سیستم مورچه (AS) نام داشت
AS نتایج قابل توجهی در حل مسئله TSP داشت اما از نظر کیفیت نسبت به الگوریتم های جدید ضعیف تر است.
اثبات مفاهیم تئوریک ACO با AS صورت می پذیرد.
الگوریتم های جدیدتر از توسعه ی ASمحسوب می شود و اهمیت اصلی این الگوریتم در ایده هایی است که در بسط تعدادی از الگوریتم ACO استفاده شدند و باعث بهبود قابل توجه عملکرد ACO گردید
فراابتکاری ACO
AS و بسیاری از الگوریتم های بعدی ACO نیز ، برای اولین بار روی TSP آزمایش شدند
دلائل انتخاب TSP
الگوریتم های بهینه سازی توسط کلونی مورچه برای حل مساله فروشنده دوره گرد
TSP یک مساله بهینه سازی NP-hard است که کاربرد های فراوان دارد
مساله ای است که الگوریتم های ACO به سادگی روی آن قابل کاربرد می باشد
به راحتی قابل درک است
TSP بستر آزمایشی مناسبی برای نظریه های الگوریتمیک جدید است
تاریخچه ACO نشان می دهد که اکثر الگوریتم های ACO که در مورد TSP کارایی داشتند، در زمره کاراترین الگوریتم هایی قرار گرفته اند که برای گستره وسیعی از سایر مسائل نیز کارایی دارند
در گراف شهرهای فروشنده دوره گرد اگر یک از یال ها (گره ها) حذف شود الگریتم کلونی مورچگان این توانایی را دارد که تا به سرعت مسیر بهینه را با توجه به شرایط جدید پیدا کند . به این ترتیب که اگر یال (یا گره ای) حذف شود دیگر لازم نیست که الگوریتم از ابتدا مسئله را حل کند ، بلکه از جایی که مسئله حل شده تا محل حذف یال (یا گره ) هنوز بهترین مسیر را داریم ، از این به بعد مورچه ها می توانند پس از مدت کوتاهی مسیر بهینه (کوتاهترین) را بیابند
مزیت ACO برای TSP
یک مسئله ساده ی TSP
dAB =10
dAC =8
dAD =7
dBC = 6
dBD = 11
dCD =15
گام اول – آماده سازی
به هر مسیر مقدار اولیه فرومون و مقدار ابتکاری اختصاص میابد.
گام اول – آماده سازی (ادامه)
تکرار 1- ثبت در حافظه
A
D
C
B
تکرار 1- انتخاب مسیر بعدی (مورچه 1)
تکرار 1- حل مثال در اکسل
تکرار 1- ثبت مسیر جدید در حافظه (مورچه 1)
تکرار 1- کلیه مورچه ها
L1 =28
L2 =21
L3 =24
L4 =23
تکرار 1- ارزیابی مسیرها
In ACO algorithms artificial ants are stochastic constructive procedures that build solutions by moving on graph…
به روز رسانی فرومون
اول تبخیر
برای جلوگیری از افزایش بی نهایت فرومون صورت میگیرد.
باعث فراموش شدن مسیرهای نامطلوب می شود.
روی همه شاخه ها اعمال میشود.
سپس تعدیل
نوعی بازخور مثبت برای تقویت پاسخ های مطلوب است.
پاسخ های بهتر بازخور های قوی تر میگیرند.
تنها برای شاخه هائی که مورچه ای از آنها عبور کرده اعمال میشود.
به فرومون موجود روی شاخه هائی که مورچه ای از آن عبور کرده مقداری فرومون اضافه میشود.
تکرار 1- تبخیر فرومون
چگونگی تعدیل فرومون
برای موچه Kام میزان فرومونی که به شاخه i-j اضافه میشود برابر است با :
کلیه مورچه هائی که از شاخه i-j عبور کرده اند به آن فرومون اضافه می کنند.
مثالی از تعدیل فرومون
تمام مورچه ها از شاخه A-D عبور کرده اند. میزان فرومون اضافه شده به این مسیر :
از شاخه C-D فقط مورچه 1 عبور کرده است:
تکرار 1- تعدیل فرومون
شبه کد الگوریتم AS
مسیریابی شبکه های کامپیوتری با استفاده از ACO
اطلاعات بر روی شبکه به صورت بسته های اطلاعاتی کوچکی منتقل می شوند.هریک از این بسته ها بر روی شبکه در طی مسیر از مبدء تا مقصد باید از گره های زیادی که مسیریاب (router) نام دارند عبور می کنند در داخل هر مسیریاب جدولی قرار دارد تا بهترین و کوتاه ترین مسیر بعدی تا مقصد از طریق ان مشخص می شود، بنابراین بسته های اطلاعاتی حین گذر از مسیریاب ها با توجه به محتویات این جدول عبور داده می شوند.
روشی به نام Ant Colony Routering (ACR) پیشنهاد شده که براساس ایده کلونی مورچه به بهینه سازی جداول می پردازیم و درواقع به هر مسیری با توجه به بهینگی ان امتیاز می دهیم
استفاده از ACR به این منظور دارای برتری نسبت به سایر روش هاست که با طبیعت دیمنامیک شبکه سازگاری دارد، زیرا به عنوان مثال ممکن است مسیری پرترافیک شود یا حتی مسیریابی از کار افتاده باشد و به دلیل انعطاف پذیری که ACO در برابر این تغییرات دارد همواره بهترین راه حل بعدی را در دسترس قرار می دهد
ادامه
لیست مقالات فارسی مربوط به ACO
منابع و ماخذ
بهینه سازی توسط کلونی مورچگان تالیف دکتر مهدی تقوی و دو تن دیگر
http://forum.patoghu.com
http://studentkhorramabad.blogfa.com
http://abbastaieban.blogfa.com
افق آینده و یک سوال کلیدی …
توجه به کولونی مورچه ها و نیز استفاده وسیع ازآن بیشتر ناشی از توجه خاصی بوده که پیشتر، بیولوژیست ها به کولونی مورچه ها داشته اند. چه بسا سیستم های دیگر طبیعی نیز باشند که تاکنون مورد مطالعه قرار نگرفته اند یا اگرهم مطالعه شده اند با دید معطوف به هوشمندی و بهینه سازی نبوده است.
بنابراین می توان تصورکرد که در سال های آینده روش های زیاد دیگری جهت بهینه سازی و نیز کنترل هوشمند با استفاده از سیستم های طبیعی پیشنهاد شوند . تا به حال به کرات به مزایای این نوع هوشمندی اشاره کرده ایم اما اکنون بار دیگر تاکید می کنیم که این نوع از هوشمندی علاوه بر تمامی مزایای مهندسی، یک مزیت عمده و اصلی دارد: تمامی این روش ها قابلیت تعمق زیستی دارند(biologically plausible) به این معنی که طبیعت آنها را در طی میلیون ها سال به عنوان روش بهینه انتخاب کرده است. پس این سوال پیش می آید که آیا ما می توانیم روشی بهتر از روش های طبیعت ارائه دهیم؟
الگوریتم کلونی زنبور عسل
ABC
چندین الگوریتم اکتشافی جدید برای حل مسایل بهینه سازی عددی و توابع ترکیبی توسعه یافته اند. این الگوریتم ها می توانند به گروههای مختلف طبقه بندی شوند با توجه به ضوابطی که در نظر گرفته شده: مانند بر اساس جمعیت ، مبتنی بر تکرار شونده ، تصادفی ، قطعی ، و غیره. در حالی که الگوریتم با یک مجموعه راه حل هاکار میکند و در جهت بهبود آنها تلاش می کنند که مبتنی بر جمعیت نامیده می شوند ، یکی از کاربرد تکرار های چندگانه برای پیداکردن راه حل مطلوب که به عنوان الگوریتم تکرار شونده نام گذاری شده است. اگر یک الگوریتم یک قانون احتمالی را برای بهبود راه حل بکار بگیرد سپس آن را احتمال یا اتفاقی نامیده میشود. یکی دیگر از طبقه بندی را می توان بسته به ماهیت پدیده توسط الگوریتم شبیه سازی کرد
الگوریتم کلونی زنبور عسل (ABC)
یک کلونی زنبور عسل می تواند در مسافت زیادی و نیز در جهت های گوناگون پخش شود تا از منابع غذایی بهره برداری کند. قطعات گلدار با مقادیر زیادی نکتار و گرده که با تلاشی کم قابل جمع آوری است، به وسیله¬ی تعداد زیادی زنبور بازدید می شود؛ به طوری که قطعاتی از زمین که گرده یا نکتار کمتری دارد، تعداد کمتری زنبور را جلب می کند. پروسهٔ جستجوی غذای یک کلونی به وسیلهٔ زنبورهای دیده¬بان آغاز می شود که برای جستجوی گلزارهای امید بخش (دارای امید بالا برای وجود نکتار یا گرده) فرستاده می شوند
شرح الگوریتم زنبور عسل
. زنبورهای دیده بان به صورت کتره ای از گلزاری به گلزار دیگر حرکت می کنند. در طول فصل برداشت محصول (گل دهی)، کلونی با آماده نگه داشتن تعدادی از جمعیت کلونی به عنوان زنبور دیده بان به جستجوی خود ادامه می دهند. هنگامی که جستجوی تمام گلزارها پایان یافت، هر زنبور دیده بان، بالای گلزاری که اندوختهٔ کیفی مطمئنی از نکتار و گرده دارد، رقص خاصی را اجرا می کند. این رقص که به نام رقص چرخشی شناخته می شود، اطلاعات مربوط به جهت تکه گلزار (نسبت به کندو)، فاصله تا گلزار و کیفیت گلزار را به زنبورهای دیگر انتقال می دهد. این اطلاعات زنبورهای اضافی و پیرو را به سوی گلزار می فرستد. بیش تر زنبورهای پیرو به سوی گلزارهایی می¬روند که امید بخش¬تر هستند و امید بیش تری برای یافتن نکتار و گرده در آن ها وجود دارد. وقتی همهٔ زنبورها به سمت ناحیه ای مشابه بروند، دوباره به صورت تصادفی و به علت محدوده¬ی رقصشان در پیرامون گلزار پراکنده می شوند تا به موجب این کار سرانجام نه یک گلزار، بلکه بهترین گل¬های موجود درون آن تعیین موقعیت شوند.
. الگوریتم زنبور عسل هر نقطه را در فضای پارامتری – متشکل از پاسخ های ممکن- به عنوان منبع غذا تحت بررسی قرار می دهد. زنبورهای دیده بان – کارگزاران شبیه سازی شده – به صورت تصادفی فضای پاسخ¬ها را ساده می¬کنند و به وسیله¬ی تابع شایستگی کیفیت موقعیت¬های بازدید شده را گزارش می-دهند. جواب های ساده شده رتبه بندی می شوند و دیگر زنبورها نیروهای تازه¬ای هستند که فضای پاسخ ها را در پیرامون خود برای یافتن بالاترین رتبه محل ها جستجو می کنند که گلزار نامیده می شود. الگوریتم به صورت گزینشی دیگر گلزارها را برای یافتن نقطه¬ی بیشینه¬ی تابع شایستگی جستجو می کند
* میزان کردن کنترل کننده های منطق فازی برای ربات های ورزشکارالگوریتم زنبور شامل گروهی مبتنی بر الگوریتم جستجو است که اولین بار در سال 2005 توسعه یافت ؛ این الگوریتم شبیه سازی رفتار جستجوی غذای گروههای زنبور عسل است. در نسخه ابتدایی این الگوریتم، الگوریتم نوعی از جستجوی محلی انجام می دهد که با جستجوی کتره ای (Random) ترکیب شده و می تواند برای بهینه سازی ترکیبی {زمانی که بخواهیم چند متغیر را همزمان بهینه کنیم.}یا بهینه سازی تابعی به کار رود.
یک کلونی زنبور عسل می تواند در مسافت زیادی و نیز در جهت های گوناگون پخش شود تا از منابع غذایی بهره برداری کند.
قطعات گلدار با مقادیر زیادی نکتار و گرده که با تلاشی کم قابل جمع آوری است،به وسیلهی تعداد زیادی زنبور بازدید می شود؛ به طوری که قطعاتی از زمین که گرده یا نکتار کمتری دارد، تعداد کمتری زنبور را جلب می کند.
جستجوی غذا در طبیعت
الگوریتم زنبور هر نقطه را در فضای پارامتری_ متشکل از پاسخ های ممکن_به عنوان منبع غذا تحت بررسی قرار می دهد.”زنبور های دیده بان”_ کارگزاران شبیه سازی شده _به صورت کتره ای (Random) فضای پاسخ ها را ساده می کنند و به وسیله ی تابع شایستگی کیفیت موقعیت های بازدید شده را گزار ش می دهند. جواب های ساده شده رتبه بندی می شوند، و دیگر “زنبورها” نیروهای تازه ای هستند که فضای پاسخ ها را در پیرامون خود برای یافتن بالا ترین رتبه محل ها جستجو می کنند(که “گلزار” نامیده می شود) الگوریتم به صورت گزینشی دیگر گلزار ها را برای یافتن نقطه ی بیشینه ی تابع شایستگی جستجو می کند.
آموزش شبکه عصبی برای الگو شناسی
زمان بندی کارها برای ماشین های تولیدی
دسته بندی اطلاعات
بهینه سازی طراحی اجزای مکانیکی
بهینه سازی چند گانه
برخی کاربرد های الگوریتم زنبور در مهندسی:
الگوریتم زنبور شامل گروهی مبتنی بر الگوریتم جستجو است که اولین بار در سال 2005 توسعه یافت ؛ این الگوریتم شبیه سازی رفتار جستجوی غذای گروه های زنبور عسل است. در نسخه ابتدایی این الگوریتم نوعی از جستجوی محلی انجام می دهد که با جستجوی کتره ای{Random } ترکیب شده و می تواند برای بهینه سازی ترکیبی {زمانی که بخواهیم چند متغیر را همزمان بهینه کنیم.}یا بهینه سازی تابعی به کار رود.
یک کلونی زنبور عسل می تواند در مسافت زیادی و نیز در جهت های گوناگون پخش شود تا از منابع غذایی بهره برداری کند.
قطعات گلدار با مقادیر زیادی نکتار و گرده که با تلاشی کم قابل جمع آوری است،به وسیله ی تعداد زیادی زنبور بازدید می شود؛ به طوری که قطعاتی از زمین که گرده یا نکتار کمتری دارد، تعداد کمتری زنبور را جلب می کند.
الگوریتم های الهام گرفته شده از کلونی زنبورها
دراین جا میخواستم و چندتا پست دیگه کمی درباره ی پروژه ی هوش مصنوعی خودم توضیح بدم که تونستم این الگوریتم رو پیاده سازی کنم و اگه کسی کمک خواست تا حدی که بتونم کمکش می کنم.
این متن مقاله ی خودمه که ارائه دادم :
تلاشهای زیادی برای مدل کردن رفتارهای خاص و هوشمندانه تجمع زنبورهای عسل انجام گرفته است Tereshko و Loengarov کلونی زنبور را به عنوان یک سیستم پویا درنظر گرفتند که از محیط اطراف اطلاعات جمع اوری میکند و رفتار خود را براساس این اطلاعات بدست آمده تنظیم می نماید. آنها یک ایده روباتی با توجه به رفتار کاوشی زنبورها مطرح کردند. غالبا این روباتها به صورت فیزیکی و عملکردی یکسان هستند. در نتیجه هر روبات میتواند به طور تصادفی جایگزین دیگر روباتها گردد. تجمع، قابلیت تحمل خطا را دارد. با رخ دادن خطا در یک عامل کار کل سیستم مختل نخواهد شد
. روباتهای مجزا، مانند حشرات، دارای قابلیتها وتواناییهای محدودی هستند. همچنین دانش محدودی از محیط دارند. به عبارتی دیگر تجمع)ازدحام)، هوش جمعی همکارانه را بهبود میدهد. همچنین این آزمایش نشان میدهد که روباتهای حشره مانند در انجام وظایف حقیقی روباتها، موفق هستند. به علاوه آنها یک مدل کمینه از از رفتار کاوشگرانه زنبورها ارائه داند. این مدل شامل سه مولفه مهم میباشد: 1)منبع غذایی ۲(زنبورهای کارگر ۳(زنبورهای غیرکارگر. این مدل دو نوع رفتار را دربرمیگیرد: سربازگیری برای یک منبع شهد و ترک منبع. Teodorovic پیشنهاد داد تا از هوش جمعی زنبورها در توسعه و بهبود سیستمهای مصنوعی با هدف حل مسائل پیچیده در حمل و نقل و ترافیک استفاده شود، همچنین او الگوریتم BCO (Bee Colony Optimization)را ارائه کرد که قادر است مسائل ترکیبی قطعی را همانند مسائل ترکیبی به خوبی حل نماید
بسیاری از مسائل به روش های معمول ریاضی قابل حل نیستند و یا حل کردن آنها زمان بسیار زیادی را می طلبد. در این نوع از مسائل ما به دنبال پیدا کردن یک نقطه بهینه در مسئله هستیم که اصطلاحا به آن نقطه، نقطه بهینه می گوییم. نقطه بهینه زمانی بدست می آید که ما کمترین خطا در مسئله را داشته باشیم. الگوریتم هایی تصادفی مانند الگوریتم ژنتیک و الگوریتم های تکاملی برای حل مسائل بهینه سازی استفاده می شوند.
یکی دیگر از روش های حل مسائل بهینه سازی الگوریتم های هوش ازدحامی است که الگوریتم زنبور عسل از جمله این الگوریتم ها است. الگوریتم زنبور (Bee Algorithm) یک الگوریتم گروهی مبتنی بر جستجو است که در سال ۲۰۰۵ میلادی ابداع شده است.این الگوریتم شبیه سازی رفتار جستجوی غذای گروه های زنبور عسل است. در نسخه ابتدایی این الگوریتم، الگوریتم نوعی از جستجوی محلی انجام می دهد که با جستجوی تصادفی کتره¬¬ا ترکیب شده و می تواند برای بهینه سازی ترکیبی یا بهینه سازی تابعی استفاده شود.
میزان کردن کنترل کننده های منطق فازی برای ربات های ورزشکار
Artificial Bee Colony Algorithm
الگوریتم کلونی زنبورعسل مصنوعی
Reference:
Dervis Karaboga, An Idea Based On Honey Bee Swarm for Numerical Optimization, Technical Report-TR06,Erciyes University, Engineering Faculty, Computer Engineering Department 2005.
وجود ویژگی های هوش جمعی در زنبورها
-خودسازمانده
– دنبال کردن منابع غذایی بهتر توسط زنبور های بیشتر
ترک منبع غذایی متروک شده
جستجوی منبع غذای بهتر
– تقسیم کار
– مشخص کردن جهت، فاصله، کیفیت و کمیت منبع یافت شده
الگوریتم کلونی زنبورعسل مصنوعی
الگوریتم کلونی زنبورعسل مصنوعی
الگوریتم ارائه شده توسط Karaboga در سال 2005
مبتنی بر رفتار کاوشی زنبور عسل در یافتن منابع غذایی
مناسب برای حل مسائل بهینه سازی چند حالته و چند بعدی
الگوریتم کلونی زنبورعسل مصنوعی
فرآیند های انتخاب در الگوریتم کلونی زنبور عسل مصنوعی
فرآیند انتخاب سراسری
فرآیند انتخاب محلی توسط زنبور های کارگر
فرآیند انتخاب محلی توسط زنبورهای ناظر
فرآیند انتخاب تصادفی توسط زنبور پیشاهنگ
الگوریتم کلونی زنبورعسل مصنوعی
الگوریتم کلونی زنبورعسل مصنوعی
مقداردهی اولیه به منابع غذایی
ابتدا منابع غذایی، یا پاسخ هایی اولیه مساله به صورت تصافی از طریق معادله 1، مقدار دهی اولیه می شوند.
(1)
الگوریتم کلونی زنبورعسل مصنوعی
زنبورهای کارگر به سمت منابع غذایی حرکت می کنند.
منابع غذایی همان موقعیت زنبورها در فضای مساله است.
الگوریتم کلونی زنبورعسل مصنوعی
هر زنبور کارگر، به طور تصادفی یک همسایه انتخاب می کند و از طریق معادله 2، به سمت آن حرکت می کند.
(2)
الگوریتم کلونی زنبورعسل مصنوعی
الگوریتم کلونی زنبورعسل مصنوعی
الگوریتم کلونی زنبورعسل مصنوعی
حرکت زنبورهای ناظر به منابع غذایی با احتمال محاسبه شده از طریق چرخ رولت با استفاده از معادلات زیر و تعیین محله های جدید:
حرکت زنبورهای ناظر
الگوریتم کلونی زنبورعسل مصنوعی
(3)
(4)
زنبورهای پیشاهنگ آن ناحیه هایی که از نظر شهد نامطلوب شناسایی شدند، ترک و به تصادف ناحیه های دیگری را انتخاب می کنند. درصورتی که یک منبع غذایی بهتر پس از رسیدن شاخص محاکمه به حد تعیین شده یافت نشود، منبع غذایی جدیدی توسط زنبورهای پیشاهنگ به صورت تصادفی با استفاده از معادله زیر مقداردهی می گردد:
الگوریتم کلونی زنبورعسل مصنوعی
The pseudo code of the ABC algorithm
الگوریتم کلونی زنبورعسل مصنوعی
GABC,
Best-so-far ABC, qABC
چند الگوریتم بهینه شده کلونی زنبورعسل مصنوعی
Reference:
1- G. Zhu, S. Kwong, Gbest-guided artificial bee colony algorithm for numerical function optimization, Applied Mathematics & Compution. 217 (2010) 3166–3173.
2- A. Banharnsakun, T. Achalakul, B. Sirinaovakul, The best-so-far selection in Artificial Bee Colony algorithm, Applied Soft Computing. 11 (2011) 2888–2901.
3- D. Karaboga, B. Gorkemli, A quick artificial bee colony (qABC) algorithm and its performance on optimization problems, Applied Soft Computing. 23 (2014) 227–238.
الگوریتم Gbest- guided ABC
در فاز اول و دوم الگوریتم، از معادله زیر به جای معادله 2 در الگوریتم کلونی زنبور عسل مصنوعی استفاده می کند.
با توجه به الگوریتم ازدحام ذرات، بهترین موقعیت بدست آمده توسط گروه ، yj، محاسبه می گردد.
الگوریتم Best-so-far ABC
در فاز اول از همان معادله 2 و در فاز دوم الگوریتم از معادله زیر به جای معادله 2 در الگوریتم کلونی زنبور عسل مصنوعی استفاده می کند.
بهترین موقعیت بدست آمده توسط زنبورها در پایان فاز اول، محاسبه می گردد.
الگوریتم Best-so-far ABC
شرط جایگزینی راه حل بهتر بر اساس مقدار تابع هدف است.
الگوریتم Best-so-far ABC
شرط جایگزینی راه حل بهتر بر اساس مقدار تابع هدف است زیرا:
الگوریتم Best-so-far ABC
در فاز سوم از رابطه زیر استفاده می کند و در صورتی Vij جایگرین Xij می گردد که از نظر تابع هدف بهتر باشد. اگر نباشد مقدار شاخص محاکمه یک واحد اضافه می گردد.
الگوریتم qABC
استفاده از یک شعاع همسایگیr برای بدست آوردن همسایه مناسب، :mdm میانگین فاصله زنبورها تا زنبور m
Parallel Artificial Bee Colony
(PABC)
الگوریتم کلونی زنبورعسل مصنوعی موازی
Reference:
Harikrishna Narasimhan , Parallel Artificial Bee Colony (PABC) Algorithm, World Congress on Nature & Biologically Inspired Computing, NaBIC, 2009.
هدف در این الگوریتم:
پیاده سازی الگوریتم کلونی زنبورعسل مصنوعی به صورت موازی
عدم تاثیر گذاری بر روی جواب نهایی الگوریتم
افزایش سرعت پاسخ گویی
توزیع زنبورها روی پردازنده های مختلف و بهبود راه حل های پیشنهادی به صورت مستقل
جستجوی همسایگی
محاسبه ی احتمال
استفاده از یک حافظه اشتراکی
الگوریتم کلونی زنبورعسل موازی
الگوریتم کلونی زنبورعسل موازی
(5)
بهبود راه حل موجود در حافظه محلی با انتخاب تصادفی یک راه حل از حافظه ی اشتراکی در جستجوی همسایگی
(6)
انتخاب یک راه حل توسط زنبورهای ناظر از حافظه محلی براساس رابطه احتمالی زیر:
(7)
الگوریتم کلونی زنبورعسل موازی
The pseudo code of the Parallel ABC algorithm
Reference:
Mustafa Servet Kiran, The continuous artificial bee colony algorithm for binary optimization, Applied Soft Computing 33 (2015) 15–23.
D. Jia, X. Duan, M.K. Khan, Binary Artificial Bee Colony optimization using bitwise operation, Computer and Industrial Engineering. 76 (2014) 360–365.
حل مسائل ناپیوسته و دودویی توسط الگوریتم کلونی زنبور عسل مصنوعی
الگوریتم اول:
The continuous artificial bee colony algorithm for binary optimization
الگوریتم اول:
1. Initialization
a. Set N as the number of food source s
b. Set trial for each food source.
c. Set the limit control para mete r value
d. Set the termination condition
e. Set D as dimensionality of the problem.
f. Create food source s (N x D) using Eq. 1
g. Convert continuous solutions to binary solutions using Eq. 6
h. Evaluate the fitness of the solutions by using objective function specific for the problem and Eq. 2
i. Memorize the best solution
حل مسائل دودویی
حل مسائل دودویی
2. Employed Bee Phase
a. For each employed bee
i. Select a neighbor solution randomly.
ii. Produce a candidate food source by using Eq. 3
iii. Convert to continuous solution to binary solution using Eq. 6
iv. Evaluate the fitness of the solution by using objective function specific for the problem and Eq. 2
v. If fitness of the new solution is better than old one, memorize the new solution and reset trial of this food source; otherwise increase trial by 1
حل مسائل دودویی
3. Onlooker Bee Phase
a. Calculate designation probability of each food source by using Eq. 4
b. For each onlooker bee
i. Select a food source by using designation probability.
ii. Select a food source randomly.
iii. Produce a candidate food source by using Eq. 3
iv. Convert to continuous solution to binary solution using Eq. 6
v. Evaluate the fitness of the solution by using objective function specific for the problem and Eq. 2
vi. If fitness of the new solution is better than old one, memorize the new solution and reset trial of this food source; otherwise increase trial by 1
حل مسائل دودویی
4. Scout Bee Phase
a. Fix the trial with maximum content
b. If this content is higher than limit,
i. Remove this solution from the population
ii. Create a new solution by using Eq. 1
iii. Convert continuous solution to binary solution using Eq. 6
iv. Evaluate the fitness of the solution by using objective function specific for the problem and Eq. 2
v. Reset trial of new solution.
حل مسائل دودویی
5. Termination
a. If the best solution of the population is better previous best solution, memorize the new best solution
b. If the termination condition is met, report the best solution; otherwise go to Employed Bee Phase
الگوریتم دوم:
Binary Artificial Bee Colony optimization using bitwise operation
ابتدا منابع غذایی، یا پاسخ های اولیه مساله به صورت تصادفی از طریق معادله زیر، مقدار دهی اولیه با صفر و یک می شوند.
حل مسائل دودویی
Binary Artificial Bee Colony optimization using bitwise operation
حل مسائل دودویی
Binary Artificial Bee Colony optimization using bitwise operation
در فاز اول و دوم الگوریتم، از معادله زیر به جای معادله 2 در الگوریتم کلونی زنبور عسل مصنوعی استفاده می کند.
φ از رابطه زیر تبدیل به صفر و یک می گردد:
http://www.prozhe.com
http://ww1.nayabprojects.com/?sub1
https://fa.wikipedia.org/
http://faraebtekari.ir
http://www.pcporoje.com/filedata/815636.pdf
https://faradars.org/courses/mvrabc9107-artificial-bee-colony-in-matlab-video-tutorial
http://isiarticles.com/topic/204
منابع
منابع
wikipedia.org
M. Dorigo & L.M Gambardella “Ant algorithm for Discrete optimization ”
END OF ANT COLONY OPTIMIZATION
پایان
با تشکر از توجه شما