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 (MC...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.展开更多
Unlike the shortest path problem that has only one optimal solution and can be solved in polynomial time, the muhi-objective shortest path problem ( MSPP ) has a set of pareto optimal solutions and cannot be solved ...Unlike the shortest path problem that has only one optimal solution and can be solved in polynomial time, the muhi-objective shortest path problem ( MSPP ) has a set of pareto optimal solutions and cannot be solved in polynomial time. The present algorithms focused mainly on how to obtain a precisely pareto optimal solution for MSPP resulting in a long time to obtain multiple pareto optimal solutions with them. In order to obtain a set of satisfied solutions for MSPP in reasonable time to meet the demand of a decision maker, a genetic algo- rithm MSPP-GA is presented to solve the MSPP with typically competing objectives, cost and time, in this pa- per. The encoding of the solution and the operators such as crossover, mutation and selection are developed. The algorithm introduced pareto domination tournament and sharing based selection operator, which can not only directly search the pareto optimal frontier but also maintain the diversity of populations in the process of evolutionary computation. Experimental results show that MSPP-GA can obtain most efficient solutions distributed all along the pareto frontier in less time than an exact algorithm. The algorithm proposed in this paper provides a new and effective method of how to obtain the set of pareto optimal solutions for other multiple objective optimization problems in a short time.展开更多
Based on the theory of fuzzy decision making, a two phrase approach is proposed for the decentralized bi level linear programming problem(DBLPP). The approach considers the conflicts between the upper and lower leve...Based on the theory of fuzzy decision making, a two phrase approach is proposed for the decentralized bi level linear programming problem(DBLPP). The approach considers the conflicts between the upper and lower levels decision makers (DMs), and among the lower level DMs themselves, a satisfactory solution is got with the non conflict matrix and decision power distribution. Compared with the other methods that have ever been proposed, the solution process is more fit to a kind of real decision making processes.展开更多
下一代互联网NGI(Next Generation Internet)需要提供服务质量QoS(Quality of Service)路由能力,支持总最佳连接ABC(Always Best Connected).但是,由于链路状态的难以精确测量与用户QoS需求的难以准确表达,因此QoS路由基于的信息实际上...下一代互联网NGI(Next Generation Internet)需要提供服务质量QoS(Quality of Service)路由能力,支持总最佳连接ABC(Always Best Connected).但是,由于链路状态的难以精确测量与用户QoS需求的难以准确表达,因此QoS路由基于的信息实际上是模糊的.同时,在网络运营日益商业化的环境下,支持ABC需要兼顾用户和网络提供方利益,考虑双方效用共赢.为此,文中引入模糊数学、概率论和博弈论知识,设计了一种ABC支持型QoS单播路由机制.该机制采用区间形式描述用户QoS需求和边(链路)参数,引入用户满意度和边评价,通过博弈分析,基于人工鱼群算法,寻找使用户和网络提供方效用达到或接近Nash均衡下Pareto最优的QoS单播路径.仿真结果表明,该机制是可行和有效的.展开更多
基金the Natural Science Foundation of Anhui Province of China (050420212)the Excellent Youth Science and Technology Foundation of Anhui Province of China (04042069).
文摘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.
文摘Unlike the shortest path problem that has only one optimal solution and can be solved in polynomial time, the muhi-objective shortest path problem ( MSPP ) has a set of pareto optimal solutions and cannot be solved in polynomial time. The present algorithms focused mainly on how to obtain a precisely pareto optimal solution for MSPP resulting in a long time to obtain multiple pareto optimal solutions with them. In order to obtain a set of satisfied solutions for MSPP in reasonable time to meet the demand of a decision maker, a genetic algo- rithm MSPP-GA is presented to solve the MSPP with typically competing objectives, cost and time, in this pa- per. The encoding of the solution and the operators such as crossover, mutation and selection are developed. The algorithm introduced pareto domination tournament and sharing based selection operator, which can not only directly search the pareto optimal frontier but also maintain the diversity of populations in the process of evolutionary computation. Experimental results show that MSPP-GA can obtain most efficient solutions distributed all along the pareto frontier in less time than an exact algorithm. The algorithm proposed in this paper provides a new and effective method of how to obtain the set of pareto optimal solutions for other multiple objective optimization problems in a short time.
文摘Based on the theory of fuzzy decision making, a two phrase approach is proposed for the decentralized bi level linear programming problem(DBLPP). The approach considers the conflicts between the upper and lower levels decision makers (DMs), and among the lower level DMs themselves, a satisfactory solution is got with the non conflict matrix and decision power distribution. Compared with the other methods that have ever been proposed, the solution process is more fit to a kind of real decision making processes.
文摘下一代互联网NGI(Next Generation Internet)需要提供服务质量QoS(Quality of Service)路由能力,支持总最佳连接ABC(Always Best Connected).但是,由于链路状态的难以精确测量与用户QoS需求的难以准确表达,因此QoS路由基于的信息实际上是模糊的.同时,在网络运营日益商业化的环境下,支持ABC需要兼顾用户和网络提供方利益,考虑双方效用共赢.为此,文中引入模糊数学、概率论和博弈论知识,设计了一种ABC支持型QoS单播路由机制.该机制采用区间形式描述用户QoS需求和边(链路)参数,引入用户满意度和边评价,通过博弈分析,基于人工鱼群算法,寻找使用户和网络提供方效用达到或接近Nash均衡下Pareto最优的QoS单播路径.仿真结果表明,该机制是可行和有效的.