ETRI-Knowledge Sharing Plaform

ENGLISH

성과물

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

상세정보

학술대회 Bidirectional Constructive Crossover for Evolutionary Approach to Travelling Salesman Problem
Cited 3 time in scopus Download 0 time Share share facebook twitter linkedin kakaostory
저자
강세민, 김성수, 원종호, 강영민
발행일
201508
출처
International Conference on IT Convergence and Security (ICITCS) 2015, pp.1-4
DOI
https://dx.doi.org/10.1109/ICITCS.2015.7292958
협약과제
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.
키워드
Biological cells, Cities and towns, Convergence, Electronic mail, Indexes, Sociology, Statistics
KSP 제안 키워드
Biological cells, Electronic mail, Empirical experiments, Feasible solution, Genetic approach, Index management, Travelling salesman problem(TSP), cities and towns, convergence speed, effective index, evolutionary approach