遺伝的アルゴリズムによる離散最適化とその応用に関する研究 GA知ってるくらいを対象 同志社大学大学院 工学研究科 知識工学専攻 46041701　花田　良子

最適化問題 設計や生産計画など多くの問題は最適化問題として記述 例) 工場の生産計画(スケジューリング) その他にも，回路設計など 複数の製品を複数の機械で製造 どの機械にどの製品を処理するとアウトプットが最大になるか？ その他にも，回路設計など (引用: http://www.in.ec.saga-u.ac.jp/spp/)

最適化問題 minimize f(x)，subject to x ∈ F ある制約条件のもと，所与の目的関数の最小値(最大値)を与える設計変数を求めること minimize f(x)，subject to x ∈ F f(x) ： 目的関数 x　： 設計変数 F　： 実行可能領域 (制約条件を満たす解の集合)

離散最適化問題 minimize f(x)，subject to x ∈ F 世の中の多くの問題が離散最適化として定式化 例) 工場のスケジューリング 　　 回路設計 　 割り当て 　　 パッケージング 　　 フロアプランニング 設計問題や生産計画など応用分野が広く，重要な問題領域

最適化によるアプローチ 離散最適化問題の多くは膨大な解空間 … N!，NM など (1) 厳密解法 分枝限定法，動的計画法など (2) 近似解法 / 発見的解法　～ 現実的な時間で満足解 欲張り法，局所探索，散布探索 遺伝的アルゴリズム(GA)，シミュレーテッドアニーリング（SA）

遺伝的アルゴリズム(GA) 生物の進化を模倣した確率的な最適化アルゴリズム (1) 直接探索法 ～ 高い適用性 複雑な非線形関数や任意の離散的な構造体(順列など)を解として直接扱う (2) 多点探索 ～大域的な探索 (単峰性，多峰性)

遺伝的アルゴリズム(GA) 遺伝的オペレータを繰り返すことで探索を進める 選択 交叉 突然変異 適合度(～目的関数値)の高い個体が生き残る 個体(解)の情報交換 よい部分解が組み合さる 突然変異 個体(解)の情報の変更 未知の部分解を得る

遺伝的アルゴリズム(GA) 遺伝的オペレータを繰り返すことで探索を進める 選択 交叉 突然変異 適合度(～目的関数値)の高い個体が生き残る 解 適合度(～目的関数値)の高い個体が生き残る 交叉 個体(解)の情報交換 よい部分解が組み合さる 目的関数の ランドスケープ 突然変異 大域的最適解 個体(解)の情報の変更 未知の部分解を得る

研究の目的 GAは数ある確率的最適化手法の中でも有望な手法 実際の問題におけるGAの要求が高まっている 背景：計算機，ネットワーク性能の向上 「十分速い」あるいは「許容できる/現実的」な時間内に計算できる量が飛躍的向上 Super Computingの分野においてもGAのアプリケーションが見られるようになってきている 離散最適化問題におけるGAの実用性の向上

GAの実用化における課題 (1) より強力な探索の実現 (2) 高速に良い解を求める/信頼性の高い探索の実現 主探索オペレータである交叉において性能かつ汎用性を高める 離散最適化問題における従来の交叉のアプローチ ・性能が高い 　 ⇔ 問題に特化 ・汎用性が高い ⇔ 性能が低い (2) 高速に良い解を求める/信頼性の高い探索の実現 GAは従来より並列処理 (多点探索)で解決 年々，並列計算環境の規模が拡大 従来の粒度の並列処理 → 爆発的な並列度数を有する計算環境に対応できる 　　GAの並列モデルの開発 より大域的な探索の実現

発表の流れ Ⅰ順序付け問題におけるGAの有効な探索オペレータの開発 (3章) Ⅱ多資源計算環境下でのGAの並列モデル(4章) 内挿 / 外挿領域における遺伝的多段階探索 巡回セールスマン問題，スケジューリング問題，割り当て問題 Ⅱ多資源計算環境下でのGAの並列モデル(4章) 過去の探索の利用のためのデータベース Ⅲ実際の離散最適化問題へのGAの適用(5章) 複雑ネットワーク解析

順序付け問題におけるGAの有効な探索オペレータの開発 (3章)

