Interactive Adaptive-weight GA for Capacitated Multipoint Problem in communication Networks

カテゴリ: 部門大会

論文No: MC2-2

グループ名: 【C】平成17年電気学会電子・情報・システム部門大会講演論文集

発行日: 2005/09/06

タイトル(英語): Interactive Adaptive-weight GA for Capacitated Multipoint Problem in communication Networks

著者名: 姜英蔚 (早稲田大学)

著者名(英語): Yingwei Jiang(Waseda University)

キーワード: multipoint problem|minimum spanning tree problem|communication network|multiobjective genetic algorithm|priority-based encodingpareto optimal solutions

要約(日本語): Genetic Algorithm (GA) and other Evolutionary Algorithms (EAs) have been successfully applied to solve communication network design problems of the large, real-life instances. Choosing an appropriate representation of candidate solutions to the problem is the foundation for applying GAs to solve real world problems, since the encoding and the interaction of the encoding with the crossover, mutation and selection operators have strongly influence on the success of GAs.

In this paper, an interactive adaptive-weight genetic algorithm for Capacitated Multipoint Minmum Spanning Tree Problem (cmMSTP) in communication network is proposed. The capacitated multipoint problem is to find a set of links which connect communication nodes such that the cost (or delay) of the selected paths between pairs of nodes is minimized, and the constraints of network capacity and reliability are met. It is a well-known combinatorial optimization problem, namely, the constrained minimum spanning tree (cMST) problem. We investigate the different encoding, crossover and mutation operators on the performance of GAs to design of MST problems. Based on the performance analysis of these encoding methods in GAs, we improved predecessor-based encoding, in which initialization depends on an underlying random spanning-tree algorithm. Considering the characteristic of predecessor-based encoding, we propose new crossover and mutation operators. In addition, this paper also introduces a new genetic approach to the two conflicting objectives of minimizing cost and minimizing delay, the Interactive Adaptive-weight GA (i-awGA) that assigns weights to each objective and combines the weighted objectives into a single objective function. We compared with the recent approachs, and provide better results on larger instances.

PDFファイルサイズ: 15,582 Kバイト