遗伝的アルゴリズムによる狈クイーン问题の解法
?
1 like?1,481 views
解析的な方法で解くことができず、Nか?増えることによって爆発的に解か?増えることて?知られている「Nクイーン問題」を、遺伝的アルゴリズム GA を用いて解く場合の解法について解説する
遗伝的アルゴリズムによる狈クイーン问题の解法
- 3. 従来の解法 現在のところこの問題を解析的な方法では解くことはできず、盤面に実際に駒を配置して確認しな ければならない 単純な組み合わせによる解法 効率的な解法バックトラック法 なぜ遺伝的アルゴリズムが効果的なのか とにかく n 個のクイー ンを置い てみて条件を満たし ているか調 べる すなわち、盤上の点n2から、n個 を選ぶ組み合わせ n2Cn 通り ex ) 64C8 = 4,426,165,368 (44億通り) 同じ行に2つ以上のクイーンは存 在できないため、N行に1個ずつ クイーンを並べる すなわち、1～Nまでの順列であ らわすことができる n! 通り ex ) 8! = 40, 320 クイーンを1個ずつ置いてい き、解が見つからないことが 判明した時点で、１つ前のク イーンの位置を違う位置に変 更して探索する 参考: 安本 慶一 : アルゴリズム概論 http://www.aist-nara.ac.jp/~yasumoto/lecture/algorithm2012/algo2012-6.pdf 3
- 4. GAの応用ポイント 2. 解の明確な評価方法があるか 3. 解を遺伝子表現できるか1. 問題がGAに適しているか 複数の個体間で選択や交叉などの遺伝的操作により相互協力的に解の探索を行っているため単純な並 列的探索に比べてより良い解が見つかりやすく、問題が多くの組み合わせの中から解を求めるような 性質を持つ場合に有効 Nクイーン問題は盤上の点n2か ら、n個を選ぶ組み合わせの中 から解を求めるため、遺伝的ア ルゴリズムの問題として適して いる 解の評価方法が不明確だと、各 個体の適応度の定義も不明確に なり、無意味に多くの解候補が えられる。 Nクイーン問題は全てのクイー ンが互いに競合しないという明 確な解の評価方法が存在する Nクイーン問題がGAに適しているかを考える 詳しくは後述するが、解候補は 全て1~Nの順列として表現でき 遺伝子表現が可能である。 Q Q Q Q Q Q Q Q 5 7 1 3 8 6 4 2 (遺伝子表現) 参考: 萩原 将文 著: ニューロ?ファジィ?遺伝的アルゴリズム p159 4
- 5. GAによる解法 開始 Step1: 遺伝子型の決定 Step2: 初期遺伝子集団の決定 Step6: 突然変異 Step5: 交叉 Step4: 選択(淘汰と増殖) Step3: 各個体の適応度 の評価基準をみ たしているか 終了 Step1. 対象となる問題からPTYPE/GTYPE(遺伝子 型)を決定する 遺伝的アルゴリズムの基本手順 遺伝的アルゴリズムの全体の流れは以下の7つのステップにより構成される。 Step2. 要素がことなる様々な固体をランダムに発 生させる。 Step3. 各個体の適応度をあらかじめ定めた方法で 計算する。 Step4. 交叉を行うための個体の生存分布を決定 Step5. 2つの個体の遺伝子を組み替えて、新しい個 体を生成させる Step6. 遺伝子のある部分を強制的に変更する 参考: 萩原 将文 著: ニューロ?ファジィ?遺伝的アルゴリズム p99-101 5
- 6. Step 1: 遺伝子型の決定 PTYPE GTYPE 解の最低条件 同じ列に二つ以上のクイーンは存在しない 開始 Step1: 遺伝子型の決定 Step2: 初期遺伝子集団の決定 Step6: 突然変異 Step5: 交叉 Step4: 選択(淘汰と増殖) Step3: 各個体の適応度 の評価基準をみ たしているか 終了 対象となる問題からPTYPE/GTYPE(遺伝子型)を決定する Q Q Q Q Q Q Q Q 盤上のクイーンの配置をそのま まPTYPE(表現型)として定義す る すなわち、盤を左から右に見てクイーンの位 置する行数を1～Nの順列で表現できる 5 7 1 3 8 6 4 2 参考: 伊藤 斉志 著: 遺伝的アルゴリズムの基礎 p38-39 6
- 7. 順列表現によるGTYPEの問題 5 7 1 3 8 6 4 2 Q Q Q Q Q Q Q Q 現状の順列表現によるGTYPEでは交叉時に同じ行にクイーンをもつ個体が生まれてしまう。このた め交差によって解としての最低条件を満たさない個体(致死遺伝子)が生まれてしまう 交叉による致死遺伝子の発生 1 7 5 3 6 6 4 2 Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q 1 7 5 3 6 2 8 4 5 7 1 3 8 2 8 4 交叉 親1 親2 子1 子2 参考: 伊藤 斉志 著: 遺伝的アルゴリズムの基礎 p39 7
- 8. 1 2 3 4 5 6 7 8 Step1’: 遺伝子型の再設計 効果的な探索のためには遺伝子型表現の工夫(順序表現)や、交叉方法の工夫(部分一致交叉)によって 致死遺伝子の発生を抑える必要があり、ここでは順序表現を使い致死遺伝子の発生を抑える。 順序表現を使った致死遺伝子発生の抑制 2. 順序表現への変換 3. 全てのクイーンに適応1. 配置行リストの作成 クイーンを配置する行の順番に 並べた配置行リストを作成する。 ここでは上の行から順番にク イーンを配置するとし、リスト を作成する。 次に配置する行のクイーンの列 が、リストの左から何番目にあ るのかを調べてその数字に置き 換える。その後リストから配置 した行を取り除く 1-2の手順を全てのクイーンに 対して適応する。 Q Q Q Q Q Q Q Q 参考: 萩原 将文 著: ニューロ?ファジィ?遺伝的アルゴリズム p146-148 8
- 9. 順序表現への変換例 以下のクイーンの配置を順列表現から順序表現に変換する手順を示す。 1 2 3 4 5 6 7 8 5 7 1 3 8 6 4 2 1 2 3 4 5 6 7 8 １ 1 2 3 4 6 7 8 5 7 1 3 8 6 4 2 1 2 3 4 5 6 7 2 2 3 4 6 8 5 6 1 3 8 6 4 2 1 2 3 4 5 4 1 2 3 4 6 8 5 6 1 3 8 6 4 2 1 2 3 4 5 6 3 2 4 5 6 1 2 4 3 4 2 1 2 7 2 4 6 8 5 6 1 2 8 6 4 2 1 2 3 4 5 2 4 6 5 6 1 2 4 6 4 2 1 2 3 6 2 5 6 1 2 4 3 2 2 1 8 リスト 順列表現 5 6 1 2 4 3 2 1順序表現 9
- 10. Step 2: 初期遺伝子集団の決定 少なすぎると並列的な 処理を特徴とする遺伝 的アルゴリズムの良さ が発揮されない 大体のNクイーン問題では20個程の個体をランダ ムで発生させる Step1で決定した遺伝子型で、要素がことなる様々な固体をランダムに発生させる。発生させる個体 数は問題の難易度や性質によるが一般的に数十件以上発生させる。 少なすぎる場合 多すぎる場合 多すぎると１世代あたり の計算量が大きくなり無 駄がおおくなってしまい 非効率になる 開始 Step1: 遺伝子型の決定 Step2: 初期遺伝子集団の決定 Step6: 突然変異 Step5: 交叉 Step4: 選択(淘汰と増殖) Step3: 各個体の適応度 の評価基準をみ たしているか 終了 参考: 萩原 将文 著: ニューロ?ファジィ?遺伝的アルゴリズム p100 10
- 11. 解の条件 全てのクイーンが互いに競合しないこと 適応度 クイーンが競合する数が少ない = 適合度が高い 目的関数 最大値が1になるように目的関数を定める ? ? + ??(?????) ※ NQ(PTYPE)はPTYPEの表す配置でクイーンの 競合する数を示す Step 3: 適応度の評価 開始 Step1: 遺伝子型の決定 Step2: 初期遺伝子集団の決定 Step6: 突然変異 Step5: 交叉 Step4: 選択(淘汰と増殖) Step3: 各個体の適応度 の評価基準をみ たしているか 終了 各個体の適応度を計算する目的関数を定義する。集団の中にあらかじめ定めた基準を満足する個体が あるかチェックし、あれば終了、なければ次のステップへ進む 目的関数の定義 参考: 伊藤 斉志 著: 遺伝的アルゴリズムの基礎 p39 11
- 12. 集団の中で適応度の１番低い個体を適応度の１番高 い個体で置き換える方式。 Step 4: 選択(淘汰と増殖) 開始 Step1: 遺伝子型の決定 Step2: 初期遺伝子集団の決定 Step6: 突然変異 Step5: 交叉 Step4: 選択(淘汰と増殖) Step3: 各個体の適応度 の評価基準をみ たしているか 終了 Step3で求めた適応度に基づいて、次のステップで交叉を行う個体の生存分布を決定する。 単純なエリート保存選択法 淘汰 増殖 1 6 4 5 1 2 2 1 1 3 2 4 1 1 1 1 1 2 1 3 8 6 4 2 5 7 1 3 4 2 1 1 1 6 4 5 1 2 2 1 1 6 4 5 1 2 2 1 1 3 2 4 1 1 1 1 1 2 1 3 8 6 4 2 適応度 0.9 0.7 0.6 0.3 0.9 0.7 0.6 0.9 適応度 参考: 萩原 将文 著: ニューロ?ファジィ?遺伝的アルゴリズム p102-103 12
- 13. 交叉位置 ２つの遺伝子を組にして、交叉位置をランダムに 選択する。 Step 5: 交叉 開始 Step1: 遺伝子型の決定 Step2: 初期遺伝子集団の決定 Step6: 突然変異 Step5: 交叉 Step4: 選択(淘汰と増殖) Step3: 各個体の適応度 の評価基準をみ たしているか 終了 2つの個体の遺伝子を組み替えて、新しい個体を生成させる。 新しい個体の生成 要素の交換 交叉位置を境にして遺伝子の要素を互いに交換す る 1 6 4 5 1 2 2 1 1 3 2 4 1 1 1 1 1 6 4 5 1 1 1 1 1 3 2 4 1 2 2 1 13
- 14. ２つの遺伝子を組にして、交叉 位置をランダムに選択する。 補足: 部分一致交叉 順序表現を使わずに，順列表現のまま交叉方法の工夫(部分一致交叉)によって致死遺伝子の発生を抑 えることが可能 2. 対応するシンボルを作成 3. シンボル同士を交換1. 交叉させる位置を決定 部分一致交叉を使った致死遺伝子発生の抑制 1 3 8 7 2 4 5 6 7 5 2 6 4 8 1 3 交叉させる要素から、同じ位置 に対応する各要素のシンボルの 組を作る。 交叉位置 交叉位置 1 3 8 7 2 4 5 6 7 5 2 6 4 8 1 3 各個体において対応させたシン ボル同士を交換する 1 3 8 6 4 2 5 7 7 5 2 6 4 8 1 3 参考: 萩原 将文 著: ニューロ?ファジィ?遺伝的アルゴリズム p146-148 14
- 15. 順序表現においては変異する遺伝子を適切な数字 から選択する必要がある 数字の選択 一般に順序表現では第i番目の遺伝子に可能な数字 は，1,2,3,???,N-i+1である。 GTYPE(12312)の場合 第１の遺伝子が突然変位する場合、変異後の候補 は2,3,4,5であり，第２の遺伝子では1,3,4となる。 Step 6: 突然変異 開始 Step1: 遺伝子型の決定 Step2: 初期遺伝子集団の決定 Step6: 突然変異 Step5: 交叉 Step4: 選択(淘汰と増殖) Step3: 各個体の適応度 の評価基準をみ たしているか 終了 遺伝子のある要素を一定の確率で強制的に変更し、遺伝子集団のばらつきを大きくすることでより良 い解を持つ個体の発生を期待する。 順序表現による突然変異 参考: 伊藤 斉志 著: 遺伝的アルゴリズムの基礎 p34 15
- 16. GAのまとめ 適用における全体の流れ 結局問題が与えられた際に各ステップでしなければならないことは以下である Step1. 遺伝子型の決定 ?GTYPE/PTYPEの定義 Step2. 初期遺伝子集団の生成 ?個体数の設定 ?ランダムな個体を生成 Step3. 適応度の計算 ?適応度の定義 ?目的関数の設計 Step4.選択(淘汰と増殖) ?選択方式の選択 Step5.交叉 ?交叉方法の選択 ?交叉の組をランダムに決定 ?交叉位置をランダムに決定 Step5.突然変異 ?突然変異確率の設定 16
- 17. 16クイーン問題の場合、遺伝的アルゴリズムで解いた場合、従来の解法に比べ約212倍効率が良い。 ちなみに16クイーン問題の解は14772512(≒15?106)個存在する GAと従来の解法との比較 単純な組み合わせによる解法 効率的な解法 遺伝的アルゴリズム 盤上の点n2から、n個を選ぶ組み 合わせ n2Cn 通り 256C16≒10抒(10?1028)通り (10?1028)/(15?106) 平均 6.7?1021 回 必要 1～Nまでの順列であらわすこ とができ n! 通り 16! ≒21兆(21?1012)通り (21?1012)/(15?106) 平均 6.7?1021 回必要 変数の設定値などの細かいこと はこの際いいとして、あるGA では 283世代目 評価数5660回 １６クイーン問題の場合 参考: 伊藤 斉志 著: 遺伝的アルゴリズムの基礎 p41 17