Metropolitan Area Network Design Using GA Based on Hierarchical Linkage Identification

Miwako Tsuji, Masaharu Munetomo, and Kiyoshi Akama

Hokkaido University
North 11, West 5
Sapporo, 060-0811, Japan
{m_tsuji,munetomo,akama}@cims.hokudai.ac.jp

Abstract. Network design is a difficult combinatorial optimization problem which search-es an optimal network configuration that satisfies geographical constraints, user traffic constraints etc. from a huge number of candidates. In solving the problem with GAs, building block (BB) destructions occur frequently which misleads the algorithms to unfavorable local optima, because appropriate encoding only with prior knowledge is not usually an easy task. To overcome this difficulty, linkage identification techniques that identify linkage groups - sets of loci tightly linked to form BBs - must be employed. In addition, some real-world problems, especially large and complex problems, seem to have interactions not only among loci but among linkage groups in a hierarchical manner. Therefore we propose a hierarchical version the LIEM² [1] (Linkage Identification with Epistasis Measure considering Monotonicity) and apply it to the network design problem.

LNCS 2724, p. 1616 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003