A Self-controlled Genetic Algorithm for Communication Spanning Tree Problem

カテゴリ: 部門大会

論文No: OS3-3

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

発行日: 2006/09/05

タイトル(英語): A Self-controlled Genetic Algorithm for Communication Spanning Tree Problem

著者名: 林 林(早稲田大学),玄 光男(早稲田大学)

著者名(英語): Lin Lin(Waseda University),Mitsuo Gen(Waseda University)

キーワード: 通信ネットワーク|最小スパンニング木|遺伝的アルゴリズム|ファジィ・ロジック|Communication Network|Minimum Spanning Tree|Genetic Algorithm|Fuzzy Logic

要約(日本語): Genetic Algorithm (GA) and other Evolutionary Algorithms (EAs) have been successfully applied to solve constrained minimum spanning tree (MST) problems of the communication network design and also have been used extensively in a wide variety of communication network design problems. In this paper, we propose a self-control genetic algorithm (scGA) to communication spanning tree problem. This scGA adopts fuzzy logic control (FLC) for self-control the balance between exploration and exploitation. Main idea in the concept is adaptively regulation of stochastic search and heuristic search probabilities based on the change of the average fitness of parents and offspring which is occurred at each generation. In addition, we improved predecessor-based encoding, in which initialization depends on an underlying random spanning-tree algorithm. We compared with the recent approaches, and provide better results on larger instances.

PDFファイルサイズ: 9,307 Kバイト