本章で提案した手法の有用性を検証するため，ベンチマーク問題を用いて数値実験を行 う。ベンチマーク問題としては，4.4で用いた問題と同様のものを使用する。POPを考慮 した多点探索型多目的組合せ最適化手法（Proposed Method: PM）について，探索点数 m = 20，l = 2とし，タブーリストに追加する情報は4.4と同様のものとする。比較手法 として，4章で提案した手法を，n =mおよびn= 1として用いる。
表6.1に，実験条件および20回試行したときのHypervolume Ratioの平均値（Mean）， 最良値（Best），最悪値（Worst），標準偏差（S. D.）と，評価回数の平均値（Function Call） の結果を示す。Hypervolumeの基準点Rは，全ての試行における初期解の評価値のうち，
各目的関数について最悪値fi,worstを用いて，R= (f1, f2) = (f1,worst, f2,worst)とする。ま た，表6.2に，0-1KPに対して20回試行したときのγ評価指標の平均値（Mean），最良値
（Best），最悪値（Worst），標準偏差（S. D.）の結果を示す。図6.2から図6.5に，0-1KP， TSP，FSP，QAPのそれぞれについて得られた解の例を示す。
第6章 近接最適性原理に基づく多点探索型多目的最適化手法の提案 47
表6.1： 実験条件と結果（Hypervolume Ratio）
Problem Size Method LT kmax Mean Best Worst S. D. Function Call n=m 495 0.865 0.885 0.846 0.01072 4480520 0-1KP 500 Items n= 1 50 495 0.827 0.840 0.813 0.00664 4480520 PM 1000 0.684 0.786 0.529 0.06039 4488666 n=m 159 0.912 0.917 0.907 0.00221 3398509 TSP 48 Cities n= 1 10 159 0.907 0.912 0.901 0.00226 3395482 PM 300 0.821 0.854 0.759 0.02212 3416424 20 jobs n=m 138 0.910 0.930 0.887 0.00796 491920 FSP 10 machines n= 1 8 138 0.905 0.920 0.897 0.00567 492265 PM 500 0.846 0.875 0.804 0.01403 494270 n=m 151 0.530 0.553 0.506 0.00911 1269484
QAP 30 n= 1 10 151 0.509 0.523 0.497 0.00611 1269688
PM 500 0.470 0.497 0.408 0.02417 1270547
表6.2： 実験条件と結果（γ評価指標）
Method kmax Mean Best Worst S. D. Function Call n=m 495 875.41 748.46 1003.21 63.1 4480520
n= 1 495 1106.22 990.63 1246.54 60.5 4480520 PM 1000 1760.34 1167.01 2513.59 344.0 4488666
第6章 近接最適性原理に基づく多点探索型多目的最適化手法の提案 48
(a) n=m
(b) n= 1
(c) PM
図6.2： 得られた解の例（0-1KP）
(a)n =m
(b) n= 1
(c) PM
図6.3： 得られた解の例（TSP）
第6章 近接最適性原理に基づく多点探索型多目的最適化手法の提案 49
(a) n=m
(b) n= 1
(c) PM
図6.4： 得られた解の例（FSP）
(a)n =m
(b) n= 1
(c) PM
図6.5： 得られた解の例（QAP）
第6章 近接最適性原理に基づく多点探索型多目的最適化手法の提案 50
6.4.2 数値実験に対する考察
表6.1より，全ての問題において，POPを考慮した多点探索型多目的組合せ最適化手法 は，同じく一対一の移動を行うn= 1のときと比較してもHypervolume Ratioが低い値と なっている。また，表6.2，および図6.2から図6.5より，Hypervolume Ratioが低い原因 として，n=mのときおよびn= 1のときと比較して，解の正確性が劣るからであると考 えることができる。
この主な原因として，以下のものが考えられる。
• ランク1の探索点が，正確性を高めるための適切な移動を行えていない
– POPを考慮した多点探索型多目的組合せ最適化手法では，評価値空間上で近く に位置する解から離れるような近傍生成を行い，さらにタブーを用いて探索の サイクリングを防ぐように方向づけを行ったが，適切な近傍生成になっていな かった
– POPを考慮した多点探索型多目的組合せ最適化手法における，評価値空間上で ランクが高く，疎な領域に存在する解を選択し，探索点ごとに一対一で移動す る移動方法が，生成した近傍に対して適切なものではなかった
• ランク2以下の探索点が，広がりを持った解を得るための適切な移動を行えていない – POPを考慮した多点探索型多目的組合せ最適化手法では，得られたパレート解 に評価値空間上で近づくような近傍生成を行ったが，このような近傍生成が，
広がりを持つ解を得る妨げとなった
– 各目的関数について最良値を取る解を新たな探索点とするような移動戦略が，
うまく働かなかった
これらについての検証は，今後の課題である。
7 結論
7.1 まとめ
本論文では，多目的組合せ最適化問題を対象とした，実用的な最適化手法の構築を目標 とし，近傍探索に基づく多点探索型多目的組合せ最適化手法を提案した。
そして，数値実験を通してその有用性を検証した。本論文で得られた成果を以下に述 べる。
(1) 近傍生成は，近傍探索に基づく代表的な手法であるTSに基づき，選択・移動につ いては，EMOの代表的な手法であるNSGA-IIにおいて導入されているCrowding
Tournament選択を参考に新たに提案した，TSに基づく多点探索型多目的最適化手
法を提案した。代表的なベンチマーク問題を用いた数値実験を通して，NSGA-IIと 比較し，有用性を確認した。
(2) メタヒューリスティクスの探索における代表的な探索戦略である多様化と集中化の 観点から，(1)で提案したTSに基づく多点探索型多目的最適化手法について解析を 行った。解析を踏まえて，探索の多様化・集中化を制御するパラメータとして，各 探索点の近傍から新たな探索点となる解の最大許可数nに注目した。nを，反復ご とに変化させるパラメータnkと解釈し，探索段階によってスケジューリングするこ とで，探索序盤は解空間を多様に探索し，探索終盤にかけて良い解周辺を集中的に 探索することを狙う新たな移動戦略を提案した。代表的なベンチマーク問題を用い た数値実験を通して，提案した移動戦略の有用性を確認した。
第7章 結論 52 (3) 最適化問題の解構造に広く見られる良構造の偏りであるPOPについて，多目的最 適化問題において新たな解釈を行った。多目的最適化におけるPOPを基に，探索 点の近傍生成および探索点の選択・移動において，評価値情報と距離情報に基づく 探索点間の相互作用を有する，新たな多点探索型多目的組合せ最適化手法を提案し た。代表的なベンチマーク問題を用いた数値実験を通して，提案手法の有用性を検 証した。