5 拡張的探索機構
本章では，本研究の中心とされる新しい拡張的探索機構の提案について，新しい探索機 構の要点と特徴、解空間の上位構造に基づく探索戦略との親和性を述べ，両者の結合で双 方の長所を活かせる新たな探索戦略を説明する。更に拡張的探索機構の有効性と新たな探 索戦略の探索性能を検証するための新しい提案手法を述べる。
第5章 拡張的探索機構 33
以上の特徴を踏まえ，組合せ最適化問題の解空間の構造を簡単に考えると，その形は無 限延長の曲面ではなく，小さいブロックで構成される大きさが確定した球型の面として捉 えることができる。サッカーボールの表面を解空間の例にすると，解はそれを組立てる5・ 6角形の面であり，隣接の面はその近傍解である。
解空間における探索は，未探索の解を探索済みの解へ転換することに相当する。もし探 索済みの解が占める小さいブロックを探索点が占拠された領域とし，未探索の解が占める 小さいブロックを占拠されない領域とすれば，各探索点の探索行動は解空間を占拠し続け ることと見なせる。そして，少ない手順でより質の良い（評価値の良い）ブロックを占拠 することは，効率の高い探索行動を意味する。
上述のイメージに基づき，近傍関係で構成される組合せ最適化問題の解空間を地球の表 面に連想でき，探索点の探索済み領域を国々の領土にする。そして探索点の探索を領土の 拡張とし，効率の高い探索（移動）戦略は少ない手順でより質の良い領土を早めに占拠す ることと見なせる。
国々の領土拡張行動は以下の性質を持つことが考えられる。
（1） 領土の連続性
個々の国の領土は連続な空間を占める。つまり，任意の国の領土は一つの面積・
体積のある実体と見なせる。
（2） 領土の非重複性
個々の国の間に共有される領土は存在しない。つまり，任意の空間がある国に占 拠されれば，他の国に再び占拠されることができない。
（3） 領土拡張の高効率性
ある国が領土を拡張しようとする時に，常に拡張方向に近い領土境界から拡張を 始める。拡張方向が変化すると，拡張を始める場所も拡張方向に応じて変わる。必 ずしも前回までに拡張された場所から次回の拡張を始めるわけではない。
（4） 情報利用の近接性
任意の国は他のすべての国との間で，早めに質の良い領土を占拠するように競争 し，他国の情報を利用し，領土拡張の方針を定める。特に，他国の情報を利用する 時に，該当国との距離が近い部分の他国領土の情報を重視する。
以上の性質を踏まえ，本研究では国々の領土拡張行動を探索点の移動方針へ抽象化し，
第5章 拡張的探索機構 34
新しい拡張的探索機構を構築する。国々の領土拡張におけるの性質を継承するため，拡張 的探索機構は以下の特徴を持つ：
（1） 探索の更新則
通常の探索機構が単一の解の更新に注目することと比べ，拡張的探索機構では，
「領土の連続性」を継承するため，同一探索点で得たすべての解を一つの集団にし，
単一の点ではなく，集団全体の更新に注目する。
（2） 集団の加入則
「領土の非重複性」を継承するため，集団の間に共有される解は存在しない。あ る探索点が得た新しい解は既に他の集団に属する場合，該当解は該当探索点におけ る集団に再び属することができない。
（3） 移動起点の変更則
「領土拡張の高効率性」を継承するため，拡張的探索機構では，必ずしも前回の 探索で得た解で次回の探索（拡張）を始めない。探索の起点は探索方向（拡張方向）
の変化に応じて変わり，探索方向に近い集団の中の解である。
（4） 情報の利用則
「情報利用の近接性」を継承するため，ある集団が探索済み領域を拡張しようと する時，拡張方向を定める際には，周囲の他の集団の中の距離の近い領域における 解の情報を重視する。また，自らの集団における良い解の情報も重視する。
拡張的探索機構の上述の特徴を踏まえ，拡張的探索機構を用いる探索の進行にも以下の 特徴を持つ：
（1） 探索経路の形については，通常の探索機構を用いる時の単一ルートと異なっており，
拡張的探索機構を用いる場合，探索経路は枝状である。
（2） 領土の連続性と非重複性により，各集団の探索済み領域に境界線が存在する。その ため，解空間の中の探索済み領域と未探索領域は簡単に分けられる。
拡張的探索機構と通常の探索機構の間の違いは図 5.1に示される。
第5章 拡張的探索機構 35
㏆ഐゎ
᥈⣴⤒㊰ ᭦᪂ᑐ㇟ ḟᅇࡢ⛣ື࡛㑅ᢥྍ⬟ࡢ᪉ྥ
๓ᅇࡢ⛣ື࡛ᚓࡓゎ
ᣑᙇⓗ᥈⣴ᶵᵓ ㏻ᖖࡢ᥈⣴ᶵᵓ
図5.1: 通常の探索機構との比較
また，拡張的探索機構の特徴により，以下の注意点が存在する：
（1） 機能の需要
「移動起点の変更則」に基づき，拡張的探索機構では，探索方向に近い集団内の 探索の起点を定めなければならない。そのため，「近い」の概念を定量的に評価する 距離計算機能，及び探索点の移動を定められた探索方向に保持する移動方向選択機 能は，拡張的探索機構を適用する時に用意しなければならない。
（2） 計算量の増大
拡張的探索機構は，通常の探索機構が現在の解をそのまま起点とすることより，
探索起点を確定する手順を増えた。そのため，計算量の増加が予想できる。更に探 索点の移動回数の増加と共に，計算量は比率的に増加する。拡張的探索機構を探索 点の全ての移動に適用すれば，増加する計算量が膨大になる。
より性能の高い手法を開発するため，拡張的探索機構を適用する時に，上述の注意点を 解決，或いは解消しなければならない。
第5章 拡張的探索機構 36