چکیده فارسی :

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

کلمات کلیدی: الگوریتم مورچگان ، کاهش تورینگ ، الگوریتم فراابتکاری ، مسئله فروشنده دوره گرد ، برنامه ریزی فروشگاه کار ، مسئله کوله پشتی.

چکیده انگلیسی:

Nowadays, there is an increasing dependence on metaheuristic algorithms for solving combinatorial optimization problems. This paper discusses various metaheuristic algorithms, their similarities and differences and how Ant Colony Optimization algorithm is found to be much more suitable for providing a generic implementation. We start with the solution for Travelling Salesman Problem using Ant Colony Optimization (ACO) and show how Polynomial Turing Reduction helps us solve Job Shop Scheduling and Knapsack Problems without making considerable changes in the implementation. The probabilistic nature of metaheuristic algorithms, especially ACO helps us to a greater extent in avoiding parameter fine-tuning. Through Sensitivity analysis we find that ACO exhibits better resilience to changes in parameter values in comparison to other metaheuristic algorithms .

Keywords : Ant Colony Optimization ; Turing Reductions ; Metaheuristic Algorithms ; Travelling Salesman Problem ; Job Shop Scheduling ; Knapsack Problem ;