Autonomous Distributed GA for Solving Real-Time Combinatorial Problems
Autonomous Distributed GA for Solving Real-Time Combinatorial Problems
复制标题
用于解决实时组合问题的自治分布式遗传算法
DOI：
10.1109/sitis.2013.61
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Y. Sakurai
中科院分区：
文献类型：
--
作者：
Y. Kobayashi;M. Suzuki;S. Tsuruta;Y. Sakurai
组合问题是NP完全的，这意味着即使无限数量的CPU也需要多项式时间来搜索最优解。因此，近似搜索算法，如遗传算法的使用。然而，这样的近似搜索算法容易福尔斯局部最优，只是分布式/并行处理似乎效率低下。本文以TSP库为例进行最优路径调度仿真，证明了这种低效率。然后，一个自治的分布式遗传算法，以科普这种低效率，通过交换信息的个人（计算健身/分歧/情况）自治CPU之间提出了解决实时组合问题。再次利用TSP库，通过仿真实验验证了该方法的有效性.
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.