探索オペレータに関する研究の目標 遺伝的アルゴリズム(GA)の2種の特徴的な探索 (1) 母集団が持つ部分解(形質)の遺伝 …交叉 重点的に開発，オペレータをしっかり設計 しっかり設計 (2) 母集団にない部分解(形質)の獲得 …突然変異 (1) の補助的な操作，ランダム 本研究の主張したいこと，目的を先に述べる． GAは2種の特徴的な探索を用いて，解を探索する． 1つは母集団にあるよい部分解を増やすこと，組み合わせること． もう1つは部分解を獲得することです． (1)は母集団がカバーする領域を集中的に探索 (2)はカバーしない領域を探索 GAの一般的な枠組みは(1)を交叉，(2)を突然変異が担っている． 順序付け問題を対象

順序付け問題 minimize f(x)，subject to x ∈ F 解 x が順列表現される最適化問題 産業的な応用性の高い重要な問題領域 例) 巡回セールスマン問題(TSP) 　　 スケジューリング問題 　　 ネットワーク設計 　 各種割当問題など NP-困難性 …膨大な解空間(N!，NM など) GAで効率よく最適解を探索するためには，高い探索性能を有する交叉の開発が重要

順序付け問題の交叉の設計の難しさ 順序付け問題は厳しい制約条件や変数間の依存が強いものが多い 子 単純な解表現と交叉 制約条件を満たさない解が多く生成 これまでに多くの交叉 問題の構造を考慮 親のよい部分をうまく受け継がれるような交叉 親

順序付け問題の交叉の課題[1] – 形質遺伝 形質遺伝性に優れた交叉 親2個体の両方の形質(部分解/部分的な順列)を受け継いだ多様な子個体群を生成したい 組合せ最適化問題は~を受け継ぎにくい

形質遺伝の難しさ 順序付け問題は変数間の依存が強いものが多い バランスよく親の部分解(形質)を受け継がせるのが難しい pattern 1 親1よりの個体しか生成されない pattern 2 組合せ最適化問題は~を受け継ぎにくい 親1,2とまったく違う個体が生成される 親2よりの個体しか生成されない

順序付け問題の交叉の課題[1] – 形質遺伝 形質遺伝性に優れた交叉 多段階の近傍探索交叉が有効 dMSXF [Ikeda02] 親2個体の両方の形質(部分解/部分的な順列)を受け継いだ多様な子個体群を生成したい 多段階の近傍探索交叉が有効 dMSXF [Ikeda02] TSPで非常に強力な交叉

deterministic Multi-step Crossover Fusion (dMSXF) [Ikeda02] 親1から親2に近づいていく方向に探索が進む交叉 親2の形質(部分順列)を少しずつ受け継いでいく 多段階のステップからなる近傍探索 (近傍を生成→解遷移) dMSXFは距離と近傍 問題によって定義しなければならないものであり，うまく定義すると 非常に強力な探索が可能となる重要な要素 親2個体の両方の形質を受け継いだ多様な子個体群が生成

deterministic Multi-step Crossover Fusion (dMSXF) [Ikeda02] 距離(~類似性)を用いて解遷移を決定的に判定 1ステップの操作 step kのベストの解 xk から近傍を生成→ベストを選択 必ず距離が短くなる: d(step kの近傍，親2) ＞ d(step (k+1)の近傍，親2) {x1, x2,…, xkｍaｘ} のベストがp1と置き換わる 2種のパラメータ 総ステップ数：kmax dMSXFは距離と近傍 問題によって定義しなければならないものであり，うまく定義すると 非常に強力な探索が可能となる重要な要素 近傍個体数：μ

順序付け問題の交叉の課題[2] – 形質獲得 より大域的な探索を実現させるには 親の良い形質の組み合わせ＋ 親が持っていない形質の獲得 (内挿領域での探索) (外挿領域での探索) 距離概念の導入 内挿領域： 両親の内側 d(s, p1) ≦d(p1, p2) かつ d(s, p2) ≦d(p1, p2) を満たす領域 図のアニメーションを逆に EDX＋JOX MSXF＋MSMF 外挿領域： 両親の外側 d(s, p1) ＞d(p1, p2) または d(s, p2) ＞d(p1, p2) を満たす領域 内挿・外挿領域[Sakuma00]

外挿領域への多段階探索の提案 dMSXFは内挿領域における優れた交叉 … 親2個体が近すぎるとうまく働かない dMSMF (deterministic Multi-step Mutation Fusion) を提案 親1，2が近すぎると強制的に離れていく方向に探索を進める 図のアニメーションを逆に EDX＋JOX MSXF＋MSMF

deterministic Multi-step Mutation Fusion (dMSMF) 親1，2から遠ざかる方向に探索が進む交叉 親1の形質(部分順列)を少しずつ変更させていく 1ステップの操作 step kのベストの解から近傍を生成→ベストを選択 必ず距離が大きくなる: d(step kの近傍，親1,2) ＜ d(step (k+1)の近傍，親1,2) {x1, x2,…, xkｍaｘ} のベストがp1と置き換わる 2種のパラメータ dMSXFと相補的 総ステップ数：kmax 近傍個体数：μ

deterministic Multi-step Mutation Fusion (dMSMF) 親の付近から探索を進める 近傍探索 (←順序付け問題に有効) dMSXFと相補的 提案手法dMSMF 従来からの突然変異

内挿・外挿領域への多段階探索 より大域的な探索を実現させるために 親の良い形質の組み合わせ＋ 親が持っていない形質の獲得 (内挿領域での多段階探索) (外挿領域での多段階探索) dMSXF：内挿交叉 dMSXFと相補的 dMSMF：外挿交叉

順序付け問題における内挿・外挿交叉の有効性 3種の問題で有効性を検証 単峰性 巡回セールスマン問題(TSP) 大域的単峰性のランドスケープ(推定)の問題として ジョブショップスケジューリング問題(JSP) 多峰性 多峰性のランドスケープ(推定)の問題として 二次割当問題(QAP) より一般化された順序付け問題．JSP，TSP∈QAP dMSXFと相補的 異なる3種の特性を持つ問題で有効性を検証することで内挿・外挿交叉の一般的な有効性を検証

順序付け問題における内挿・外挿交叉の有効性 3種の問題で有効性を検証 内挿交叉 内挿+外挿交叉 TSP 既に実証[ikeda02] 本研究 JSP QAP dMSXFと相補的

巡回セールスマン問題(TSP) すべての都市を訪問するツアーの中でもっとも短いものを探す問題 内挿交叉の有効性は既に示されている 内挿+外挿交叉の有効性

内挿・外挿交叉を適用するために 内挿・外挿交叉は近傍探索 近傍の設計 距離の設計 問題によって異なり，特性をとらえた定義 距離と近傍で解遷移を決定的に判定 近傍の設計 距離の設計 問題によって異なり，特性をとらえた定義

TSPにおける近傍と距離 近傍の設計 距離の定義 ABサイクル[Nagata97]に基づく近傍 …効率よく良好な巡回路が生成可能 2つの個体の異なるエッジの個数 異なるエッジ 親1 親2

TSPにおける内挿交叉 (親p1→p2の近づけ方)

TSPにおける外挿交叉 (親p1,p2の遠ざかり方)

TSPにおける内挿+外挿交叉の有効性 実験：内挿 / 内挿+突然変異 / 内挿+外挿(提案手法)の比較 最適解を得た回数 ステップ数：5 生成近傍数：8 母集団サイズ：100 内挿+外挿＞内挿+突然変異＞内挿 ： 外挿性要因が有効に働く

ジョブショップスケジューリング問題 (JSP) スケジューリング問題の中でも最も困難な問題の1つ N個の仕事をM台の機械で処理 すべての仕事を処理し終えるまでの総所要時間(makespan)を最小化 技術的順序 各仕事を処理する機械の順序 内挿交叉の有効性および内挿+外挿交叉の有効性

JSPにおける近傍と距離 近傍の設計 距離の定義 アクティブCB近傍[Yamada96]を利用 クリティカルパスに基づく高性能な近傍 I2 距離[Sakuma2000]を利用 各仕事の絶対的な位置(順列上の位置)の差

JSPにおける内挿交叉と外挿交叉 内挿交叉 外挿交叉 親p2に近づく近傍個体の生成 親p1に親p2の仕事の絶対位置をコピー

JSPにおける内挿交叉の有効性 実験：内挿交叉 / 他の内挿性の交叉の比較 最適解を得た回数 比較対象 CCM [Ono，2001] & inter machine JOX [Ono98] 母集団サイズ：100 内挿交叉は他の高性能な交叉よりも良好な結果が得られる

JSPにおける内挿+外挿交叉の有効性 実験：内挿 / 内挿+突然変異 / 内挿+外挿(提案手法)の比較 内挿+外挿＞内挿+突然変異＞内挿 ： 外挿性要因が有効に働く

10 tough problemsの性能 近傍構造を考慮した有力な交叉との比較 その他の結果は論文から引用

順序付け問題における交叉設計のまとめ 順序付け問題における有効な探索の実現 親の良い形質の組み合わせ＋ 親が持っていない形質の獲得 (内挿領域での探索) (外挿領域での探索) 内挿+外挿領域における多段階探索の有効性をTSP(単峰性)，JSP(多峰性)で示した 内挿+外挿交叉 ＞ 内挿交叉+突然変異 ＞ 内挿交叉 その他，より一般化された順序付け問題であるQAPにおいてもその有効性は示されている 順序付け問題一般において，内挿/外挿領域の多段階探索の有用性

GAの実用化における課題 (1) より強力な探索の実現 (2)高速に良い解を求める/信頼性の高い探索の実現 主探索オペレータである交叉において性能かつ汎用性を高める (2)高速に良い解を求める/信頼性の高い探索の実現 GAは従来より並列処理 (多点探索)で解決 年々，並列計算環境の規模が拡大 従来の粒度の並列処理 → 爆発的な並列度数を有する計算環境に対応できる 　　GAの並列モデルの開発

多資源計算環境下でのGAの並列モデル(4章)

最適設計をとりまく計算環境 膨大な計算資源の供給源 限られた少数の資源 膨大な資源の使用が可能 数千ノード規模のPCクラスタ 限られた少数の資源　　　膨大な資源の使用が可能 数千ノード規模のPCクラスタ 大規模なGrid計算環境 5～10x106ノード 今後も増加，大規模化 だいたい2000以上 4000～8000 最適設計の将来 1つの解の評価がやっと → 設計を数理モデル化し，計算シミュレーションで

GAにおける並列処理 GAの特徴 GAの並列化の研究 多点探索 高い並列性を有する 将来的には，膨大な資源を用いたGAによる最適設計 多点探索　　　高い並列性を有する 数十～数百ノードのPCクラスタ 将来的には，膨大な資源を用いたGAによる最適設計 GAの並列化の研究 大規模計算環境を対象としたアプリケーション

従来の並列GAの問題点 (大規模計算環境) 爆発的な並列度数の計算環境でのノードの利用方法 1．個体数の増加による並列度の向上 多様性の極端な増大 収束が遅くなる 計算コスト(時間，評価計算回数)を制限した場合は性能が低下 収束の早いモデルを利用すると解探索性能が低下 研究を通してGAの問題点がわかってきました． もちろん10000個体だとよくなるけど スケーラビリティは低下しない(←?)が探索性能が落ちる 不要な計算は行っていない

従来の並列GAの問題点 (大規模計算環境) 爆発的な並列度数の計算環境でのノードの利用方法 2. 複数の母集団で並列してGAを実行 　(複数回の試行を並列) 同じ解への探索が進む可能性 ノード間で探索の重複 これまでにいくつかgridへの適用が見られる． GAの並列化の研究の主流はこれらの環境を対象としたアプリケーションとなっていく 1.は不要な計算をしない 計算量は増えているのに，

ノード間の重複 複数の母集団で並列してGAを実行 (複数回の試行を並列) Rastrigin関数(2次元)：探索空間の大きさ＝220 ＝ 1.05x106 1台のノード･･･10個体で20世代のGA　(2010評価計算) 500台のノード･･･2010x500 ＝ 1.005x106 全探索と同等の個体数を計算しても，GAで探索している領域は20％ 不要な計算をしているノードが存在 これは，実際に探索の重複の度合いを検証したものです． 1試行で10個体20世代のGAについてその試行数を増やしたとき，すなわち実行ノード数を増やしたときの探索した領域の 増加を示しています．なお対象問題は2次元のrastrigin関数問題で，20ビットの問題です．全探索領域の大きさは100万 程度です． ちょうど500台くらいノードを使ったときに100万程度の個体を評価しており，総評価計算回数が全探索領域の大きさに 相当するのですが，実際に探索されていた個体は20万程度，すなわち，残り80万の個体は 重複して計算していたことがわかります． 飽和状態に向かう傾向が見られる これ以上ノードを増やしてもその効果は得られない 探索性能は維持できるが，無駄な計算が行われている

