DocumentCode :
1445949
Title :
Solving Multicommodity Capacitated Network Design Problems Using Multiobjective Evolutionary Algorithms
Author :
Kleeman, Mark P. ; Seibert, Benjamin A. ; Lamont, Gary B. ; Hopkinson, Kenneth M. ; Graham, Scott R.
Author_Institution :
Dept. of Electr. & Comput. Eng., Air Force Inst. of Technol., Dayton, OH, USA
Volume :
16
Issue :
4
fYear :
2012
Firstpage :
449
Lastpage :
471
Abstract :
Evolutionary algorithms can be applied to a variety of constrained network communication problems with centric type models. This paper shows that with real-world complex network communication problems of this type, sophisticated statistical search is required. This situation occurs due to the fact that these optimization problems are at least NP-complete. In order to appreciate the formal modeling of realistic communication networks, historical network design problems are presented and evolved into more complex real-world models with associated deterministic and stochastic solution approaches discussed. This discussion leads into the design of an innovative multiobjective evolutionary algorithm (MOEA) to solve a very complex network design problem variation called the multicommodity capacitated network design problem (MCNDP). This variation represents a hybrid real-world communication architecture as reflected in real-world network centric models with directional communications, multiple objectives including costs, delays, robustness, vulnerability, and operating reliability within network constraints. Nodes in such centric systems can have multiple and varying link capacities as well as rates and information (commodity) quantities to be sent and received. Each commodity can also have independent prioritized bandwidth and spectrum requirements. The nondominated sorting genetic algorithm (NSGA-II) is selected as the MOEA framework which is modified and parallelized to solve the generic MCNDP. Since the MCNDP is highly constrained but with an enormous number of possible network communication topologies, a novel initialization procedure and mutation method are integrated resulting in reduced search space. Empirical results and analysis indicate that effective topological Pareto solutions are generated for use in highly constrained, communication-based network design.
Keywords :
computational complexity; genetic algorithms; stochastic processes; telecommunication links; telecommunication network reliability; telecommunication network topology; MCNDP; MOEA; NP-complete problem; NSGA-II; centric type model; constrained network communication problem; delay; deterministic approach; directional communication; multicommodity capacitated network design problem; multiobjective evolutionary algorithm; network communication topology; nondominated sorting genetic algorithm; operating reliability; optimization problem; real-world complex network communication problem; robustness; statistical search; stochastic solution approach; vulnerability; Biological system modeling; Communication networks; Evolutionary computation; Government; Mathematical model; Network topology; Topology; Multicommodity capacitated networks; multiobjective evolutionary algorithms; network centric systems; network topology; pareto optimization;
fLanguage :
English
Journal_Title :
Evolutionary Computation, IEEE Transactions on
Publisher :
ieee
ISSN :
1089-778X
Type :
jour
DOI :
10.1109/TEVC.2011.2125968
Filename :
6151105
Link To Document :
بازگشت