Abstract: 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.