ゲーム理論と最適化手法 第
6回
:遺伝的アルゴリズム
のプログラムの理解
上田 俊
佐賀大学理工学部 Email: [email protected] Web: https://www.fu.is.saga-u.ac.jp/sgrueda/
今日のプログラム
• https://www.fu.is.saga-
u.ac.jp/sgrueda/?page id=65 から Genetic Algorithm.xlsx と Genetic Algorithm.txt をダウンロード
• どちらかのボタンを右クリック → マク ロを登録 → 編集 でマクロの画面を開 き，テキストファイルの中身をコピー
巡回セールスマン問題
• N 個の都市と都市間の移動コスト ci,j が 与えられる．
• 全ての都市をひとつずつ回って最初の都 市に戻ってくる時に，最も移動コストの 小さい都市の巡回順を求める．
• 組合せ最適化問題のひとつ
• 可能な巡回順の数は? ⋆
N!
の計算時間
• ひとつの巡回順のコストの計算に 1 秒 かかるとする．
• 現代のコンピュータはもっと速い．
• N = 6 のとき ⋆
• 6! = 720 [s] = 12 [m]
• N = 9 のとき ⋆
• 9! = 6048 [m] = 4.2 [day]
• スターリングの公式 ⋆
• N! ∼ √
2πN(Ne)N = O(NN)
個体
(染色体
)の表現法
• どんな表現方法を使うか ⋆
• ナップサック問題では，各荷物 i を入れる (xi = 1) か入れない (xi = 0) で表現して いた．
• 順序表現 (order representation)
• i 番目の遺伝子が 1 以上 N −i+ 1 以下の いずれかの整数
• 例: x = (8 3 5 4 5 2 1 2 1)
順序表現の利点
• それぞれが 1 以上 N − i + 1 以下であれ ば，正しい巡回順に変換できる．
• 2回以上同じ都市に訪れたり，訪れない都 市が現れたりしない．
• ふたつの遺伝子から別の遺伝子を作ると き (交叉させるとき)，各遺伝子をそのま ま切り貼りできる．
• 突然変異も 1 以上 N − i + 1 以下の別の 数値に変えるだけで良い．
巡回順への変換方法
1 i 番目の遺伝子を j とする．
2 順序リストの j 番目の要素を i 番目に訪 問する都市の番号とみなし，i 番目に訪 問する都市を決める．
3 順序リストから j 番目の要素を削除 する．
交叉方法
(1/2)• 一点交叉
• ある一点を基準にふたつの遺伝子を入れ替 える．
• x1 = (8 3 5 | 4 5 2 1 2 1) と x2 = (6 2 5 | 3 5 2 2 1 1) から x′1 = (6 2 5 | 4 5 2 1 2 1) と
x′2 = (8 3 5 | 3 5 2 2 1 1) を作る．
交叉方法
(2/2)• 二点交叉
• 一点交叉のように遺伝子を入れ替える．正 し，入れ替えもとを変える基準が二点ある．
• 一様交叉
• 各遺伝子ごとにどちらの遺伝子をもとにす るかランダムに決める．
エリート保存戦略
• どの交叉方法でも，コストか小さくなる とは限らない．
• 最も良い (コストの小さい) 解をいくつ か保存しておくことで，後戻りすること が無いようにする．
• ただし，残しすぎると山登り方のように 局所最適解に落ち入りやすくなる．
遺伝的アルゴリズム
1 最初の世代をランダムに作成する．
2 for i = 1 to L (世代交代数) do
1 最良の個体をいくつか保存する．
2 repeat
1 親をふたつランダムに選ぶ．
2 {一点交叉，二点交叉，一様交叉}を用いて，
ふたつの子を作成する．
3 until 個体数が十分に集まる．
4 突然変異を何箇所かに起こす．
3 end for
今日のプログラム
(再掲
)• https://www.fu.is.saga-
u.ac.jp/sgrueda/?page id=65 から Genetic Algorithm.xlsx と Genetic Algorithm.txt をダウンロード
• どちらかのボタンを右クリック → マク ロを登録 → 編集 でマクロの画面を開 き，テキストファイルの中身をコピー
第
6回小レポート課題
• 自分の分野における，遺伝的アルゴリズ ムが適用できそうな問題とその理由を説 明しなさい．
• 解の組合せが指数的に増える問題を探す．
• 問題サイズを表すパラメータ N に対して，
可能な組合せが 2N や 3N, NN など．
• logN は増え方が指数的では無いので注意．
• 第 5 回レポートは欠番．
