基于进化规划的网络多目标路由算法

多目标路由问题要求极小化网络带宽资源消耗 ,它与图论中 NP完全的 Steiner问题等价 ,不存在多项式时间算法 ,只能采用近似算法或启发式算法 .进化算法是一类有效求解优化问题的新算法 .应用进化算法中的进化规划方法 ,求解 Steiner问题 ,提出了一种新的多目标路由算法 .仿真结果显示 ,该算法性能高于启发式方法

Multi-Destination Routing Algorithm Based on Evolutionary Programming

The multi- destination routing problem is finding transmitting routes thatcostthe minimum net- work bandwidth resources.When the network is modeled as a graph,the problem is thatof finding Steiner tree.Because the Steiner tree problem is a NP- complete problem,heuristic algorithm and appproximate al- gorithm are usually considered.Evolutionary algorithm( including gene algorithm,evolutionary program- ming and evolutionary strategy) shows its capability to solve complex optimization problem,such as trav- eling salesman problem.This paper shows that evolutionary programming method can be used to solve the Steiner problem. The multi- destination routing algorithm based on evolutionary programming produces more network resources saving results in simulation.