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

摘要

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