Developments of High Performance Memetic Algorithms for Combinatorial Optimization Problems

在我们的研究中，我们开发了高性能的元启发式算法，称为模因算法，用于组合优化问题。作为组合优化问题，我们处理了最大团问题（MCP）、二次分配问题（QAP）和节点放置问题（NPP），这是已知的NP-hard问题。特别是，对于QAP，我们展示了一种有效的元启发式算法，称为遗传迭代局部搜索（GILS），该算法结合了基于变深度搜索思想的k-opt局部搜索。计算结果表明，与QAP的标准迭代局部搜索元启发式算法相比，具有KLS的GILS平均获得了良好的结果。

In our research, we developed high-performance metaheuristic algorithms called memetic algorithms for combinatorial optimization problems. As combinatorial optimization problems, we deal with the Maximum Clique Problem(MCP), Quadratic Assignment Problem(QAP), and Node Placement Problem(NPP), which are known to be NP-hard. Particularly, for the QAP, we show an effective metaheuristic algorithm called genetic iterated local search(GILS) incorporating k-opt local search based on the idea of variable depth search. Computational results showed that the GILS with KLS obtained good results on average in comparison to standard iterated local search metaheuristic algorithms for the QAP.