Genetic algorithm for pareto optimum-based route selection |
| |
作者单位: | Cui Xunxue(New Star Research Inst. of Applied Technology, Hefei 230031, P. R. China;Jiangsu Key Lab of Computer Information Processing Technology, Soochow Univ., Suzhou 215006, P. R. China) ;
Li Qin(New Star Research Inst. of Applied Technology, Hefei 230031, P. R. China) ;
Tao Qing(New Star Research Inst. of Applied Technology, Hefei 230031, P. R. China) ; |
| |
基金项目: | 安徽省自然科学基金;安徽省杰出青年科学基金 |
| |
摘 要: | A quality of service (QoS) or constraint-based routing selection needs to find a path subject to multiple constraints through a network. The problem of finding such a path is known as the multi-constrained path(MCP) problem, and has been proven to be NP-complete that cannot be exactly solved in a polynomial time. The NPC problem is converted into a multiobjective optimization problem with constraints to be solved with a genetic algorithm. Based on the Pareto optimum, a constrained routing computation method is proposed to generate a set of nondominated optimal routes with the genetic algorithm mechanism. The convergence and time complexity of the novel algorithm is analyzed. Experimental results show that multiobjective evolution is highly responsive and competent for the Pareto optimum-based route selection. When this method is applied to a MPLS and metropolitan-area network, it will be capable of optimizing the transmission performance.
|
收稿时间: | 6 November 2005 |
Genetic algorithm for pareto optimum-based route selection |
| |
Authors: | Cui Xunxue Li Qin Tao Qing |
| |
Institution: | 1. New Star Research Inst. of Applied Technology, Hefei 230031, P. R. China;Jiangsu Key Lab of Computer Information Processing Technology, Soochow Univ., Suzhou 215006, P. R. China 2. New Star Research Inst. of Applied Technology, Hefei 230031, P. R. China |
| |
Abstract: | A quality of service (QoS) or constraint-based routing selection needs to find a path subject to multiple constraints through a network. The problem of finding such a path is known as the multi-constrained path(MCP) problem, and has been proven to be NP-complete that cannot be exactly solved in a polynomial time. The NPC problem is converted into a multiobjective optimization problem with constraints to be solved with a genetic algorithm. Based on the Pareto optimum, a constrained routing computation method is proposed to generate a set of nondominated optimal routes with the genetic algorithm mechanism. The convergence and time complexity of the novel algorithm is analyzed. Experimental results show that multiobjective evolution is highly responsive and competent for the Pareto optimum-based route selection. When this method is applied to a MPLS and metropolitan-area network, it will be capable of optimizing the transmission performance. |
| |
Keywords: | Route selection Multiobjective optimization Pareto optimum Multi-constrained path Genetic algorithm |
本文献已被 万方数据 ScienceDirect 等数据库收录! |
| 点击此处可从《系统工程与电子技术(英文版)》浏览原始摘要信息 |
| 点击此处可从《系统工程与电子技术(英文版)》下载免费的PDF全文 |