Traveling Salesman Problem: path-evolution

The goal is to find the shortest cycle in a complete graph of N nodes. The nodes represent cities that are visited by a salesman.

Traveling Salesman

  • GA - interface help
  • GA - Theory should be an applet here

    Travelling Salesman Problem - Problem Info

    The salesman has to visit n cities and every city shall only be visited once. The postions of the n cities are given and fixed. The salesman is looking for the shortest path on his tour through all cities.
    The cities are numbered from 1 through n. A vector containig a permutation of the numbers from 1 through n is created and interpreted as the sequence the cities are visited. To close the salesmans path, the last city (i.e. the number at vector position n) is connected with the first on (number at vector postion 1). The salesman will have to find the permutation of numbers from 1 through n, that the length of the path associated with this permutation becomes minimal.

    chromosome (genotype repesentation)

    The permutation is encoded using a bitvector with n*ld(n)-bits. Each of the ld(n)-sections contains a different BCD-value of 1 through n.
    A special crossover operator, the 'Genetic Edge Recombination'-Operator( see Whitley D, "Scheduling Problems and Travelling Salesman: The Genetic Edge REcombination Operator, Computer Sciende Department, Colorado State University, 1989) is used.
    Genetic Edge Recombination Operator For each node A create an edgelist, containing all nodes that have an edge to A (they have an edge when they are neighbours in the permutation). For both crossover-partner-chromosomes a shared edgelist is created for all nodes. Repeat the following steps until all edgelists are empty. Initially the edgelist having the highest number of entries is the activat edgelist (if more than one list: random choice).
    1. add the node coresponding to the active edgelist to the result.
    2. delete this node from all edgelists
    3. from nodes in the active edgelist, choose the edgelist with the lowest number of entries (if more than one list: random choice) and make it the active edgelist

    drawing the chromsome (phenotype representation)

    Simply draw the cities and draw the path given by the permutation.

    applet parameters

  • param name="n" value="25"
    number of cities (nodes) n;