Proposal and Evaluation of "Selfish-Gene with Limited Allowance" Type GA for Solving Constraint TSP

Takashi Onoyama, Sen Kubota, Yoshio Taniguchi, and Setsuo Tsuruta

For realizing large-scale distribution network simulation applicable to supply-chain management, it is required to solve hundreds of time constraint large-scale (100 cities) Traveling Salesman Problem (TSP) within interactive response time, with practicable optimality. Thus, a "selfish-gene with limited allowance" type GA is proposed. Here, each gene of an individual satisfies only its constraints selfishly, disregarding the constraints of other genes in the same individual. Further, to some extent, even individuals that violate constraints can survive over generations and are given the chance of improvement. Our experiment proves that this method gives expert-level solutions for time constraint large-scale TSPs within several seconds.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.