用基于多目标决策的遗传算法解网络拓扑结构设计问题

多点网络拓扑结构设计问题是NP-完全问题。该文提出了一个基于多目标决策的遗传算法(MCGA)来解决多点网络拓扑结构问题。和其它多目标遗传算法不同的是:首先,对网络节点进行预划分,使得Pareto优的节点归于候选分枝节点集合;其次,修改了Prüfer编码,使得编码中的码元代表候选分枝节点,以利于对分枝节点的搜索;最后,构造了分枝变异算子与非分枝变异算子作为主要的进化算子。该算法以概率1收敛于全局最优解集。数值实验表明该算法优于其它多目标遗传算法。

Using Multi-criteria Genetic Algorithm for the Topological Design of a Network

The problem of multipoint network topological design is NP-complete.In this paper,a multi-criteria genetic algorithm(MCGA)is proposed.MCGA differs from other genetic algorithms mainly in following:First,the nodes of network are divided into candidate inner node set and candidate leaf node set so that the nodes of candidate inner node set are Pareto optimal,this paper call this division predivision.Second,the paper modifies the Prüfer coding strategy so that the members of code come from candidate node set,which contributes to the search of nodes.Finally,two corresponding mutation operators are given.The algorithm converges to the global optimum of the problem with probability one.The simulation result indicates that this method is effective than other multiobjective genetic algorithm.