第55回 月例発表会（2002年11月） 知的システムデザイン研究室 遺伝的アルゴリズムに組み込んだローカルサーチのパラメータおよび実装の検討 斉藤 宏樹
1 今月の課題
今月の課題は，遺伝的アルゴ リズム（ Simple GA）に ローカルサーチを組み込み，パラメータおよび実装の検 討を行うことである．2 課題の進捗状況
2.1 ローカルサーチを組み込んだ SGA 作成した SGA に対して，Fig. 1 に示すようにローカ ルサーチを組み込む． trial>max_trial Crossover Mutation Select Local_search VTKCNKPVGTXCN = ҁ Evaluate Fig. 1 SGAのフローチャートの一部 ローカルサーチは，SGA における評価と選択の間で 行われ，評価された母集団の中で一番適合度高い個体を 抽出して行う．そして，設定したある一定間隔で行う． 2.2 ローカルサーチのモデル ローカルサーチでは，次の４つのモデルを実装する．• LF モデル（Linear Flip Model）
初期点だけランダ ムに遺伝子を選び ，その点から 順にフリップを行う．適合度が現在の値よりも良く なった時点で探索を終了するモデル．
• LF/SP モデル（Linear Flip for a Set Period
Model）
初期点だけランダムに遺伝子を選び，その点から順 にフリップを行う．規定した評価回数分だけ探索を 行い，その中から一番適合度の高いものを選択する モデル．
• RF モデル (Random Flip Model）
ランダムに選んだ遺伝子に対してフリップを行う． 適合度が現在の値よりも良くなった時点で探索を終 了するモデル．
• RF/SP モデル (Random Flip for a Set Period
Model） ランダ ムに選んだ遺伝子に対してフリップを行う． 規定した評価回数分だけ探索を行い，その中から一 番適合度の高いものを選択するモデル． 2.3 数値実験 ローカルサーチを組み込んだ SGA のパラ メータを Table 1に示す．なお，選択はトーナメント選択である． Table 1 SGAのパラメータ 個体数 100 突然変異率 0.001 遺伝子長 1000 エリート保存 1 交叉 一点交叉 終了世代 500 交叉率 1.0 試行回数 20 ４つのモデルでローカルサーチ間隔を 1，5，10，50， 100に変えて，Onemax 問題を解き，20 回試行におけ る各世代の評価計算回数と適合度の中央値を計算した． LF/SP，RF/SP モデルついては，1 回のローカルサー チ時における評価計算回数を 100 と規定した．結果を Fig. 2に示す． 㪌㪌㪇 㪍㪇㪇 㪍㪌㪇 㪎㪇㪇 㪎㪌㪇 㪏㪇㪇 㪏㪌㪇 㪐㪇㪇 㪐㪌㪇 㪈㪇㪇㪇 㪇㪅㪇㪜㪂㪇㪇 㪈㪅㪇㪜㪂㪇㪋 㪉㪅㪇㪜㪂㪇㪋 㪊㪅㪇㪜㪂㪇㪋 㪋㪅㪇㪜㪂㪇㪋 㪌㪅㪇㪜㪂㪇㪋 㩺㪜㫍㪸㫃㫌㪸㫋㫀㫆㫅㫊 㪝 㫀㫋 㫅㪼㫊 㫊 㫎㫀㫋㪿㫆㫌㫋㩷㫃㫆㪺㪸㫃㩷㫊㪼㪸㫉㪺㪿 㫀㫅㫋㪼㫉㫍㪸㫃㩷㪈 㫀㫅㫋㪼㫉㫍㪸㫃㩷㪌 㫀㫅㫋㪼㫉㫍㪸㫃㩷㪈㪇 㫀㫅㫋㪼㫉㫍㪸㫃㩷㪌㪇 㫀㫅㫋㪼㫉㫍㪸㫃㩷㪈㪇㪇 (a) LF モデル 㪌㪌㪇 㪍㪇㪇 㪍㪌㪇 㪎㪇㪇 㪎㪌㪇 㪏㪇㪇 㪏㪌㪇 㪐㪇㪇 㪐㪌㪇 㪈㪇㪇㪇 㪇㪅㪇㪜㪂㪇㪇 㪈㪅㪇㪜㪂㪇㪋 㪉㪅㪇㪜㪂㪇㪋 㪊㪅㪇㪜㪂㪇㪋 㪋㪅㪇㪜㪂㪇㪋 㪌㪅㪇㪜㪂㪇㪋 㩺㪜㫍㪸㫃㫌㪸㫋㫀㫆㫅㫊 㪝 㫀㫋 㫅㪼㫊 㫊 㫎㫀㫋㪿㫆㫌㫋㩷㫃㫆㪺㪸㫃㩷㫊㪼㪸㫉㪺㪿 㫀㫅㫋㪼㫉㫍㪸㫃㩷㪈 㫀㫅㫋㪼㫉㫍㪸㫃㩷㪌 㫀㫅㫋㪼㫉㫍㪸㫃㩷㪈㪇 㫀㫅㫋㪼㫉㫍㪸㫃㩷㪌㪇 㫀㫅㫋㪼㫉㫍㪸㫃㩷㪈㪇㪇 (b) LF/SP モデル 㪌㪌㪇 㪍㪇㪇 㪍㪌㪇 㪎㪇㪇 㪎㪌㪇 㪏㪇㪇 㪏㪌㪇 㪐㪇㪇 㪐㪌㪇 㪈㪇㪇㪇 㪇㪅㪇㪜㪂㪇㪇 㪈㪅㪇㪜㪂㪇㪋 㪉㪅㪇㪜㪂㪇㪋 㪊㪅㪇㪜㪂㪇㪋 㪋㪅㪇㪜㪂㪇㪋 㪌㪅㪇㪜㪂㪇㪋 㩺㪜㫍㪸㫃㫌㪸㫋㫀㫆㫅㫊 㪝 㫀㫋 㫅㪼㫊 㫊 㫎㫀㫋㪿㫆㫌㫋㩷㫃㫆㪺㪸㫃㩷㫊㪼㪸㫉㪺㪿㫀㫅㫋㪼㫉㫍㪸㫃㩷㪈 㫀㫅㫋㪼㫉㫍㪸㫃㩷㪌 㫀㫅㫋㪼㫉㫍㪸㫃㩷㪈㪇 㫀㫅㫋㪼㫉㫍㪸㫃㩷㪌㪇 㫀㫅㫋㪼㫉㫍㪸㫃㩷㪈㪇㪇 (c) RF/モデル 㪌㪌㪇 㪍㪇㪇 㪍㪌㪇 㪎㪇㪇 㪎㪌㪇 㪏㪇㪇 㪏㪌㪇 㪐㪇㪇 㪐㪌㪇 㪈㪇㪇㪇 㪇㪅㪇㪜㪂㪇㪇 㪈㪅㪇㪜㪂㪇㪋 㪉㪅㪇㪜㪂㪇㪋 㪊㪅㪇㪜㪂㪇㪋 㪋㪅㪇㪜㪂㪇㪋 㪌㪅㪇㪜㪂㪇㪋 㩺㪜㫍㪸㫃㫌㪸㫋㫀㫆㫅㫊 㪝 㫀㫋 㫅㪼㫊 㫊 㫎㫀㫋㪿㫆㫌㫋㩷㫃㫆㪺㪸㫃㩷㫊㪼㪸㫉㪺㪿 㫀㫅㫋㪼㫉㫍㪸㫃㩷㪈 㫀㫅㫋㪼㫉㫍㪸㫃㩷㪌 㫀㫅㫋㪼㫉㫍㪸㫃㩷㪈㪇 㫀㫅㫋㪼㫉㫍㪸㫃㩷㪌㪇 㫀㫅㫋㪼㫉㫍㪸㫃㩷㪈㪇㪇 (d) RF/SP モデル Fig. 2 実験結果 Table 1のパラメータの場合，ローカルサーチ間隔が 1，5，10 のときに，LF と RF モデルが，ローカルサー チを用いな SGA よりも有効であることがわかった．
