الگوريتم مورچه Ant colony optimization

جوجو13

اخراجی موقت
الگوريتم کلوني مورچه براي اولين بار توسط دوريگو (Dorigo) و همکارانش به عنوان يک راه حل چند عامله (Multi Agent) براي مسائل مشکل بهينه سازي مثل فروشنده دوره گرد (TSP :Traveling Sales Person) ارائه شد. عامل هوشند(Intelligent Agent) موجودي است که از طريق حسگر ها قادر به درک پيرامون خود بوده و از طريق تاثير گذارنده ها مي تواند روي محيط تاثير بگذارد. الگوريتم کلوني مورچه الهام گرفته شده از مطالعات و مشاهدات روي کلوني مورچه هاست. اين مطالعات نشان داده که مورچه ها حشراتي اجتماعي هستند که در کلوني ها زندگي مي کنند و رفتار آنها بيشتر در جهت بقاء کلوني است تا درجهت بقاء يک جزء از آن. يکي از مهمترين و جالبترين رفتار مورچه ها، رفتار آنها براي يافتن غذا است و بويژه چگونگي پيدا کردن کوتاهترين مسير ميان منابع غذايي و آشيانه. اين نوع رفتار مورچه ها داراي نوعي هوشمندي توده اي است که اخيرا مورد توجه دانشمندان قرار گرفته است.بايد تفاوت هوشمندي توده اي(کلوني) و هوشمندي اجتماعي را روشن کنيم. در هوشمندي اجتماعي عناصر ميزاني از هوشمندي را دارا هستند. بعنوان مثال در فرآيند ساخت ساختمان توسط انسان، زماني که به يک کارگر گفته ميشود تا يک توده آجر را جابجا کند، آنقدر هوشمند هست تا بداند براي اينکار بايد از فرغون استفاده کند نه مثلا بيل!!! نکته ديگر تفاوت سطح هوشمندي افراد اين جامعه است. مثلا هوشمندي لازم براي فرد معمار با يک کارگر ساده متفاوت است. در هوشمندي توده اي عناصر رفتاري تصادفي دارند و بين آن ها هيچ نوع ارتباط مستقيمي وجود ندارد و آنها تنها بصورت غير مستقيم و با استفاده از نشانه ها با يکديگر در تماس هستند. مثالي در اين مورد رفتار موريانه ها در لانه سازي است. جهت علاقه مند شدن شما به اين رفتار موريانه ها وتفاوت هوشمندي توده اي و اجتماعي توضيحاتي را ارائه مي دهم : فرآيند ساخت لانه توسط موريانه ها مورد توجه دانشمندي فرانسوي به نام گرس قرار گرفت. موريانه ها براي ساخت لانه سه فعاليت مشخص از خود بروز مي دهند. در ابتدا صدها موريانه به صورت تصادفي به اين طرف و آن طرف حرکت مي کنند. هر موريانه به محض رسيدن به فضايي که کمي بالاتر از سطح زمين قرار دارد شروع به ترشح بزاق مي کنند و خاک را به بزاق خود آغشته مي کنند. به اين ترتيب گلوله هاي کوچک خاکي با بزاق خود درست مي کنند. عليرغم خصلت کاملا تصادفي اين رفتار، نتيجه تا حدي منظم است. در پايان اين مرحله در منطقه اي محدود تپه هاي بسيار کوچک مينياتوري از اين گلوله هاي خاکي آغشته به بزاق شکل مي گيرد. پس از اين، همه تپه هاي مينياتوري باعث مي شوند تا موريانه ها رفتار ديگري از خود بروز دهند. در واقع اين تپه ها به صورت نوعي نشانه براي موريانه ها عمل مي کنند. هر موريانه به محض رسيدن به اين تپه ها با انرژي بسيار بالايي شروع به توليد گلوله هاي خاکي با بزاق خود مي کند. اين کار باعث تبديل شدن تپه هاي مينياتوري به نوعي ستون مي شود. اين رفتار ادامه مي يابد تا زماني که ارتفاع هر ستون به حد معيني برسد. در اين صورت موريانه ها رفتار سومي از خود نشان مي دهند. اگر در نزديکي ستون فعلي ستون ديگيري نباشد بلافاصله آن ستون را رها مي کنند در غير اين صورت يعني در حالتي که در نزديکي اين ستون تعداد قابل ملاحظه اي ستون ديگر باشد، موريانه ها شروع به وصل کردن ستونها و ساختن لانه مي کنند. تفاوتهاي هوشمندي اجتماعي انسان با هوشمندي توده اي موريانه را در همين رفتار ساخت لانه مي توان مشاهده کرد. کارگران ساختماني کاملا بر اساس يک طرح از پيش تعيين شده عمل مي کنند، در حالي که رفتار اوليه موريانه ها کاملا تصادفي است. علاوه بر اين ارتياط مابين کارگران سختماني مستقيم و از طريق کلمات و ... است ولي بين موريانه ها هيچ نوع ارتباط مستقيمي وجود ندارد و آنها تنها بصورت غير مستقيم و از طريق نشانه ها با يکديگر در تماس اند. گرس نام اين رفتار را Stigmergie گذاشت، به معني رفتاري که هماهنگي مابين موجودات را تنها از طريق تغييرات ايجاد شده در محيط ممکن مي سازد.
 

