# 1.مقدمه:
در بسیاری از ابداعات بشر، انسان از موارد موجود در طبیعت الهام گرفته است. مطلبی که در این پروژه مد نظر قرار داده شده است استفاده از رفتار مورچه‌ها در طبیعت برای یافت غذا می‌باشد. مورچه‌ها برای به دست آوردن غذا رفتار جالبی از خود نشان می‌دهند. ان‌ها وقتی برای یافتن غذا از لانه خود بیرون می‌آیند به صورت اتفاقی در یک جهت به حرکت خود ادامه می‌دهند و پس از یافتن غذا در مسیر بازگشت به لانه ماده‌ای را بر روی زمین برجا می‌گذارند. در هنگام رسیدن به لانه بقیه مورچه‌ها متوجه می‌شوند که باید مسیر بو را دنبال کنند تا به غذا برسند. اما نکته‌ای که باعث شده است تا این رفتار مورچه‌ها الهام بخش استفاده از آن در زمینه علوم کامپیوتر شود قابلیت تشخیص شدت بو توسط مورچه‌هاست. بویی که مورچه‌ها از خود بر روی زمین باقی می‌گذارند ماده‌ای است که پس از گذشت مدتی بخار می‌شود و شدت آن کاهش می‌یابد. در این صورت هنگامی که مورچه می‌خواهد مسیری را دنبال کند با استفاده از قابلیت ذکر شده مسیری را انتخاب می‌کند که بوی باقی‌مانده بر روی آن بیشتر باشد. این مسیر به دلیل اینکه مسیر کوتاه‌تری برای رسیدن به غذاست بوی باقی‌مانده بر روی آن کمتر از بین می‌رود. لازم به ذکر است که مورچه‌ها پس از طی مسیر دوباره همان ماده را در راه ترشح می‌کنند تا از بین نرود. پس از گذشت مدتی مورچه‌ها کوتاه‌ترین مسیر را برای رسیدن به هدف خود می‌یابند.
این مسئله برای اولین بار با انجام آزمایشی اثبات شد که یک کلننی مورچه را در یک محفظه قرار دادند و دو راه برای رسیدن به غذا برای مورچه‌ها قرار دادند که یکی از آن‌ها کوتاه‌تر بود. با گذشت زمان رفت آمد مورچه‌ها تغییر کرد و به حالتی در آمد که همه از مسیر کوتاه‌تر می‌رفتند[1].
با مطالعه این رفتار مورچه‌ها برای اولین بار در سال 1991 آقای M. Dorigo مبدع ایجاد الگوریتم‌هایی شدند که امروزه به Ant Colony Optimization یا به طور مخفف ACO شناخته می‌شوند [2]. ایشان از جمله افرادی بودند که رفتارهای حشرات را وارد دنیای کامپیوتر کردند[12]. این الگوریتم‌ها با استفاده از شبیه‌سازی همین رفتار در مورچه‌ها قادر به حل تعدادی از مسائل ترکیبیاتی هستند. از جمله این مسائل میتوان به فروشنده دوره‌گرد و مسئله کوله‌پشتی اشاره کرد. این دسته از الگوریتم‌ها کاربردهای بسیاری دارند که در بخش بعدیبه برخی از آن‌ها پرداخته شده است. هدف این پروژه این است که نوعی از ACO را برای حل مسئله **فروشنده دوره‌گرد** پیاده‌سازی کرد[3].
**1.1.کاربردهای ACO:**
الگوریتم‌های ACO دارای انواع مختلفی هستند که به صورت جدول زیر می‌باشند[4].
در زیر برخی از کاربردهای این نوع الگوریتم‌ها به طور خاص به اختصار ذکر شده است.
**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.کارهای مرتبط:
**1.2.الگوریتم نزدیک ترین همسایه:**
این الگوریتم که در انگلیسی با نام Nearest Neighbor شناخته می‌شود طوری عمل می‌کند که به فروشنده اجازه می‌دهد در هر مرحله نزدیکترین شهر موجود از همسایگان خود را که آن را ندیده است انتخاب کند و به آن مرحله برود. برای n شهر که به صورت تصادفی در صفحه قرار می‌گیرند به صورت میانگین الگوریتم مسیری را انتخاب می‌کند که از بهینه ترین مسیر 25 درصد طولانی تر است[15]. اما ترکیب‌های بسیار زیادی از شهرها وجود دارد که این الگوریتم بدترین حالت را می‌دهد[16].
**2.2. روش Pairwise Exchange:**
در این روش دو یال از گراف را پاک کرده و با دو یال دیگر رئوس جدا شده را طوری متصل می‌کنیم که مسیر کوتاه‌تر شود. این روش هم بسیار محدود است و همواره جواب مناسبی نمی‌دهد. از این روش برای بهینه سازی راه‌های پیدا شده در حل مسئله Vehicle Routing Problem نیز استفاده می‌شود.[15]
# 3. تعریف Meta-Heuristic:
الگوریتم‌های ACO در دسته‌ای از الگوریتم‌ها قرار می‌گیرند که به آن‌ها Meta-Heuristic گفته می‌شود. در اینجا بررسی می‌کنیم که این لغت به چه معناست.
مسائل زیادی وجود دارند که در دسته مسائل ترکیبیاتی قرار می‌گیرند و مسائل زیادی در واقعیت هستند که می‌توانند به یکی از مسائل ترکیبیاتی تبدیل شوند. رااه حل ساده برای حل این مسائل یک راه حل مستقیم به وسیله Exhaustive Search می‌باشد که به معنای بررسی تمامی حالت ممکن و انتخاب بهترین جواب از بین آن‌هاست. متاسفانه در اکثر مواقع با بالا رفتن حجم مسئله استفاده از این روش ناممکن می‌شود، به این دلیل که زمان اجرای آن به ازای اضافه شدن یک عضو نمایی بالا می‌رود. در برخی موارد با دانستن خصوصیات مربوط به یک مسئله ترکیبیاتی میتوان بهترین جواب را با راهی بهتر از Exhaustive Search یافت. اما این روش‌ها همچنان برای تعداد بالای داده کند هستند. به این روش‌های بدست آوردن جواب Exact می‌گویند.
دسته دیگر الگوریتم‌ها برای حل این مسائل الگوریتم‌های تقریبی(Approximate Algorithms) هستند [17] که بدست آمدن یک بهترین جواب یک مسئله را تضمین نمی‌کنند اما یک جواب به نسبت خوب را در زمان بسیار کوتاه‌تری بدست می‌آورند. این الگوریتم‌ها به نام Heuristic Method یا به طور ساده‌تر Heuristic هم خطاب می‌شوند. این الگوریتم‌ها به صورت کلی به دو نوع Constructive و یا Local Search تقسیم می‌شوند. برای مثال در زیر یک شبه کد برای Constructive Heuristic مشاهده می‌کنید.
در این عکس sp حالتی است که توسط تابع ChooseFirstComponent برای اولین بار انتخاب می‌شود و سپس به حالت sp توسط تابع GreedyComponent(sp) یک حالت دیگر با تقریبی که توسط Heuristic زده می‌شود اضافه می‌شود. و در انتها این روال یک حالت کامل را به عنوان جواب با عنوان s برمی‌گرداند.
مشکل اینجاست که این متدها، که به یکباره جواب را می‌سازند، تعداد بسیار محدودی از جواب‌های نزدیک ممکن را تولید می‌کنند یا اینکه در جواب‌های گیر می‌کنند که خیلی خوب نیستند. حتی نشان داده شده است که با وسیع‌تر کردن Local Search و اجرای چندباره آن عملا چندان پیشرفت چشمگیری در جواب‌ها صورت نمی‌گیرد. این جریان باعث شد که یک سری راهکار‌های کلی که امروزه به آن‌ها Metaheuristic گفته می‌شوند برای حل این مشکلات ایجاد شوند.
در واقع Metaheuristic یک سری مفاهیم الگوریتمی است که میتوان با استفاده از آن برای دامنه وسیعی از مسائل Heuristic تعریف کرد. میتوان آن را یک General Purpose Heuristic در نظر گرفت. مثال‌هایی از این موارد:
Simulated Annealing [18] ، Tabu Search [19] ، Evolutionary Computation [20] و Ant Colony Optimization
# 4. متاهیوریستیک ACO:
در واقع ACO نوعی Metaheuristic است که در آن یک کلونی از مورچه‌های کنترل شده توسط هوش مصنوعی با همکاری هم راهی برای یافتن یک جواب خوب پیدا می‌کنند. این همکاری نکته کلیدی در طراحی الگوریتم بر اساس ACO است. این الگوریتم باعث می‌شود که منابع محاسباتی را به چند Agent ساده که همان مورچه‌های مصنوعی هستند بسپاریم. این مورچه‌ها به صورت غیرمستقیم با یکدیگر از طریق تغییر دادن محیط ارتباط برقرار می‌کنند و این ارتباط باعث پیدایش جواب‌های نزدیک به بهینه می‌شود.
به صورت خلاصه ACO متشکل از 3 روال است که با یکدیگر کار می‌کنند. این روال‌ها به ترتیب توضیح داده خواهند شد.
**1.4. Construct Ant Solutions:**
این روال یک کلونی از مورچه‌ها را که به صورت آسنکرون و همروند به خانه‌های اطراف حالتی که اکنون در آن هستند می‌روند را مدیریت می‌کند. این خانه‌ها در گراف تولید شده از مسئله مشخص شده‌اند حرکت آن‌ها بر اساس یک قاعده تصمیم‌گیری محلی است که از Pheromone Trail و اطلاعات داده شده توسط Heuristic می‌باشد. بدین ترتیب مرحله به مرحله جوابی برای مسئله ساخته می‌شود. پس از رسیدن یک مورچه به جواب یا در حال ساختن جواب مورچه راه حل‌های محلی را بررسی کرده و با استفاده از آن‌ها و روال بعدی یعنی Update Pheromone Trails مشخص می‌کند که باید چه مقدار Pheromone بر روی مسیر باقی بگذارد.
**2.4. Update Pheromone Trails:**
این روال تعیین می‌کند که Pheromone Trail ها چگونه تغییر می‌کنند. میزان Pheromone بر روی یک مسیر می‌تواند بر اثر ریختن آن توسط یک مورچه زیاد شود یا اینکه بر اثر تبخیر آن در طی مراحل کم شود. در واقع این روال باعث می‌شود که مسیرهای خوب به وجود آمده توسط مورچه‌ها تشدید شوند و مسیرهای بد از بین بروند. در نهایت مورچه‌های مصنوعی مسیرشان به سمت یک مسیر خیلی خوب همگرا می‌شود[13].
**3.4. DeamonActions:**
این روالی است که یک سری کارها را که توسط یک مورچه مصنوعی قابل انجام نیست را انجام می‌دهد. مثال‌هایی از این کارها: فعال‌سازی روالی برای بهبود محلی در یک قسمت، جمع‌آوری اطلاعات Global از سیستم و استفاده از آن‌ها برای بالا بردن مقدار ریختن Pheromone توسط یک مورچه و ... .
تصویر زیر به طور خلاصه این روال‌ها را نشان می‌دهد:
البته باید توجه داشت که شبه کد بالا الزامی را برای موازی کارکردن این روال‌ها قرا نمی‌دهد و به همین دلیل است که برنامه‌نویس آزاد است که به هر صورتی که صلاح می‌داند آن‌ها را مدیریت کند.
# 5. تعریف مسئله فروشنده دوره‌گرد:
مسئله فروشنده دوره‌گرد از جمله مسائل معروف در علوم کامپیوتر است. در این مسئله که با نام انگلیسی Travelling Salesman Problem یا به اختصار TSP معروف است یک فروشنده می‌خواهد از شهر محل زندگی خود شروع کند و می‌خواهد که به تمامی شهرهایی که در آن جنس میفروشد برود و در انتها به شهر خود بازگردد به طوری که هر شهر را فقط یک بار ببیند و کوتاه‌ترین مسیر را برای این سفر طی کند. این مسئله توسط یک گراف وزن‌دار به صورت G = ( N, A ) که در آن N مجموعه راس‌ها که نشاندهنده همان شهرها هستند و A یال‌ها که هرکدام وزنی به اندازه $$d_{ij}$$ دارند و نشاندهنده مسیر بین دو شهر هستند بیان می‌شود. لازم به ذکر است که دو نوع از این مسئله وجود دارد. نوع اول که به آن Symmetric TSP گفته می‌شود حالتی از مسئله است که درآن برای هر دو شهر i و j مسیر رفت و برگشت طولشان یکسان است$$d_{ij} = d_{ji}$$. در حالت دوم که به آن Asymmetric TSP گفته می‌شود حداقل دو راس وجود دارد که در آن دو طول مسیر رفت با مسیر برگشت برابر نیست$$d_{ij}\neq d_{ji}$$.
حالا نحوه حل مسئله توسط ACO را بیان می‌کنیم.
# 6. نحوه حل مسئله به روش ACO :
نحوه حل مسئله بدین صورت است[4]:
**1.6. Construction Graph:**
این گراف متناظر با گراف توضیح داده شده در قسمت قبل است. مجموعه C مجموعه همه راس‌‌‌های گراف است که متناظر با مجموعه N در بخش قبلی می‌باشد. مجموعه L متشکل از تمامی ارتباطات بین رئوس است که متناظر با A در بخش قبلی می‌باشد. و هر ارتباط یک وزن دارد که مشخص کننده طول آن است و توسط$$d_{ij}$$ نشان داده می‌شود.
**2.6. Constraint:**
تنها محدودیت در مسئله این است که همه شهرها باید دیده شده باشند و هر شهر باید حداکثر یک بار دیده شود. این محدودیت در صورتی رعایت می‌شود که در هر مرحله هر مورچه از بین شهرهای اطاف خود یکی از شهرها را انتخاب کند که هنوز آن را ندیده است. همسایگی قابل انتخاب یک مورچه به صورت $$N_{i}^{k}$$ نشان داده می‌شود که k شناسه مورچه مورد نظر و i شهری است که مورچه هم‌اکنون در آن قرار دارد می‌باشد.
**3.6. Pheromone Trails and Heuristic Information:**
Pheromone Trail که به صورت$${\tau_{ij} }$$نشان داده می‌شود در مسئله TSP اشاره دارد به میزان علاقه یک مورچه برای رفتن به شهر j بلافاصله پس از شهر i. Heuristic Information که به صورت $${\eta_{ij} }$$ نشان داده می‌شود به صورت کلی متناسب است با عکس فاصله بین دو شهر i و j که در ساده‌ترین حالت با فرمول $${\eta_{ij} } = 1/d_{ij}$$ محاسبه می‌شود. در واقعیت از این فرمول برای اکثر الگوریتم‌های ACO در مسئله TSP استفاده می‌شود.
**4.6. Solution Construction:**
برای ساخت یک جواب در ابتدا هر مورچه به صورت اتفاقی روی یک شهر قرار می‌گیرد و در هر مرحله یک شهر دیده نشده را به مسیر خود اضافه می‌کند تا اینکه تمام شهرها را دیده باشد[10].
نکته: مسئله‌ای که در این پروژه بررسی می‌شود دانستن این موضوع نیست که آیا چنین مسیری که نشان دهنده یک دور همیلتونی در گراف است وجود دارد یا خیر، بلکه به صورت پیش‌فرض داده‌های انتخابی همگی دارای دور همیلتونی هستند و ما می‌خواهیم طول کوتاه‌ترین دور را بیابیم.
# 7. توضیح نحوه کلی انجام آزمایش:
برای انجام آزمایش نیاز به برنامه‌ای است که یکی از روش‌های موجود در ACO برای حل مسئله TSP در آن پیاده‌سازی شده باشد. پس از پیاده‌سازی کد نیاز به مجموعه‌ای از داده‌های استاندارد در مورد مسئله است. سپس با اجرای برنامه و استفاده از داده‌ها به نتایجی می‌رسیم که می‌توانیم از آن‌ها برای ارزیابی این روش در حل این مسئله استفاده کنیم. برای انجام این آزمایش‌ها مراحل ذکر شده انجام شده‌اند که در ادامه توضیح داده خواهند شد. شایان ذکر است که الگوریتم پیاده‌سازی شده برای حل Symmetric TSP می‌باشد.
# 8. پیاده‌سازی الگوریتم حل مسئله به روش Min-Max Ant System:
این روش که به اختصار به آن MMAS گفته می‌شود یکی از روش‌های ACO برای حل مسئله TSP است که نوع پیشرفته‌تری از روش پایه‌ای Ant System است که چهار قابلیت را برای سیستم معرفی می‌کند.اول با استفاده از دو مورد از مورچه‌های مصنوعی در این روش بهترین و کوتاه‌ترین مسیرها شناسایی می‌شوند. تنها به این دو نوع مورچه اجازه ریختن Pheromone در مسیرها داده می‌شود. نوع اول مورچه‌ایست که بهترین مسیر را در حلقه کنونی طی کرده است و نوع دوم مورچه‌ایست که بهترین مسیر را در بین حلقه‌های به وجود آمده در چند حلقه قبلی طی کرده است. اما این روش باعث می‌شود که مورچه‌ها به سمت بهترین مسیر تا به حال یافت شده متمایل شوند که ممکن است صرفا بهترین مسیر قابل یافتن نباشد. دوم اینکه برای جلوگیری از این انفاق روشی که در MMAS به کار برده می‌شود این است که دامنه مقادیر Pheromone Trail ها در بازه – محدود می‌شوند. سوم اینکه در ابتدا Pheromone Trail ها همگی به اندازه حد بالای بازه ذکر شده یعنی – مقدار دهی می‌شوند. و چهارم اینکه در MMAS مقدار Pheromone Trail ها پس از گذشت چند حلقه و تغییر نکردن و بهتر نشدن مسیرهای یافت شده دوباره مقداردهی اولیه می‌شوند[4].
**1.8. Pheromone Trails Update:**
پس از اینکه همه مورچه‌ها یک مسیر پیدا کردند مقادیر Pheromone ها بر اساس رابطه زیر بر اثر تبخیر کم می‌شوند:
$$\tau_{ij}\leftarrow (1-\rho )\tau_{ij}, \forall (i,j) \in L$$
در این رابطه $$\tau_{ij}$$ همان میزان Pheromone بر روی مسیر بین i و j است و $$\rho $$ نرخ تبخیر آن می‌باشد.
سپس میزان Pheromone جدید بر اساس رابطه زیر اضافه می‌شود:
$$\tau_{ij}\leftarrow \tau_{ij} + \Delta \tau_{ij}^{best}$$
در این رابطه $$ \Delta \tau_{ij}^{best} = 1/ C^{best}$$است. $$C^{best}$$بسته به اینکه از روش اضافه کردن Pheromone بر اساس بهترین مورچه در این iteration اضافه کرده باشیم یا از روش بهترین مورچه تا به حال می تواند برابر با$$C^{ib}$$ برای مورد اول و یا برابر با $$C^{bs}$$ برای مورد دوم باشد. در اکثر پیاده‌سازی‌ها از هر دو روش توئمان استفاده می‌شود. در این پیاده‌سازی هم همینطور است.
**2.8. Pheromone Trail Limits:**
در MMAS حد بالا$$ \tau_{max}$$ و حد پایین$$ \tau_{min}$$ برای Pheromone ها اعمال می‌شود تا سیستم در یک حالت خاص متوقف نشود. به صورت دقیق‌تر تعیین دامنه برای Pheromone Trail ها چنان بر روی سیستم تاثیر می‌گذارد که احتمال $$p_{ij}$$که نشان دهنده احتمال این است که شهر j انتخاب شود وقتی در شهر i هستیم در محدوده $$[ \tau_{min}, \tau_{max}]$$ قرار گیرد به صورتی که $$ 0 < p_{min} \leq p_{ij} \leq p_{max} \leq 1 $$ باشد. یعنی موقعی که مورچه برای رفتن به خانه بعدی تنها یک انتخاب داشته باشد داریم$$ p_{min} = p_{max} = 1 $$ .
اثبات شده است که در طول زمان حد بالای میزان Pheromone به سمت $$1/ \rho C^{*}$$میل می‌کند که $$C^{*}$$ در این رابطه طول بهترین مسیر ممکن است[8]. بر اساس این قضیه MMAS برای تعیین حد بالا از تقریب$$1/ \rho C^{bs}$$ استفاده می‌کند و $$ \tau_{max}$$را مشخص می‌کند. حد پایین آن توسط رابطه $$ \tau_{max}/a$$تعیین می‌شود که a یک پارامتر است.
**3.8. Pheromone Trail Initialization and Reinitialization:**
همانطور که قبلا توضیح داده شد در ابتدای الگوریتم مقادیر اولیه Pheromone Trail ها به اندازه حد بالای دامنه مقادیر مقداردهی اولیه می‌شوند. این مورد به همراه یک نرخ تبخیر کوچک باعث می‌شود که در ابتدای کار MMAS بسیار مایل به جست‌وجوهای متفاوت باشد.
راه دیگری که تنوع جست‌وجوها را بالا می‌برد مقداردهی دوباره Pheromone Trail هاست که در هنگام گیر کردن الگوریتم در یک مسیر رخ می‌دهد.
**4.8. شبه کد سطح بالای ACO برای TSP:**
در زیر شبه کد سطح بالای روش‌های ACO برای حل مسئله TSP که MMAS نیز جزئی از آن‌هاست را به صورت خیلی کلی مشاهده می‌کنید[4]. **برای مشاهده پیاده‌سازی واقعی می‌توانید به [اینجا](https://github.com/Sh4hr14r/ACOforTSP) بروید.**
# 9. مجموعه داده‌های مورد آزمایش:
برای تست برنامه از داده‌های موجود در دیتاست TSPLib استفاده شده است. این داده‌ها برای تست کدهای نوشته شده در زمینه حل مسائل TSP نمونه‌های استاندارد محسوب می‌شوند. برای انجام آزمایش از دیتاست‌های ، و استفاده شده است. برای مثال دیتاست att532 متشکل از 532 شهر در کشور ایالات متحده است. در زیر تصویر شبیه سازی شده از روی این دیتاست را مشاهده می‌کنید:
فرمت این دیتاست‌ها بدین صورت است که یک سری Meta Data در مورد روش خواندن هر کدام در بالای فایل هر یک از آن‌ها داده شده است که فرمت خواندن و تحلیل آن را مشخص می‌کند. مهمترین این Meta Data ها به شرح زیر است:
**1.9. Name:**
نشان دهنده نامیست که دیتاست با آن مشخص می‌شود.
**2.9. Type:**
نشاندهنده نوع دیتاست است. یعنی دیتاست برای چه نوع مسئله‌ای طراحی شده است. مثل: TSP ، ATSP و ... .
**3.9. Comment:**
توضیحاتی تکمیلی در مورد دیتاست
**4.9. Dimension:**
تعداد راس های موجود در گراف
**5.9. Edge_Weight_Type:**
بر اساس آن می‌تولن اندازه فواصل بین رئوس را محاسبه کرد.
**6.9. غیره:**
برای دیدن لیست کاملی از Meta Data ها می‌تولنید Documentation را از سایت TSPLib دانلود کنید.
لازم به ذکر است که در این سایت میزان کمترین فاصله برای هر دیتاست با الگوریتم‌های دقیق محاسبه شده و برای مقایسه قرار داده شده است.
# 10. آزمایش‌ها و مقایسه نتایج با میزان دقیق جواب:
در همه این آزمایش‌ها از 20 مورچه و مقادیر$$\rho = 0.5$$ و 10 try و 10 ثانیه برای زمان اجرای برنامه استفاده شده است. خروجی هر قسمت نشاندهنده بهترین حالت، حالت متوسط، بهترین حالت برای try ها و تعداد iteration در آن‌ها و زمان رسیدن به بهترین جواب است.
**1.10. دیتاست att532:**
بهترین طول مسیر ممکن:
27686
خروجی:
نتیجه:
مشاهده می‌شود که در بهترین حالت به بهترین حالت ممکن دست یافتیم.
**2.10. دیتاست rat783:**
بهترین طول مسیر ممکن:
8806
خروجی:
نتیجه:
مشاهده می‌شود که در بهترین حالت به بهترین حالت ممکن بسیار نزدیک شدیم.
**2.10. دیتاست pcb1173:**
بهترین طول مسیر ممکن:
56892
خروجی:
نتیجه:
مشاهده می‌شود که در بهترین حالت به نسبت طول کل مسیر و تعداد رئوس پردازش شده به بهترین حالت ممکن بسیار نزدیک شدیم.
# 11. نتیجه‌گیری کلی:
با استناد به آزمایش‌های انجام شده میتوان نتیجه گرفت که ACO در مورد مسئله TSP جواب‌های بسیار خوبی می‌دهد. این امر نشان دهنده قدرت و پتانسیل بالای ACO و به طور کلی Meta Heuristic ها برای حل تخمینی مسائل دنیای واقعی است.
# 12. کارهای آینده:
همانطور که مشاهده کردیم منطق روش‌های ACO بر پایه چند Agent است. بنا به این دلیل میتوان جهت بهبود عملکرد این روش‌ها از موازی سازی استفاده کرد. در آینده قصد دارم با استفاده از روش‌های برنامه نویسی همروند راهی برای اجرای موازی اینگونه الگوریتم‌ها بیابم.
# مراجع:
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).
15. Johnson, D. S.; McGeoch, L. A. (1997). The Traveling Salesman Problem: A case study in local optimisation
16. Ray, S. S.; Bandyopadhyay, S.; Pal, S. K. (2007). "Genetic Operators for Combinatorial Optimization in TSP and Microarray Gene Ordering". _Applied Intelligence_ 26 (3): 183–195
17. Jain, Kamal, and Vijay V. Vazirani. "Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation." _Journal of the ACM (JACM)_ 48.2 (2001): 274-296.
18. Cerný, V. (1985). Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. _Journal of optimization theory and applications_, _45_(1), 41-51.
19. Brandao, Jose, and Alan Mercer. "A tabu search algorithm for the multi-trip vehicle routing and scheduling problem." _European journal of operational research_ 100.1 (1997): 180-191.
20. Fogel, Lawrence J., Alvin J. Owens, and Michael J. Walsh. "Artificial intelligence through simulated evolution." (1966).