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.展开更多
The minimal unsatisfiability problem is considered of the prepositional formulas in CNF which in the case of variablesx 1,?,x n consist ofn +k clauses including it,x 1 V ? Vx n and ?x 1 V ? V ?x n It is shown that whe...The minimal unsatisfiability problem is considered of the prepositional formulas in CNF which in the case of variablesx 1,?,x n consist ofn +k clauses including it,x 1 V ? Vx n and ?x 1 V ? V ?x n It is shown that whenk ?4 the minimal unsatisfiability problem can be solved in polynomial time.展开更多
基金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.
基金Project supported by the National Natural Science Foundation of China (Grant No. 19771045)Nationl High-Tech R&D Project (863) (Grant No. 863-306-ET06-01-2).
文摘The minimal unsatisfiability problem is considered of the prepositional formulas in CNF which in the case of variablesx 1,?,x n consist ofn +k clauses including it,x 1 V ? Vx n and ?x 1 V ? V ?x n It is shown that whenk ?4 the minimal unsatisfiability problem can be solved in polynomial time.