جوجو13

اخراجی موقت
نکته ديگر مسئله تبخير شدن فرومون بر جاي گذاشته شده است. برفرض اگر مانع در مسير AB برداشته شود و فرومون تبخير نشود مورچه ها همان مسير قبلي را طي خواهند کرد. ولي در حقيقت اين طور نيست. تبخير شدن فرومون و احتمال به مورچه ها امکان پيدا کردن مسير کوتاهتر جديد را مي دهند.
1-1


2-1

3-1
4-1
مزيتهاي ACO :
همانطور که گقته شد «تبخير شدن فرومون» و «احتمال-تصادف» به مورچه ها امکان پيدا کردن کوتاهترين مسير را مي دهند. اين دو ويژگي باعث ايجاد انعطاف در حل هرگونه مسئله بهينه سازي مي شوند. مثلا در گراف شهرهاي مسئله فروشنده دوره گرد، اگر يکي از يالها (يا گره ها) حذف شود الگوريتم اين توانايي را دارد تا به سرعت مسير بهينه را با توجه به شرايط جديد پيدا کند. به اين ترتيب که اگر يال (يا گره اي) حذف شود ديگر لازم نيست که الگوريتم از ابتدا مسئله را حل کند بلکه از جايي که مسئله حل شده تا محل حذف يال (يا گره) هنوز بهترين مسير را داريم، از اين به بعد مورچه ها مي توانند پس از مدت کوتاهي مسير بهينه(کوتاهترين) را بيابند.

کاربردهاي ACO :
از کاربردهاي ACO مي توان به بهينه کردن هر مسئله اي که نياز به يافتن کوتاهترين مسير دارد ، اشاره نمود :
1. مسير يابي داخل شهري و بين شهري

2. مسير يابي بين پست هاي شبکه هاي توزيع برق ولتاژ بالا
3. مسير يابي شبکه هاي کامپيوتري

مسير يابي شبکه هاي کامپيوتري با استفاده از ACO :
در ابتدا مقدمه اي از نحوه مسير يابي در شبکه هاي کامپيوتري را توضيح خواهيم داد :
اطلاعات بر روي شبکه بصورت بسته هاي اطلاعاتي کوچکي (Packet) منتقل مي شوند. هر يک از اين بسته ها بر روي شبکه در طي مسير از مبدا تا مقصد بايد از گره هاي زيادي که مسيرياب (Router) نام دارند عبور مي کنند. در داخل هر مسيرياب جدولي قرار دارد تا بهترين و کوتاهترين مسير بعدي تا مقصد از طريق آن مشخص مي شود، بنابر اين بسته هاي اطلاعاتي حين گذر از مسيرياب ها با توجه به محتويات اين جداول عبور داده مي شوند.
روشي بنام ACR : Ant Colony Routering پيشنهاد شده که بر اساس ايده کلوني مورچه به بهينه سازي جداول مي پردازيد و در واقع به هر مسيري با توجه به بهينگي آن امتياز مي دهد. استفاده از ACR به اين منظور داراي برتري نسبت به ساير روش هاست که با طبيعت ديناميک شبکه سازگاري دارد، زيرا به عنوان مثال ممکن است مسيري پر ترافيک شود يا حتي مسير يابي (Router) از کار افتاده باشد و بدليل انعطاف پذيري که ACO در برابر اين تغييرات دارد همواره بهترين راه حل بعدي را در دسترس قرار مي دهد.
 

