解决单目标和多目标优化问题的进化算法

以进化算法为代表的仿生随机算法由于具有智能性、通用性和全局搜索能力,以成为求解复杂优化问题的重要工具。本文对于单目标和多目标优化问题进行了深入的研究,提出了几种求解不同问题的进化算法,本文主要进行了下面几个方面的工作: 1.将具有任意个约束条件的单目标优化问题转化为双目标优化问题,其中一个为原目标函数,另一个为违反约束程度最大的约束条件。采用偏好于第二个目标的粒子比较准则;为了避免算法陷入局部最优,当全局最优解连续几代不发生改变时,采用改进的多父体单形杂交算子对其进行扰动,使得产生的新点更好的继承父代的特性,将扰动后的粒子作为新的寻优方向。数值实验表明:对于某些特定函数,本算法寻优性能优良。 2.对于较复杂的约束单目标优化问题,提出了模糊粒子群算法。设计了一个新的扰动算子,使得扰动后的粒子偏向于当前种群中约束违反度小或目标函数值小的粒子。在此基础上定义了模糊个体极值和模糊全局极值,利用这两个定义改进了粒子群进化方程,利用该方程更新粒子的速度与位置,可以避免早熟收敛问题;定义了不可行度阈值,利用此定义给出了新的粒子比较准则,该准则采用对约束逐个处理的技术,使得一部分性能较优的不可行解微粒得以保留,从而达到使不可行解向可行解进化的目的。仿真结果表明,对于复杂约束优化问题,算法寻优性能优良,特别是对超高维约束优化问题,该算法获得了更高精度的解。 3.提出了基于粒子群优化的多目标Memetic算法。将无约束多目标优化问题转化成单目标约束优化问题,其中将解的质量度量看作是约束条件,均匀性度量看作是目标函数。对转化后的问题提出了基于约束主导原理的比较准则;用基于模拟退火的加权法对非劣解进行局部搜索。算例测试说明该算法寻优性能优良。 4.提出了解决无约束多目标优化问题的模糊粒子群算法。设计了新的扰动算子,使得扰动后的粒子偏向于当前种群中序值较小或位于目标空间稀疏区域中的粒子。在此基础上定义了模糊个体极值和模糊全局极值,利用这两个定义改进了粒子群进化方程;通过改进的进化方程和遗传算法共同作用产生新群体。实验结果表明,该方法可以求出一组分布均匀且散布广泛的最优解。 5.提出了基于新模型的多目标Memetic算法。将无约束多目标优化问题转化为单目标约束优化问题;针对转化后的模型提出了新的选择策略:将目标空间划分为若干个区域,该选择算子偏好于位于稀疏区域的个体而不考虑该个体序值的大小。这样,可以保证产生一组分布均匀且更接近真实Pareto前沿的非劣解;新的多目标Memetic算法引进了C-metric,将模拟退火算法与遗传算法结合起来,使得算法能产生质量较好的子种群。仿真结果表明新算法对无约束多目标优化问题是有效可行的。 6.提出了解决多目标约束优化问题的混合粒子群算法。设计了一个基于阈值的粒子比较准则,使之适用于处理多目标约束优化问题,该准则可以保留一部分序值较小且约束违反度在允许范围内的不可行解微粒,从而达到由不可行解向可行解进化的目的;设计了一个新的拥挤度函数,使得位于稀疏区域和Pareto前沿边界附近的点有较大的拥挤度函数值,从而被选择上的概率也较大;设计了一个具有两阶段的变异算子,第一阶段变异:计算出参与变异的粒子所受的合作用力,在此合力的基础上定义了个体的变异方向,沿着该方向进行变异可能会找到序值较小或约束违反度较小的粒子。为了避免粒子沿着一个固定的方向进行搜索,保证算法的全局收敛性,选择一定数目的粒子参与第二次变异。 7.针对多目标约束优化问题提出了基于不可行精英保留策略的粒子群优化算法。为了保留一部分约束违反度较大、序值较小的不可行粒子,设计了一个不可行精英保留策略,在进化初期从不可行精英集合中选出一定数目序值较小的不可行解微粒,而不考虑这些微粒约束违反度的大小,在进化后期从不可行精英集合中选择一部分约束违反度较小的粒子作为不可行精英粒子的代表参与进化;设计了一个新的拥挤度函数。该函数只需使用较少的计算量就可以使得位于稀疏区域和Pareto前沿边界附近的点具有较大的函数值,从而使这些点被选择上的概率很大。改进了混合粒子群算法中所设计的变异算子,新的变异算子减少了计算量,只有当粒子的约束违反度小于给定的阈值时才被选择参与变异。 8.针对粒子群算法中线形递减的惯性权重无法适应于复杂的非线性优化搜索过程的问题,提出了两种改进的粒子群算法:动态改变惯性权重的粒子群算法及一种简化的粒子群优化算法。第一种算法使得惯性权重与粒子的聚集度及全局最优值变化的速度有关,第二种算法使得粒子的飞行无记忆性,结合平滑函数和一维搜索重新生成停止进化粒子的位置。仿真结果表明这两种算法是有效可行的。