分散遺伝的アルゴリズムを用いた巡回セールスマン問題

並列分散遺伝的アルゴリズムを用いた
巡回セールスマン問題の解法
知的システムデザイン研究室
16970056 水田伯典
Intelligent Systems Design Laboratory, Doshisha Univ.
巡回セールスマン問題 (TSP)
与えられた全都市を1回ずつ通って，
もとの都市に戻る最短巡回路を求める問題
Paris
Tokyo
Cairo
New
York
Sydney
Intelligent Systems Design Laboratory, Doshisha Univ.
巡回セールスマン問題 (TSP)
与えられた全都市を1回ずつ通って，
もとの都市に戻る最短巡回路を求める問題
Intelligent Systems Design Laboratory, Doshisha Univ.
巡回セールスマン問題 (TSP)
与えられた全都市を1回ずつ通って，
もとの都市に戻る最短巡回路を求める問題
Intelligent Systems Design Laboratory, Doshisha Univ.
巡回セールスマン問題 (TSP)
与えられた全都市を1回ずつ通って，
もとの都市に戻る最短巡回路を求める問題
Intelligent Systems Design Laboratory, Doshisha Univ.
巡回セールスマン問題 (TSP)
与えられた全都市を1回ずつ通って，
もとの都市に戻る最短巡回路を求める問題
Intelligent Systems Design Laboratory, Doshisha Univ.
巡回セールスマン問題 (TSP)
与えられた全都市を1回ずつ通って，
もとの都市に戻る最短巡回路を求める問題
Intelligent Systems Design Laboratory, Doshisha Univ.
巡回セールスマン問題 (TSP)
与えられた全都市を1回ずつ通って，
もとの都市に戻る最短巡回路を求める問題
実問題への様々な応用
基盤の配線
VLSIの設計
X線結晶構造解析
(タンパク質の構造解析) etc...
Intelligent Systems Design Laboratory, Doshisha Univ.
巡回セールスマン問題 (TSP)
与えられた全都市を1回ずつ通って，
もとの都市に戻る最短巡回路を求める問題
実問題への様々な応用
基盤の配線
VLSIの設計
X線結晶構造解析
(タンパク質の構造解析) etc...
Ｘ線を当てた回折像
Intelligent Systems Design Laboratory, Doshisha Univ.
巡回セールスマン問題 (TSP)
与えられた全都市を1回ずつ通って，
もとの都市に戻る最短巡回路を求める問題
実問題への様々な応用
基盤の配線
VLSIの設計
X線結晶構造解析
(タンパク質の構造解析) etc...
大幅な費用削減
時間短縮が可能
Intelligent Systems Design Laboratory, Doshisha Univ.
巡回セールスマン問題 (TSP)
与えられた全都市を1回ずつ通って，
もとの都市に戻る最短巡回路を求める問題
組み合わせ最適化問題
5都市問題 ‥ 12通りの巡回路
10都市 ‥ 181440通りの巡回路
・・
・
100都市 ‥ 4.6 ×10 155通り
すべての組み合わせを
計算することは不可能
Intelligent Systems Design Laboratory, Doshisha Univ.
分散GA(DGA)の操作
母集団を複数のサブ母集団に分割
各サブ母集団ごとに遺伝的操作を行う
一定期間ごとに異なるサブ母集団間で移住を行う
遺伝的操作
移住
Intelligent Systems Design Laboratory, Doshisha Univ.
研究背景と目的
DGAは単一母集団GA(SPGA)と比較して
連続最適化問題‥‥高品質の解が得られる
離散的最適化問題‥性能は明らかではない
・巡回セールスマン問題(TSP)における
DGAの性能を検証
・性能を向上させる新手法の提案
Intelligent Systems Design Laboratory, Doshisha Univ.
パラメータ
SPGAとDGAを比較
母集団サイズ
サブ母集団数
交叉法
交叉率
突然変異
突然変異率
移住間隔
移住率
対象問題
400
4, 16
枝交換交叉(EXX)
0.8
2-change法
1/ L
10世代
0.5
51都市問題(eil51)
Intelligent Systems Design Laboratory, Doshisha Univ.
枝交換交叉(EXX)
2 つの親の持つ枝のうち1つを交換する交叉法
親
枝交換
１
子
１
EXX
親
子
２
２
Intelligent Systems Design Laboratory, Doshisha Univ.
2-Change法
・任意の枝を1つ選び枝の終点を変更する
2-Change
Intelligent Systems Design Laboratory, Doshisha Univ.
パラメータ
SPGAとDGAを比較
母集団サイズ
サブ母集団数
交叉法
交叉率
突然変異
突然変異率
移住間隔
移住率
対象問題
400
4, 16
枝交換交叉(EXX)
0.8
2-change法
1/ L
10世代
0.5
51都市問題(eil51)
Intelligent Systems Design Laboratory, Doshisha Univ.
SPGAとDGAの比較結果
SPGAのほうがDGAより
収束が速い
DGAのほうが結果が
よくなる
SPGA, DGAともに
最適解は得られない
結果は30試行の平均値
Intelligent Systems Design Laboratory, Doshisha Univ.
TSPでのDGAの問題点
・探索後半に解が改善されない
母集団全体の個体の差がなくなっている
交叉法の枝交換がうまく機能していない
交叉によって最適解を得ることは困難
突然変異を用いて解を改善
Intelligent Systems Design Laboratory, Doshisha Univ.
最適解と局所解の比較
最適解: 距離428.8
局所解: 距離429.8
Intelligent Systems Design Laboratory, Doshisha Univ.
突然変異の効果
突然変異1回
局所解
突然変異2回
距離が長くなる距離が短くなる
429.8
431.1
429.5
2ヶ所の突然変異が同時に起こらなければ
巡回路は改善されない
Intelligent Systems Design Laboratory, Doshisha Univ.
最適解と局所解の比較
TSPにおいては突然変異によって
局所解からの脱出を行うことが困難
10ヶ所以上異なる
枝を突然変異により
作ることはできない
黒: 共通部分赤: 最適解青: 局所解
Intelligent Systems Design Laboratory, Doshisha Univ.
TSPでのDGAの問題点
・探索後半に解が改善されない
・突然変異では局所解から脱出が困難
(選択によって淘汰される)
SPGA, DGAでは
良好な結果を得ることは困難
Intelligent Systems Design Laboratory, Doshisha Univ.
新手法の提案
DGAの問題点
探索の後半に局所解に陥り脱出が困難
局所解を利用する
局所解に存在する
部分解を組み合わせて最適解を得る
Intelligent Systems Design Laboratory, Doshisha Univ.
提案手法の概念
枝をうまく組み合わせると最適解を得られる
DGAの結果得られた
巡回路
最適解
Intelligent Systems Design Laboratory, Doshisha Univ.
新手法の提案
DGAの問題点
探索の後半に局所解に陥り脱出不可能
局所解を利用する
局所解に存在する
部分解を組み合わせて最適解を得る
集中的に交叉のみを行う
集中多段交叉 (Centralized Multiple Crossover: CMX)
Intelligent Systems Design Laboratory, Doshisha Univ.
提案手法の操作(1)
エリートのみ集める
初
期
個
体
2-opt法による
・・・初期母集団での
局所解の生成
部分解の生成
母集団サイズまで
子を生成
Intelligent Systems Design Laboratory, Doshisha Univ.
提案手法の操作(2)
サブ母集団に
分割
交叉のみ繰り返す
・・
・
選択を行わないため
エリートの持つ部分解を
振り分けることが可能
移住無し
DGA
(iDGA)
又は
通常の
DGA
Intelligent Systems Design Laboratory, Doshisha Univ.
パラメータと対象問題
提案手法とDGAの性能を比較
母集団サイズ
サブ母集団数
交叉法
交叉率
突然変異
突然変異率
移住間隔
移住率
対象問題
400
16
枝交換交叉(EXX)
0.8
2-change法
1/ L
10世代
0.5
51都市問題(eil51)
Intelligent Systems Design Laboratory, Doshisha Univ.
51都市問題の結果
CMXはDGAより
高い性能を示す
CMXの適用回数が
多いほど性能が良い
結果は30試行の平均値
Intelligent Systems Design Laboratory, Doshisha Univ.
CMXを複雑な問題に適用
提案手法とDGAの性能を比較
母集団サイズ
サブ母集団数
交叉法
交叉率
突然変異
突然変異率
移住間隔
移住率
対象問題
400
16
枝交換交叉(EXX)
0.8
2-change法
1/ L
10世代
0.5
100都市問題
Intelligent Systems Design Laboratory, Doshisha Univ.
100都市問題の結果
CMXの適用回数
1 ‥ DGAより悪い
2 ‥ DGAより良い
5 ‥ DGAより良い
2回より悪い
結果は30試行の平均値
Intelligent Systems Design Laboratory, Doshisha Univ.
CMXの性能
DGAよりも高い性能を示した
課題
・適用回数を増やしても
性能が悪くなることがある
・適用回数が少ないとDGAより劣る
CMXの適用回数についての検討が必要
Intelligent Systems Design Laboratory, Doshisha Univ.
まとめ
結論
・ TSPを通常のDGAで解くことは困難
・提案手法はDGAよりも良好な性能を示す
・ CMXを複数回行うことでさらに性能が向上
今後の課題
・適切なCMX適用回数の設定
・提案手法の操作法の検討
・他の離散的問題への提案手法の適用
Intelligent Systems Design Laboratory, Doshisha Univ.
Intelligent Systems Design Laboratory, Doshisha Univ.
遺伝的アルゴリズム(GA)
遺伝的アルゴリズム(GA)
- 高い解探索能力
- 実装が容易
反復計算のため計算負荷が高い
処理の並列化
・・
・
島モデルの分散GA(DGA)
Intelligent Systems Design Laboratory, Doshisha Univ.
遺伝的アルゴリズム(GA)
生物の進化を模倣した確率的なアルゴリズム
母集団の生成
遺伝的操作(選択，交叉，突然変異)
遺伝的操作を繰り返し
個体を成長させる
最適解を得る
最適解
Intelligent Systems Design Laboratory, Doshisha Univ.
遺伝的アルゴリズム(GA)
生物の進化を模倣した確率的なアルゴリズム
母集団の初期化
評価
終了判定
選択
交叉
突然変異
繰り返しによる反復計算
計算回数が膨大に
・・
・
処理の並列化
島モデルの分散GA
Intelligent Systems Design Laboratory, Doshisha Univ.
遺伝的アルゴリズム(GA)
生物の進化を模倣した確率的なアルゴリズム
母集団の初期化 … 母集団をランダムに生成
… 各個体の適合度を計算
評価
終了判定
… 終了条件を満たせばGAの探索終了
選択
… 適合度に応じて次世代の個体を生成
交叉
… 2つの親個体の染色体の組み替えを
突然変異
行い子個体を生成
… 染色体上の遺伝子を置き換える
Intelligent Systems Design Laboratory, Doshisha Univ.
提案手法の操作
母集団サイズまで
子を生成
エリートのみ
集める
交叉
・・
・
親個体も残す
交叉のみ複数回
集中して行う(CMX)
個体数を増やす
エリートの持つ枝の振り分け
Intelligent Systems Design Laboratory, Doshisha Univ.
提案手法の流れ
初期母集団の生成 … 2-opt法を用いて個体を生成
… エリート個体を集める
個体を集める
CMX適用個体生成 … 交叉を用いて個体を増やす
交叉を連続して行う … 一定回数、交叉だけを
個体を分割
連続して行う
… 個体をサブ母集団に戻す
iDGAを行う
… 移住を行わないDGAを行う
Intelligent Systems Design Laboratory, Doshisha Univ.
提案手法の流れ
初期母集団の生成
個体を集める
CMX適用個体生成
交叉を連続して行う
CMXを繰り返す
個体を分割
iDGAを行う
CMX終了
通常のDGA
Intelligent Systems Design Laboratory, Doshisha Univ.
提案手法のパラメータ
1. 最初のCMX適用までの世代数
2. CMXを行う回数
3. CMXを行う世代間隔
4. CMXにおける多段交叉回数
5. CMXに適用する個体
Intelligent Systems Design Laboratory, Doshisha Univ.
150都市問題の結果
CMXは
適用回数によらず
DGAより優れている
適用回数を増やす
解の性能が高まる
結果は30試行の平均値
Intelligent Systems Design Laboratory, Doshisha Univ.
その他の交叉法
EXX以外の交叉法
・ Partially Mapped Crossover (PMX) [Goldberg
85]
・ Cycle Crossover (CX) [Oliver 87]
・ Subtour Exchange Crossover (SXX) [山村 92]
・ Edge Assembly Crossover (EAX) [永田 97]
・ EAXの性能は非常に高い
・提案手法に取り入れる場合,
用いる交叉法により性能が異なる
Intelligent Systems Design Laboratory, Doshisha Univ.
EAXの適用
枝組み立て交叉(Edge Assembly Crossover: EAX)
・ EXXよりも大域的な探索が可能な交叉法
・新たな枝を生成する能力が高い
(EXXでは親個体の持つ枝の交換のみ)
・ 3000都市以上の問題でも
最適解を得ることが可能
Intelligent Systems Design Laboratory, Doshisha Univ.
EAXの適用結果
CMXを適用すると
DGAよりも性能が高い
CMXの適用回数は
多い方が良い
150都市問題の結果
Intelligent Systems Design Laboratory, Doshisha Univ.
交叉回数ごとの性能
CMXはDGAよりも
性能が高い
CMXの適用回数を
増やすと性能があがる
51都市問題の結果
結果は30試行の平均値
Intelligent Systems Design Laboratory, Doshisha Univ.
交叉回数ごとの性能
CMXの適用回数
1 ‥ DGAより悪い
2 ‥ DGAより良い
5 ‥ DGAより良い
2回より悪い
100都市問題の結果
結果は30試行の平均値
Intelligent Systems Design Laboratory, Doshisha Univ.
交叉回数ごとの性能
CMXは
適用回数によらず
DGAより優れている
適用回数を増やす
解の性能が高まる
150都市問題の結果
結果は30試行の平均値
Intelligent Systems Design Laboratory, Doshisha Univ.
交叉回数ごとの性能
CMXを適用すると
DGAよりも性能が高い
CMXの適用回数は
多い方が良い
150都市問題の結果(EAX)
結果は30試行の平均値
Intelligent Systems Design Laboratory, Doshisha Univ.
枝交換交叉(EXX)
親１ { A B C D E F } ‥‥ { AB BC CD DE EF FA }
親２ { B F D A E C } ‥‥ { BF FD DA AE EC CB }
逆順
枝交換
{ AE ED DC CB EF FA }
{ AE BC CD DE EF FA }
{ BF FD DA AB BC CE }
{ BF FD DA AB EC CB }
枝交換
{ AE ED DC CB BF
FA }
‥‥ { A E D C B F } 子１
‥‥ { E F D A B C } 子２
{ EF FD DA AB BC
CE }
Intelligent Systems Design Laboratory, Doshisha Univ.

Download Report