ETRI-Knowledge Sharing Plaform



논문 검색
구분 SCI
연도 ~ 키워드


학술대회 Bidirectional Constructive Crossover for Evolutionary Approach to Travelling Salesman Problem
Cited 4 time in scopus Download 0 time Share share facebook twitter linkedin kakaostory
강세민, 김성수, 원종호, 강영민
International Conference on IT Convergence and Security (ICITCS) 2015, pp.1-4
15ZS1400, 듀얼모드 배치.쿼리 분석을 제공하는 빅데이터 플랫폼 핵심기술 개발, 원종호
In this paper, we propose an improved crossover method for genetic approach to travelling salesman problem (TSP). Because any feasible solution of TSP must be an ordered permutation, the validity of an offspring generated by the simple crossover where corresponding parts of genes or chromosomes of parents are exchanged. Therefore, researchers have proposed special crossover methods, and so far it is known that SCX is superior to other methods in the aspect of convergence speed and fitness of the genes. In this paper, we extend the SCX to have bidirectional and circular search properties in the construction of offsprings. We also devised an simple and effective index management so that the search for candidate nodes during the offspring construction can be performed in an efficient way. The proposed BCSCX shows the better convergence speed and even better solution than those of SCX in the empirical experiments.
KSP 제안 키워드
Empirical experiments, Feasible solution, Genetic approach, Index management, Travelling salesman problem(TSP), convergence speed, effective index, evolutionary approach