The quadratic assignment problem(QAP) is one of the NP-hard combinatorial optimization problems. Then, it is required to develop approximate algorithms for finding near optimal solutions in realistic time. On the other hand, to solve traveling salesman problems which is a special case of QAP, the Lin-Kernighan algorithm has been proposed. In this report, we propose an algorithm for solving QaPs by introducing characteristic property of searching process in the Lin-Kernighan algorithm. We also introduced chaotic dynamics into the proposed algorithm to escape undesirable local minima. To evaluate solving performance of the proposed method, we compared the performance of the proposed method with that of the conventional methods. As a result, the solving performance of the proposed method with chaotic dynamics exhibits smaller gaps from optimal solutions than the conventional algorithms.%二次割当問題はNP困難な組合せ最適化問題である.二次割当問題の特殊な例に，巡回セールスマン問題がある.巡回セールスマン問題に対する最も強力な近似解法の一つとしてLin-Kernighan法がある.Lin-Keraighan法における探索では，交換する枝数を適応的に決定するという特徴がある.本稿ではLin-Kernighan法の持つ特徴を二次割当問題に応用した新しい探索法を提案している.提案法では，交換する要素数を適応的に決定することで，計算時間を押さえつつ，効率の良い探索法を実現している.本稿ではさらに，提案手法が局所最適解に陥ることを避けるために，カオスダイナミクスを導入した手法も提案している.カオスダイナミクスの有効性を評価するために，既存の二次割当問題の局所探索法との性能比較を行う.数値実験の結果より，カオスダイナミクスを導入することで，効率良く局所最適解を抜け出すことができることが示された.
展开▼
