A genetic algorithm for the multiple destination routing problems
A genetic algorithm for the multiple destination routing problems
复制标题
DOI：
10.1109/4235.738982
复制
发表时间：
1998-11
期刊：
影响因子：
--
通讯作者：
Y. Leung;Guo Li;Zongben Xu
中科院分区：
文献类型：
--
作者：
Y. Leung;Guo Li;Zongben Xu
多目的地路由（MDR）问题可以表述为在给定的通信网络中寻找一棵包含指定的源节点和多个目的节点的最小代价树，使得满足一定的约束。这是一个典型的NP难问题，因此只有启发式算法才有实际价值。作为第一步，一个新的遗传算法被开发来解决MDR问题没有约束。它基于MDR问题的底层网络到其距离完全形式的转换，最小生成树（个体）的自然染色体表示，以及个体适应度的全新计算。与已知的遗传算法和启发式算法相比，该算法具有许多优点。首先，它保证以概率1收敛到最优解。其次，不仅所得的解决方案都是可行的，解决方案的质量也远远高于其他方法（事实上，在我们的模拟中，几乎在每一种情况下，该算法都可以找到问题的最优解）。第三，该算法具有较低的计算复杂度，并且随着问题中目的节点数量的增加，计算复杂度可以显著降低。稀疏网络和稠密网络的仿真研究都表明，该算法是高度鲁棒性和非常有效的意义上产生高质量的解决方案。
The multiple destination routing (MDR) problem can be formulated as finding a minimal cost tree which contains designated source and multiple destination nodes so that certain constraints in a given communication network are satisfied. This is a typical NP-hard problem, and therefore only heuristic algorithms are of practical value. As a first step, a new genetic algorithm is developed to solve the MDR problems without constraints. It is based on the transformation of the underlying network of an MDR problem into its distance complete form, a natural chromosome representation of a minimal spanning tree (an individual), and a completely new computation of the fitness of individual. Compared with the known genetic algorithms and heuristic algorithms for the same problem, the proposed algorithm has several advantages. First, it guarantees convergence to an optimal solution with probability one. Second, not only are the resultant solutions all feasible, the solution quality is also much higher than that obtained by the other methods (indeed, in almost every case in our simulations, the algorithm can find the optimal solution of the problem). Third, the algorithm is of low computational complexity, and this can be decreased dramatically as the number of destination nodes in the problem increases. The simulation studies for the sparse and dense networks all demonstrate that the proposed algorithm is highly robust and very efficient in the sense of yielding high-quality solutions.