Learning ۲-opt Algorithm for the Euclidean Symmetric Traveling Salesman Problem
- سال انتشار: 1402
- محل انتشار: شانزدهمین کنفرانس بین المللی انجمن ایرانی تحقیق در عملیات
- کد COI اختصاصی: ICIORS16_043
- زبان مقاله: انگلیسی
- تعداد مشاهده: 155
نویسندگان
Department of Mathematics and Computer Science, University of BonabBonab, Iran
چکیده
The traveling salesman problem (TSP) is known one of the NP-hard problems to find the optimal solution. However, in the case that arc costs satisfy the triangle inequality there are polynomial time approximation algorithms; ۲-opt algorithm is a heuristic method to obtain a good approximate solution for TSP. The proposed learning ۲-opt algorithm improves the classical ۲-opt algorithm to remove cross arcs and cross regions and provides a good approximate solution in a reasonable iteration. So, in the optimal solution for the Euclidean symmetric TSP (ES-TSP) there is neither cross arcs nor cross regions, and a learning phase determine the cross regions, and the ۲-opt heuristic algorithm removes the cross arcs. A Markov decision process is applied to determine the states of the learning process, and it is considered to reward function according to the improvement of the current state solution. The topology of the network and the order of nodes are learned by the proposed method, and the proper ۲-opt improvement policy is implemented during transitions in the Markov chain process.کلیدواژه ها
Machain Learning, Traveling Salesman Problem, ۲-opt Heuristic Algorithm, Markov Decision Process, Approximate solution.مقالات مرتبط جدید
اطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.