bardiajoon

عضو جدید
يك ناگفته :

الگوريتم مورچه به طور همزمان در برلين توسط شخصي با نام روربت ديويدسون ابداع شد كه با مطالعه روش هاي سارختاري اثبات و تحليل اون به اين تيجه رسيدم كه وي در اين زمينه پيشگام تررررر بوده است!!
 

bahman.eng

عضو جدید
درخواست راهنمایی

درخواست راهنمایی

سلام مهندسان عزیز
میخوام الگوریتم کلونی مورچه رو توی شبکه های کامپیوتری پیاده سازی بکنم
میتونید راهنماییم کنید؟
 

Macboy

عضو جدید
Ant Colony Optimization – Bradford Book

Ant Colony Optimization – Bradford Book

Ant Colony Optimization – Bradford Book





Ant Colony Optimization

نام: Ant Colony Optimization
نویسنده: Marco Dorigo
ناشر: The MIT Press
سال انتشار: جولای ۲۰۰۴
فرمت: PDF
تعداد صفحات: ۳۱۹
حجم: ۱MB
الگوریتم بهینه سازی مورچه یا Ant colony optimization چیست؟

الگوریتم کلونی مورچه برای اولین بار توسط دوریگو (Dorigo) و همکارانش به عنوان یک راه حل چند عامله (Multi Agent) برای مسائل مشکل بهینه سازی مثل فروشنده دوره گرد (TSP :Traveling Sales Person) ارائه شد. عامل هوشند(Intelligent Agent) موجودی است که از طریق حسگر ها قادر به درک پیرامون خود بوده و از طریق تاثیر گذارنده ها می تواند روی محیط تاثیر بگذارد. الگوریتم کلونی مورچه الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچه هاست. این مطالعات نشان داده که مورچه ها حشراتی اجتماعی هستند که در کلونی ها زندگی می کنند و رفتار آنها بیشتر در جهت بقاء کلونی است تا درجهت بقاء یک جزء از آن. یکی از مهمترین و جالبترین رفتار مورچه ها، رفتار آنها برای یافتن غذا است و بویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه. این نوع رفتار مورچه ها دارای نوعی هوشمندی توده ای است که اخیرا مورد توجه دانشمندان قرار گرفته است.باید تفاوت هوشمندی توده ای(کلونی) و هوشمندی اجتماعی را روشن کنیم. در هوشمندی اجتماعی عناصر میزانی از هوشمندی را دارا هستند. بعنوان مثال در فرآیند ساخت ساختمان توسط انسان، زمانی که به یک کارگر گفته میشود تا یک توده آجر را جابجا کند، آنقدر هوشمند هست تا بداند برای اینکار باید از فرغون استفاده کند نه مثلا بیل!!! نکته دیگر تفاوت سطح هوشمندی افراد این جامعه است. مثلا هوشمندی لازم برای فرد معمار با یک کارگر ساده متفاوت است. در هوشمندی توده ای عناصر رفتاری تصادفی دارند و بین آن ها هیچ نوع ارتباط مستقیمی وجود ندارد و آنها تنها بصورت غیر مستقیم و با استفاده از نشانه ها با یکدیگر در تماس هستند. مثالی در این مورد رفتار موریانه ها در لانه سازی است. جهت علاقه مند شدن شما به این رفتار موریانه ها وتفاوت هوشمندی توده ای و اجتماعی توضیحاتی را ارائه می دهم : فرآیند ساخت لانه توسط موریانه ها مورد توجه دانشمندی فرانسوی به نام گرس قرار گرفت. موریانه ها برای ساخت لانه سه فعالیت مشخص از خود بروز می دهند. در ابتدا صدها موریانه به صورت تصادفی به این طرف و آن طرف حرکت می کنند. هر موریانه به محض رسیدن به فضایی که کمی بالاتر از سطح زمین قرار دارد شروع به ترشح بزاق می کنند و خاک را به بزاق خود آغشته می کنند. به این ترتیب گلوله های کوچک خاکی با بزاق خود درست می کنند. علیرغم خصلت کاملا تصادفی این رفتار، نتیجه تا حدی منظم است. در پایان این مرحله در منطقه ای محدود تپه های بسیار کوچک مینیاتوری از این گلوله های خاکی آغشته به بزاق شکل می گیرد. پس از این، همه تپه های مینیاتوری باعث می شوند تا موریانه ها رفتار دیگری از خود بروز دهند. در واقع این تپه ها به صورت نوعی نشانه برای موریانه ها عمل می کنند. هر موریانه به محض رسیدن به این تپه ها با انرژی بسیار بالایی شروع به تولید گلوله های خاکی با بزاق خود می کند. این کار باعث تبدیل شدن تپه های مینیاتوری به نوعی ستون می شود. این رفتار ادامه می یابد تا زمانی که ارتفاع هر ستون به حد معینی برسد. در این صورت موریانه ها رفتار سومی از خود نشان می دهند. اگر در نزدیکی ستون فعلی ستون دیگیری نباشد بلافاصله آن ستون را رها می کنند در غیر این صورت یعنی در حالتی که در نزدیکی این ستون تعداد قابل ملاحظه ای ستون دیگر باشد، موریانه ها شروع به وصل کردن ستونها و ساختن لانه می کنند. تفاوتهای هوشمندی اجتماعی انسان با هوشمندی توده ای موریانه را در همین رفتار ساخت لانه می توان مشاهده کرد. کارگران ساختمانی کاملا بر اساس یک طرح از پیش تعیین شده عمل می کنند، در حالی که رفتار اولیه موریانه ها کاملا تصادفی است. علاوه بر این ارتیاط مابین کارگران سختمانی مستقیم و از طریق کلمات و … است ولی بین موریانه ها هیچ نوع ارتباط مستقیمی وجود ندارد و آنها تنها بصورت غیر مستقیم و از طریق نشانه ها با یکدیگر در تماس اند. گرس نام این رفتار را Stigmergie گذاشت، به معنی رفتاری که هماهنگی مابین موجودات را تنها از طریق تغییرات ایجاد شده در محیط ممکن می سازد.
منبع: e-commerc.blogfa.com
معرفی کتاب
رفتار پیچیده و اجتماعی مورچه ها، در گذشته توسط زیست شناسان و حشره شناسان مورد مطالعه قرار گرفته می شد. امروزه از این دستاوردهای زیستی در زمینه بهینه سازی استفاده می شود و این زمینه به یکی از زمینه های مطالعاتی و تحقیقاتی دانشمندان علوم کامپیوتری، تبدیل شده است. توانایی الگوریتم بهینه سازی مورچه ها، در حل دسته های خاصی از مسائل، با نام مسائل کوتاه ترین مسیر، مطالعه و توسعه این الگوریتم را به یک امر جذاب و پرطرفدار در رشته علوم کامپیوتر تبدیل کرده است. در این کتاب منحصر به فرد، پیش زمینه های تئوری مربوط به الگوریتم های مورچه، در کنار کاربردهای عملی آن، به خوبی مورد بحث و بررسی قرار گرفته شده است. همچنین نسخه های مختلف الگوریتم مورچه به طور کامل تحلیل و بررسی شده اند و همه این مطالب در این کتاب قرار داده شده اند. این کتاب یک کتاب بسیار ارزشمند در زمینه اگوریتم مورچه می باشد و در آن فرمولها و تئوری های مختلفی همراه با گرافهای مختلف گنجانده شده است تا درک مطالب و مفاهیم برای خواننده آسان گردد.


