基于个体排斥的多目标遗传算法研究

摘要

进化算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。随着进化算法在解决多目标现实问题中所体现出的独特魅力，越来越多的研究者投入到多目标进化领域的研究上来，进化计算的效率和适用性成为大家研究的一个方向，而其中非支配集的构造技术对算法的性能有着非常大的影响。本文在分析传统进化算法的基础上，针对现阶段经典遗传算法存在的不足，提出两种基于NSGAⅡ框架上的非支配集构造方法：基于个体排挤算法的非支配集构造方法和基于自适应ε支配的个体排挤算法。
　　 本文首先简要介绍了遗传算法的起源、国内外研究现状以及当前流行的几种进化多目标算法，简要介绍了基本遗传算法的基本概念和术语、实现框架以及遗传算法的特点和发展趋势，提出了基于个体排挤算法的非支配集构造方法，将个体比较引入到非支配集构造过程中，与NSGAⅡ有效结合起来，处理多目标进化问题过程中不再让每一个群中个体依次比较其他个体进行分层，而是通过每两个个体的比较争当擂主，通过对两个标准测试函数的比较测试，表明基于个体排挤算法构造非支配集引入NSGAⅡ算法中，不但降低了计算复杂度，而且更好了维持了解得分布均匀度。在分析NSGAⅡ和基于个体排挤算法的基础上，针对个体排挤算法的稳定性相对较弱的缺点，引入ε-Pareto支配概念改进遗传算子，利用该算法在维持种群多样性、跳出局部最优解，快速收敛到全局最优解的能力有很大提高。