Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to produce a good genetic algorithm for the travelling salesman problem with multiple salesmen. In other words, assume we are given a graph $G$ with $n$ vertices and $k$ edges connecting them, each edge $i$ having a weight $c_i$. $G$ is symmetric, ie. all the edges can be traveled in both directions. We also have $m$ travelers. Assume also that all travelers start from the same, given, node. (this one node thus part of every subgraph, all others belong to unique graphs.) Assume that the optimal path, ie, the path with smallest sum of edge weights, for a given graph $H$ is $\sum H.$

The problem is that we need to find a partition of $G$ into $m$ subgraphs such that the sum $\sum_{j} (\sum G_j)$ is minimized.

I want to use a genetic algorithm to solve this. Here are the states I use:

  1. Use Floyd-Warshall's Algorithm to discover the shortest paths from every node to every other node.
  2. Denote the partition as $(a_1,a_2...a_n)$ where $a_i=j$, if $i$th node belongs to the $j$th subgraph. (This excludes the starting node) Generate $v$ partitions, assigning the nodes randomly. This leads to vector of partitions $P^* = (P_1,P_2...,P_v)$
  3. Calculate the fitness of each partition. This means that we calculate, using the known shortest paths for every pair of nodes, the $\sum_{j=1}^m (\sum G_j), \ \forall P \in P^*$.
  4. Using the fitness, select $\frac{v}{2}$ best partitions and breed them, ie. select two partitions $((a_1,a_2...a_n),(b_1,b_2...b_n))$ $v$ times, select randomly $\frac{n}{2}$ (denote these as $A$) of the elements of the first and generate new partition $(d)$, where $d_i =\begin{cases}a_i, & \text{if $a_i \in A$} \\b_i, & \text{if $a_i \notin A$} \\ \end{cases}$
  5. Return to stage 3 and repeat till convergence.

I would really like comments, what should I add, subtract or alter in the algorithm to make it better?

I implemented this on Mathematica and it converges, sometimes to the optimal, though close to it anyway.

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.