http://dl.bookburger.net/dl/ebook/Engineering/IT/Ant-Colony-Optimization(www.BookBurger.net).rar
 

negin17h

مدیر تالارهای مهندسی کامپیوتر و رباتیکمتخصص #C
مدیر تالار
سلام کلا میتونین یه pdfکامل در مورد الگوریتم مورچه بزارین؟:que:

تو کتاب زیر یک بخش در این مورد هست. در کتب ژنتيک هم میتونی پیداش کنی :gol:

دانلود کتاب مروری بر برخی از روشهای بهینه سازی هوشمند


نام کتاب : مروری بر برخی از روشهای بهینه سازی هوشمند
نویسنده : حبیب مطیع قادر، شهریار لطفی، میر مهدی سید اسفهلان
زبان کتاب : پارسی
تعداد صفحه : ۲۱۹
قالب کتاب : PDF
حجم فایل : ۳,۷۱۱ کیلوبایت
توضیحات : وجود مسایل پیچیده علمی منجر میشود تا سراغ روشهای بهینه سازی رفته و مساله مورد نظر را به وسیله آنها حل کرد. با توجه به زمانبر بودن و پیچیدگی روشهای دقیق از روشهای بهینه سازی هوشمند استفاده میشود. تاکنون روشهای بهینه سازی متعددی معرفی شده اند که از مهم ترین آن ها میتوان به الگوریتم های تکاملی، الگوریتم تپه نوردی، الگوریتم شبیه ساز سرد کردن فلزات ، الگوریتم بهینه سازی انبوه ذرات، الگوریتم جستجوی ممنوع، الگوریتم بهینه سازی مورچه ها، خودکارهای یادگیر و غیره اشاره نمود. هدف از گردآوری این کتاب معرفی برخی از مهم ترین روش های بهینه سازی است . مسایل بهینه سازی در علوم مختلفی اعم از فنی و مهندسی، علوم پایه و انسانی کاربرد فراوانی دارند. به علت پر اهیمت بودن این موضوع تلاش نمودهایم تا در این راستا کتابی را گردآوری نماییم . در این کتاب شش روش مختلف بهینه سازی معرفی خواهیم کرد . این شش روش عبارتند از : الگوریتم ژنتیک، الگوریتم شبیه ساز سرد کردن فلزات، الگوریتم بهینه سازی مورچه ها، الگوریتم بهینه سازی انبوه ذرات، یادگیری تقویتی و خودکارهای یادگیر. این روشها از جمله روشهای پر طرفدار و پر کاربرد است که در بیشتر مسایل بهینه سازی مورد استفاده قرار گرفته اند. مخاطبین اصلی این کتاب کسانی هستند که در یکی از رشته های تحصیلی علوم کامپیوتر، ریاضیات کاربردی، الکترونیک، الکتروتکنیک، کنترل، صنایع ، مکاترونیک و علوم انسانی فعالیت دارند. البته این کتاب میتواند در رشته های مرتبط دیگری که به نحوی با مسایل بهینه سازی روبرو هستند نیز مورد استفاده قرار گیرد . از مخاطبین گرامی مشتاقانه درخواست میشود تا در صورت مشاهده هرگونه ایراد و کاستی در کتاب آن را از طریق آدرس پست الکترونیکی به نویسندگان اعلام نمایند.


