求解最大割问题的自适应混合免疫遗传算法

Adaptive Hybrid Immune Algorithm for Maximum Cut Problem

为了获得NP难的最大割问题的最优解,提出了一种自适应混合免疫遗传算法,它在初始化阶段按照局部最大权生成树来进行疫苗抽取操作,生成疫苗集合,再将图的划分可行解表示为抗体,并在演化过程中通过疫苗接种和基于亲和度的选择来加速收敛,并保持种群多样性,从而获得全局最优解。此外,疫苗的接种概率按照接种效果进行自适应调节,并基于信息熵理论定义抗体之间的亲合度及抗体的选择概率。大量仿真实验的结果表明该算法优于现有的贪婪搜索算法和最大神经网络算法。

For the NP-hard maximum cut problem, an Adaptive Hybrid Immune Genetic Algorithm is proposed, which abstracts vaccine-set according to the local maximum spanning tree in the initialization stage, then the potential solutions are encoded as antibodies, and vaccination and affinity-based selection are performed in the evolution process of antibodies to accelerate the convergence of antibodies and preserve population diversity. Additionally, the vaccination possibilities of vaccines are adaptive to the effects of vaccination and the affinities and selection possibilities of antibodies are defined according to the information entropy theory. A large number of instances have been simulated, and the results show that our algorithm is superior to the existing greedy search and maximum neural network algorithms.