A memetic algorithm based on edge-state learning for max-cut
A memetic algorithm based on edge-state learning for max-cut
复制标题
一种基于边缘状态学习的最大割模因算法
DOI：
10.1016/j.eswa.2022.118077
复制
发表时间：
2022-07
影响因子：
8.5
通讯作者：
Zhou Zhou
中科院分区：
文献类型：
--
作者：
Zhi-zhong Zeng;Zhi-peng Lv;Xin-guo Yu;Qing-hua Wu;Yang Eang;Zhou Zhou
最大割问题是最经典的NP-难组合优化问题之一。它的对称性导致在提取有意义的配置信息学习的特殊困难，没有一个国家的最先进的算法采用任何学习算子。本文提出了一种新颖的最大割学习方法，即翻转后边状态学习（PF-ESL）。与以往算法不同的是，PF-ESL将边的状态（切割或未切割）而不是顶点的位置作为构形的关键信息，并提取其在种群上的统计信息进行学习。它基于以下观察。1)边缘是目标函数考虑的唯一因素。2)当局部构形旋转到其对称位置时，边态保持不变，而顶点位置则不同。这些表明，边状态比顶点位置包含更多有意义的信息。由于边的依赖性，不可能设置边的状态而不影响其他边的状态。因此，PF-ESL不是直接设置边状态，而是对顶点上的翻转进行采样。顶点上的翻转根据它们在增加给定解与种群之间的边缘状态的相似性方面的能力进行采样。PF-ESL被用于EDA（分布估计算法）扰动算子和路径重连算子中。实验结果表明，我们的算法是有竞争力的，并表明边缘状态学习是增值的两个算子。本文的主要贡献如下。首先，针对以往最大割进化算法在进化操作中主要关注顶点位置的问题，本文提出了一种新的更合理的观点，即边状态是划分图的关键信息，而不是顶点位置，并在此基础上引入了一种新的方法来衡量和利用它们的相似性。这种观点是基于学习的最大值算法设计的基础。割和其他图划分问题，并可以为未来的研究提供启示。此外，由于最大割是最经典和最基本的NP难问题之一，许多现实世界的问题涉及将图数据划分为不同的部分以优化某些函数，这种新的视角可能会启发相关或类似的问题。其次，除了原来的基于边缘状态的角度，和翻转后的边缘状态学习（PFESL）运营商的基础上，我们的模因算法还纳入了一个新的进化框架之间交替基于EDA的迭代禁忌搜索（ITS）和路径重链接的遗传算法。最后，该算法提供了两个最常用的基准集上的竞争力的结果，并提高了6个最具挑战性的情况下，最知名的结果。
Max-cut is one of the most classic NP-hard combinatorial optimization problems. The symmetry nature of it leads to special difficulty in extracting meaningful configuration information for learning; none of the state-of-the-art algorithms has employed any learning operators. This paper proposes an original learning method for max-cut, namelypost-flip edge-state learning(PF-ESL). Different from previous algorithms, PF-ESL regards edge-states (cut or not cut) rather than vertex-positions as the critical information of a configuration, and extracts their statistics over a population for learning. It is based on following observations. 1) Edges are the only factors considered by the objective function. 2) Edge-states keep invariant when rotating a local configuration to its symmetry position, but vertex-positions do not. These suggest that edge-states contain more meaningful information about a configuration than vertex-positions do. It is impossible to set the state of an edge without influencing some other edges’ states due to their dependencies. Therefore, instead of setting edge-states directly, PF-ESL samples the flips on vertices. Flips on vertices are sampled according to their capacities in increasing the similarity on edge-states between the given solution and a population. PF-ESL is employed in an EDA (Estimation of Distribution Algorithm) perturbation operator and a path-relinking operator. Experimental results show that our algorithm is competitive, and show that edge-state learning is value-added for both the two operators.The main contributions of this paper are as follows. Firstly, previous state-of-the-art evolutionary algorithms for max-cut focus on vertex positions in their evolutionary operation, this paper proposes a new and more reasonable perspective suggesting that edge-states are the critical information of divided graphs rather than vertex positions, and introduces a novel method to measure and utilize their similarities based on it. Such a perspective is fundamental to learning based algorithms design for max-cut and other graph partitioning problems, and can shed lights on future researches. Furthermore, since max-cut is one of the most classic and fundamental NP hard problems, many real-world problems involve dividing graph data into different parts to optimize certain functions, this new perspective may inspire related or similar problems. Secondly, besides the original edge-states based perspective, and the post-flip edge-states learning (PFESL) operator based on it, our memetic algorithm also incorporates a novel evolutionary framework which alternates between EDA based Iterated Tabu search (ITS) and path relinking based genetic algorithm. Finally, the proposed algorithm provides competitive results on two mostly used benchmark sets and improves the best-known results of 6 most challenging instances.
登录
查看更多内容
基于禁忌搜索的最大割问题混合进化算法
影响因子：
8.7
作者：
Wu, Qinghua;Wang, Yang;Lu, Zhipeng
通讯作者：
Lu, Zhipeng
DOI：
10.1287/ijoc.1080.0275
发表时间：
2009
期刊：
INFORMS J. Comput.
影响因子：
--
作者：
R. Martí;A. Duarte;M. Laguna
通讯作者：
R. Martí;A. Duarte;M. Laguna
DOI：
10.1016/j.ejor.2012.07.012
发表时间：
2012-12
期刊：
Eur. J. Oper. Res.
影响因子：
--
作者：
Yang Wang;Zhipeng Lü;F. Glover;Jin-Kao Hao
通讯作者：
Yang Wang;Zhipeng Lü;F. Glover;Jin-Kao Hao
DOI：
10.1145/1569901.1570167
发表时间：
2009-07
期刊：
Proceedings of the 11th Annual conference on Genetic and evolutionary computation
影响因子：
--
作者：
E. Arráiz;Oswaldo Olivo
通讯作者：
E. Arráiz;Oswaldo Olivo
DOI：
10.1016/j.cor.2017.05.005
发表时间：
2017-10
期刊：
Comput. Oper. Res.
影响因子：
--
作者：
Yi Zhou;Jin-Kao Hao
通讯作者：
Yi Zhou;Jin-Kao Hao