Traveling salesman problem (TSP) was demonstrated to be non-deterministic polynomial complete problem

let alone unconnected graph constraint.Because the traditional genetic algorithm (TGA) had defects of premature convergence and slow convergence

a chaos genetic algorithm (CGA) was put forward.The CGA adopted the chromosome encoding scheme based on sequence of city which traveling salesman passed through

combined stochastic method and greedy method ways to produce the initial populations so as to contain optimal value

avoid infeasible chromosomes and improve the subsequently genetic efficiency.Then

precedence preservation crossover and shift change mutation operations were executed.At the same time

local neighborhood and chaos search were introduced to accelerate convergence.Furthermore

the criterion was given to judge whether optimal solution meets unconnected graph constraints or not.Finally

computation results proved the effectiveness of CGA.