提案した移動戦略の有用性を検証するため，ベンチマーク問題を用いて数値実験を行 う。ベンチマーク問題としては，4.4で用いた問題と同様のものを使用し，n=m，n= 1， n=nkのそれぞれについて，TSに基づく多点探索型多目的最適化手法（Proposed Method:
PM）を用いて探索を行う。探索点数m= 20とし，タブーリストに追加する情報は4.4と 同様のものとする。ここで，提案手法のnkについては，簡単のため，
nk =
1 k ≤kmax/2
km−1max/2k+ 2−m otherwise
の式を用いてスケジューリングした。これは，nkでは反復回数がkmax/2に達するまでは n = 1であり，それ以降はnを1からmまで線形に変化させることを意味する。ただし，
nは整数しかとれないため，nkは小数第一位で四捨五入した値を用いることとする。
表5.1に，実験条件および50回試行したときのHypervolume Ratioの平均値（Mean）， 最良値（Best），最悪値（Worst），標準偏差（S. D.）と，評価回数の平均値（Function Call） の結果を示す。Hypervolumeの基準点Rは，全ての試行における初期解の評価値のうち，
各目的関数について最悪値fi,worstを用いて，R= (f1, f2) = (f1,worst, f2,worst)とする。ま た，表5.2に，0-1KPに対して50回試行したときのγ評価指標の平均値（Mean），最良値
（Best），最悪値（Worst），標準偏差（S. D.）の結果を示す。図6.2から図6.5に，0-1KP， TSP，FSP，QAPのそれぞれについて得られた解の例を示す。
第5章 多様化と集中化を考慮した新たな移動戦略の提案 35
表5.1： 実験条件と結果（Hypervolume Ratio）
Problem Size n LT kmax Mean Best Worst S. D. Function Call
m 0.886 0.901 0.869 0.00787 9025520
0-1KP 500 Items 1 50 1000 0.854 0.864 0.843 0.00419 9025520 nk 0.878 0.888 0.868 0.00528 9025520
m 0.915 0.919 0.912 0.00146 6404853
TSP 48 Cities 1 10 300 0.912 0.915 0.909 0.00132 6397930 nk 0.914 0.918 0.911 0.00165 6401660
20 jobs m 0.925 0.939 0.912 0.00573 1778932
FSP 10 machines 1 8 500 0.920 0.931 0.908 0.00514 1779945 nk 0.925 0.937 0.912 0.00604 1779543
m 0.545 0.557 0.532 0.00744 4198185
QAP 30 1 10 500 0.529 0.542 0.519 0.00539 4198709
nk 0.544 0.557 0.528 0.00568 4198482
表5.2： 実験条件と結果（γ評価指標）
n kmax Mean Best Worst S. D. Function Call m 722.53 617.40 814.56 54.0 9025520
1 1000 936.01 884.81 986.96 31.1 9025520 nk 1008.84 931.88 1098.54 53.6 9025520
第5章 多様化と集中化を考慮した新たな移動戦略の提案 36
(a) n=m
(b) n= 1
(c) n=nk
図5.1： 得られた解の例（0-1KP）
(a)n =m
(b) n= 1
(c) n =nk
図5.2： 得られた解の例（TSP）
第5章 多様化と集中化を考慮した新たな移動戦略の提案 37
(a) n=m
(b) n= 1
(c) n=nk
図5.3： 得られた解の例（FSP）
(a)n =m
(b) n= 1
(c) n =nk
図5.4： 得られた解の例（QAP）
第5章 多様化と集中化を考慮した新たな移動戦略の提案 38
5.3.2 数値実験に対する考察
表5.1より，全ての問題について，n = 1のときと比較して，n = nk のときの方が Hypervolume Ratioが良い。また，図からも，TSP，FSP，QAPにおいて，n= 1のとき に幅広い解が得られるという特徴を活かしながら，より正確な解を得られていることが分 かる。以上より，提案した戦略は一定の有用性があると言える。
一方で，0-1KPにおいては，表5.1より，n = 1のときと比較してHypervolume Ratio は改善しているものの，表5.2から解の正確性はn=mのときおよびn= 1のときの両方 と比較して悪化していることが分かる。また，図からは，評価値空間で両端付近に存在す る解はn = 1のときよりも改善しているものの，それ以外の解の改善が見られていない。
このような原因として，
• 0-1KPの場合，近傍N(x)内の解は，xと比較して全ての目的関数において改良す るか改悪するかの二通りに分別されるため，幅広い近傍生成を行うことができない こと
• 制約条件を満たさない解の扱いが不適切であること
などが考えられる。
また，本章では多様化・集中化を制御するパラメータとしてnを扱った。しかし，これ は整数値しかとれないパラメータであり，また今回は単純なスケジューリングを用いてい るため特に探索中盤において多様化・集中化のバランスが適切にとれているかどうかに関 しては検討の余地がある。適切なnkの決定方法など，より適切に多様化・集中化を評価す る指標・パラメータや，多様化・集中化を実現する移動戦略の開発に関しては，今後の課 題であると言える。
6 近接最適性原理に基づく 多点探索型多目的最適化 手法の提案
4章および5章では，Tabu Searchに基づく多点探索型多目的最適化手法につい て扱った。一方で，最適化問題の解構造に広く見られる良構造の偏りとして，近 接最適性原理が知られており，多くのメタヒューリスティクスは，POPを根幹に 探索を行っていると考えられる。本章では，多目的最適化問題に対する近接最適 性原理について検討を行う。そして，その検討を基にした近傍生成および探索点 の選択・移動を行う，新たな多点探索型多目的組合せ最適化手法を提案する。