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...
详细信息
ISBN:
(纸本)9781479932115
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.
暂无评论