مسیریابی بر اساس الگوریتم رفتار مورچه‌ها

![توضیح تصویر](https://boute.s3.amazonaws.com/181-Ant-individual-.png)
# 1.مقدمه:
در بسیاری از ابداعات بشر، انسان از موارد موجود در طبیعت الهام گرفته است. مطلبی که در این پروژه مد نظر قرار داده شده است استفاده از رفتار مورچه‌ها در طبیعت برای یافت غذا می‌باشد. مورچه‌ها برای به دست آوردن غذا رفتار جالبی از خود نشان می‌دهند. ان‌ها وقتی برای یافتن غذا از لانه خود بیرون می‌آیند به صورت اتفاقی در یک جهت به حرکت خود ادامه می‌دهند و پس از یافتن غذا در مسیر بازگشت به لانه ماده‌ای را بر روی زمین برجا می‌گذارند. در هنگام رسیدن به لانه بقیه مورچه‌ها متوجه می‌شوند که باید مسیر بو را دنبال کنند تا به غذا برسند. اما نکته‌ای که باعث شده است تا این رفتار مورچه‌ها الهام بخش استفاده از آن در زمینه علوم کامپیوتر شود قابلیت تشخیص شدت بو توسط مورچه‌هاست. بویی که مورچه‌ها از خود بر روی زمین باقی می‌گذارند ماده‌ای است که پس از گذشت مدتی بخار می‌شود و شدت آن کاهش می‌یابد. در این صورت هنگامی که مورچه می‌خواهد مسیری را دنبال کند با استفاده از قابلیت ذکر شده مسیری را انتخاب می‌کند که بوی باقی‌مانده بر روی آن بیشتر باشد. این مسیر به دلیل این‌که مسیر کوتاه‌تری برای رسیدن به غذاست بوی باقی‌مانده بر روی آن کمتر از بین می‌رود. لازم به ذکر است که مورچه‌ها پس از طی مسیر دوباره همان ماده را در راه ترشح می‌کنند تا از بین نرود. پس از گذشت مدتی مورچه‌ها کوتاه‌ترین مسیر را برای رسیدن به هدف خود می‌یابند.
![توضیح تصویر](https://boute.s3.amazonaws.com/181-ants-pests-argentine1.jpg)

این مسئله برای اولین بار با انجام آزمایشی اثبات شد که یک کلننی مورچه را در یک محفظه قرار دادند و دو راه برای رسیدن به غذا برای مورچه‌ها قرار دادند که یکی از آن‌ها کوتاه‌تر بود. با گذشت زمان رفت آمد مورچه‌ها تغییر کرد و به حالتی در آمد که همه از مسیر کوتاه‌تر می‌رفتند.[1]
.
![توضیح تصویر](http://www.scholarpedia.org/w/images/a/a6/DiffLengthDoubleBridge.png)
با مطالعه این رفتار مورچه‌ها برای اولین بار در سال 1991 آقای M. Dorigo مبدع ایجاد الگوریتم‌هایی شدند که امروزه به Ant Colony Optimization یا به طور مخفف ACO شناخته می‌شوند. [2]. ایشان از جمله افرادی بودند که رفتارهای حشرات را وارد دنیای کامپیوتر کردند. [12].  این الگوریتم‌ها با استفاده از شبیه‌سازی همین رفتار در مورچه‌ها قادر به حل تعدادی از مسائل ترکیبیاتی هستند. از جمله این مسائل می‌توان به فروشنده دوره‌گرد و مسئله کوله‌پشتی اشاره کرد. این دسته از الگوریتم‌ها کاربرد‌های بسیاری دارند که در بخش بعدیبه برخی از آن‌ها پرداخته شده است. هدف این پروژه این است که نوعی از ACO را برای حل مسئله **فروشنده دوره‌گرد** پیاده‌سازی کرد.[3]

# .
 **1.1.کاربردهای ACO:**
الگوریتم‌های ACO دارای انواع مختلفی هستند که به صورت جدول زیر می‌باشند.[4].
![توضیح تصویر](https://boute.s3.amazonaws.com/181-Applications.PNG)
در زیر برخی از کاربردهای این نوع الگوریتم‌ها به طور خاص به اختصار ذکر شده است.
**1.1.1.برنامه‌نویسی خودکار به وسیله ACO**:
	برنامه‌نویسی خودکار نوعی تکنیک جست‌و‌جو برای یافتن یک برنامه که یک مسئله را حل می‌کند می‌باشد.  شناخته شده ترین راه این نوع برنامه‌نویسی، برنامه‌نویسی ژنتیک می‌باشد که در آن از الگوریتم‌های ژنتیک برای یافتن برنامه استفاده می‌شود. در روشی جدیدتر از تکنیکی به نام Ant Colony Programming که به اختصار به آن ACP گفته می‌شود استفاده شده است. [5]. 
**2.1.1داده‌کاوی با استفاده از ACO**:
	تحقیقاتی بر روی داده‌کاوی با استفاده از ACO صورت گرفته است که یکی از آن‌ها داده‌کاوی برای کلاس‌بندی می‌باشد. الگوریتمی که برای این کار ارائه شده است Ant-Miner نام دارد. شواهد به دست آمده از این تحقیقات حاکی از آن است که این روش قابلیت رقابت با الگوریتم CN2 که یکی از شناخته شده ترین الگوریتم‌ها برای کلاس‌بندی است قابل رقابت می‌باشد. از ACO برای داده‌کاوی برای Clustering  نیز استفاده شده است.[7].
**3.1.1.تحلیل تصویر با استفاده از ACO**:
روشی برای تشخیص کناره‌های یک تصویر با استفاده از ACO ارائه شده است. با استفاده از این روش می‌توان کناره‌های یک عکس دیجیتال را تشخیص داد که در زمینه‌های دید ماشین و تحلیل تصویر و دانستن محتوای درون تصویر کاربرد دارد.[6].
# 2.کارهای مرتبط:


# گزارش آزمایش:
به [این](https://github.com/Sh4hr14r/ACOforTSP) آدرس مراجعه کنید. 

# مراجع:

1.  S. Goss, S. Aron, J.-L. Deneubourg et J.-M. Pasteels, _Self-organized shortcuts in the Argentine ant_, Naturwissenschaften, volume 76, pages 579-581, 1989
2. M. Dorigo, _Optimization, Learning and Natural Algorithms_, PhD thesis, Politecnico di Milano, Italy, 1992.
3. Michel Gendreau, Jean-Yves Potwin_Handbook of Metaheuristics 2nd Edition_, Springer 2010
4. M. Dorigo & T. Stützle, 2004. _Ant Colony Optimization_, MIT Press. ISBN 0-262-04219-3                                                                                                                                                                                                            
5. Green, Jennifer, Jacqueline L. Whalley, and Colin G. Johnson. "Automatic programming with ant colony optimization." Proceedings of the 2004 UK Workshop on Computational Intelligence. Loughborough University, 2004.
6. Baterina, Anna Veronica, and Carlos Oppus. "Image edge detection using ant colony optimization." WSEAS Transactions on Signal Processing 6.2 (2010): 58-67.
7. Parpinelli, Rafael S., Heitor S. Lopes, and Alex Alves Freitas. "Data mining with an ant colony optimization algorithm." Evolutionary Computation, IEEE Transactions on 6.4 (2002): 321-332.
8. Darquennes, Denis. "Implementation and Applications of Ant Colony Algorithms." Facultées Universitaires Notre-Dame de la Paix, Namur Institut d’Informatique 40 (2005).
9. Dorigo, Marco. "Ant algorithms solve difficult optimization problems." _Advances in Artificial Life_. Springer Berlin Heidelberg, 2001. 11-22.
10. Yaseen, Saad Ghaleb, and Nada MA Al-Slamy. "Ant colony optimization."_IJCSNS_ 8.6 (2008): 351.
11. Gutjahr, Walter J. "First steps to the runtime complexity analysis of ant colony optimization." _Computers & Operations Research_ 35.9 (2008): 2711-2727.
12. Bonabeau, Eric, Marco Dorigo, and Guy Theraulaz. "Inspiration for optimization from social insect behaviour." _Nature_ 406.6791 (2000): 39-42.
13. Doerr, Benjamin, et al. "On the influence of pheromone updates in ACO algorithms." (2007).
14. GiriRajkumar, S. M., Dr K. Ramkumar, and O. V. Sanjay Sarma. "Real time application of ants colony optimization." _International Journal of Computer Applications (0975-8887) Vol_ (2010).