遺伝的アルゴリズムによる離散最適化と
その応用に関する研究
同志社大学大学院
工学研究科 知識工学専攻
46041701 花田 良子
最適化問題
設計や生産計画など多くの問題は最適化問題として記述
例) 工場の生産計画(スケジューリング)
複数の製品を複数の機械で製造
どの機械にどの製品を処理する
とアウトプットが最大になるか？
その他にも，回路設計など
(引用: http://www.in.ec.saga-u.ac.jp/spp/)
最適化問題
ある制約条件のもと，所与の目的関数の最小値(最大値)を
与える設計変数を求めること
minimize f(x)，subject to x ∈ F
f(x) ： 目的関数
x ： 設計変数
F ： 実行可能領域 (制約条件を満たす解の集合)
離散最適化問題
解空間Fが離散集合(組合せ的) …整数，{0,1}，順列など可算集合
minimize f(x)，subject to x ∈ F
世の中の多くの問題が離散最適化として定式化
例) 工場のスケジューリング
回路設計
割り当て
パッケージング
フロアプランニング
設計問題や生産計画など応用分野が広く，重要な問題領域
最適化によるアプローチ
離散最適化問題の多くは膨大な解空間 … N!，NM など
実際の問題はNも大きい
(1) 厳密解法
分枝限定法，動的計画法など
(2) 近似解法 / 発見的解法 ～ 現実的な時間で満足解
欲張り法，局所探索，散布探索
遺伝的アルゴリズム(GA)，シミュレーテッドアニーリング（SA）
遺伝的アルゴリズム(GA)
生物の進化を模倣した確率的な最適化アルゴリズム
(1) 直接探索法 ～ 高い適用性
複雑な非線形関数や任意の離散的な構造体(順列など)を解として直接扱う
(2) 多点探索 ～大域的な探索 (単峰性，多峰性)
遺伝的アルゴリズム(GA)
遺伝的オペレータを繰り返すことで探索を進める
選択
適合度(～目的関数値)の
高い個体が生き残る
交叉
個体(解)の情報交換
よい部分解が組み合さる
突然変異
個体(解)の情報の変更
未知の部分解を得る
遺伝的アルゴリズム(GA)
遺伝的オペレータを繰り返すことで探索を進める
選択
適合度(～目的関数値)の
高い個体が生き残る
GAの母集団
解
交叉
個体(解)の情報交換
よい部分解が組み合さる
突然変異
個体(解)の情報の変更
未知の部分解を得る
目的関数の
ランドスケープ
大域的最適解
研究の目的
GAは数ある確率的最適化手法の中でも有望な手法
実際の問題におけるGAの要求が高まっている
背景：計算機，ネットワーク性能の向上
「十分速い」あるいは「許容できる/現実的」な時間
内に計算できる量が飛躍的向上
Super Computingの分野においてもGAのアプリケーションが見られる
ようになってきている
離散最適化問題におけるGAの実用性の向上
GAの実用化における課題
(1) より強力な探索の実現
主探索オペレータである交叉において性能かつ汎用性を高める
離散最適化問題における従来の交叉のアプローチ
・性能が高い
⇔ 問題に特化
・汎用性が高い ⇔ 性能が低い
(2) 高速に良い解を求める/信頼性の高い探索の実現
GAは従来より並列処理 (多点探索)で解決
年々，並列計算環境の規模が拡大
従来の粒度の並列処理
→ 爆発的な並列度数を有する計算環境に対応できる
GAの並列モデルの開発
発表の流れ
Ⅰ順序付け問題におけるGAの有効な探索オペレータの開発 (3
章) 内挿 / 外挿領域における遺伝的多段階探索
巡回セールスマン問題，スケジューリング問題，割り当て問題
Ⅱ多資源計算環境下でのGAの並列モデル(4章)
過去の探索の利用のためのデータベース
Ⅲ実際の離散最適化問題へのGAの適用(5章)
複雑ネットワーク解析
順序付け問題におけるGAの有効な
探索オペレータの開発 (3章)
探索オペレータに関する研究の目標
遺伝的アルゴリズム(GA)の2種の特徴的な探索
(1) 母集団が持つ部分解(形質)の遺伝 …交叉
重点的に開発，オペレータをしっかり設計
(2) 母集団にない部分解(形質)の獲得 …突然変異
(1) の補助的な操作，ランダム
しっかり設計
順序付け問題を対象
順序付け問題
解 x が順列表現される最適化問題
minimize f(x)，subject to x ∈ F
産業的な応用性の高い重要な問題領域
例) 巡回セールスマン問題(TSP)
スケジューリング問題
ネットワーク設計
各種割当問題など
NP-困難性 …膨大な解空間(N!，NM など)
GAで効率よく最適解を探索するためには，高い探索性能を有する
交叉の開発が重要
順序付け問題の交叉の設計の難しさ
順序付け問題は厳しい制約条件や変数間の依存
が強いものが多い
単純な解表現と交叉
制約条件を満たさない
解が多く生成
これまでに多くの交叉
問題の構造を考慮
親のよい部分をうまく受け
継がれるような交叉
親
子
順序付け問題の交叉の課題[1] – 形質遺伝
形質遺伝性に優れた交叉
親2個体の両方の形質(部分解/部分的な順列)を受け継いだ多様な
子個体群を生成したい
形質遺伝の難しさ
順序付け問題は変数間の依存が強いものが多い
バランスよく親の部分解(形質)を受け継がせるのが難しい
pattern 1
pattern 3
親1よりの個体しか生成されない
pattern 2
親2よりの個体しか生成されない
親1,2とまったく違う個体が生成される
順序付け問題の交叉の課題[1] – 形質遺伝
形質遺伝性に優れた交叉
親2個体の両方の形質(部分解/部分的な順列)を受け継いだ多様な
子個体群を生成したい
多段階の近傍探索交叉が有効
dMSXF [Ikeda02]
TSPで非常に強力な交叉
deterministic Multi-step Crossover Fusion (dMSXF)
[Ikeda02]
親1から親2に近づいていく方向に探索が進む交叉
親2の形質(部分順列)を少しずつ受け継いでいく
多段階のステップからなる近傍探索 (近傍を生成→解遷移)
親2個体の両方の形質を受け継いだ多様な子個体群が生成
deterministic Multi-step Crossover Fusion (dMSXF)
[Ikeda02]
距離(~類似性)を用いて解遷移を決定的に判定
1ステップの操作
step kのベストの解 xk から近傍を生成→ベストを選択
必ず距離が短くなる: d(step kの近傍，親2) ＞ d(step (k+1)の近傍，親2)
2種のパラメータ
総ステップ数：kmax
近傍個体数：μ
{x1, x2,…, xkｍaｘ} のベストがp1と置き換わる
順序付け問題の交叉の課題[2] – 形質獲得
より大域的な探索を実現させるには
親の良い形質の組み合わせ＋ 親が持っていない形質の獲得
(内挿領域での探索)
(外挿領域での探索)
距離概念の導入
内挿領域： 両親の内側
d(s, p1) ≦d(p1, p2) かつ d(s, p2) ≦d(p1, p2)
を満たす領域
外挿領域： 両親の外側
d(s, p1) ＞d(p1, p2) または d(s, p2) ＞d(p1, p2)
を満たす領域
内挿・外挿領域[Sakuma00]
外挿領域への多段階探索の提案
dMSXFは内挿領域における優れた交叉
… 親2個体が近すぎるとうまく働かない
dMSMF (deterministic Multi-step Mutation Fusion) を提案
親1，2が近すぎると強制的に離れていく方向に探索を進める
deterministic Multi-step Mutation Fusion (dMSMF)
dMSMF：多段階のステップからなる近傍探索
親1，2から遠ざかる方向に探索が進む交叉
親1の形質(部分順列)を少しずつ変更させていく
1ステップの操作
step kのベストの解から近傍を生成→ベストを選択
必ず距離が大きくなる: d(step kの近傍，親1,2) ＜ d(step (k+1)の近傍，親1,2)
2種のパラメータ
総ステップ数：kmax
近傍個体数：μ
{x1, x2,…, xkｍaｘ} のベストがp1と置き換わる
deterministic Multi-step Mutation Fusion (dMSMF)
dMSMFは外挿領域への多段階の近傍探索
親の付近から探索を進める
近傍探索 (←順序付け問題に有効)
提案手法dMSMF
従来からの突然変異
内挿・外挿領域への多段階探索
より大域的な探索を実現させるために
親の良い形質の組み合わせ＋ 親が持っていない形質の獲得
(内挿領域での多段階探索)
(外挿領域での多段階探索)
dMSXF：内挿交叉
dMSMF：外挿交叉
順序付け問題における内挿・外挿交叉の有効性
3種の問題で有効性を検証
単峰性
巡回セールスマン問題(TSP)
大域的単峰性のランドスケープ(推定)の問題として
ジョブショップスケジューリング問題
(JSP)
多峰性のランドスケープ(推定)の問題として
二次割当問題(QAP)
より一般化された順序付け問題．JSP，TSP∈QAP
異なる3種の特性を持つ問題で有効性を検証することで
内挿・外挿交叉の一般的な有効性を検証
多峰性
順序付け問題における内挿・外挿交叉の有効性
3種の問題で有効性を検証
内挿交叉
内挿+外挿交叉
TSP
既に実証[ikeda02]
本研究
JSP
本研究
本研究
QAP
本研究
本研究
巡回セールスマン問題(TSP)
すべての都市を訪問するツアーの中でもっとも
短いものを探す問題
内挿交叉の有効性は既に示されている
内挿+外挿交叉の有効性
内挿・外挿交叉を適用するために
内挿・外挿交叉は近傍探索
距離と近傍で解遷移を決定的に判定
近傍の設計
距離の設計
問題によって異なり，特性をとらえた定義
TSPにおける近傍と距離
近傍の設計
ABサイクル[Nagata97]に基づく近傍 …効率よく良好な巡回路が生成可能
距離の定義
2つの個体の異なるエッジの個数
親1
親2
異なるエッジ
TSPにおける内挿交叉 (親p1→p2の近づけ方)
親p2に近づく近傍個体の生成
親p1に親p2のエッジを少し加えて，巡回路を生成
近傍探索のステップが進むにつれて，p2のエッジをよりよく
受け継いだ解が生成
TSPにおける外挿交叉 (親p1,p2の遠ざかり方)
親p1, p2 から遠ざかる近傍個体の生成
親p1, p2 に共通するエッジを取り除き，新たにエッジを加える
ことで巡回路を生成
近傍探索のステップが進むにつれて，親p1, p2にないエッジを
持つ解が生成
TSPにおける内挿+外挿交叉の有効性
実験：内挿 / 内挿+突然変異 / 内挿+外挿(提案手法)の比較
最適解を得た回数
ステップ数：5
生成近傍数：8
母集団サイズ：100
内挿+外挿＞内挿+突然変異＞内挿 ： 外挿性要因が有効に働く
ジョブショップスケジューリング問題 (JSP)
スケジューリング問題の中でも最も困難な問題の1つ
N個の仕事をM台の機械で処理
すべての仕事を処理し終えるまでの総所要
時間(makespan)を最小化
技術的順序
各仕事を処理する機械の順序
内挿交叉の有効性および内挿+外挿交叉の有効性
JSPにおける近傍と距離
近傍の設計
アクティブCB近傍[Yamada96]を利用
クリティカルパスに基づく高性能な近傍
距離の定義
I2 距離[Sakuma2000]を利用
各仕事の絶対的な位置(順列上の位置)の差
JSPにおける内挿交叉と外挿交叉
内挿交叉
親p2に近づく近傍個体の生成
親p1に親p2の仕事の絶対位置をコピー
近傍探索のステップが進むにつれて，p2の部分仕事列を
よりよく受け継いだ解が生成
外挿交叉
親p1, p2 から遠ざかる近傍個体の生成
親p1, p2 に共通する部分仕事列に変更を加える
近傍探索のステップが進むにつれて，親p1, p2にない仕事列
を持つ解が生成
JSPにおける内挿交叉の有効性
実験：内挿交叉 / 他の内挿性の交叉の比較
最適解を得た回数
比較対象
CCM [Ono，2001] &
inter machine JOX [Ono98]
母集団サイズ：100
内挿交叉は他の高性能な交叉よりも良好な結果が得られる
JSPにおける内挿+外挿交叉の有効性
実験：内挿 / 内挿+突然変異 / 内挿+外挿(提案手法)の比較
内挿+外挿＞内挿+突然変異＞内挿 ： 外挿性要因が有効に働く
10 tough problemsの性能
近傍構造を考慮した有力な交叉との比較
内挿+外挿
MSXF
EDX
best #opt best #opt best #opt
abz7
abz8
abz9
la21
la24
la25
la27
la29
la38
la40
658
--
678
--
670
--
668
--
686
--
683
--
679
--
697
--
686
--
1047
--
1046 (9/30)
1046 (1/10)
935 (5/10)
935 (4/30)
935 (4/10)
977 (7/10)
977 (9/30)
977 (4/10)
1235 (5/10)
1235 (1/30)
1236
--
1160
1166
1167
--
--
--
1154 (10/10)
1196 (21/30)
1196 (1/10)
1224
1224
1224
--
--
--
順序付け問題における交叉設計のまとめ
順序付け問題における有効な探索の実現
親の良い形質の組み合わせ＋ 親が持っていない形質の獲得
(内挿領域での探索)
(外挿領域での探索)
内挿+外挿領域における多段階探索の有効性を
TSP(単峰性)，JSP(多峰性)で示した
内挿+外挿交叉 ＞ 内挿交叉+突然変異 ＞ 内挿交叉
その他，より一般化された順序付け問題であるQAPにおいてもその有効性
は示されている
順序付け問題一般において，内挿/外挿領域の多段階探索
の有用性
GAの実用化における課題
(1) より強力な探索の実現
主探索オペレータである交叉において性能かつ汎用性を高める
(2)高速に良い解を求める/信頼性の高い探索の実現
GAは従来より並列処理 (多点探索)で解決
年々，並列計算環境の規模が拡大
従来の粒度の並列処理
→ 爆発的な並列度数を有する計算環境に対応できる
GAの並列モデルの開発
多資源計算環境下でのGAの並列モデル
(4章)
最適設計をとりまく計算環境
膨大な計算資源の供給源
限られた少数の資源
膨大な資源の使用が可能
数千ノード規模のPCクラスタ
大規模なGrid計算環境
5～10x106ノード
今後も増加，大規模化
最適設計の将来
1つの解の評価がやっと → 設計を数理モデル化し，計算シミュレーションで
GAにおける並列処理
GAの特徴
多点探索
高い並列性を有する
数十～数百ノードのPCクラスタ
将来的には，膨大な資源を用いたGAによる最適設計
GAの並列化の研究
大規模計算環境を対象としたアプリケーション
従来の並列GAの問題点 (大規模計算環境)
爆発的な並列度数の計算環境でのノードの利用方法
1．個体数の増加による並列度の向上
多様性の極端な増大
収束が遅くなる
計算コスト(時間，評価計算回数)を
制限した場合は性能が低下
収束の早いモデルを利用すると
解探索性能が低下
従来の並列GAの問題点 (大規模計算環境)
爆発的な並列度数の計算環境でのノードの利用方法
2. 複数の母集団で並列してGAを実行
(複数回の試行を並列)
同じ解への探索が進む可能性
ノード間で探索の重複
ノード間の重複
複数の母集団で並列してGAを実行 (複数回の試行を並列)
Rastrigin関数(2次元)：探索空間の大きさ＝220 ＝ 1.05x106
1台のノード･･･10個体で20世代のGA (2010評価計算)
500台のノード･･･2010x500 ＝ 1.005x106
全探索と同等の個体数を計算し
ても，GAで探索している領域は
20％
不要な計算をしているノード
が存在
探索性能は維持できるが，
無駄な計算が行われている
大規模計算環境におけるGAで考慮する点
計算資源数の増加に対して，解探索性能を低下させることなく，
スケーラビリティを向上
スケーラビリティ
計算資源の増加
探索した領域の拡大
不要な計算が行わなれない
従来の並列化の方法
1．個体数の増加による並列度の向上
不要な計算は行わないが性能が低下
2. 複数の母集団で並列してGAを実行(複数回の試行を並列)
性能は低下しないが，不要な計算が存在(探索の重複)
GAは膨大な計算リソースを有効に利用できない
大規模計算環境におけるGAで考慮する点
不要な計算が行わなれない仕組み
探索の重複の回避･･･既に探索したところは探索しない
1試行内での重複, 試行間での重複
タブ・サーチ，リスタート ← 既探索領域のデータベース
計算資源を有効に利用する仕組み
資源が膨大に存在するときには，GAが利用しきれない
一部のノードを効率的に利用
未探索領域を探索するローカルサーチ
既探索領域の拡大操作
スケーラビリティを保持する仕組み
既探索個体を保存するデータベース
巨大な解空間での探索解の保存
1つの個体を1つのデータとして保存
膨大なデータ量
例) 個体：{0,1}のビット列 染色体長=30のとき…230(=109)
既探索解の参照時にも多大な時間
限られたデータで全既探索領域を表現する必要
(1) スキーマを用いた表現
(2) 2次元座標を用いた表現
マッピング手法
[T.Collins, 1996]
個体と座標が1:1に対応
データベースの個体を用いたローカルサーチ
計算資源を有効に利用する仕組み
未探索領域を探索するローカルサーチ
既探索領域の近傍個体を探索･･･探索領域を拡大
ローカルサーチ
(x1,y1)
GA
(x2,y2)
1領域を1ノードに割り当てる
ことで並列化
データベースを組み込んだGA
実験: ローカルサーチを適用することの効果
データベースの利用方法は任意
Step1: GAの母集団に対して，遺伝的オペレータを適用
Step2: GAの母集団の個体をデータベースに保存 (部分的，例:ベストの解)
Step3: データベースに保存されている領域に対して
ローカルサーチ(未探索領域の探索)を適用
探索の特徴
最良解の適合度，既探索領域の大きさの推移 (1max問題)
母集団サイズ：20
世代交代モデル：ER
GAをベースとしているためGAと同等の解探索性能
既探索領域の大きさが定量的に把握可能
[Thierens94]
ベストを毎世代保存
有限の計算コストの下で全探索(得られた解が最適解であること)を保証
探索の特徴
最良解の適合度，既探索領域の大きさの推移 (3-DECEPTIVE問題)
母集団サイズ：20
世代交代モデル：ER
[Thierens94]
ベストを毎世代保存
3-DECEPTIVE問題：GAが局所解に陥りやすいだまし問題
GAと同様に局所解に陥るが，探索を進めることにより最適解が得られる
分散環境での実装
Grid MPを用いて実装
2006年度より同志社大学が分散コンピューティング
環境を運用開始
ローカルサーチ
(x1,y1)
GA
(x2,y2)
Grid MP
米United Devices社の商用ミドルウェア
マスターワーカ型
サーバ(MP Server)，計算ノード(Devices)
実行形態
1. ユーザがMP Serverにジョブをサブミット
2. 計算ノードはポーリングの際にジョブを取得し，実行の後，MP Server
に結果を返す.
分散環境での実装
GA とローカルサーチを非同期
GAをローカルのマシンで実行
MP Serverでデータベースを保持
ベストの解を毎世代データベースに保存
分散環境での実装
GA とローカルサーチを非同期
ローカルサーチを分散環境で実行
各計算ノードは割り当てられた既探索領域から未探索領域を探索し，
定期的に結果をサーバに返す
利用できる計算ノード数分だけローカルサーチ
分散環境での検証
同志社大学キャンパスグリッドのテスト環境
#Nodes
Processor
Memory
Local Machine
1 Intel Xeon 2.8G*2 1GB
Server
1 Intel Pentium4 3G 1GB
Worker
60 Intel Pentium4 2.4G512M
5-trap関数(20 partitions)
解探索性能
既探索領域
GA
LS
ローカルサーチ
１分毎にサーバに結果を返す
ノード数を増加させることで
解探索性能，既探索領域
が向上
多資源計算環境下でのGAの研究まとめ
データベースをGAに適用することで有効性を検討
計算コストを制限しない場合の解探索性能
解探索の特徴
有限の計算コストの下で全探索(得られた解が最適解
であること)を保証
計算ノード数の影響
ノード数を増加させることで解探索性能，既探索領域が向上
計算コストを制限した場合の解探索性能
既探索領域情報を利用したタブサーチとリスタート
１試行内，試行間での探索の重複を回避
GAの実用化における課題
(1) より強力な探索の実現
主探索オペレータである交叉において性能かつ汎用性を高める
(2)高速に良い解を求める/信頼性の高い探索の実現
GAは従来より並列処理 (多点探索)で解決
爆発的な並列度数を有する計算環境に対応できる
GAの並列モデルの開発
実問題への適用として複雑ネットワーク設計
GAによる複雑ネットワーク設計(5章)
複雑ネットワーク設計の研究の目的
これまでの提案手法の実用例として
内挿+外挿交叉(3章)
大規模並列のためのデータベース(4章)
複雑ネットワークの解析のためのツールとしてのGAの利用
複雑ネットワーク
現実世界に存在する複雑で巨大なネットワークの性質について
研究する，グラフ理論の1分野
例) WWWのリンク
実在するネットワーク
航空路のネットワーク
たんぱく質の相互作用ネットワークなど
スケールフリー性，スモールワールド性
次数分布のべき乗則，平均パス長の
短いネットワーク
(引用:http://ja.wikipedia.org/wiki/)
複雑ネットワーク解析の目標
ネットワークの発生，成長が何に起因しているのか
最適化に基づくアプローチ
ネットワークの特性量を目的関数とした最適化問題に定式化
最適化により生成されたネットワークと複雑ネットワークの特性を比較する
ことで複雑ネットワークが有する特性は何に起因しているかを探求
例) 航空路のネットワーク
因子の仮説
- 都市の規模(人口)
比較
- 都市間の親密度
(人の行き来)
⇔
新密度と距離
距離を最適化
の最適化
- 都市間の距離
実際のネットワーク
ネットワーク間の(部分的な)類似性，複雑性が見られたなら，仮説の因子は妥当
ネットワークを形成する因子間の相互関係を把握
最適化に基づくアプローチ
問題：複雑ネットワークを形成すると考えられる基本的な
ネットワーク特性量を最小化するようなネットワークを生成
目的関数：平均パス長，クラスター係数など
制約条件：ノード数，総エッジ数を固定
GAの利用
(1) 解表現を工夫することでネットワークをダイレクトに操作可能
(2) 初期の探索ステップで解が未進化な状態でも，完全な解候補として
扱うことが可能
(3) 多点を用いた探索のため，多目的問題への拡張が容易
(複数の特性量を最小化)
目的関数(1)
平均最短移動距離を最小化 …エネルギーフローなどに対応
n
n
1
Objective function: D
( Dij ) (i j )
n(n 1) i 1 j 1
Dij ノード ni ，nj 間の最小距離
各ノード間には距離 (例.ユークリッド)
e.g. distance(n0,n4) = 8
n2から n5の最短パス：
n2->n1->n3 ->n4 ->n5
n2から n5の最短距離
D25=1+3+1+1=6
目的関数(2)
クラスタ係数の最大化 …ハブの形成の要因
頂点 i が持つ辺数：ki
頂点 i が持つクラスタの数：Ei
頂点 i のクラスタ係数：Ci = Ei/kiC2
実在のネットワークでは，大きな値を示すことが多い
kA = 4
EA = 2
CA = 2/(4*3/2)
C = 3/10
GAによるネットワーク設計
実験のための例題
例題：点(座標)の集合と総エッジ数
(TSPベンチマークより都市配置を利用)
bayg29-45： bayg29(29点)，制約としてエッジの総数45
eil51-76： eil51(51点)，制約としてエッジの総数76
eil101-150： eil101(101点)，制約としてエッジの総数150
目的関数：ネットワークの特徴量
Fitness = WD * (平均移動距離)+ WC * (クラスタ係数)
WD ，WC は重み
ネットワーク設計問題における内挿・外挿交叉
距離と近傍
距離の定義： エッジの異なり
近傍の生成： エッジの交換
内挿･･･親1に親2のエッジを加え，親1特有のエッジを削除
外挿･･･親1，2に共通するのエッジ削除し，任意のエッジを加える
平均最短移動距離の最小化
実験：内挿+外挿交叉 / 内挿交叉 / 他の内挿性の交叉(一様交叉)
Fitness = WD * (平均移動距離)
bayg29-45
eil51-76
eil101-150
内挿+外挿
best
avg
1014.5
1015.0
38.88
38.93
38.58
38.79
内挿
best
1015.1
38.93
38.86
avg
1017.9
39.0
39.13
内挿+外挿交叉 ＞ 内挿交叉 ＞ 他の内挿性の交叉
一様交叉
best
avg
1018.1
1021.8
38.99
39.1
38.92
39.17
平均最短移動距離の最小化
実験：内挿+外挿交叉 +データベース
#Nodes
Local Machine
Server
Worker
Processor
1 Intel Xeon 2.4G
1 Intel Pentium4 3G
185 Intel Pentium4 3.6G
Mem
1GB
1GB
1GB
(同志社大学 キャンパスグリッド環境)
bayg29-45を対象
ローカルサーチを有するデータベース
を適用することにより，さらに探索性能
は向上
ネットワーク設計問題におけるまとめ
これまでの提案手法の実用例として
内挿+外挿交叉(3章)
大規模並列のためのデータベース(4章)
ネットワークの特性量を目的関数とした最適化問題
に定式化し，ネットワークを生成
内挿+外挿+データベース＞内挿+外挿＞ 内挿交叉 ＞一般の交叉
GAで得られたネットワーク群
Fitness = WD * (平均移動距離)+ WC * (クラスタ係数)
全体的ににクラスタ係数の高いネットワーク
クラスタ係数と距離にトレードオフ
全体のまとめ
(1) 探索性能，汎用性の向上
外挿領域における遺伝的多段階探索を提案
内挿 / 外挿領域における遺伝的多段階探索
2種の異なる問題(ランドスケープの観点より)，巡回セールスマン問題，
スケジューリング問題において有効性を示した
(2) 実用性の向上
大規模計算環境におけるGAのためのデータベースとローカルサーチ
データベースの応用としてのタブサーチ，リスタート
計算コストを多くするほど，既探索領域の拡大，探索性能の向上
GAの1試行内，試行間の探索重複の回避
(1) ，(2)について実問題(ネットワーク設計)で有効性を示した
本研究の意義
離散最適化におけるGAの応用に関する2つの課題
(1) GAの強力かつ汎用性の高いオペレータの提案
(2) 大規模計算環境におけるGAの並列モデル
将来的には， GA によるGrid計算環境や超並列PCクラスタでの
最適化の実現
GAの大規模複雑な問題への応用性を高めた
論文リスト
(査読付)
(1)三木光範，廣安知之，花田良子，水田伯典，“エリート解の集中的な交叉メカニズムを持つ分散遺伝的アルゴリズム
のTSP における解探索性能の検討”，システム制御情報学会論文誌，Vol. 16，No. 12，pp.607-615，2003
(2) Yoshiko Hanada, Tomoyuki Hiroyasu, Mitsunori Miki and Yuko Okamoto,“Mega Process Genetic
Algorithm Using Grid MP”, Life Science Grid 2004Revised Selected and Invited Papers, Lecture Notes in
Computer Science, vol.3370, pp. 152-170, 2005
(3) 花田良子，廣安知之，三木光範，“多資源計算環境下での遺伝的アルゴリズムのためのローカルサーチメカニズムを
有するデータベースの提案”，情報処理学会論文誌「数理モデル化と応用」，Vol. 47，No. SIG 1，pp.19-28，2006
(4) 花田良子，廣安知之，三木光範，“組合せ最適化問題における内挿/外挿的な領域への遺伝的多段階探索の有効
性”，情報処理学会論文誌，Vol. 47，No. 10，pp. 2897–2908，2006
(5) Yoshiko Hanada, Tomoyuki Hiroyasu and Mitsunori Miki, “Construction of Complex Networks Using
Mega Process GA and GRID MP”, Grid Workshop, Grid Computing in Life Sciences, World Scientific, pp.
197–211, 2006
(6) 花田良子，廣安知之，三木光範，“多資源計算環境下での遺伝的アルゴリズムのためのローカルサーチメカニズムを
有するデータベースの改良”，情報処理学会論文誌「数理モデル化と応用」(掲載決定，平成18 年6 月9 日付)
(7) 花田良子，佐藤史隆，廣安知之，三木光範，鈴木泰博，“遺伝的アルゴリズムによるネットワーク特性量に着目した
ネットワーク設計法”，日本ソフトウェア科学会(掲載決定，平成18 年10 月19 日付)
平均最短移動距離，クラスタ係数
実験：平均最短移動距離を最小化およびクラスタ係数の最大化
発表の流れ
1. 研究の背景と目的
- 離散最適化問題
- 遺伝的アルゴリズム (Genetic Algorithm; GA)
2. 順序付け問題におけるGAの有効な探索オペレータの開発
3. 多資源計算環境下でのGAの並列モデル
4. 実際の離散最適化問題へのGAの適用
複雑ネットワーク解析
5. 結論
GAの実問題への適用にあたっての課題
(1) 探索性能，汎用性の向上
主探索オペレータである交叉の設計
離散最適化問題における従来の交叉のアプローチ
・性能が高い
⇔ 問題に特化
・汎用性が高い ⇔ 性能が低い
(2) 実用性の向上
GAは多点探索 → 並列処理，大規模計算環境におけるモデルの開発
年々，利用可能な計算機環境の規模が拡大
使える計算資源を効果的に利用できるモデル
最適化によるアプローチ
離散最適化問題の多くは膨大な解空間 … N!，NM など
(1) 厳密解法
分枝限定法，動的計画法など
(2) 近似解法 / 発見的解法 ～ 現実的な時間で満足解
欲張り法，局所探索，散布探索
遺伝的アルゴリズム(GA)，シミュレーテッドアニーリング（SA）
背景：計算機，ネットワーク性能の向上
「十分速い」あるいは「許容できる/現実的」な時間
内に計算できる量が飛躍的向上
遺伝的アルゴリズム(GA)
生物の進化を模倣した確率的な最適化アルゴリズム
設計変数は遺伝子型で表現
染色体=解，個体
{0,1}ビット，整数，順列
形質遺伝の難しさ
順序付け問題は変数間の依存が強いものが多い
バランスよく親の部分解(形質)を受け継がせるのが難しい
pattern 1
pattern 3
親1よりの個体しか生成されない
pattern 2
親2よりの個体しか生成されない
親1,2とまったく違う個体が生成される
順序付け問題の交叉の課題[1] – 形質遺伝
dMSXFは形質遺伝性に優れた交叉
両親の間に子個体を生成
TSPにおける内挿+外挿交叉の有効性
実験：内挿+外挿(提案手法)の有効性
最適解を得た回数
母集団サイズが小さいとき
内挿+外挿 ＞ 内挿
母集団が十分大きいとき
内挿+外挿 ＝ 内挿
単峰性の問題の特徴
JSPにおける内挿交叉 (親p1→p2の近づけ方)
親p2に近づく近傍個体の生成
親p1に親p2の仕事の絶対位置をコピー
近傍探索のステップが進むにつれて，p2の部分仕事列を
よりよく受け継いだ解が生成
JSPにおける外挿交叉 (親p1,p2の遠ざかり方)
親p1, p2 から遠ざかる近傍個体の生成
親p1, p2 に共通する部分仕事列に変更を加える
近傍探索のステップが進むにつれて，親p1, p2にない仕事列
を持つ解が生成
JSPにおける外挿交叉の役割
実験：局所解側に母集団を初期化
50試行
局所解A
大域的最適解
局所解A
大域的最適解
他の局所解
内挿
48
1
1
内挿+外挿
21
28
1
多資源計算環境での並列モデルに関する研究の目的
GAの探索の特徴
現実的な計算コストで満足解を得られる
⇔ 計算コスト，計算ノードを費やしすぎると性能向上が飽和
無駄な計算の存在
計算コストを費やすほど良い
結果が得られる仕組み
解を{0,1}ビットで表現するGA
(解空間が可算かつ有限)を対象
従来の並列GAの問題点 (大規模計算環境)
爆発的な並列度数の計算環境でのノードの利用方法
2. 複数の母集団で並列してGAを実行
(複数回の試行を並列)
同じ解への探索が進む可能性
ノード間で探索の重複
探索性能は維持できているが，無駄な計算が行われている
大規模計算環境におけるGA
個体の表現
ビット列の個体を2次元座標(x, y)で表現
マッピング手法：N次元の解空間
個体と座標は1:1に対応
2次元平面 [T.Collins, 1996]
2次元平面全体=解空間
既探索個体を保存するデータベース
e.g. 6ビットの問題の2次元平面
個体と座標は1:1に対応
2次元平面全体=解空間
個体間のハミング距離が1
既探索個体を保存するデータベース
ビット列の個体を2次元座標(x, y)で表現
マッピング手法：N次元の解空間
2次元平面 [T.Collins, 1996]
連続した座標を持つ個体群は矩形 (xmin, ymin)-(xmax, ymax) で表現
データベースの個体を用いたローカルサーチ
計算資源を有効に利用する仕組み
未探索領域を探索するローカルサーチ
既探索領域の近傍個体を探索･･･探索領域を拡大
2次元平面のたて，よこ方向に既
探索領域が拡大
良好な解が見つかった方向に
探索を進める
計算コストを制限したときの解探索性能
実験：総評価計算回数を制限
(10次元のRastrigin，Ridge，Griewank関数)
0.5×105 ,1×105, 1.5×105, 2×105 , 1×106
計算コストを制限した場合でもGAと同等の性能
データベースの応用
データベースを適用することにより，既探索領域と未
探索領域が完全に分離
過去の探索の利用：解の評価時にはデータベースを参照
既探索領域の利用：試行間，試行内の
探索重複の回避
リスタート
GAが収束
未探索領域へ再初期化
タブサーチ
データベースに保存されている領域を
タブリストとして利用
既探索領域内に解がある場合外にだす
タブサーチ
実験：GA+LSとGA+LS+TSの比較
Griewank関数
ベストの解の推移
既探索解の再評価数
最適解を得た回数
データベースをタブサーチに利用することで試行内の探索の重複を回避
リスタート
実験：タブサーチ，リスタートの有効性
Griewank関数(2次元)
母集団が収束
初期化
既探索領域内の解の再評価の禁止
200回のリスタート
得られた解の種類
タブサーチ無
22
タブサーチ有
200
リスタートによる複数試行においても探索
の重複が回避可能
分散環境での検証
同志社大学メディア課が運用するGrid MPテスト環境
#Nodes
Processor
Memory
Local Machine
1 Intel Xeon 2.8G*2
1GB
Server
1 Intel Pentium4 3G
1GB
Worker
60 Intel Pentium4 2.4G 512M
ローカルサーチ
１分毎にサーバに結果を返す
5-trap関数(20 partitions)
GA
LS
分散環境での検証
5-trap関数(20 partitions)，500世代での結果
解探索性能
既探索領域
ノード数を増加させることで解探索性能，既探索領域が向上
多資源計算環境下でのGAの研究まとめ
最適化に基づくアプローチ
ネットワークの特性量を目的関数とした最適化問題
に定式化し，ネットワークを設計
設計されたネットワークの持つ特性と複雑ネットワークの持つ特性とを比較
することで複雑ネットワークが有する特性は何に起因しているかを探求
例) 航空路のネットワーク
要因の仮説
- 都市の規模(人口)
- 都市間の関連度
(人の行き来)
⇔
実際のネットワーク
距離を最適化した
ネットワーク
- 都市間の距離
ネットワーク間に(部分的な)類似性が見られたなら，仮説の要因は妥当
最適化に基づくアプローチ
ネットワークの特性量を目的関数とした最適化問題
に定式化し，ネットワークを設計
例) 航空路のネットワーク
因子の仮説
- 都市の規模(人口)
比較
- 都市間の関連度
(人の行き来)
⇔
関連度と距離
距離を最適化
の最適化
- 都市間の距離
実際のネットワーク
ネットワーク間に(部分的な)類似性が見られたなら，仮説の因子は妥当
因子間の相互関係
目的関数(1)
平均最短移動距離を最小化
n
n
1
Objective function: D
( Dij ) (i j )
n(n 1) i 1 j 1
Dij ノード ni ，nj 間の最小距離
D=5.733
Pattern 1が最良解
D= 5.933
D=6.333
最適化に基づくアプローチ
ネットワークの特性量を目的関数とした最適化問題に定式化
最適化により生成されたネットワークと複雑ネットワークの特性を比較する
ことで複雑ネットワークが有する特性は何に起因しているかを探求
例) 航空路のネットワーク
因子の仮説
- 都市の規模(人口)
比較
- 都市間の関連度
(人の行き来)
⇔
関連度と距離
距離を最適化
の最適化
- 都市間の距離
実際のネットワーク
ネットワーク間に(部分的な)類似性が見られたなら，仮説の因子は妥当
比較を通して，ネットワークを形成する因子間の相互関係を把握
© Copyright 2024 ExpyDoc
