Minimization of the Total Traveling Distance and Maximum Distance by Using a Transformed-Based Encoding EDA to Solve the Multiple Traveling Salesmen Problem
學年 104
學期 1
出版（發表）日期 2015-09-17
作品名稱 Minimization of the Total Traveling Distance and Maximum Distance by Using a Transformed-Based Encoding EDA to Solve the Multiple Traveling Salesmen Problem
作品名稱（其他語言）
著者 Chen, S. H.
單位
出版者
著錄名稱、卷期、頁數 Mathematical Problems in Engineering 2015, 640231 (13 pages)
摘要 Estimation of distribution algorithms (EDAs) have been used to solve numerous hard problems. However, their use with in-group optimization problems has not been discussed extensively in the literature. A well-known in-group optimization problem is the multiple traveling salesmen problem (mTSP), which involves simultaneous assignment and sequencing procedures and are shown in different forms. This paper presents a new algorithm, named EDAMLA, which is based on self-guided genetic algorithm with a minimum loading assignment (MLA) rule.This strategy uses the transformed-based encoding approach instead of direct encoding. The solution space of the proposed method is only 𝑛!. We compare the proposed algorithm against the optimal direct encoding technique, the two-part encoding genetic algorithm, and, in experiments on 34 TSP instances drawn from the TSPLIB, find that its solution space is 𝑛! ( 𝑛−1 𝑚−1 ). The scale of the experiments exceeded that presented in prior studies. The results show that the proposed algorithm was superior to the two-part encoding genetic algorithm in terms of minimizing the total traveling distance. Notably, the proposed algorithm did not cause a longer traveling distance when the number of salesmen was increased from 3 to 10. The results suggest that EDA researchers should employ the MLA rule instead of direct encoding in their proposed algorithms.
關鍵字
語言 en
ISSN 1563-5147
期刊性質 國外
收錄於 SCI
產學合作
通訊作者
審稿制度 是
國別 EGY
公開徵稿
出版型式 ,電子版,紙本
相關連結

機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/121393 )