Lin-Kernighanアルゴリズムの二次割当問題解法への応用

摘要

二次割当問題（QAP）の優れた解法として，カオスニューロンモデルを用いたニューラルネットワークによるカオスダイナミクスで2-opt局所探索を駆動する，指数減衰カオスタブーサーチが提案されている．一方，巡回セールスマン問題（TSP）においては，Lin-Kernighanアルゴリズムをカオスニューラルネットワークで駆動する方法が提案され2-opt法をカオスニューラルネットワークで駆動する方法よりも優れた性能を示している．我々は，QAPの解法において，指数減衰カオスタブーサーチの2-opt局所探索の代わりに，Lin-Kernighanアルゴリズムを導入することを目的としている．しかし，Lin-KernighanアルゴリズムはTSPを解く局所探索アルゴリズムであるため，そのままではQAPを解くための指数減衰カオスタブーサーチに導入することはできない．そこで，本稿では，Lin-Kernighan アルゴリズムを指数減衰カオスタブーサーチに導入するための準備として，Lin-Kernighanアルゴリズムの考え方をQAPの解法に適用したアルゴリズムを提案する．また，シミュレーション実験により，提案した手法と2-opt法の解探索能力を比較·検討する．さらに，提案手法に用いるLin-Kernighan的アルゴリズムでの割り当て回数を変更した場合の解法能力について検討する．