実験結果は同じく表6.1〜表6.4に示される。括弧中の数値は，厳密な最適値（Global
Optimal）に対する相対誤差率である。また“♦”でマークされた結果は2つ手法の結果の
中に優れた結果である。
第6章 数値実験 49
実験結果は以下のことを表す：
（1） 2つの手法の結果の差は小さいが，0-1KP問題，TSP問題，FSP問題では，提案手 法の結果が少し劣ることが示された。QAP問題だけに，特に集団数が多い場合に，
良い平均値や最良値を得たことがある。
（2） 探索点数の増加と共に，2つの手法の結果の差は更に減少する。探索点数が少ない 時の提案手法の結果から，探索点数が多い時の結果への改善は，従来手法の改善よ り大きい。
以上の結果から，以下のことを明らかにした。
（1） 結果の差が小さいことから，提案手法は従来手法と同等な探索性能を有することが 分かった。特に近接最適性原理（POP）の成立度合いが弱いQAP問題に対する探 索性能は，従来手法より探索性能が上回っている。したがって，本研究で提案した 拡張的探索機構を用いる新たな探索点の移動戦略の有用性が検証され，それを用い れば，性能が高い組合せ最適化手法を開発できることを証明した。
（2） 拡張的探索機構の導入によって，従来手法の課題である集中化探索への偏りは一定 程度解消できることを証明した。また，探索点数（集団数）の増加により，多様化 効果の増大も確認された。
現実の最適化では，解決する問題に適合する近傍生成・距離計算方法の使用は望まれず，
解空間のPOPの成立度合いが弱いのは殆どである。したがって，実応用において，新たな 探索戦略と提案手法の性能が従来手法より発揮できると考えられ，新たな探索戦略と提案 手法の汎用性はより高いと考えられる。
また，実験結果が劣ることについて，前節に述べたように，2つの手法では，重複探索 等の課題に与えた影響は既に排除された。その原因を多様化・集中化戦略の観点から考慮 すべきである。
殆どの結果に提案手法は従来手法と同じように厳密な最適値を最良値として得られるこ とから，提案手法の最大性能は従来手法に劣らないことが分かった。そして平均値，最悪 値，標準偏差から，提案手法の性能の安定性が少し劣ることは明白である。移動のメカニ ズムと実際の移動状況を分析すると，性能が劣る原因が主に提案手法の集中化の不十分で あることが分かりました。具体的に：
第6章 数値実験 50
• 良い解の付近により良い解を探索する戦略を同じく使用するが，先行研究の手法で は，最良解が広く共有され，多数の探索点は良い解に接近できる。故に，過剰な集中 化による無駄な探索が生じるが，最良解付近に十分な集中化探索が保証されている。
• しかし提案手法の場合に，最良解の共有は限定的である。各集団は別集団の解だけ を目指すため，集団の良い解の付近に自ら集中探索できない。また，最良解の所属 集団が拡張するため，最良解を拡張方向とする集団は最良解に接近できなくなる可 能性が存在する。つまり，最良解を保有する集団も別集団も最良解の付近に集中探 索できない可能性があり，提案手法で使用するPOPの戦略が妨害される可能性は 生じる。
上述の現象が示す根本的な原因は，設計された方向ペアの生成・選択方法は完全に探索 戦略に適合していないことである：
• 方向ペアの生成は，他の集団の解の情報に基づく拡張方向で行っており，集団自身 の情報に基づく方向ペアの生成はない。
• 方向ペアの選択は，単純に方向とする解の評価値の良さで行われる。この時，該当 解との距離が大きく，少ない手順で近づかない（集中化できない）可能性が存在し る。故にPOPに基づく方向ペアの選択方法では，方向とする解の評価値だけでな く，方向ペアの内部距離も考慮すべきてある。
以上を解決するため，探索戦略に更に適合する方向ペアの生成・選択方法を検討する必 要がある。それを今後の課題とする。
第6章 数値実験 51
表6.1:0-1KP問題における数値実験のバラメータ設定と実験結果 ProblemGlobalOptimalFCm=10m=20 HS-MCOMPMHS-MCOMPM 50bit5725×104
w00.2500.1 r44 mean571.90♦(0.02%)569.16(0.50%)571.70♦(0.05%)570.22(0.31%) best572.00♦(0.00%)572.00♦(0.00%)572.00♦(0.00%)572.00♦(0.00%) worst570.00♦(0.35%)565.00(1.22%)570.00♦(0.35%)569.00(0.52%) SD0.361.500.541.07 100bit20532.5×105
w0.10.10.10 r44 mean2050.60♦(0.12%)2047.10(0.29%)2051.64♦(0.07%)2050.08(0.14%) best2053.00♦(0.00%)2053.00♦(0.00%)2053.00♦(0.00%)2053.00♦(0.00%) worst2045.00♦(0.39%)2030.00(1.12%)2048.00♦(0.24%)2039.00(0.68%) SD1.966.291.573.59 500bit104905×106
w0.2500.100 r44 mean10456.20♦(0.32%)10398.54(0.87%)10477.06♦(0.12%)10422.26(0.65%) best10483.00♦(0.07%)10433.00(0.54.00%)10488.00♦(0.02%)10457.00(0.31%) worst10407.00♦(0.79%)10363.00(1.21%)10453.00♦(0.35%)10394.00(0.92%) SD16.6815.457.2013.93
第6章 数値実験 52
表6.2:TSP問題における数値実験のバラメータ設定と実験結果 ProblemGlobalOptimalFCm=10m=20 HS-MCOMPMHS-MCOMPM bayg2916105×105
w0.10.10.10 r44 mean1610.00♦(0.00%)1610.50(0.03%)1610.00♦(0.00%)1610.10(0.01%) best1610.00♦(0.00%)1610.00♦(0.00%)1610.00♦(0.00%)1610.00♦(0.00%) worst1610.00♦(0.00%)1615.00(0.31%)1610.00♦(0.00%)1615.00(0.31%) SD0.001.520.000.71 att48106282.5×106
w0.250.10.250 r1020. mean10640.36♦(0.12%)10656.20(0.27%)10632.58♦(0.04%)10639.74(0.11%) best10628.00♦(0.00%)10628.00♦(0.00%)10628.00♦(0.00%)10628.00♦(0.00%) worst10707.00♦(0.74%)10738.00(1.04%)10707.00(0.74%)10688.00♦(0.56%) SD19.0229.9713.2015.62 st706751×107
w0000 r1010 mean676.26♦(0.19%)676.77(0.26%)675.30♦(0.04%)676.06(0.16%) best675.00♦(0.00%)675.00♦(0.00%)675.00♦(0.00%)675.00♦(0.00%) worst682.00♦(1.04%)681.00♦(0.89%)681.00(0.89%)680.00♦(0.74%) SD2.282.621.341.75
第6章 数値実験 53
表6.3:FSP問題における数値実験のバラメータ設定と実験結果 ProblemGlobalOptimalFCm=10m=20 HS-MCOMPMHS-MCOMPM ta01115821×106
w0.2500.4 r1020 mean1582.90♦(0.06%)1588.68(0.42%)1583.04♦(0.07%)1585.94(0.25%) best1582.00♦(0.00%)1582.00♦(0.00%)1582.00♦(0.00%)1582.00♦(0.00%) worst1585.00♦(0.19%)1598.00(1.01%)1586.00♦(0.25%)1601.00(1.20%) SD0.684.561.034.22 ta03127241×105
w00.100 r1010 mean2724.00♦(0.00%)2724.30(0.01%)2724.00♦(0.00%)2724.10(0.00%) best2724.00♦(0.00%)2724.00♦(0.00%)2724.00♦(0.00%)2724.00♦(0.00%) worst2724.00♦(0.00%)2729.00(0.18%)2724.00♦(0.00%)2729.00(0.18%) SD0.001.200.000.71 ta04129912×107
w00.2500 r2020 mean3030.16♦(1.31%)3044.64(1.79%)3028.66♦(1.26%)3040.24(1.65%) best3025.00♦(1.14%)3034.00(1.44%)3025.00♦(1.14%)3025.00♦(1.14%) worst3052.00♦(2.04%)3055.00(2.14%)3039.00♦(1.60%)3052.00(2.04%) SD7.475.905.777.65
第6章 数値実験 54
表6.4:QAP問題における数値実験のバラメータ設定と実験結果 ProblemGlobalOptimalFCm=10m=20 HS-MCOMPMHS-MCOMPM Tai30a18181461×106
w0.10.40.10.25 r66 mean1851720.04♦(1.85%)1855422.00(2.05%)1854985.80(2.03%)1854270.92♦(1.99%) best1830440.00♦(0.68%)1835642.00(0.96%)1836572.00(1.01%)1829136.00♦(0.60%) worst1865750.00♦(2.62%)1867190.00(2.70%)1864704.00♦(2.56%)1867142.00(2.69%) SD8004.607103.116473.728713.89 Tai30b6371171131×106
w0.40.40.40.1 r66 mean639818394.84♦(0.42%)642165058.10(0.79%)640249405.10(0.49%)640034272.14♦(0.46%) best637808503.00(0.11%)637137951.00♦(0.00%)637140976.00(0.00%)637125163.00♦(0.00%) worst652650019.00♦(2.44%)657446440.00(3.19%)651358423.00♦(2.24%)652781459.00(2.46%) SD2971466.895371400.643013931.353635193.54