遺伝的アルゴリズムにおける個体の優劣度に基づく適応的パラメータ値設定手法

概要

論文の詳細を見る
NP困難なクラスに属する組合せ最適化問題の解法の一つとして近年注目を集めている手法に遺伝的アルゴリズム(GA)がある。遺伝的アルゴリズムとは生物の遺伝機構に着想を得た確率的探索手法であり, 実用的な時間で質の良いヒューリスティック解を出力することが知られている。GAにおいて, パフォーマンスを向上させるためには適切なパラメータ値の設定が必要となるが, パラメータ値の調整に多大の計算時間を要したり, 適切なパラメータ値の設定が行なえないという問題がある。適応的遺伝的アルゴリズムは, GAの実行中に対象とする問題のインスタンスの性質に合わせてGAを制御するパラメータ値を自動的に調整する機構をもつGAである。そのため, 従来のGAに対しては必要であった, ベンチマーク等を用いたパラメータ調整のための試行実験が不用になる。また, 問題のインスタンスに合わせたパラメータの動的な調整が可能となる。しかしパラメータ値を調整する際に, 何を基準に調整すればよいかという指標に適切なものは知られていない。著者らは, 個体の潜在的な優劣の度合を示す指標であるエリート度を提案し, これをもとにパラメータ値を調整する適応的遺伝的アルゴリズムを提案している。提案手法では, 従来の適応的GAとは異なり, 個体が生成された履歴に注目することにより個体の潜在的な優劣の度合を予測することが可能となり, GAの探索能力が向上する。文献[2]においては, 著者らはGAの探索能力に大きな影響を及ぼす交差について, 交差の対象となる個体のエリート度に基づいて交差手法を動的に選択する手法を提案した。しかしGAのパフォーマンスを決定するパラメータには多くの種類があり, 交差手法のみの調整でGAの性能を最大限に引き出すことは困難である。本稿では, 遺伝操作の中で交差と並んでGAのパフォーマンスに大きな影響を持つ突然変異に着目し, エリート度に基づく突然変異確率の動的調整手法を提案し, シミュレーション実験により提案手法の有効性を検証する。
一般社団法人情報処理学会の論文
1997-09-24

遺伝的アルゴリズムにおける個体の優劣度に基づく適応的パラメータ値設定手法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク