竞争合作型协同进化免疫算法及其在旅行商问题中的应用

Competitive-cooperative coevolutionary immune-dominant clone selection algorithm for solving the traveling salesman problem

中文关键词  人工免疫  克隆选择  局部最优免疫优势  竞争合作  协同进化  旅行商问题(TSP)

英文关键词  artificial immune system(AIS)  clonal selection  local optimization immunodominance  competitivecooperative  coevolution  traveling salesman problem(TSP)

中文摘要

      为提高人工免疫算法的收敛性能, 提出了一种竞争合作型协同进化免疫优势克隆选择算法(CCCICA). 把生态学中的协同进化思想引入到人工免疫算法中, 考虑了环境和子群间相互竞争的关系, 子种群内部通过局部最优免疫优势, 克隆扩增, 自适应动态高频混合变异等相关算子的操作加快了种群亲和度成熟速度. 把信息熵理论引入到算法中完善了种群的多样性. 所有子种群共享同一高层优良库, 并将其作为抗体子种群领导集合, 对高层优良种 群进行免疫杂交操作, 通过迁移操作把优良个体返回到各子种群, 实现了整个种群信息交流与协作. 针对旅行商问题(traveling salesman problem, TSP)多个实例结果表明: 与其它智能算法相比较该算法具有较好的性能.

英文摘要

      To improve the convergence performance of artificial immune algorithm, we propose a competitivecooperative coevolutionary immune-dominant clone selection algorithm(CCCICA). Enlightened by the knowledge of ecological environment and population competition, we incorporate the cooperative evolution in ecology into the artificial immune system. The affinity maturation of antibody is enhanced by the local optimization of the immune-dominance, the clone expansion and the adaptive dynamic hyper-hybrid mutation and other factors in the species. The population diversity is evaluated and adjusted by the locus information entropy. All subpopulations share one memory which is also used as a leader set consisting of the dominant representatives of each evolved subpopulation. The high level memory is optimized by using the immune genetic crossover operator. Several best individuals are migrated to subpopulations from the top excellent population based on the predefined condition. Through those operations, information is shared among populations for co-evolution. The results demonstrate good performance of the CCCICA in solving the traveling salesman problem(TSP) when compared with other modern intelligent algorithms.