【作者】 陈琼；

【导师】 马炫；

【作者基本信息】 西安理工大学 ， 控制理论与控制工程， 2006， 硕士

【摘要】 有约束多源多目的路径问题是组合优化中的NP完全问题,它是在一个连通的无向图中,寻找包括所有源节点和目的节点的满足约束条件的最优子图集。有约束多源多目的路径问题的每一个源节点都与数个目的节点相对应,即源节点与目的节点是一种一对多的关系。本文将有约束多源多目的路径问题分解为以下两个问题来解决:1.多个有约束单源多目的路径寻优问题;2.将多个有约束单源多目的路径寻优问题的最优解和次优解进行组合,求满足约束条件的最优组合路径的问题。这两个问题都是基于遗传算法来解决的。主要内容包括以下两个方面:(1)提出了解决度约束单源多目的路径寻优问题的遗传算法,算法采用一种新的节点路径形式的编码方式来表示一棵生成树,设计了以子树为对象的交叉算子和变异算子,实现了具有树形结构的染色体的遗传进化,算法对不可行解还采用了节点度的改变算法,改善了算法的性能。该算法可以应用于大规模网络中求解目的节点比较多的路径寻优问题。(2)第二个问题属于组合优化问题,本文对该问题采用了一维多值编码方式,简单易实现的单点交叉算子和位变异算子。数值实验表明本文的算法能有效地解决有约束多源多目的路径问题。更多还原

【Abstract】 The multiple-origins-multiple-destinations routing (MOMD) problems with constraints is a NP-complete problem. The object of the MOMD problems with constraints is to find a optimum connection of figs including all the origins and destinations ,which meet constraints in a directionless connection network. Here every origins are correlative with many destinations. For resolving the MOMD problems with constraints, it can be divided into two-branch problems: The first one is many single-origin-multiple-destinations routing (SOMD) problems with constraints; The second one that optimal and superior solutions of each SOMD problem with constraints is combined to find the optimum solution of the MOMD problem with constraints. Then, the two problems are solved by genetic algorithm. Two aspects are following :(1)A genetic algorithm for solving the SOMD problem with degree-constraint is proposed. The coding with form of node path is adopted. The crossover operator and mutation operator retained tree-structure, and the method of modifying degree of nodes are designed. The proposed algorithm can be applied to large-scale network to solve the SOMD problems.(2) The second question belongs to combinatorial optimization. Multiple value coding is used in the algorithm. Simple point crossover operator and position mutation operator is adopted. The algorithm is simple and easy to realize.The algorithm effectively solved the MOMD problem with degree-constraint by numerical simulation results .更多还原