A ۲-Opt Genetic Algorithm for the Symmetric Traveling Salesman Problem

سال انتشار: 1401
محل انتشار: پانزدهمین کنفرانس بین المللی انجمن ایرانی تحقیق در عملیات
کد COI اختصاصی: ICIORS15_106
زبان مقاله: انگلیسی
تعداد مشاهده: 285

نویسندگان

Department of Mathematics and Computer Science, University of Bonab, Bonab, Iran

چکیده

The genetic algorithm is a kind of evolutionary metaheuristicalgorithm, those find a good solution for some hard problemsin a reasonable time. Traveling salesman problem is an NPhardproblem, and its optimal solution is one of the mostchallenged discussions. So, researchers consider theproblem to find a nearby optimal solution instead of theoptimal solution. In the symmetric traveling salesmanproblem, the arc cost parameters satisfy the triangleinequality, in addition to the froward arc costs equal to thebackward arc costs in the network. The ۲-Opt heuristic couldimprove an obtained solution by transforming some crossarcs into the straight arcs. There is not any cross arc in theoptimal solution, then we apply the ۲-Opt algorithm on thegenerated population by the crossover operator in theproposed genetic algorithm. Therefore, the obtained solutionby the proposed ۲-Opt genetic algorithm performs a goodcomputation time as well as the optimality. The proposedalgorithm accelerates the improving trajectory in the geneticalgorithm by the features of the ۲-Opt heuristic.

کلیدواژه ها

Traveling Salesman Problem, Genetic Algorithm, ۲-OptAlgorithm, Metaheuristic Algorithm, Network Optimization.

مقالات مرتبط جدید

اطلاعات بیشتر در مورد COI

COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.

کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.