CAJ | 학술논문

针对所有旅行商路径最大值最小的多旅行商问题,提出改进的差分进化算法优化.在该优化方法中,编码采用实数编码;改进的差分进化算法采用轮盘赌选择;根据旅行商问题的特点,在差分进化算法中增加邻域搜索算子.该方法适于距离对称和非对称的多旅行商问题求解.以距离非对称的多旅行商问题的实例进行了仿真和比较,可以看出所提出的改进差分用来解决多旅行商这类离散组合优化问题是有效的.
침대소유여행상로경최대치최소적다여행상문제,제출개진적차분진화산법우화.재해우화방법중,편마채용실수편마;개진적차분진화산법채용륜반도선택;근거여행상문제적특점,재차분진화산법중증가린역수색산자.해방법괄우거리대칭화비대칭적다여행상문제구해.이거리비대칭적다여행상문제적실례진행료방진화비교,가이간출소제출적개진차분용래해결다여행상저류리산조합우화문제시유효적.
Previous research on multiple traveling salesman problem were mostly limited to the kind that employed total-path-shortest as the evaluating rule,but little notice was paid attention to the kind that employed longest-path-shortest as the evaluating rule.In order to solve this problem,an improved differential evolution algorithm was proposed to optimize it.In these methods,real number encoding and roulette wheel selection were adopted for improved differential evolution and neighborhood search operator was added to it.It was fit for solving symmetric and asymmetric multiple traveling salesman problem. Asymmetric multiple traveling salesman problems were simulated.Through comparison of results,it is shown that improved differential evolution algorithm is efficient to solve the kind of discrete combinatorial problem,such as multiple traveling salesman problems.