论文部分内容阅读
遗传算法(Genetic Algorithm)因其全局搜索性和鲁棒性,在解决大规模组合优化问题等领域得到了广泛应用。实际中,很多的优化问题是带有约束条件的,遗传算法求解有约束优化问题是对目标函数在整个遗传空间中搜索满足约束条件的可行解。不满足约束条件的染色体被称为致死染色体。在遗传算法的种群进化过程中,由于交叉变异操作,致死染色体的产生经常发生,特别是对于约束比较强的优化问题,致死染色体的产生率比较大。当种群中致死染色体数量比较多时,算法的搜索性能将会恶化,甚至使算法不能运行。如果致死染色体的产生有一定的规律,可以通过设计算法来避免致死染色体的产生,然而在大多数情况下,找到避免致死染色体产生的方法是比较困难的。目前,在遗传算法中一般采取将致死染色体从种群中剔除的方法。由于经过若干代的进化,产生的致死染色体中包含了一些优秀的基因,如果对致死染色体加以利用将会改善和提高算法的搜索性能。本文根据人工免疫算法原理,结合染色体的进化信息和问题的特征信息提取疫苗和接种疫苗,提出一种基于免疫算子的致死染色体复活方法。在双岛模型中的“活岛”和“死岛”之间,将致死染色体和复活的致死染色体进行迁移,实现致死染色体的利用。在免疫算子中,根据致死染色体的特征信息,优秀染色体的特征信息和问题本身的特征信息的不同,分别设计了三种不同的免疫方法。将算法应用于经典的0-1背包问题和多重选择背包问题,通过数值实验结果表明了算法的有效性。该方法可以应用于求解约束优化问题的遗传算法,有效改善遗传算法的应用性能和搜索性能。