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

分散遺伝的アルゴリズムを用いた
巡回セールスマン問題の解法
三木
廣安
○ 水田
吉田
光範（同志社大学工学部）
知之（同志社大学工学部）
伯典（同志社大学 [学] ）
純一（同志社大学 [院] ）
Intelligent Systems Design Laboratory
遺伝的アルゴリズム(Genetic
Algorithm:GA)
生物の進化を模倣した確率的なアルゴリズム
母集団の生成
遺伝的操作(選択，交叉，突然変異)
遺伝的操作を繰り返し
個体を成長させる
最適解を得る
最適解
Intelligent Systems Design Laboratory
処理の並列化
GAの処理は計算負荷が高い
並列化によって計算負荷を分散させ
処理速度を向上させる
並列化のモデル
・島モデルの分散GA
・近傍モデル
Intelligent Systems Design Laboratory
分散GA(DGA)の操作
母集団を複数の
サブ母集団に分割
各サブ母集団ごとに
遺伝的操作を行う
一定期間ごとに異なる
サブ母集団間で移住を行う
Intelligent Systems Design Laboratory
DGAの性能
DGAは単一母集団GA(SPGA)と比較して
連続最適化問題‥‥高品質の解が得られる
離散的最適化問題‥性能は明らかではない
・巡回セールスマン問題(TSP)における
DGAの性能を検証
・性能を向上させる新手法の提案
Intelligent Systems Design Laboratory
パラメータ
SPGAとDGAを比較
母集団サイズ
サブ母集団数
交叉法
交叉率
突然変異
突然変異率
移住間隔
移住率
対象問題
400
4, 16
枝交換交叉(EXX)
0.8
2-change法
0.4/L
5世代
0.5
51都市問題(eil51)
Intelligent Systems Design Laboratory
枝交換交叉(EXX)
2 つの親の持つ枝のうち1つを交換する交叉法[前川95]
親
１
枝交換
EXX
子
１
親
子
２
２
Intelligent Systems Design Laboratory
2-Change法
・任意の枝を1つ選び枝の終点を変更する
・変更した後の枝を元の枝よりも短くする
2-Change
Intelligent Systems Design Laboratory
TSPにおけるDGAの性能
SPGAとDGAを比較
母集団サイズ
サブ母集団数
交叉法
交叉率
突然変異
突然変異率
移住間隔
移住率
対象問題
400
4, 16
枝交換交叉(EXX)
0.8
2-change法
0.4/L
5世代
0.5
51都市問題(eil51)
Intelligent Systems Design Laboratory
SPGAとDGAの比較結果
DGAのほうがSPGAより
収束が速い
DGAでは探索後半に
改善がみられなくなる
10試行の結果では
SPGA, DGAともに
最適解は得られなかった
値は10試行の平均値
Intelligent Systems Design Laboratory
TSPでのDGAの問題点
・探索後半に解が改善されない
母集団全体の個体の差がなくなっている
交叉法の枝交換がうまく機能していない
通常の交叉によって最適解を得ることは困難
突然変異を用いて解を改善
Intelligent Systems Design Laboratory
最適解と局所解の比較
最適解: 距離428.8
局所解: 距離429.8
Intelligent Systems Design Laboratory
突然変異の効果
局所解
突然変異1回
突然変異2回
距離が長くなる距離が短くなる
2ヶ所の突然変異が同時に起こらなければ
巡回路は改善されない
Intelligent Systems Design Laboratory
最適解と局所解の比較
TSPにおいては突然変異によって
局所解からの脱出を行うことができない
10ヶ所以上異なる
枝を突然変異により
作ることはできない
黒: 共通部分赤: 最適解青: 局所解
Intelligent Systems Design Laboratory
TSPでのDGAの問題点
・探索後半に解が改善されない
・ TSPにおいては突然変異によって
局所解からの脱出を行うことができない
SPGA, DGAでは
良好な結果を得ることは困難
Intelligent Systems Design Laboratory
新手法の提案
・探索後半に解が改善されない
一定世代まで移住を行わないDGA
isolated DGA(iDGA)
・突然変異で局所解から脱出できない
集中的に交叉のみを行う
集中多段交叉
Centralized Multiple Crossover(CMX)
Intelligent Systems Design Laboratory
iDGAの結果生成されたルート
51都市問題
サブ母集団数：8
800世代における
各サブ母集団の
エリートの様子
赤：最適解(4以上) 青：最適解(2,3個) 黒：局所解(4以上)
緑：最適解(1個)
Intelligent Systems Design Laboratory
iDGAの結果生成されたルート
51都市問題
サブ母集団数：8
800世代における各サブ
母集団のエリートの様子
すべてのエリートから
最適解が構成できる
赤：最適解黒：局所解(4以上)
枝をうまく組み合わ
せると最適解を
得られる
Intelligent Systems Design Laboratory
提案手法の操作
エリートのみ
集める
母集団サイズまで
交叉により子を生成
サブ母集団
に分割
交叉のみを行う(CMX)
・・
・
移住なしDGA ・
・・母集団全体の
(iDGA)
選択を行わないため
エリートの持つ枝を
振り分けることが可能
多様性があがる
Intelligent Systems Design Laboratory
パラメータと対象問題
提案手法とDGAの性能を比較
母集団サイズ
サブ母集団数
交叉法
交叉率
突然変異
突然変異率
移住間隔
移住率
対象問題
800
32
枝交換交叉(EXX)
0.8
2-change法
0.4/L
5世代
0.5
51都市問題(eil51)
Intelligent Systems Design Laboratory
51都市問題への適用
800,900世代目で
CMX適用
提案手法はDGAと
比較して高い性能を
示す
CMXの適用回数が
多いほど性能が良い
最適解を得られた
値は10試行の平均値
Intelligent Systems Design Laboratory
提案手法におけるパラメータの影響
CMXを51都市問題に適用した結果
通常のDGAよりも性能が向上した
CMXでの多段交叉回数の影響
CMXを適用する世代数の影響
Intelligent Systems Design Laboratory
多段交叉回数の影響
1回の交叉では
DGAよりも劣る
10回以上の交叉
でDGAを上回る
多段交叉回数は
10回以上が適当
値は10試行の平均値
Intelligent Systems Design Laboratory
CMXまでの世代数
CMXの適用が早すぎると
性能はDGAよりも劣る
CMXの適用は
500世代以降が適当
CMXの適用が
十分に後ならば
性能が高い
値は10試行の平均値
Intelligent Systems Design Laboratory
CMXを複雑な問題に適用
母集団サイズ
サブ母集団数
交叉法
交叉率
突然変異
突然変異率
移住間隔
移住率
対象問題
800
32
枝交換交叉(EXX)
0.8
2-change法
0.4/L
5世代
0.5
100,150都市問題
Intelligent Systems Design Laboratory
100都市問題への適用
CMXの適用回数が
少ないとDGAより
性能が劣る
CMXの適用回数を
増やすと最適解を
得られた
値は10試行の平均値
Intelligent Systems Design Laboratory
150都市問題への適用
100都市問題と
同様の結果
適用回数を増やす
解の品質が向上する
用いたパラメータでは
最適解を得られなかった
値は10試行の平均値
Intelligent Systems Design Laboratory
CMXの複雑な問題への適用結果
DGAよりも高い性能を示した
課題
適切なパラメータの設定
・適用回数を増やす必要がある
・複雑な問題に対しては
個体数, サブ母集団数を増やす
Intelligent Systems Design Laboratory
まとめ
結論
・ TSPを通常のDGAで解くことは困難
・提案手法はDGAよりも良好な性能を示す
・ CMXを複数回行うことでさらに性能が向上
今後の課題
・適切なパラメータ設定
・他の離散的問題への提案手法の適用
Intelligent Systems Design Laboratory
Intelligent Systems Design Laboratory
その他の交叉法
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
提案手法の操作
母集団サイズまで
子を生成
エリートのみ
集める
交叉
・・
・
親個体も残す
交叉のみ複数回
集中して行う(CMX)
個体数を増やす
エリートの持つ枝の振り分け
Intelligent Systems Design Laboratory
提案手法のパラメータ
1. 最初のCMXを行うまでの世代数
2. CMXを行う回数
3. CMXを行う世代間隔
4. CMXにおける多段交叉回数
Intelligent Systems Design Laboratory
提案手法の操作(1)
エリートのみ
集める
母集団サイズまで
交叉により子を生成
移住なしDGA
・
母集団全体の
(iDGA) ・・
多様性があがる
Intelligent Systems Design Laboratory
提案手法の操作(2)
母集団サイズまで
子を生成
サブ母集団に
分割
iDGA
又は
交叉のみを行う
・・
(CMX)
・
通常の
DGA
選択を行わないため
エリートの持つ枝を
振り分けることが可能
Intelligent Systems Design Laboratory
2-Change法
Intelligent Systems Design Laboratory
枝交換交叉(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 }
{ EF FD DA AB BC
CE }
‥‥ { A E D C B F } 子１
‥‥ { E F D A B C } 子２
Intelligent Systems Design Laboratory

Download Report