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

摘要

二次割当問題（QAP）の優れた解法として，カオスニューロンモデルを用いたニューラルネットワークによるカオスダイナミクスで2-opt局所探索を駆動する，指数減衰カオスタブーサーチが提案されている．一方，巡回セールスマン問題（TSP）においては，Lin-Kernighanアルゴリズムをカオスニューラルネットワークで駆動する方法が提案され2-opt法をカオスニューラルネットワークで駆動する方法よりも優れた性能を示している．我々は，QAPの解法において，指数減衰カオスタブーサーチの2-opt局所探索の代わりに，Lin-Kernighanアルゴリズムを導入することを目的としている．しかし，Lin-KemighanアルゴリズムはTSPを解く局所探索アルゴリズムであるため．そのままではQAPを解くための指数減衰カオスタブーサーチに導入することはできない．そこで，本稿では，Lin-Kernighanアルゴリズムを指数減衰カオスタブーサーチに導入するための準備として，Lin-Kernighanアルゴリズムの考え方をQAPの解法に適用したアルゴリズムを提案する．また，シミュレーション実験により，提案した手法と2-opt法の解探索能力を比較.検討する．さらに，提案手法に用いるLin-Kernighan的アルゴリズムでの割り当て回数を変更した場合の解法能力について検討する．%A 2-opt local search driven by a chaotic neural network (exponential chaotic tabu search) was proposed for quadratic assignment problems (QAPs). The exponential chaotic tabu search has been demonstrated to have a high ability to solve QAPs. For traveling salesman prolems (TSPs), a chaos driven Lin-Kernighan algorithm was proposed, and further, showed a better performance than chaos driven 2-opt algorithm. Our final goal is to apply the Lin-Kernighan algorithm to the exponential chaotic tabu search for QAPs instead of the 2-opt algorithm. We, however, cannot directly apply the Lin-Kernighan algorithm to QAPs because the algorithm was originally for TSPs. Therefore, in this paper, we propose a technique to solve QAPs based on the Lin-Kernighan algorithm before applying it to the exponential tabu search. We show numerical simulation results to compare the performances of the proposed technique and the 2-opt algorithm. Furthermore, we show simulation results with a different number of exchanges in the Lin-Kernighan algorithm used in the proposed technique.