解空間中の凹凸を判断することにより重複探索を避ける能力 を付加したハイブリッド遺伝的アルゴリズム

橘 達弘(0250161)


自然界の仕組みを模倣した組合せ最適化手法として遺伝的アルゴリズム (Genetic Algorithm、 以降GA)がある。 GAは、他の組合せ最適化手法と比較して計算量が大きいという欠点を持つ。そのため、適当な他の手法と組合せて欠点を補うハイブリッド手法について広く研究されている。

本研究では解空間内において個体間で情報を共有し、それぞれの個体に自律的に判断して探索する能力を持たせることにより、計算量当りの探索効率を向上させたハイブリッ ドGAを提案する。提案手法は、大域探索層と局所探索層の2層からなる。 大域探索層では、解空間中の地勢を考慮しつつ局所探索の起点を配置し、局所探 索層では、解空間中の同一局所解の探索の重複を避けつつ局所探索を行なう。 また提案手法に対する評価実験を行なった。

発表では、研究背景及び提案した手法とその実装、評価実験について述べる。