課題の解決

拡張的探索機構の適用により，新たな多点の移動戦略は，通常の探索機構から生じる課 題を解決できる。

まず，移動の観点から考慮される課題は，拡張的探索機構の特徴によって自然に解決さ れる。各課題が解決されるの理由は，下に示す：

（1） 重複探索の解決

拡張的探索機構の特徴である「集団の加入則」により，異なる集団に関する局所 的最適解の共有は避けられる。また，一度使用された方向ペアは再び使用しないた め，新しく得た解は既に他の集団に属することが生じても，同じような重複は再び 発生しない。更に，「移動起点の変更則」により，用いる拡張起点とする解が変わる ため，継続的な重複探索も避けられる。

重複探索を解決するのイメージは図5.5に示される。

（2） 遠回りの解決

「移動起点の変更則」により，拡張起点は拡張方向の変化に応じて変わる。拡張 方向が大幅に変更されても，集団の中の近い解から拡張し始める。そのため，離脱 領域の外縁部に沿って移動し，遠回りすることは生じない。

遠回りの解決のイメージは図5.6に示される。

第5^{章 拡張的探索機構} 41

␗࡞ࡿ᥈⣴Ⅼࡢ

ᒁᡤⓗ᭱㐺ゎࡢ᥈⣴ᒚṔ ᥈⣴⤒㊰

㔜」᥈⣴ࡍࡿ⤒㊰

¼ ¼

᪂ࡓ࡞⛣ືᡓ␎ࡢ᥈⣴⤒㊰

図5.5: 重複探索の解決

¼

᥈⣴⤒㊰

㐲ᅇࡾࡍࡿ⤒㊰

㞳⬺㡿ᇦ

௒ࡲ࡛┠ᣦࡍ᥈⣴᪉ྥ

¼

᪂ࡓ࡞⛣ືᡓ␎ࡢ᥈⣴⤒㊰

¼ ¼ ¼ ¼

図5.6: 遠回りの解決

（3） POP妨害の解決

拡張的探索機構を導入した新しい多点の移動戦略では，離脱領域はその集団自身 であり，移動方向とする解は常に周辺集団にあるため，その解への接近に対する妨 害は存在しない。そのイメージは図5.7に示される。

¼

␗࡞ࡿ᥈⣴Ⅼࡢ᥈⣴ᒚṔ ᥈⣴⤒㊰

ඛ⾜◊✲ࡢ⛣ືᡓ␎ࡢ㞳⬺㡿ᇦ

௒ࡲ࡛┠ᣦࡍ᥈⣴᪉ྥ

¼

᭦᪂ᑐ㇟

᪂ࡓ࡞⛣ືᡓ␎ࡢ㞳⬺㡿ᇦ

᪂ࡓ࡞⛣ືᡓ␎ࡢ᥈⣴᪉ྥ

¼ ¼

図5.7: POP妨害の解決

（4） 移動速度による影響の解消

新しい多点の移動戦略では，下層の探索構造をそのまま用いるため，移動速度に

第5^{章 拡張的探索機構} 42

対する改善はない。しかし「情報の利用則」により，方向ペアの内部距離は短くな る。したがって，移動方向とする解の付近に近づくための手順が少くなり，POPに 基づく良い解付近の探索はうまく行うことができ，移動速度が遅いことから生じる 影響は解消される。そのイメージは図5.8^{に示される。}

␗࡞ࡿ᥈⣴Ⅼࡢ᥈⣴ᒚṔ ᚲせ࡞⛣ືᅇᩘ

᥈⣴᪉ྥ

᭦᪂ᑐ㇟

᪂ࡓ࡞⛣ືᡓ␎ࡢ᥈⣴᪉ྥ

¼

図5.8: 移動速度による影響の解消

また，多様化・集中化戦略の観点から考えられる課題について：

• 通常の探索機構を用いる場合に移動方向とする解が広く共有される状況と異なって，

新たな探索戦略では，各集団は自らの状況と周辺集団の近い部分の状況だけで方向 ペアを生成・選択するため，各集団の拡張方向の共有レベルが低い。そのため，同 じPOPを用いて拡張方向とする解が最も良い方向ペアを選択しても，各集団の拡 張方向の共有レベルが低く，探索全体の集中化への偏りは緩和される。

• 「集団の加入則」の特徴から，解空間が各集団の探索済み領域に相対的に平均占拠 されることは推測でき，集団の数は多ければ多いほど多様化の効果が期待できる。

通常の探索機構を用いる探索戦略と比べ，POPの成立度合いの弱い組合せ最適化問 題に対する探索性能が期待できる。

• 拡張的探索機構の適用により，解空間の中に探索済み領域と未探索領域は簡単に分 けることができる。そのため，領域の拡張を良い解のある方向へ進み，集中化探索 をすること，或いは未探索領域が大きい方向へ進み，多様化探索することは，方向 ペアの評価・選択による直接的なコントロールで実現できる。多様化・集中化のバ ランスの良い探索点の移動戦略の構築で，さらなる汎用性が広い，性能の高い手法 の開発が可能である。

第5^{章 拡張的探索機構} 43