大規模計算環境におけるGAで考慮する点 計算資源数の増加に対して，解探索性能を低下させることなく，スケーラビリティを向上 スケーラビリティ 計算資源の増加　　 探索した領域の拡大 不要な計算が行わなれない 1．個体数の増加による並列度の向上 2. 複数の母集団で並列してGAを実行(複数回の試行を並列) 不要な計算は行わないが性能が低下 性能は低下しないが，不要な計算が存在(探索の重複) 従来の並列化の方法 スケーラビリティの考えにそった仕組み→ローカルサーチ GAは膨大な計算リソースを有効に利用できない

大規模計算環境におけるGAで考慮する点 不要な計算が行わなれない仕組み 計算資源を有効に利用する仕組み 探索の重複の回避･･･既に探索したところは探索しない 1試行内での重複, 試行間での重複 タブ・サーチ，リスタート ← 既探索領域のデータベース 計算資源を有効に利用する仕組み 資源が膨大に存在するときには，GAが利用しきれない 一部のノードを効率的に利用 スケーラビリティの考えにそった仕組み→ローカルサーチ 未探索領域を探索するローカルサーチ 既探索領域の拡大操作

スケーラビリティを保持する仕組み スケーラビリティの考えにそった仕組み→ローカルサーチ

既探索個体を保存するデータベース 巨大な解空間での探索解の保存 限られたデータで全既探索領域を表現する必要 1つの個体を1つのデータとして保存　 　膨大なデータ量 例) 個体：{0,1}のビット列　染色体長=30のとき…230(=109) 既探索解の参照時にも多大な時間 限られたデータで全既探索領域を表現する必要 (1) スキーマを用いた表現 (2) 2次元座標を用いた表現 マッピング手法 　　[T.Collins, 1996] 個体と座標が1:1に対応

データベースの個体を用いたローカルサーチ 計算資源を有効に利用する仕組み 未探索領域を探索するローカルサーチ 既探索領域の近傍個体を探索･･･探索領域を拡大 1領域を1ノードに割り当てることで並列化 ローカルサーチ (x1,y1) (x2,y2) GA

データベースを組み込んだGA 実験: ローカルサーチを適用することの効果 データベースの利用方法は任意 Step1: GAの母集団に対して，遺伝的オペレータを適用 Step2: GAの母集団の個体をデータベースに保存 (部分的，例:ベストの解) Step3: データベースに保存されている領域に対して 　　　　 ローカルサーチ(未探索領域の探索)を適用 シンプルな方法を利用

探索の特徴 最良解の適合度，既探索領域の大きさの推移 (1max問題) GAをベースとしているためGAと同等の解探索性能 母集団サイズ：20 世代交代モデル：ER [Thierens94] ベストを毎世代保存 GAをベースとしているためGAと同等の解探索性能 既探索領域の大きさが定量的に把握可能 有限の計算コストの下で全探索(得られた解が最適解であること)を保証

探索の特徴 最良解の適合度，既探索領域の大きさの推移 (3-DECEPTIVE問題) 母集団サイズ：20 世代交代モデル：ER [Thierens94] ベストを毎世代保存 3-DECEPTIVE問題：GAが局所解に陥りやすいだまし問題 GAと同様に局所解に陥るが，探索を進めることにより最適解が得られる

分散環境での実装 Grid MPを用いて実装 2006年度より同志社大学が分散コンピューティング環境を運用開始 GA ローカルサーチ (x1,y1) (x2,y2) GA

Grid MP 米United Devices社の商用ミドルウェア マスターワーカ型 　サーバ(MP Server)，計算ノード(Devices) 実行形態 1. ユーザがMP Serverにジョブをサブミット 2. 計算ノードはポーリングの際にジョブを取得し，実行の後，MP Server に結果を返す. These operations we talk until now are our local search mechanism in the database.

分散環境での実装 GA とローカルサーチを非同期 GAをローカルのマシンで実行 MP Serverでデータベースを保持 ベストの解を毎世代データベースに保存 Because of overhead

分散環境での実装 GA とローカルサーチを非同期 ローカルサーチを分散環境で実行 各計算ノードは割り当てられた既探索領域から未探索領域を探索し，定期的に結果をサーバに返す Because of overhead 利用できる計算ノード数分だけローカルサーチ

分散環境での検証 同志社大学キャンパスグリッドのテスト環境 LS GA 5-trap関数(20 partitions) 解探索性能 既探索領域 ローカルサーチ １分毎にサーバに結果を返す ノード数を増加させることで解探索性能，既探索領域が向上

多資源計算環境下でのGAの研究まとめ データベースをGAに適用することで有効性を検討 既探索領域情報を利用したタブサーチとリスタート 計算コストを制限しない場合の解探索性能 解探索の特徴 有限の計算コストの下で全探索(得られた解が最適解であること)を保証 計算ノード数の影響 ノード数を増加させることで解探索性能，既探索領域が向上 計算コストを制限した場合の解探索性能 既探索領域情報を利用したタブサーチとリスタート １試行内，試行間での探索の重複を回避

GAの実用化における課題 (1) より強力な探索の実現 (2)高速に良い解を求める/信頼性の高い探索の実現 主探索オペレータである交叉において性能かつ汎用性を高める (2)高速に良い解を求める/信頼性の高い探索の実現 GAは従来より並列処理 (多点探索)で解決 爆発的な並列度数を有する計算環境に対応できる GAの並列モデルの開発 実問題への適用として複雑ネットワーク設計

GAによる複雑ネットワーク設計(5章)

複雑ネットワーク設計の研究の目的 これまでの提案手法の実用例として 複雑ネットワークの解析のためのツールとしてのGAの利用 内挿+外挿交叉(3章) 大規模並列のためのデータベース(4章) 複雑ネットワークの解析のためのツールとしてのGAの利用

複雑ネットワーク 現実世界に存在する複雑で巨大なネットワークの性質について研究する，グラフ理論の1分野 複雑ネットワーク解析の目標 例) WWWのリンク 実在するネットワーク 航空路のネットワーク たんぱく質の相互作用ネットワークなど スケールフリー性，スモールワールド性 次数分布のべき乗則，平均パス長の短いネットワーク (引用:http://ja.wikipedia.org/wiki/) 複雑ネットワーク解析の目標 ネットワークの発生，成長が何に起因しているのか

最適化に基づくアプローチ ネットワークの特性量を目的関数とした最適化問題に定式化 ⇔ 最適化により生成されたネットワークと複雑ネットワークの特性を比較することで複雑ネットワークが有する特性は何に起因しているかを探求 例) 航空路のネットワーク 因子の仮説 新密度と距離の最適化 距離を最適化 - 都市の規模(人口) 比較 - 都市間の親密度 ⇔ (人の行き来) - 都市間の距離 ネットワークを通して，要因どうしの相互関係をみる 実際のネットワーク ネットワーク間の(部分的な)類似性，複雑性が見られたなら，仮説の因子は妥当 ネットワークを形成する因子間の相互関係を把握

最適化に基づくアプローチ 問題：複雑ネットワークを形成すると考えられる基本的な ネットワーク特性量を最小化するようなネットワークを生成 問題：複雑ネットワークを形成すると考えられる基本的な 　　　 ネットワーク特性量を最小化するようなネットワークを生成 目的関数：平均パス長，クラスター係数など 制約条件：ノード数，総エッジ数を固定

GAの利用 (1) 解表現を工夫することでネットワークをダイレクトに操作可能 (2) 初期の探索ステップで解が未進化な状態でも，完全な解候補として 　　 扱うことが可能 (3) 多点を用いた探索のため，多目的問題への拡張が容易 　　 (複数の特性量を最小化)

目的関数(1) 平均最短移動距離を最小化 Objective function: ノード ni ，nj 間の最小距離 …エネルギーフローなどに対応 Objective function: ノード 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を対象 (同志社大学 キャンパスグリッド環境) bayg29-45を対象 ローカルサーチを有するデータベースを適用することにより，さらに探索性能は向上

ネットワーク設計問題におけるまとめ これまでの提案手法の実用例として 内挿+外挿交叉(3章) 大規模並列のためのデータベース(4章) ネットワークの特性量を目的関数とした最適化問題に定式化し，ネットワークを生成 内挿+外挿+データベース＞内挿+外挿＞ 内挿交叉 ＞一般の交叉

GAで得られたネットワーク群 Fitness = WD * (平均移動距離)+ WC * (クラスタ係数) 全体的ににクラスタ係数の高いネットワーク クラスタ係数と距離にトレードオフ

全体のまとめ (1) 探索性能，汎用性の向上 (2) 実用性の向上 (1) ，(2)について実問題(ネットワーク設計)で有効性を示した 外挿領域における遺伝的多段階探索を提案 内挿 / 外挿領域における遺伝的多段階探索 2種の異なる問題(ランドスケープの観点より)，巡回セールスマン問題，スケジューリング問題において有効性を示した (2) 実用性の向上 大規模計算環境におけるGAのためのデータベースとローカルサーチ データベースの応用としてのタブサーチ，リスタート 計算コストを多くするほど，既探索領域の拡大，探索性能の向上 GAの1試行内，試行間の探索重複の回避 (1) ，(2)について実問題(ネットワーク設計)で有効性を示した

本研究の意義 離散最適化におけるGAの応用に関する2つの課題 (1) 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. 研究の背景と目的 2. 順序付け問題におけるGAの有効な探索オペレータの開発 3. 多資源計算環境下でのGAの並列モデル - 離散最適化問題 - 遺伝的アルゴリズム (Genetic Algorithm; GA) 2. 順序付け問題におけるGAの有効な探索オペレータの開発 3. 多資源計算環境下でのGAの並列モデル 4. 実際の離散最適化問題へのGAの適用 複雑ネットワーク解析 5. 結論

GAの実問題への適用にあたっての課題 (1) 探索性能，汎用性の向上 (2) 実用性の向上 主探索オペレータである交叉の設計 離散最適化問題における従来の交叉のアプローチ ・性能が高い 　 ⇔ 問題に特化 ・汎用性が高い ⇔ 性能が低い (2) 実用性の向上 GAは多点探索 → 並列処理，大規模計算環境におけるモデルの開発 年々，利用可能な計算機環境の規模が拡大 使える計算資源を効果的に利用できるモデル

最適化によるアプローチ 離散最適化問題の多くは膨大な解空間 … N!，NM など (1) 厳密解法 分枝限定法，動的計画法など (2) 近似解法 / 発見的解法　～ 現実的な時間で満足解 欲張り法，局所探索，散布探索 遺伝的アルゴリズム(GA)，シミュレーテッドアニーリング（SA） 背景：計算機，ネットワーク性能の向上 「十分速い」あるいは「許容できる/現実的」な時間内に計算できる量が飛躍的向上

遺伝的アルゴリズム(GA) 生物の進化を模倣した確率的な最適化アルゴリズム 設計変数は遺伝子型で表現 染色体=解，個体 {0,1}ビット，整数，順列

形質遺伝の難しさ 順序付け問題は変数間の依存が強いものが多い バランスよく親の部分解(形質)を受け継がせるのが難しい pattern 1 親1よりの個体しか生成されない pattern 2 組合せ最適化問題は~を受け継ぎにくい 親1,2とまったく違う個体が生成される 親2よりの個体しか生成されない

順序付け問題の交叉の課題[1] – 形質遺伝 dMSXFは形質遺伝性に優れた交叉 両親の間に子個体を生成

TSPにおける内挿+外挿交叉の有効性 実験：内挿+外挿(提案手法)の有効性 単峰性の問題の特徴 最適解を得た回数 母集団サイズが小さいとき 内挿+外挿 ＞ 内挿 母集団が十分大きいとき 内挿+外挿 ＝ 内挿 単峰性の問題の特徴

JSPにおける内挿交叉 (親p1→p2の近づけ方)

JSPにおける外挿交叉 (親p1,p2の遠ざかり方)

JSPにおける外挿交叉の役割 実験：局所解側に母集団を初期化 50試行 48 1 21 28 内挿 内挿+外挿 局所解A 大域的最適解 他の局所解 内挿 48 1 内挿+外挿 21 28

多資源計算環境での並列モデルに関する研究の目的 GAの探索の特徴 現実的な計算コストで満足解を得られる ⇔ 計算コスト，計算ノードを費やしすぎると性能向上が飽和 無駄な計算の存在 計算コストを費やすほど良い結果が得られる仕組み なんで01 得られた解に何の保証もない 解を{0,1}ビットで表現するGA (解空間が可算かつ有限)を対象

