Autonomous Distributed GA for Solving Real-Time Combinatorial Problems

Combinatorial problems are NP-complete, which means even infinite number of CPUs take polynomial time to search an optimal solution. Therefore approximate search algorithms such as Genetic Algorithms are used. However, such an approximate search algorithm easily falls into local optimum and just distributed / parallel processing seems inefficient. In this paper, this inefficiency is shown by simulation using TSP library as the example of optimal route scheduling. Then, an autonomous distributed GA to cope with this inefficiency through exchanging information about individuals (to calculate fitness /divergence /situation) among autonomous CPUs is proposed in solving real-time combinatorial problems. Using TSP library again, its effectiveness is shown by simulation experiments.