確率モデル遺伝的アルゴリズムＥＨＢＳＡにおける戦略、パラメータの調査１Ｇ０１Ｐ０４６７酒井大輔 1 背景と動機 • 厳密解を求めることの難しい問題について近似解を求める手法の必要性が高まっている（例：データマイニング、生命情報学） • このような手法として遺伝的アルゴリズム（ＧＡ）がある。しかし従来のＧＡは直観性に欠け、その分広い範囲の応用が難しい。またパラメータなどに直観性に欠け計算時間もかかるという問題がある。 • 生物の高い探索能力とコンピュータへ素直に実装可能な手法として確率モデルＧＡに着目した • 実際への応用はほとんど研究されていないが、ＴＳＰについての解法であるＥＨＢＳＡがあるのでそれを調べた。 2 確率モデルＧＡ • 従来のＧＡは交叉と突然変異を用いて子個体を生成 • 確率モデルＧＡは集団の個体分布を確率モデルで近似し、それを基に子個体を生成 • 従来のＧＡに比べ高い探索能力が期待されている初期集団の選択確率モデルを基に次世代の個体を生成遺伝オペレータによって次世代の個体を生成終了条件？ 3 ＥＨＢＳＡ(edge histogram based sampling algorithm) 1. 個体をランダムに生成する 2. 選択オペレータを用い、有望集団を作る 3. 有望集団からＥＨＭ(edge histogram matrix) を作成する 4. ＥＨＭを基に子個体をサンプリングする 5. 終了条件が満たされるまで２から５を繰り返す 4 実装 • EHBSAアルゴリズムを複数のフェーズに分け、各フェーズごとにいくつかの戦略を選択できるようにした。その際、計測を効率的にするため、パラメータの直積を計算し、それを基に計測しグラフ化するユーティリティを作成した。 • プログラミング言語はOCaml を用い、MPIを使った並列化も行った • ehbsawo, ehbsawt, mpiehbsawo, mpiehbsawt を実装パラメータの基となるファイルを手動で作成直積を計算計測 or グラフ化 5 集団数集団の選択 ×４ templateの選択 sampling nodeの選択送受信数送信受信 ×４、×４カット数 ×３、×２ＥＨＭの作成 ×２局所的改善手法 ×２ 6 実験結果の例 70000 60000 50000 40000 戦略１戦略２戦略３ 30000 20000 10000 0 0世代５０世代１００世代戦略１：工夫なし戦略２：ＥＨＭの重み付け、2opt 戦略３：戦略２のＭＰＩ版、送受信はエリート戦略１５０世代都市数：４００集団数：１００集団の選択法：エリート戦略 7 実験結果のまとめ • 初期集団の選択の戦略ではエリート戦略、トーナメント戦略が優れていて計算時間、解の精度共に同程度の性能を示した • ＥＨＭの重み付け戦略は有効である • EHBSAWTでのカット数は増やすと世代交代にかかる時間は少なくなるが解の精度は悪化する • 集団数は都市数の４分の１程度が適切で、収束には１００世代程度かかる。これは都市の数に依存しない • 送受信の戦略はエリート戦略が適切で、解の精度が1.3倍から1.6倍程度向上した外乱効果を増やすことで性能向上できる可能性 8