منبع
دانلود کتاب

پسورد : www.aghazeh.com
 
آخرین ویرایش:

cs_84

عضو جدید
سلام دوستان
من الگوریتم مورچه رو برای حل مسئله TSp پیدا کردم.اما یه مشکلی دارم.
ببینید مسئله ای که میخوام با ACOحلش کنم پیدا کردن کوتاهترین مسیر بین دو نقطه در گراف هست.در واقع چند تا نقطه ی هدف وجود دارند اما من میخوام به نزدیکترین اونا برسم.اما تو کد نویسیش مشکل دارم.نمیدونم تعداد مورچه ها باید چند تا باشن؟!!!!از طرفی تعداد نقاطی که مورچه ازش عبور میکنه داره تو مسیرای مختلف تغییر میکنه.!!!خواهش میکنم یکی کمک کنه:confused:در واقع میخوام کاری که الگوریتم دایجسترا انجام میده رو با ACOانجام بدم.اگه کسی میتونه تابع هزینش چه شکلی نوشته میشه ممنونش میشم راهنماییم کنه
 

RoOzitA

عضو جدید
سلام بچه ها من مقاله پژوهشی انت کلونی رو به زبان اصلی میخام :( اما پیدا نمیکنم کسی میتونه کمکم کنه؟؟؟
 

upper of mind

عضو جدید
سلام دوستان
همه ی مقاله ها معمولاً از یه مقاله کپی گرفته شدن اگه می تونید یه برنامه ایی با سی شارپ یا سی پلاس پلاس ارائه بدید یا کد اصلی این الگوریتم رو اگه کسی واقعاً با این الگوریتم کار کرده به اشتراک بزاره.
با تشکر فراوان
 

upper of mind

عضو جدید
تعداد مورچه ها در یک مسئله

تعداد مورچه ها در یک مسئله

سلام دوستان
من الگوریتم مورچه رو برای حل مسئله TSp پیدا کردم.اما یه مشکلی دارم.
ببینید مسئله ای که میخوام با ACOحلش کنم پیدا کردن کوتاهترین مسیر بین دو نقطه در گراف هست.در واقع چند تا نقطه ی هدف وجود دارند اما من میخوام به نزدیکترین اونا برسم.اما تو کد نویسیش مشکل دارم.نمیدونم تعداد مورچه ها باید چند تا باشن؟!!!!از طرفی تعداد نقاطی که مورچه ازش عبور میکنه داره تو مسیرای مختلف تغییر میکنه.!!!خواهش میکنم یکی کمک کنه:confused:در واقع میخوام کاری که الگوریتم دایجسترا انجام میده رو با ACOانجام بدم.اگه کسی میتونه تابع هزینش چه شکلی نوشته میشه ممنونش میشم راهنماییم کنه
سلام دوست عزیز
راستش من خودم به طور کامل این الگوریتم رو درک نکردم ولی یه مقاله خوندم که در مورد برنامه زیزی دروس دانشگاهی بود.
اونجا نوشته بود که تعداد مورجه ها به اندازه تعداد رویدادها درنظر گرفته بشه فرضاً شما می توانید تعداد مورجه ها رو به اندازه تعداد گره های گرافتون تعیین کنید.
میشه گفت که اگه شما سه گره داشته باشید (1و2و3) و بخواهید از گره 1 به دو و سه بروید دو راه وجود دارد بنابراین حداقاً تعداد مورچه ها رو همان تعداد گره ها در نظر بگیرید
 

a1b2c3650917

عضو جدید
سلام
دو تا سوال داشتم ممنون میشم که لطفا به خاطر خدا کمکم
کنید
1-چگونه برای یک مسئله با دونوع متغییر گسسته وپیوسته به طور همزمان، می
توان دونوع متغییرگسسته و پیوسته را در الگوریتم ژنتیک متلب2014 شبیه
سازی کرد. (چون تا اونجاییکه من می دونم الگوریتم ژنتیک اورجینال متلب
فقط برای یک حالت طراحی شده است یا متغییر پیوسته یا متغییرگسسته می گیرد
حالا اگه شما هر دو تای این متغییرها را داشته باشید چگونه با آنها می
توان کار کرد ؟ واین مشکل را چگونه برطرف کرد؟
2- اگه یه برنامه ژنتیک در متلب رو آماده داشته باشیم وهیچ کدام از
option های( اندازه جمعیت اولیه- تعدادنسل-شرایط توقف و...) اون رو
ندانیم ایا راهی هست کهبه اونها پی بیریم ؟- (اجرتون با امام رضا (ع)
لطفا به این دوسوالم جواب بدید
تشکر ممنون میشم که کمکم کنید
 

Similar threads

بالا