裴 莹, 苏 山, 付加胜, 韩霄松

(1. 长春财经学院 信息工程学院, 长春 130122； 2. 吉林大学 计算机科学与技术学院, 符号计算与知识工程教育部重点实验室, 长春 130012； 3. 中国石油集团工程技术研究院有限公司 钻井工艺研究所, 北京102206)

遗传算法(genetic algorithm, GA)是一种启发式的搜索策略, 通过模拟生物进化论的自然选择和遗传学机理搜索最优解[1]. Holland[1]提出的模式定理和积木块假说为GA提供了理论依据. GA源于一组候选解决方案的种群, 其中每个候选解决方案是该种群的个体或染色体, 染色体通过基因进行编码得到. 根据优胜劣汰原则, 将种群中的染色体通过交叉、 选择和变异等操作, 产生含有更好解决方案的新群体. 产生的新种群每一代都不弱于前一代, 直到满足进化终止条件, 最优个体被解码并被用于问题的最佳解决方案. GA由于结构简单并具有强大的全局搜索能力, 广泛应用于机器人与自动控制[2]、 交通调度[3]、 车间调度[4]和神经网络训练[5]等领域.

分析表明, GA的运行依赖于大规模的个体适应度计算, 当适应度计算较复杂时, GA寻优过程十分耗时. 很多优化问题(尤其在工业领域)需要优化的参数维度通常较高(high-dimensional), 适应度计算复杂(expensive-computationally), 且有些优化问题无法得到数学解析式, 解决方案的优劣依赖于其他工具(black-box), 这类优化问题的优化较困难, 被称为HEB问题[6]. 针对HEB问题, 目前已有很多研究成果： Branke等[7]利用邻近个体的适应度值通过插值和回归估计个体的适应度, 取得了较好的实验结果； Regis[8-11]将代理模型融合到粒子群等算法中, 得到了良好的实验结果, 并将其应用到地下水除污等实际问题中[12-13]; 刘全等[14]提出了一种双精英联合遗传算法避免了GA的早熟问题, 提高了收敛速度；……