従来の並列GAの問題点 (大規模計算環境) 爆発的な並列度数の計算環境でのノードの利用方法 2. 複数の母集団で並列してGAを実行 　(複数回の試行を並列) 同じ解への探索が進む可能性 ノード間で探索の重複 探索性能は維持できているが，無駄な計算が行われている これまでにいくつかgridへの適用が見られる． GAの並列化の研究の主流はこれらの環境を対象としたアプリケーションとなっていく 1.は不要な計算をしない 計算量は増えているのに，

大規模計算環境におけるGA スケーラビリティの考えにそった仕組み→ローカルサーチ

個体の表現 ビット列の個体を2次元座標(x, y)で表現 マッピング手法：N次元の解空間 2次元平面 [T.Collins, 1996] 個体と座標は1:1に対応 2次元平面全体=解空間

既探索個体を保存するデータベース e.g. 6ビットの問題の2次元平面 個体と座標は1:1に対応 2次元平面全体=解空間 個体間のハミング距離が1 とりうるすべての解が2次元平面上に配置

既探索個体を保存するデータベース ビット列の個体を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関数 データベースをタブサーチに利用することで試行内の探索の重複を回避 ベストの解の推移 既探索解の再評価数 最適解を得た回数 データベースをタブサーチに利用することで試行内の探索の重複を回避

リスタート 実験：タブサーチ，リスタートの有効性 母集団が収束 初期化 22 200 既探索領域内の解の再評価の禁止 200回のリスタート Griewank関数(2次元) 母集団が収束　 初期化 既探索領域内の解の再評価の禁止 200回のリスタート 得られた解の種類 タブサーチ無 22 タブサーチ有 200 リスタートによる複数試行においても探索の重複が回避可能

分散環境での検証 同志社大学メディア課が運用するGrid MPテスト環境 ローカルサーチ １分毎にサーバに結果を返す 5-trap関数(20 partitions) GA LS

分散環境での検証 5-trap関数(20 partitions)，500世代での結果 解探索性能 既探索領域 ノード数を増加させることで解探索性能，既探索領域が向上

多資源計算環境下でのGAの研究まとめ

最適化に基づくアプローチ ネットワークの特性量を目的関数とした最適化問題に定式化し，ネットワークを設計 ⇔ 設計されたネットワークの持つ特性と複雑ネットワークの持つ特性とを比較することで複雑ネットワークが有する特性は何に起因しているかを探求 例) 航空路のネットワーク 要因の仮説 距離を最適化したネットワーク - 都市の規模(人口) - 都市間の関連度 ⇔ (人の行き来) ネットワークを通して，要因どうしの相互関係をみる - 都市間の距離 実際のネットワーク ネットワーク間に(部分的な)類似性が見られたなら，仮説の要因は妥当

最適化に基づくアプローチ ネットワークの特性量を目的関数とした最適化問題に定式化し，ネットワークを設計 ⇔ 例) 航空路のネットワーク 因子の仮説 関連度と距離の最適化 距離を最適化 - 都市の規模(人口) 比較 - 都市間の関連度 ⇔ (人の行き来) - 都市間の距離 ネットワークを通して，要因どうしの相互関係をみる 実際のネットワーク ネットワーク間に(部分的な)類似性が見られたなら，仮説の因子は妥当 因子間の相互関係

目的関数(1) 平均最短移動距離を最小化 Objective function: ノード ni ，nj 間の最小距離 D=5.733 Pattern 1が最良解

最適化に基づくアプローチ ネットワークの特性量を目的関数とした最適化問題に定式化 ⇔ 最適化により生成されたネットワークと複雑ネットワークの特性を比較することで複雑ネットワークが有する特性は何に起因しているかを探求 例) 航空路のネットワーク 因子の仮説 関連度と距離の最適化 距離を最適化 - 都市の規模(人口) 比較 - 都市間の関連度 ⇔ (人の行き来) - 都市間の距離 ネットワークを通して，要因どうしの相互関係をみる 実際のネットワーク ネットワーク間に(部分的な)類似性が見られたなら，仮説の因子は妥当 比較を通して，ネットワークを形成する因子間の相互関係を把握