Tunnelling Crossover Network

Tunnelling Crossover Network
Gabriela Ochoa, Francisco Chicano, Renato Tinos, Darrel Whitley,GECCO ’15, pp. 449-456, July 11-15, 2015

Local optima networks(LON)は,最近提案された適応度地形のモデルである. LONは,ノードを局所解,ノー ド間の遷移をエッジとして表現することで適応度地形を圧縮する.以前のLONは突然変異をベースとした遷移を 考慮していたが,この研究ではその代わり,決定的な交叉に基づく遷移を扱う.我々は,最近提案された擬似ブー ル関数における k-bounded partition crossover に基づくネットワークを定義し,解析する.partition crossover は 当初,巡回セールスマン問題 (travelling salesman problem: TSP) への交叉手法として提案され,TSP には局所 解間を繋ぐトンネル,すなわち局所解から局所解への遷移が存在することが明らかになった.我々のネットワー ク解析は,NKランドスケープにおいてもトンネル,が存在することを明らかにした.つまり,NKランドスケー プにおける局所解は partition crossover を経て密に接続されている.また,我々はNKランドスケープの隣接モ デルとランダムモデルの間に注目すべき違いが存在することが明らかになった.驚くべきことに,ランダムモデ ルは平均して局所解数が少なく,そのネットワークはよりスパースでいくつかのクラスターに分解できることが 分かった.また,同一のパラメーターであっても得られるランドスケープのサイズやコネクティビティのパター ンは大きなばらつきが見られた.これらのネットワーク特徴量は,なぜ一部のランドスケープが他のものに比べて,探索が困難であるか,という理由を知るのに新たな洞察を与える
Local Optima Network, Partition Crossover, Hill Climbing, Local Search, Fitness Landscapes, NK-landscapes