基于单纯形多向搜索的大规模进化优化算法

进化算法是一类常用优化算法,它们都会碰到维数灾难问题。本文旨在以Nelder-Mead单纯形多向搜索为基础,构造进化算法以解决大规模函数优化问题。具体地说,在广义邻域搜索框架下,充分挖掘运用Nelder-Mead单纯形法所蕴涵的多向搜索,构造单纯形遗传算法、单纯形粒子群算法及基于共生机制的单纯形协同进化算法。 本文主要的研究工作概括如下： (1)挖掘并充分利用Nelder-Mead单纯形法所蕴涵的多向搜索。Nelder-Mead单纯形法的缺点是：(a)梯度信息不丰富,也不准确,如不能提供雅可比矩阵,分量梯度信息；(b)容易陷入局部极点；(c)不能优化高维函数、也不能在大范围内优化低维函数。因此首要问题是充分挖掘Nelder-Mead单纯形法所蕴涵的搜索方向,提高搜索方向的精度和搜索效率。为此,提出了广义单纯形及广义单纯形矩阵概念,广义单纯形矩阵行分块、列分块及行列综合分块的分块方法；并进一步提出三种单纯形多向搜索构造方法：可变形心单纯形多向搜索Ⅰ、可变形心单纯形多向搜索Ⅱ及固定形心单纯形多向搜索。广义单纯形矩阵分块与广义单纯形多向搜索是改进基本Nelder-Mead单纯形法、构造单纯形遗传算法、单纯形粒子群算法及基于共生机制的单纯形协同进化算法的基础。 (2)设计单纯形遗传算法。单纯形遗传算法以由贪婪、精英分布、概率接受及优胜劣汰选择四种机制组合而成的综合进化机制为进化机制,以广义单纯形多向搜索Ⅰ为基础构造其繁殖算子,即方向繁殖算子。方向繁殖算子由点搜索算子、线搜索算子、面搜索算子或体搜索算子组成。单纯形遗传算法有两种实现形式：低维单纯形遗传算法和高维单纯形遗传算法。数值优化实验证实单纯形遗传算法具有大规模优化能力,低维单纯形遗传算法的性能比高维单纯形遗传算法的性能更好。 (3)设计单纯形粒子群算法。从广义单纯形多向搜索Ⅱ推导出基本单纯形粒子群算法,并用时变线性离散系统的一致收敛性定理证明它的收敛性。引入分量表示形式,构造单纯形粒子群算法。数值优化实验表明单纯形粒子群算法是收敛的,具有高维函数优化能力,但在优化大规模函数时其性能并不理想。 引入极值扰动策略和两级通信模型进一步改善单纯形粒子群算法。构造了带极值扰动的全局型单纯形粒子群算法、带极值扰动的局部型单纯形粒子群算法以及带极值扰动的综合型单纯形粒子群算法。数值优化实验证实带极值扰动单纯形粒子群算法具有大规模优化能力。 (4)设计基于共生机制的单纯形协同进化算法。改进初始的基于共生机制的协作进化算法框架,减少因矢量分解对分量之间相互作用的破坏,加强分量之间的合作。改进策略是随机动态矢量分解、二次合作优化及二次竞争。在改进的基于共生机制的协作进化算法框架下,以广义单纯形矩阵行列综合分解为基础构造单纯形协同进化算法。数值优化实验证实单纯形协同进化算法具有大规模优化能力。 (5)设计多模态单纯形混合遗传算法。以“分而治之”为指导思想,构造多模态单纯形法混合遗传算法。它具有三个特点：采用基于函数峰值的动态分类策略、在不同类别中嵌入不同的单纯形法、自动调节局部搜索和全局搜索之间的平衡。 全文以广义单纯形矩阵分块以及广义单纯形多向搜索为基础,以广义邻域搜索框架为骨架,以算法核心思想融合为主线,主要构造了三类具有大规模优化能力的进化算法。