称号及び氏名

博士（工学）

学位授与の日付

平成 24 年 3 月 31 日論

「進化型多目的最適化手法と局所探索の文

名一柳徳宏

ハイブリッド化に関する研究」
論文審査委員

主査

教授

石渕久生

副査

教授

戸出英樹

副査

教授

市橋秀友

論文要旨
最適化問題を解くための手法は大別すると，最適性が保障される厳密解法と，最適解である保証はないが，最適解に近い近似解を求めるメタヒューリスティクスに分類される．厳密解法により求められる解は，最適性が保障されている．しかし問題の規模が大きくなると，厳密解法では実用的な時間内に最適解を求めることができない．メタヒューリスティクスにより得られる解は最適解とは限らないが，短時間で効率的に探索される近似解となる．メタヒューリスティクスの分類として，単一の解を保持して改良し続ける手法と，複数の解を保持して解同士の相互作用によっ て 良 い 解 を 探 索 す る 手 法 が あ る ． 前 者 の 例 と し て は タ ブ ー サ ー チ （ TS:TabuSearch）や焼きなまし法(SA: Simulated Annealing)などの局所探索が代表的であり，後者の例としては遺伝的アルゴリズム（GA: Genetic Algorithm）のような進化型最適化手法が代表的である．
現実世界の最適化問題は，単一の目的関数で定義されることは少なく，複数の目的関数で定義されることが多い．複数の目的関数を持つ問題は多目的最適化問題と呼ばれ，トレードオフの関係にある複数の目的関数を同時に最適化する必要がある．
多目的最適化問題では，全ての目的関数を同時に最適化する唯一の最適解は存在せず，パレート最適解と呼ばれる解が複数存在する．全てのパレート最適解の集合をパレートフロントと呼ぶ．多目的最適化問題ではパレートフロント，或いはパレートフロントに可能な限り近い解を多数発見することが一般的に重要であるとされる．
進化型最適化手法は，複数の解による多点探索という特長を活かすことで，多目的最適化問題においても，複数のパレート最適解，または近似パレート最適解を獲得できる．すなわち，進化型最適化手法は，多目的最適化問題に対して高い親和性を持つ．よって多目的最適化問題に進化型最適化手法を適用した進化型多目的最適化手法（EMO: Evolutionary Multiobjective Optimization）の研究は，進化型計算の分野で活発に行われ，様々な問題に対して応用されている．
進化型最適化手法は，複数の解に基づく探索を行うため，高い大域的探索能力を持つが，問題点として局所探索能力が欠如することが多くの研究で示されている．
この点を補うために，進化型最適化手法と局所探索のハイブリッド化が 1990 年代から研究されている．例えば，巡回セールスマン問題に対して，GA と TS や SA のハイブリッド化手法が提案され，GA の探索性能が改善されることが示されている．
GA と局所探索のハイブリッド化は，遺伝的局所探索（GLS: Genetic Local Search）
やハイブリッド GA，Memetic アルゴリズム(MA: Memetic Algorithm）と呼ばれている．ハイブリッド GA は，局所探索に限らず，GA と他手法を融合した手法の総称でもあるが，GLS や MA は進化型計算と局所探索が融合した手法を指す．Memeticとは，リチャード・ドーキンスのミームという概念から生み出された造語である．
一般的に，遺伝子は生物に内在し，遺伝子情報を親から子へ伝える役割があるため，環境に適応出来なかった生物は淘汰され，その生物の遺伝子は残らない．遺伝子は体内で変化することがないため ，遺伝子に基づく GA でも，解を表す記号列は学習・経験によって変化することがない ． 一 方，ミームとは人の考えや文化を，人から人へ伝えるものであり，個々人の脳内で淘汰が行われる．MA では，個々人の脳内でミームが変化することと，学習や経験などの局所探索によって，問題に対する解である記号列が変化することが対応している．進化型最適化手法に局所探索を組み込むことで，探索性能が改善されることは多数の研究で示されている．単一目
的 MA の実装方法に関しても数多く研究されており，これまでに探索戦略の自動適応を行う MA も研究されている．従来研究されてきた MA の大多数は，単一目的最適化を意図したアルゴリズムであり，多目的最適化問題に対して多くの研究は行われていない．現在活発に研究されている EMO アルゴリズムと比較しても，多目的MA に関する研究・調査は少数である．
単一目的 MA（SOMA: Single-objective Memetic Algorithm）において，局所探索における評価関数は，進化型最適化手法で用いられる適応度関数をそのまま適用可能である．つまり，単一目的最適化問題において，進化型最適化手法と局所探索のハイブリッド化における適応度関数の設定は容易である．一般的に，局所探索は，単一目的最適化問題のために唯一の最適解を求めるが，多目的最適化問題では多数の非劣解を求めることが重要となる．つまり多目的 MA の実装において，局所探索操作を多目的最適化問題に対し実行できるように設計することが重要である．
税所に提案された多目的 MA は，多目的遺伝的局所探索（MOGLS: Multiobjective

Genetic Local Search）として，多目的フローショップスケジューリング問題に対して有効性が示された．この MOGLS アルゴリズムでは，重みベクトルを用いて，複数の目的関数をスカラー化する加重和適応度関数を用いることで，局所探索のための適応計算を単一目的最適化問題として扱っている．また，加重和適応度関数を用 い る 多 目 的 MA と は 別 に ， 優 越 関 係 を 局 所 探 索 に お け る 解 の 比 較 に 用 い る
M-PAES アルゴリズムも研究されている．M-PAES では，優越関数の基づいた適応度計算と共に，目的関数を格子状に分割することで解の比較を行う．
局所探索が大域的探索を行う進化型最適化手法と比べて優れている点として，計算効率の良さがある．局所探索では，改良の対象となる解と，その近傍解を１対１で比較するが，進化型探索では，個体群中の全ての解に基づいて適応度を計算する必要がある．すなわ ち ，終了条件を同一に 設 定した場合，EMO ア ルゴリズムよりも，MOGLS アルゴリズムの方が短時間で終了することになる．
本論文では MOGLS アルゴリズムの実装手法について論述した．探索性能の高い多目的 MA を設計するために・ 局所探索における解の比較方法
・ 局所探索と大域的探索のバランス
・ 局所探索を適用する世代間隔
・ 局所探索を適用する初期個体の選択方法
・ 制約条件を満たさない解に対する操作
・ 局所探索における近傍解生成操作
な ど 多 く の 実 装 方 法 に つ い て 論 述 し た ． 数 値 実 験 で は EMO ア ル ゴ リ ズ ム で あ る
NSGA-II に局所探索を組み込んだ S-MOGLS アルゴリズムを用いた．多目的組合せ最適化問題に対する数値実験から，探索性能の高い MOGLS アルゴリズムの実装方法を明らかにした．
第１章では，本研究の動機，目的および内容の概略を示し，本論文の構成について述べた．
第２章では，NSGA-II に局所探索を組み込んだ S-MOGLS を用いた数値実験から，局所探索における解の比較方法，局所探索と大域的探索のバランス，局所探索を適用する世代間隔，局所探索を適用する初期個体の選択方法，制約条件を満たさない解に対する操作について，高い探索性能をもつ実装方法を，多目的 0/1 ナップサック問題に対する数値実験から明らかにした．
第３章では，適用する問題の背景知識を活用した近傍探索操作を，多目的 0/1 ナップサック問題と多目的フローショップスケジューリング問題に対して提案した．
多目的 0/1 ナップサック問題では，制約条件を満たさない個体に対して，従来研究されてきた加重和利得率による修復操作に加え，修復後に更にアイテムを追加する操作や，集中して近傍解を生成する操作を提案した．多目的フローショップスケジューリング問題では，目的関数の一つである最大納期遅れを最小化する近傍解生成操作を提案した．数値実験から提案手法の有効性を示した．
第４章では，局所探索と大域的探索のバランスを適切に設定することで，多数目的最適化問題に対しても，多目的 MA が高い探索性能を持つことを示した．多数目的最適化問題は，多 目 的最適化問題の目的 数 を増加させた問題で あ り，EMO アルゴリズムの探索性能が低下することが知られている．多数目的最適化問題では，目的数の増加に伴い非劣の関係になる解の数が増大する．結果として，優越関係に基づく適応度計算では，解集合に対する選択圧が働かなくなり，探索性能が大きく悪化する．数値実験では ，従来研究されてきた EMO アルゴリズムである NSGA-IIの探索性能が，目的数の増加に伴い悪化することを示した．次に NSGA-II に局所探索を組み込み，局所探索と大域的探索のバランスを適切に設定することで，探索性能が大きく改善することを示した．
第５章では，局所探索を適用する初期個体の選択方法について論述した．従来
NSGA-II に局所探索を組み込む場合，NSGA-II の進化型探索により生成される子個体群に局所探索を適用していた．しかし，新化型探索後に生成される子個体群には，元の親個体群と比較して劣解となる解が存在する場合があった．これらの解に対して局所探索を適用することが計算時間の浪費を招くことを示した．そして進化型探索により悪化する前の親個体に対して局所探索を適用し，生成される改良個体群に対して進化型探索を適用する MOGLS アルゴリズムを提案し，数値実験から提案手法の有効性を示した．
第６章では，本研究で得られた結果についての総括を行った．

審査結果の要旨
本論文は，進化型多目的最適化（EMO）アルゴリズムの探索性能を改善する手法として，EMO アルゴリズムと局所探索のハイブリッド化に関して提案，調査したものである．ベンチマーク問題を用いた実験的解析により，以下の成果を得ている．
（１）代表的な進化型多目的最適化（EMO）アルゴリズムである NSGA-II に局所探索を組み込むハイブリッド化の実装方法について調査した．多目的 0/1 ナ
ップサック問題に対する数値実験より，局所探索における解の比較方法，局所探索と大域的探索のバランス，局所探索を適用する世代間隔，局所探索を適用する初期個体の選択方法，制約条件を満たさない解に対する操作について，高い探索性能をもつ実装方法を明らかにした．

（２）適用する問題の背景知識を活用した局所探索操作を提案した．多目的 0/1 ナ
ップサック問題では，制約条件を満たさない個体に対して，従来研究されてきた加重和利得率による修復操作を改良し，修復後に可能な限りアイテムを追加する操作と，集中して近傍解を生成する操作を提案した．多目的フローショップスケジューリング問題では，目的関数の一つである最大納期遅れを最小化する近傍解生成操作を提案した．数値実験から提案手法の有効性を示した．
（３）NSGA-II の探索性能が低下することで知られている多数目的最適化問題において，NSGA-II と局所探索のハイブリッド化アルゴリズムの探索性能を調査した．数値実験では，NSGA-II に局所探索を組み込んだことで，多様性に関する探索性能が大きく改善されることを示した．また目的数が増加するに伴い，収束性に関する探索性能も改善されることを示した．
（４）従来のハイブリッドアルゴリズムでは進化型探索後に生成される子個体群に局所探索を適用していたが，子個体群には元の親個体群と比較して劣解となる解が存在し，計算時間の浪費を招くことを示した．進化型探索により悪化する前の親個体群に対して局所探索を適用し，生成される改良個体群に対して進化型探索を適用する MOGLS アルゴリズムを提案し，数値実験から提案手法の有効性を示した．
以上の研究成果は，知能情報工学分野における進化型多目的最適化の発展に貢献するところ大である．また，申請者が自立して研究活動を行うに必要な能力と学識を有することを証したものである．本委員会は，本論文の審査ならびに最終試験の結果から，博士（工学）の学位を授与することを適当と認める．