上述移動戦略の有用性が検証されたが，性能に悪影響を及ぼす課題はまだ残っている。
本研究は，近傍関係で構成される組合せ最適化問題の解空間における通常の探索機構が 表す特性を分析する。そして，これらの特性こそが，性能に悪影響を及ぼす課題が生じる 根本的な原因と考えられる。
4.4.1 組合せ最適化問題における通常の探索機構の特徴
通常の探索機構では，何らかの近傍生成・選択のメカニズムを用いて，探索点の現在の 解の更新に注目し，現在の解から次の解への移動を繰り返すことで探索し続ける探索方法 である。通常の探索機構を用いると，現在の解より良い解へ移動する事が可能である。そ のため，通常の探索機構は解の改善に単純且つ有効な手段だと考えられる。また，通常の 探索機構は以下の特徴を有する：
• 前回の更新における移動目標の解は，常に次回の更新における移動起点の解である。
• 上述の反復により，探索点の移動経路は分岐なしの単一ルートとして解空間に表さ れる。
これらの特徴を踏まえ，多点型最適化手法では，各探索点の移動経路が互いに交差するこ とが避けられない。
連続型最適化問題の解空間で多点型最適化手法を用いる場合に，連続型最適化問題の解 空間は下記の性質
• 連続型最適化問題の解の個数は無限である。
• 連続型最適化問題の個々の解は，連続型最適化問題の解空間に実体を持たず，体積 を占めない。
を持つため，通常の探索機構を使用する多点型最適化手法における各探索点が得た解は，
以下の関係を有する。
（1） 移動経路上にある各解の間は無数の解が存在する，そのため，移動経路上の個々の
第4章 解空間の上位構造に基づく組合せ最適化手法 27
解は隣接しない。連続型最適化問題の解空間では，移動経路は離散の点として表さ れる。
（2） 連続型最適化問題の個々の解は体積を占めないため，離散の点で構成される移動経 路も体積を占めない。
そのため，通常の探索機構において，各探索点の移動経路が互いに交差しても，問題が 生じない。
しかし，近傍関係で構成される組合せ最適化問題の解空間は，連続型最適化問題の解空 間と異なる性質を持っている：
• 解空間上の解の隣接関係は解の間の近傍関係で定める。
• 組合せ最適化問題の解の個数は有限である。
• 組合せ最適化問題の個々の解は，近傍関係で構成される組合せ最適化問題の解空間 に実体を持ち，体積を占める。
そのため，近傍関係で構成される組合せ最適化問題の解空間では，通常の探索機構を用 いる各探索点が得た解とその探索経路は以下の特徴を持つ：
（1） 解空間上の解の隣接関係は解の間の近傍関係で定めるため，移動経路上にある個々 の解は隣接する。
（2） 組合せ最適化問題の個々の解は解空間に体積を占めるため，探索経路も連続的に解 空間に体積を占める。
連続型最適化問題と組合せ最適化問題の解空間の違いは図4.7に示される。
上述の特徴により，通常の探索機構は近傍探索に基づく手法において，性能に悪影響を 及ぼす課題が生じる。
4.4.2 通常の探索機構から生じる課題
前節に述べた特徴を踏まえ，数値実験の検証とメカニズムの分析により，解空間の上位 構造に基づく組合せ最適化手法には，以下の性能に悪影響を及ぼす課題が存在する。
第4章 解空間の上位構造に基づく組合せ最適化手法 28
⤌ྜࡏ᭱㐺ၥ㢟ࡢሙྜ
㐃⥆ᆺ᭱㐺ၥ㢟ࡢሙྜ
␗࡞ࡿ᥈⣴Ⅼࡢ᥈⣴ᒚṔ᥈⣴⤒㊰
図4.7: 連続型最適化問題と組合せ最適化問題の解空間の比較
（1） 重複探索
上位構造における探索では，探索経路の交差による探索済み引き込み領域に対す る重複探索が発生する。更に，探索点の移動には決定論（最良移動戦略）を使うた め，続く探索経路も継続的に重複する可能性が高い。この場合，新しい局所的最適 解を得ず，計算量だけが増加し，全体の探索性能に深刻な影響を及ぼす。重複探索 のイメージは図4.8に示される。
␗࡞ࡿ᥈⣴Ⅼࡢ
ᒁᡤⓗ᭱㐺ゎࡢ᥈⣴ᒚṔ ᥈⣴⤒㊰
㔜」᥈⣴ࡍࡿ⤒㊰
図4.8: 重複探索
（2） 移動の遠回り
探索の進行と共に，非近接領域にある最良解が変動することが発生する。その場 合，今までの移動方向とは逆の方向へ移動しなければならない可能性がある。通常 の探索機構では常に現在の解から移動し始めるが故，新しい移動方向と離脱領域を
第4章 解空間の上位構造に基づく組合せ最適化手法 29
離れる方向の2つの距離関係条件を同時に満たすため，この時に探索点は離脱領域 の外縁部に沿って移動しなければならない。このように，直接に新しい移動方向を 目指さず，遠回りすることは探索性能に影響する。遠回り移動するイメージは図4.9 に示される。
¼
ᒁᡤⓗ᭱㐺ゎࡢ᥈⣴ᒚṔ᥈⣴⤒㊰
㐲ᅇࡾࡍࡿ⤒㊰
㞳⬺㡿ᇦ
ࡲ࡛┠ᣦࡍ᥈⣴᪉ྥ
¼
᪂ࡋ࠸᥈⣴᪉ྥ図4.9: 移動の遠回り
（3） POPへの妨害
通常の探索機構は常に現在の解の更新に注目するため，探索点が移動方向である 非近接領域の中の最良解に近い所にある場合に，次の上位構造における探索をする 時，前回の最良解は近接集合に含められ，離脱領域を構成する解になる。探索点の 移動は該当する最良解から離れるように移動することとなる。この時，該当する最 良解へ近づくことができず，POPに基づく良い解付近の探索が妨害される。更に，
続く探索経路は，該当する最良解が近接集合と非近接集合への所属変動の繰り返し によって，探索点は該当する最良解の周囲に振動することとなる。該当する最良解 への接近は長い間に行うことができず，探索性能に影響する。POP妨害のイメージ は図4.10に示される。
¼
␗࡞ࡿ᥈⣴Ⅼࡢ᥈⣴ᒚṔ᥈⣴⤒㊰
᪂ࡋ࠸㞳⬺㡿ᇦ
ࡲ࡛┠ᣦࡍ᥈⣴᪉ྥ
¼
323ࡀጉᐖࡉࢀࡿ᥈⣴᪉ྥ᭦᪂ᑐ㇟
図4.10: POPへの妨害
第4章 解空間の上位構造に基づく組合せ最適化手法 30
（4） 移動速度の遅緩
通常の探索機構を用いる場合に，移動経路上にある個々の解は隣接し，探索点の 解空間における移動速度は遅い。また，非近接集合の中の最良解が広く共有されて いるので，組合せ最適化問題の規模により，探索点の現在の解と目標とする最良解 との距離が極めて遠い状況が生じる。この場合，移動目標とする最良解の付近に到 達するためには，多くの移動回数が必要である。そのため，POPに基づく良い解付 近の探索は長い間で行うことができず，探索性能に影響する。この課題のイメージ は図4.11に示される。
␗࡞ࡿ᥈⣴Ⅼࡢ᥈⣴ᒚṔ ᚲせ࡞⛣ືᅇᩘ
᥈⣴᪉ྥ
᭦᪂ᑐ㇟
図4.11: 移動速度の遅緩
上述の課題は全て探索点の移動の観点から考慮される課題である。それ以外では，多様 化・集中化戦略の観点から，通常の探索機構にも課題を生じる。
• 通常の探索機構を用いる場合，探索点の移動経路は解空間で分岐なしの単一ルート になるため，また，多点探索の場合に各探索点の移動経路が互いに交差するため，
解空間上の探索済み領域と未探索領域は直接に分けることができない。その故，上 層の探索構造から見ると，POPに基づく良い点付近の集中化探索が実現できるが，
多様な探索の実現が難しい。POPだけに基づく移動戦略では，探索全体を集中化に 偏らせ，多様化が不十分になってしまう。その場合にPOPの成立度合いの弱い組 合せ最適化問題に対する探索性能は制限される。
• 移動の観点から考慮される課題の中の(2)，(3)，(4)は一定程度多様化探索と見なす が，その発生と継続は予測できない。そのため，多様化に対するコントロールは実 現できず，多様化・集中化のバランス調整は不可能である。故に通常の探索機構だ けを用いれば，多様化・集中化のバランスを取る移動戦略の構築は困難であり，多
第4章 解空間の上位構造に基づく組合せ最適化手法 31
様化・集中化の観点からさらなる性能の良い手法の開発が難しい。
本研究グループの先行研究では，重複探索や多様化不足等の課題における単一課題の解 決案が提案され，性能の向上が数値実験で検証されたが，解決案の単純な組合せでは他の 課題を生じるため，上述の多くの課題を同時に解決することが困難である。探索機構から の根本的な解決策が必要であり，近傍関係で構成される組合せ最適化問題の解空間の特徴 に適用する新しい探索機構が必要である。
5 拡張的探索機構
本章では，本研究の中心とされる新しい拡張的探索機構の提案について，新しい探索機 構の要点と特徴、解空間の上位構造に基づく探索戦略との親和性を述べ，両者の結合で双 方の長所を活かせる新たな探索戦略を説明する。更に拡張的探索機構の有効性と新たな探 索戦略の探索性能を検証するための新しい提案手法を述べる。