下载文档原格式
约束优化和多目标优化的进化算法研究的开题报告一、研究背景与意义进化算法作为一种全局优化算法已经被广泛研究和应用。
其中，约束优化和多目标优化是进化算法研究领域中的两个重要方向，具有广泛的实际应用。
约束优化最主要的特点是在求解过程中需要考虑问题的约束条件，而多目标优化则是考虑多个目标函数。
这两个方向均是进化算法发展的重要方向。
本课题旨在研究约束优化和多目标优化的进化算法，在这两个领域取得更加鲜明的成果，具有重要的研究意义和实际应用价值。
同时，本课题也将探究进化算法在实际应用中的表现，以期为在实际问题中应用进化算法提供良好的支持。
二、研究内容和研究方法本课题将主要研究以下两个方面：1. 约束优化的进化算法研究约束优化是指优化问题存在约束条件的情况。
这些约束条件不仅需要满足优化目标，同时还需要满足特定的约束条件，否则将导致优化效果的下降或者无法得出优化解。
本课题将从多角度出发，研究约束优化的进化算法，包括但不限于遗传算法、进化策略等，主要研究内容包括：（1）约束优化算法的基本原理和优化目标。
（2）约束优化算法中代表性算法的研究，比如基于罚函数的方法、基于约束满足度的方法等等。
（3）约束优化算法的优化策略和实例分析。
2. 多目标优化的进化算法研究多目标优化是指优化问题中存在多个目标函数的情况。
在这种情况下，需要同时优化多个目标函数，以获得最优解。
本课题将从多角度出发，研究多目标优化的进化算法，主要研究内容包括：（1）多目标优化的进化算法的基本原理和优化目标。
（2）多目标优化中代表性算法的研究，比如NSGA-II、SPEA-II等等。
（3）多目标优化算法的优化策略和实例分析。
本课题主要采用的研究方法包括文献综述、实验分析与探索等，并通过实验数据进行对比研究和实验验证。
三、预期研究成果本课题主要预期研究如下几个方面的成果：（1）对进化算法在约束优化问题和多目标优化问题上的应用和研究进行深入的探究，总结和提炼关键技术和有效策略；（2）巩固深化约束优化和多目标优化领域的理论研究，解决相关问题和推动实践应用；（3）验证和证明约束优化算法和多目标优化算法的可行性，提供相应的性能测试结果和实证分析；（4）推广优化算法在实际应用中的成功案例，并能够为实际问题的解决提供借鉴与参照。
约束优化进化算法综述
约束优化进化算法是一种通过综合考虑目标函数和约束条件求解多约
束优化问题的方法。
它综合了进化算法和约束优化技术的优点，具有全局
寻优能力和对多约束问题处理能力等优点，因此受到了广泛的关注和应用。
目前，约束优化进化算法主要包括罚函数法、约束处理技术、显式约
束控制方法和隐式约束控制方法等。
罚函数法是对优化函数引入适当的惩
罚项，使得满足约束条件的解在目标函数中得到较低的数值，从而鼓励算
法尽量寻找满足约束条件的最优解。
约束处理技术主要包括基于约束传递
的方法、基于约束修剪的方法和基于约束滤波的方法等。
显式约束控制方
法是指将约束条件转化为算法操作中的限制条件。
隐式约束控制方法则是
通过改变算子操作的选择和参数设置等方式实现对约束的控制。
总的来说，约束优化进化算法在多样化的约束优化问题上有着广泛的
应用，如车间调度、电力系统调度、结构优化、参数估计等方面。
未来，
约束优化进化算法仍有很大的发展空间，可通过进一步的研究和优化来提
高算法的运行效率和求解精度。
多目标多约束优化问题算法多目标多约束优化问题是一类复杂的问题，需要使用特殊设计的算法来解决。
以下是一些常用于解决这类问题的算法：1. 多目标遗传算法（Multi-Objective Genetic Algorithm, MOGA）：-原理：使用遗传算法的思想，通过进化的方式寻找最优解。
针对多目标问题，采用Pareto 前沿的概念来评价解的优劣。
-特点：能够同时优化多个目标函数，通过维护一组非支配解来表示可能的最优解。
2. 多目标粒子群优化算法（Multi-Objective Particle Swarm Optimization, MOPSO）：-原理：基于群体智能的思想，通过模拟鸟群或鱼群的行为，粒子在解空间中搜索最优解。
-特点：能够在解空间中较好地探索多个目标函数的Pareto 前沿。
3. 多目标差分进化算法（Multi-Objective Differential Evolution, MODE）：-原理：差分进化算法的变种，通过引入差分向量来生成新的解，并利用Pareto 前沿来指导搜索过程。
-特点：对于高维、非线性、非凸优化问题有较好的性能。
4. 多目标蚁群算法（Multi-Objective Ant Colony Optimization, MOACO）：-原理：基于蚁群算法，模拟蚂蚁在搜索食物时的行为，通过信息素的传递来实现全局搜索和局部搜索。
-特点：在处理多目标问题时，采用Pareto 前沿来评估解的质量。
5. 多目标模拟退火算法（Multi-Objective Simulated Annealing, MOSA）：-原理：模拟退火算法的变种，通过模拟金属退火的过程，在解空间中逐渐减小温度来搜索最优解。
-特点：能够在搜索过程中以一定的概率接受比当前解更差的解，避免陷入局部最优解。
这些算法在解决多目标多约束优化问题时具有一定的优势，但选择合适的算法还取决于具体问题的性质和约束条件。
聚类佳点集交叉的约束优化混合进化算法龙文;梁昔明;徐松金;陈富【摘要】提出一种基于聚类佳点集多父代交叉和自适应约束处理技术的混合进化算法用于求解约束优化问题.新算法的主要特点是:在搜索机制方面,利用佳点集方法构造初始化种群,使个体能够均匀地分布在整个搜索空间.然后根据父代个体的相似度将种群个体进行聚类分析,从聚类中随机选择个体进行佳点集多父代交叉操作,利用多个父代个体所携带的信息产生新的具有代表性的子代个体,能够维持和增加种群的多样性.另外,引入局部搜索策略以提高算法局部搜索能力和收敛速度.在约束处理技术上,新算法引入了一个自适应约束处理技术,即根据当前种群中可行解的比例自适应选择不同的个体比较准则.通过15个标准测试函数验证了新算法的有效性.%A hybrid evolutionary algorithm based on multi-parent crossover of clustering good-point set and adaptive constraint-handling technique is proposed in this paper for solving constrained optimization problems. As for search mechanism, it utilizes good-point set to construct the initialization population that is scattered uniformly over the entire search space in order to maintain the diversity. The individuals of population are divided into several sub-populations according to the similarity of the two parents. The parents are selected randomly from the several sub-populations to arrange the crossover operation. The crossover operator can effectively make use of the information carried by the parents and generate representation offspring in order to maintain and increase the diversity of population. In addition, a local search scheme is introduced to enhance the local search ability and speed up the convergence of theproposed algorithm. As for constraint-handling technique, a new individual comparison criterion is proposed, which can adaptively select different individual comparison criterion according to the proportion of feasible solution in current population. The proposed algorithm is tested on 15 well-known benchmark functions, and the empirical evidence shows its effectivity.【期刊名称】《计算机研究与发展》【年(卷),期】2012(049)008【总页数】9页(P1753-1761)【关键词】约束优化;进化算法;聚类;自适应;佳点集【作者】龙文;梁昔明;徐松金;陈富【作者单位】贵州财经大学贵州省经济系统仿真重点实验室贵阳 550004;中南大学信息科学与工程学院长沙 410083;中南大学信息科学与工程学院长沙 410083;铜仁学院数学与计算机科学系贵州铜仁 554300;中南大学信息科学与工程学院长沙 410083【正文语种】中文【中图分类】TP18;TP301约束优化问题（constrained optimization problems，COPs）是科学研究、工程应用领域经常会遇到的一类数学规划问题.不失一般性，约束优化问题（最小化问题）可描述为其中，x∈S为决策变量，S为决策空间.通常S为Rs 中的s维长方体：li≤xi≤ui，li，ui 为常数，i＝1，2，…，s，f（x）为目标函数，gj（x）≤0表示第j个不等式约束条件，gj（x）＝0表示第j个等式约束条件，l是不等式约束条件的个数，（m－l）为等式约束条件的个数.遗传算法（genetic algorithm，GA）作为一种基于选择、交叉、变异机制的随机优化搜索算法，具有不依赖于问题的梯度信息、隐并行性、全局收敛的特点.结合合适的约束处理技术，遗传算法是求解约束优化问题的一种有效方法[1－3].虽然遗传算法在约束优化中取得了较好的效果，但是在其本身搜索机制上，传统的遗传算法也存在许多的缺陷，如早熟收敛、局部搜索能力差等.因此，研究者提出了大量的改进遗传算法.近年来，有些研究者尝试将优化实验设计方法，如佳点集、均匀实验设计、正交实验设计等嵌入到遗传算法中，取得了不错的搜索结果.张铃等人[4]利用数论中的佳点集理论和方法改进交叉算子，提出一种有效的佳点集遗传算法.Wang等人[5]利用均匀表设计两个父代个体的交叉算子，提出了一种基于水平集进化和拉丁方的进化算法.江中央、蔡自兴等人[6]根据父代个体的相似度自适应调整正交表因素，提出一种自适应正交混合遗传算法.在用遗传算法求解约束优化问题时，除了自身的搜索能力以外，如何处理好约束条件也是一个关键问题.目前常用的约束处理技术有惩罚函数法、可行解优于不可行解法等.惩罚函数法是处理约束最常用的方法之一，但很难确定合适的惩罚因子，算法的性能强烈地依赖于参数的选择[7].可行解优于不可行解法在搜索时没有充分利用不可行解的信息，尤其是求解一些可行域很小或全局最优解位于可行域边界上的问题时搜索效率不高[8].近年来，将约束优化问题转化为多目标优化问题来处理受到了极大的关注，并涌现出大量的研究成果[9－10].这类算法的主要特点是将问题的约束条件作为一个或多个目标来看待.考虑到遗传算法自身的搜索能力和约束处理技术对求解约束优化问题的性能影响，在搜索策略上，本文提出了聚类佳点集多父代交叉操作，以维持和增加种群的多样性，避免算法出现早熟收敛.以一定概率对每个聚类进行非均匀变异操作.同时，利用单形交叉算子对每个聚类进行局部搜索，以提高算法的收敛速度.在约束处理技术上，相似于文献[11]，本文根据群体中可行解的比例将种群的进化过程分为3个阶段，在不同进化阶段选取不同的个体比较和选择策略，从而有效地引导群体不断向最优解逼近.对15个标准测试函数的数值实验结果表明了新算法的有效性.1 基于聚类佳点集的约束优化混合进化算法1.1 种群初始化在求解优化问题前，我们对问题的全局最优解处在什么位置完全一无所知，如果随机初始化种群个体可能不具有代表性，不利于搜索到全局最优解，可能导致要增加迭代次数或种群大小来达到最优解或近似最优解，这势必会增加算法的计算量.而我们所期望的是，在初始化种群时个体应尽可能地均匀分布在整个搜索空间中，这样有利于算法在整个搜索空间内进行均匀搜索，才能以较优的方式快速逼近最优解. Fig.1 80initial individuals with good point set method.图1 佳点集产生的80个二维初始种群分布在相同取点个数的条件下，佳点序列要比其他方法选取的点序列更均匀，更逼近被积函数曲线.佳点集与决策变量同维，其规模只和所需的点数有关，这样用佳点集法求到的子集最能代表当前群体的性能.因此，本文采用佳点集方法生成初始种群，能克服正交设计方法的不足，从而保证了初始群体的多样性.图1是采用佳点集方法产生的规模为80的二维初始种群分布.从图1可以很清楚地看出，与随机方法相比，佳点集方法产生的初始种群分布均匀，没有重叠点，具有较好的多样性.1.2 聚类佳点集多父代交叉交叉算子是遗传算法搜索整个决策空间的重要操作，它通过组合父代个体的信息形成新的个体.常见的交叉算子是在子代个体的样本空间中随机产生新的子代个体，搜索具有一定的盲目性，在一定程度上降低了算法的搜索效率.利用佳点集方法安排父代个体的交叉操作，在子代个体的样本空间中产生具有代表性的子代个体，以提高搜索效率.文献[4]将佳点集方法引入到遗传算法中，设计了一种基于二进制编码的佳点集交叉算子，但针对高维、高精度优化问题时会出现个体编码长度太长而导致计算量过大.文献[12]提出了一种基于佳点集的实数编码遗传算法，设计了新的佳点集交叉算子，结合约束处理技术用于求解约束优化问题.上述佳点集遗传算法虽然在求解各类优化问题时取得了不错的结果，但是在设计交叉算子时，无论父代个体所确定的空间区域大小都产生相同数量的子代个体.设从当前种群中选取两个个体xi和xj作为父代个体，设xi＝（xi1，xi2，…，xis），xj＝（xj1，xj2，…，xjs），xi和xj共同确定了一个有界闭区间D＝[a，b]⊆Rs：D是Rs上的超长方体，即对给定的两个父代个体，如果一个交叉算子能组合出的新的个体数目越多，说明它的组合能力越强，很明显交叉算子的组合能力直接反映了算子所能搜索决策空间的大小.父代个体通过佳点集交叉产生的子代个体只能在其所确定的超长方体内，子代个体之间的距离小于父代个体对之间的距离.它是通过切割父代个体确定的超长方体获得新的基因片段，然后重组这些基因片段来生成新的子代个体.如图2所示：Fig.2 Distribution of the offspring generated by using good point set crossover operation.图2 佳点集交叉操作产生的子代个体从图2可以看出，个体c和d的距离很近，它们所确定的空间区域相对较小，如果采用佳点集方法安排它们进行交叉，则会产生很多相似度高的子代个体，种群的多样性会变差.这种现象在群体进化后期更为明显.因为在群体进化后期，所有的个体不断向适应度高的方向聚集，个体之间的空间距离越来越近.为了减少相似度高的父代个体进行佳点集交叉操作和增加种群的多样性，本文提出了一种聚类佳点集多父代交叉操作，即根据群体中个体间的空间距离不同进行聚类分析，将种群分为多个子种群，然后从每个子种群中随机选择个体来进行佳点集交叉操设x2，s）为参与交叉操作的一对父代个体.为了描述方便，我们作如下定义：定义1.个体x1和x2之间的空间距离d为根据个体的空间距离先对群体进行聚类，将种群分割成互不相交的局部领域，使每个子种群仅覆盖搜索空间一个较小的邻域.在确定好种群聚类后，针对每一个子种群，随机选择个体进行佳点集交叉操作，从而更加增加了种群的多样性.1.3 聚类局部搜索为了提高算法的局部搜索能力和收敛速度，本文引入局部搜索策略.先对群体中个体根据其空间距离进行聚类，将种群分为若干个子种群.对每个子种群，即局部邻域，采用单形交叉（SPX）算子[11]对其进行局部搜索，以加强算法的局部搜索能力和提高算法的收敛速度.单形交叉算子使算法在进化初期有较强的全局搜索能力，而在进化后期有较强的局部搜索能力.聚类单形交叉局部搜索策略将种群分割成互不相交的局部邻域，以提高单形搜索的局部收敛速度，同时对不相交的局部邻域进行并行搜索，能够充分地利用搜索空间的局部信息.1.4 约束处理技术现有的约束处理技术存在的主要问题是如何设计合理的个体比较准则和选择准则.因此，本文提出一种自适应约束处理技术，即根据当前种群中可行解的比例而选择不同的个体比较与选择准则.类似于文献[11]，本文将种群的进化过程分为3个阶段：1）种群中只有不可行解；2）种群中既有可行解又有不可行解；3）种群中只有可行解.1）当种群中可行解比例fp＝0时，也就是当前种群中只存在不可行解时，说明当前种群中个体离可行域还有一定的距离.由于对全局最优解没有任何先验知识，因此，在这个阶段中，个体的可行性比目标函数值最小化更重要.其主要目标就是如何引导群体从不同方向进入可行域或向可行域边界靠近.蔡自兴等人[3]和 Venkatraman等人[13]建议在这个阶段完全不考虑个体的目标函数值，只按照个体的约束违反程度来选择.但这样做缺乏找到或接近可行解的机会，这对于可行域高度稀疏和搜索空间离散的问题尤为关键.Wang等人[11]提出一种分层选择非劣个体进入下一代种群的方案，取得了较好的效果.本文提出一种带偏好策略的非劣个体比较和选择准则.在多目标优化过程中，群体中的主要信息均包含在非劣个体中，因此，我们感兴趣的仅仅是非劣个体，从而避免了对群体其他个体的操作所带来的计算花销.但是，对于非劣个体，用Pareto优超关系无法判断孰优孰劣.文献[11]认为，没有引入偏好信息的多目标优化方法可能并不像人们所想象的那样有效.因此，本文提出一种带有偏好策略的非劣个体选择和比较准则：关于约束优化问题，如果一个个体远离可行域边界，它对寻优过程是没有任何意义的.因而我们只关心具有低约束违反度的非劣个体，这对寻优过程而言其实就是一种搜索偏好.把当前种群中的所有非劣个体按约束违反度升序排序，选取前N（N为种群规模）个非劣个体直接进入下一代种群.如果当前种群中的非劣个体数目为N′，小于种群规模N，先直接将N′个非劣个体进入下一代群体，然后再从剩下的劣于个体中随机选择（N－N′）个进入下一代种群.由Pareto优超定义可知，与文献[3]和文献[13]中只根据个体的约束违反度选择而完全抛弃目标函数值的方法不同的是，本文方法能保证具有低约束违反度且具有低目标函数值的个体存在于下一代群体中，因为非劣个体可能同时具有两个目标都是较小的情况，在一定程度上也保留了目标函数值小的个体.这说明本文方法比文献[3]和文献[13]中的方法更具有优越性.2）当种群中可行解比例0＜fp＜1时，也就是当前种群中既有可行解又有不可行解.在这个阶段，一般认为具有目标函数值小和低约束违反度的不可行解应该存活在下一代群体中，理由是在某些情况这些个体可能比对应的可行解更重要，特别是当可行域非常小或全局最优解位于可行域边界上[13].另一方面，由于约束优化进化算法的最终目标是找到可行最优解，所以我们不能完全抛弃可行解.因此，在这个阶段，我们要倾向于保留一些重要的可行和不可行个体在种群中，维持群体中可行解与不可行解之间的平衡，避免算法陷入局部最优.其中，好的不可行个体可以协助群体快速地靠近可行域，好的可行个体有利于顺利找到全局最优解，这也正体现了约束优化进化算法两个明确目标的思路.Mezura－Montes和Coello[14]认为，确保约束违反度最小的不可行解以一定的概率进入下一代种群，以此来增加群体的多样性，同时还可以引导其他不可行个体快速地靠近可行域边界，实验结果表明这种机制对提高算法的性能是有效的.为了维持下一代种群中可行个体与不可行个体合理的比例，在此阶段我们采用一种自适应个体选择策略：若当前种群中的可行解比例0＜fp≤0.7时，则根据文献[1]中提出的个体选择法来选择，具体个体比较准则为：若被选择的两个个体均为可行解，则比较它们的目标函数值，目标函数值小的个体进入下一代种群，同时将该个体从群体中删除；否则，如果rand＜pf，则比较两个个体的目标函数值，目标函数值小的个体进入下一代；如果rand≥pf，则比较两个个体的约束违反程度，约束违反度低的个体进入下一代，将该个体从当前种群中删除.其中，参数pf表示在不可行域中仅使用目标函数比较个体的概率，且满足0≤pf≤1，rand是（0，1）中均匀分布的随机数.实验表明，pf＝0.45能够使算法保持较好的性能[1].重复上述过程直至达到下代群体的规模.若当前种群中的可行解比例0.7＜fp＜1时，则与fp＝0时的选择个体方法相同.本文方法能维持群体中可行个体和不可行个体一定的比例，同时增加约束违反度最小的不可行个体进入下一代种群的概率，增强了群体的多样性，有利于群体向最优解逼近.3）当种群中的可行解比例fp＝1时，即种群中的个体全部都是可行解.此阶段的主要目标是使群体尽快地收敛到全局最优解.其中，目标函数值的大小反映了个体与全局最优解的距离.因此，我们根据个体目标函数值的大小来进行选择操作：首先将当前种群中所有个体按目标函数值升序排序，选择前N（N表示种群规模）个个体直接进入下一代群体.1.5 算法步骤设种群规模为N，s为个体变量的维数，t为进化代数，并设置算法的其他一些参数.本文算法的具体步骤如下：Step1.产生初始种群.利用佳点集方法产生初始种群 N0＝｛x1，x2，…，xN｝，xi∈S，i＝1，2，…，N.令t＝0.Step2.交叉操作.根据相似个体聚类的规则，将种群Nt分解成若干个子种群，然后以一定概率pc从各聚类中选择个体，按照1.2节中的方法进行佳点集多父代交叉操作，生成新的种群N1t.Step3.变异操作.对于每个聚类子种群，以一定概率pm选择个体进行非均匀变异操作，产生新的种群N2t.Step4.聚类局部搜索.对每一个聚类子种群，利用单形交叉算子进行局部搜索，产生新的种群Step5.选择操作.从种群中，根据1.4节中的个体优劣比较和选择准则，选出N个最好的个体进入到下一代种群Nt＋1中.Step6.判断算法是否满足终止条件.如果满足，则输出最优解；否则，t＝t＋1，返回Step2.1.6 时间复杂度根据上述对算法的描述可以方便地计算本文算法的时间复杂度，其主要取决于将种群聚类分成若干子种群和个体比较与选择准则.设算法的种群规模为N，假设种群经过交叉、变异和局部搜索后产生的个体为N′，在最坏的情况下，算法的时间复杂度计算为：算法进行聚类时将种群分为若干个子种群的时间复杂度为O（N2）.经过交叉、变异和局部搜索后种群最多有（N＋N′）个个体，在第1种个体选择准则中，利用快速排序法辨识非劣个体需要O（2（N＋N′）log（N＋N′））次比较，对非劣个体进行排序选择的时间复杂度为O（N－2），其中N－为群体中的非劣个体数.第2种个体选择准则的复杂度为O（2（N＋N′）log（N＋N′））＋O（N －2）或O（N）.第3种个体选择准则的复杂度为O（（N＋N′）2）.其他操作的时间复杂度可忽略不计.因此，本文算法总的时间复杂度为O（N2）或O（（N＋N′）2）.2 数值实验为了评价本文算法（记为COHEA）的性能，我们选取文献[15]中的15个标准测试函数进行实验研究.对于每个测试函数，算法参数设置如下：种群规模N＝100，佳点集交叉概率pc＝0.2，变异概率pm＝0.1，m＝5，b的取值为2～5，交叉概率p1＝0.7，μ＝10，λ＝5，扩张比ε＝10，算法的适应度函数值评价次数为300 000次.新算法COHEA在上述参数设置下均进行了30次独立的实验，记录其最好结果（best）、中间结果（median）、平均结果（mean）、最差结果（worst）和解的标准方差（std.dev）.表1给出了新算法COHEA对15个测试函数的实验结果.Table 1 The Experiment Results of the COHEA on 15Benchmark Functions （30times）表1 COHEA算法对15个标准测试函数独立运行30次的实验结果Function Optimal Best Result Median Result Mean Result Worst Result Std.Dev g01 －15.000 －15.000 00 －15.000 00 －15.000 00 －15.000 00 0.000E＋00 g02 －0.803 619 －0.803 523 －0.775 518 －0.772 942 －0.696 219 3.325E－02 g03 －1.000 －1.000 00 －1.000 00 －1.000 00 －1.000 00 6.286E－08 g06 －6 961.813 88 －6 961.813 88 －6 961.813 88 －6 961.813 88 －6 961.813 88 1.851E－12 g07 24.306 2 24.306 5 24.307 3 24.307 9 24.315 0 1.915E－03 g09 680.630 0 680.630 0 680.630 0 680.630 0 680.630 0 4.601E－10 g10 7 049.248 7 049.252 7 049.271 7 049.292 7 049.423 4.141E－02 g11 0.749 9 0.749 900 0.749 900 0.749 900 0.749 900 3.387E－08ContinueFunction Optimal Best Result Median Result Mean Result Worst Result Std.Dev g12 －1.000 00 －1.000 000 0 －1.000 000 0 －1.000 0000 －1.000 000 0 0.000E＋00 g14 －47.763 －47.761 －47.761 －47.758 －47.710 1.083E－02 g15 961.715 961.715 961.715 961.715 961.715 4.625E－06 g16 －1.905 155 －1.905 155 －1.905 155 －1.905 155 －1.905 155 4.002E－13 g18 －0.866 025 －0.866 025 －0.866 025 －0.866 025 －0.866 025 3.488E－04 g19 32.656 32.659 32.695 32.708 32.861 2.141E－02 g24 －5.508 013 －5.508 013 －5.508 013 －5.508 013 －5.508 013 1.807E－15Fig.3 The number of trials versus the quality of the resulting solutions achieved for the test function g02，g10and g19.图3 测试函数g02，g10和g19进行30次独立实验所得的结果分布从表1可知，除了测试函数g02，g07，g10，g14和g19以外，COHEA对其他10个函数30次实验中一致地找到了全局最优解，对函数g02，g07，g10，g14和g19的实验结果也非常接近最优解，其中g02，g10和g19的实验结果分布图如图3所示.较小的标准方差值也说明了COHEA具有较强的稳定性：为了进一步比较算法的性能，我们将COHEA的运行结果与其他6种较好的约束优化进化算法进行了比较，它们分别是文献[1]中的基于随机排序的约束优化进化算法（记为SR），它是目前最为经典的约束优化进化算法之一；文献[7]中的自适应适应值法（记为SAFF）；文献[9]中的多目标法（记为CW）；文献[11]中的自适应均衡模型法（记为ATM）；文献[14]中的简单多元进化策略（记为SMES）和文献[16]中的加速自适应均衡模型（记为AATM），比较结果如表2所示：Table 2 Comparison of 6Algorithms on 9Benchmark Functions表2 6种算法对9个标准测试函数的实验结果比较Function/Optimal Status Methods SR[1] SAFF[7] CW[9] ATM[11] SMES[14]COHEA g01/－15.000 Best Mean Worst St.Dev－15.000－15.000－15.000 0.0E＋00－15.000－15.000－15.000 0－15.000－15.000－15.000 1.3E－14－15.000－15.000－15.000 1.6E－14－15.000－15.000－15.000 0－15.000 00－15.000 00－15.000 00 0.0E＋00g02/－0.803619 Best Mean Worst St.Dev－0.803 315－0.781 975－0.726 288 2.0E－02－0.802 97－0.790 10－0.760 43 1.2E－02－0.803 619－0.803 220－0.792 608 2.0E－03－0.803 388－0.790 148－0.756 986 1.3E－02－0.803 601－0.785 288－0.751 322 1.7E－02－0.803 523－0.772 942－0.696 219 3.325E－02 g03/－1.000 Best Mean Worst St.Dev－1.000－1.000－1.000 1.9E－04－1.000－1.000－1.000 7.5E－05－1.000－1.000－1.000 1.9E －16－1.000－1.000－1.000 1.9E－04－1.000－1.000－1.0002.1E－04－1.000 00－1.000 00－1.000 00 6.286E－08 g06/－6961.81388 Best Mean Worst St.Dev－6 961.814－6 875.940－6 350.262 1.6E＋02－6 961.800－6 961.800－6 961.800 0－6 961.814－6 961.814－6 961.814 1.8E－12－6961.814－6 961.814－6 961.814 4.6E－12－6 961.814－6 961.284－6952.482 1.9E＋00－6 961.813 88－6 961.813 88－6 961.813 88 1.851E－12g07/24.306 2 Best Mean Worst St.Dev 24.307 24.374 24.642 6.6E－02 24.48 26.58 28.40 1.1E＋00 24.306 24.306 24.306 5.7E－12 24.306 24.316 24.359 1.1E－02 24.372 24.475 24.843 1.3E－01 24.3065 24.3079 24.3150 1.915E－03 g09/680.6300 Best Mean Worst St.Dev 680.630 680.656 680.763 3.4E－02 680.64 680.72 680.87 5.9E－02 680.630 680.630 680.630 4.7E－13680.630 680.639 680.673 1.0E－02 680.632 680.643 680.719 1.6E－02 680.6300 680.6300 680.6300 4.601E－10 g10/7049.248 Best Mean Worst St.Dev 7 054.316 7 559.192 8 835.655 5.3E＋02 7 061.34 7 627.89 8 288.79 3.7E＋02 7 049.248 7 049.248 7 049.248 4.0E－09 7 052.253 7 250.437 7 560.224 1.2E＋02 7 051.903 7 253.047 7 638.366 1.4E＋02 7 049.252 7 049.271 7 049.423 4.141E－02 g11/－0.7499 Best Mean Worst St.Dev 0.750 0.750 0.750 8.0E－05 0.750 0.750 0.750 0 0.750 0.750 0.750 0.0E＋00 0.75 0.75 0.75 3.4E－04 0.75 0.75 0.75 1.5E－04 0.749 900 0.749 900 0.749 900 3.387E－08 g12/－1.000 Best Mean Worst St.Dev－1.000－1.000－1.0000.0E＋00－1.000－1.000－1.000 0－1.000－1.000－1.000 0.0E＋00－1.000－1.000－0.994 1.0E－03－1.000－1.000－1.000 0－1.000 00－1.000 00－1.000 00 0.000E＋00从表2可以看出，与SR算法、SAFF算法和SMES算法相比，COHEA 在函数g02，g06，g07，g09，g10和g11上的结果明显优于3种算法，而在函数g01，g03和g12上则取得了相似的结果.这说明算法COHEA比SR，SAFF，SMES算法具有更好的处理约束优化问题的能力.CW算法是当前已知最具竞争力的求解约束优化问题的进化算法之一，COHEA算法除了函数g02，g07和g10的结果稍逊外，在其他6个函数上取得了与CW算法相似的结果.与ATM算法相比，在函数g02，g09上略优于ATM算法，而在其他7个函数上取得了相似的结果.对于函数g14，g15，g16，g18，g19和g24，由于是最近才提出来的标准测试函数，所以文献中出现的求解结果还不多，本文将COHEA与文献[16]中的AATM算法进行了比较，比较结果如表3所示.从表3中的结果可知，除了函数g14和g19较优外，COHEA在其他4个函数上取得了与AATM相似的结果.另外，就计算代价而言，对于同一个测试函数，本文算法COHEA的适应值函数评价次数为300 000次，而SAFF算法则为1 400 000次，SR算法和CW算法则为350 000次，SMES算法和ATM算法则为240 000次，AATM算法为120 000次.基于以上比较可知，COHEA优于或相似于其他一些尖端算法.Table 3 Comparing COHEA with AATM on 6Benchmark Test Functions表3 COHEA与AATM算法对6个测试函数的实验结果比较Function Optimal Methods Best Median Mean Worst St.Dev g14 －47.763 COHEA AATM 1.0E－02 g15 961.715 COHEA AATM－47.761－47.762－47.761－47.753－47.758－47.750－47.710－47.712 1.083E－02 4.625E－06 3.0E－04 g16 －1.905 155 COHEA AATM 961.715 961.715 961.715 961.715 961.715 961.715 961.715 961.716 3.488E－04 2.1E－04 g19 32.656 COHEA AATM 4.002E－13 2.4E－14 g18 －0.866 025 COHEA AATM－1.905 155－1.905 155－1.905 155－1.905 155－1.905 155－1.905 155－1.905 155－1.905 155－0.866 025－0.866 025－0.866 025－0.866 013－0.866 025－0.865 952－0.866 025－0.864 863 2.141E－02 1.4E－01 g24 －5.508 013 COHEA AATM 32.659 32.725 32.695 32.934 32.708 32.952 32.861 33.243－5.508 013－5.508 013－5.508 013－5.508 013－5.508 013－5.508 013－5.508 013－5.508 013 1.807E－15 1.8E－153 结论算法本身的搜索能力和约束处理技术是利用进化算法求解约束优化问题时所要面临的两个关键问题.针对这两个问题，本文提出一种新的求解约束优化问题的混合进化算法，其特点为：1）利用佳点集理论产生初始种群，以保证初始种群个体能均匀地分布在整个搜索空间内；2）根据相似个体聚类规则，将种群分为若干个子种群，然后针对每个子种群，利用佳点集理论设计交叉算子，使其产生具有代表性的个体，维持种群的多样性，以便更好地搜索整个解空间，另外，引入局部搜索策略以加快算法的收敛速度；3）在进化过程中，根据群体处在不同的阶段，采用不同的个体比较和选择准则，选择优秀的个体进入下一代种群；4）通过15个标准测试函数的实验结果表明了新算法的有效性.由于本文算法的参数设置是固定的，因此，下一步研究工作就是探讨参数对算法性能的影响和将算法应用到实际中.参考文献[1] Runarsson T P，Yao X.Stochastic ranking for constrained evolutionary optimization[J].IEEE Trans on Evolutionary Computation，2000，4（3）：284－294[2] Deb K.An efficient constraint handling method for geneticalgorithm[J].Computation Methods in Applied Mechanics and Engineering，2000，186（2/3/4）：311－338[3] Cai Zixing，Jiang Zhongyang，Wang Yong，et al.A novel constrained optimization evolutionary algorithm based on orthogonal experimental design [J].Chinese Journal of Computers，2010，33（5）：855－864（inChinese）（蔡自兴，江中央，王勇，等.一种新的基于正交实验设计的约束优化进化算法[J].计算机学报，2010，33（5）：855－864）[4] Zhang Ling，Zhang Bo.Good point set based geneticalgorithm[J].Chinese Journal of Computers，2001，24（9）：917－922（in Chinese）（张铃，张钹.佳点集遗传算法[J].计算机学报，2001，24（9）：917－922）[5] Wang Y P，Dang C Y.An evolutionary algorithm for global optimization based on level－set evolution and Latin squares[J].IEEE Trans on Evolutionary Computation，2007，11（5）：579－595[6] Jiang Zhongyang，Cai Zixing，Wang Yong.Hybrid selfadaptive orthogonal genetic algorithm for solving global optimizationproblems[J].Journal of Software，2010，21（6）：1296－1307（in Chinese）（江中央，蔡自兴，王勇.求解全局优化问题的混合自适应正交遗传算法 [J].软件学报，2010，21（6）：1296－1307）[7] Farmani R，Wright J A.Self－adaptive fitness formulation for constrained optimization [J].IEEE Trans on Evolutionary Computation，2003，7（5）：445－455[8] Liang Ximing，Long Wen，Qin Haoyu，et al.Constrained optimization evolutionary algorithm based on individual feasibility ofpopulation[J].Control and Decision，2010，25（8）：1129－1132（in Chinese）（梁昔明，龙文，秦浩宇，等.基于种群个体可行性的约束优化进化算法[J].控制与决策，2010，25（8）：1129－1132）[9] Cai Z X， Wang Y.A multiobjective optimization－based evolutionary algorithm for constrained optimization [J].IEEE Trans on Evolu－tionary。
约束最优化方法
约束最优化方法是指通过给定约束条件，寻找目标函数的最优解。
以下是一些常用的约束最优化方法：
1. 拉格朗日乘子法：将约束最优化问题转化为无约束最优化问题，通过求解无约束最优化问题得到原问题的最优解。
2. 罚函数法：将约束条件转化为罚函数项，通过不断增加罚函数的权重，使目标函数逐渐逼近最优解。
3. 梯度下降法：通过迭代计算目标函数的梯度，沿着梯度的负方向搜索目标函数的最优解。
4. 牛顿法：通过迭代计算目标函数的Hessian矩阵，使用Hessian矩阵的逆矩阵乘以梯度向量来逼近最优解。
5. 遗传算法：模拟自然界的遗传机制，通过种群迭代的方式搜索最优解。
6. 模拟退火算法：模拟物理退火过程，通过随机搜索的方式搜索最优解。
7. 蚁群算法：模拟蚂蚁觅食行为，通过模拟蚂蚁的信息素传递过程来搜索最优解。
8. 粒子群算法：模拟鸟群、鱼群等群集行为，通过模拟粒子间的相互作用来搜索最优解。
这些方法各有优缺点，应根据具体问题选择合适的方法进行求解。
ISSN 1000-9825, CODEN RUXUEW E-mail: jos@Journal of Software, Vol.20, No.1, January 2009, pp.11−29 doi: 10.3724/SP.J.1001.2009.03363 Tel/Fax: +86-10-62562563© by Institute of Software, the Chinese Academy of Sciences. All rights reserved.∗约束优化进化算法王勇1+, 蔡自兴1, 周育人2, 肖赤心1,31(中南大学信息科学与工程学院,湖南长沙 410083)2(华南理工大学计算机科学与工程学院,广东广州 516040)3(湘潭大学信息工程学院,湖南湘潭 411105)Constrained Optimization Evolutionary AlgorithmsWANG Yong1+, CAI Zi-Xing1, ZHOU Yu-Ren2, XIAO Chi-Xin1,31(School of Information Science and Engineering, Central South University, Changsha 410083, China)2(School of Computer Science and Engineering, South China University of Technology, Guangzhou 516040, China)3(School of Information Engineering, Xiangtan University, Xiangtan 411105, China)+ Corresponding author: E-mail: ywang@Wang Y, Cai ZX, Zhou YR, Xiao CX. Constrained optimization evolutionary algorithms. Journal of Software,2009,20(1):11−29. /1000-9825/3363.htmAbstract: Constrained optimization problems (COPs) are mathematical programming problems frequentlyencountered in the disciplines of science and engineering application. Solving COPs has become an importantresearch area of evolutionary computation in recent years. In this paper, the state-of-the-art of constrainedoptimization evolutionary algorithms (COEAs) is surveyed from two basic aspects of COEAs (i.e.,constraint-handling techniques and evolutionary algorithms). In addition, this paper discusses some important issuesof COEAs. More specifically, several typical algorithms are analyzed in detail. Based on the analyses, it concludedthat to obtain competitive results, a proper constraint-handling technique needs to be considered in conjunction withan appropriate search algorithm. Finally, the open research issues in this field are also pointed out.Key words: evolutionary algorithm; constraint-handling technique; constrained optimization; multi-objectiveoptimization; constrained optimization evolutionary algorithms摘要: 约束优化问题是科学和工程应用领域经常会遇到的一类数学规划问题.近年来,约束优化问题求解已成为进化计算研究的一个重要方向.从约束优化进化算法=约束处理技术+进化算法的研究框架出发,从约束处理技术和进化算法两个基本方面对约束优化进化算法的研究及进展进行了综述.此外,对约束优化进化算法中的一些重要问题进行了探讨.最后进行了各种算法的比较性总结,深入分析了目前约束优化进化算法中亟待解决的问题,并指出了值得进一步研究的方向.关键词: 进化算法;约束处理技术;约束优化;多目标优化;约束优化进化算法∗ Supported by the National Natural Science Foundation of China under Grant Nos.60805027, 60234030, 60673062, 90820302 (国家自然科学基金); the Academician Foundation Project of Hu’nan Province of China under Grant No.06IJY3035 (湖南省院士基金); theGraduate Degree Thesis Innovation Foundation of Central South University of China under Grant No.1373-74334000016 (中南大学研究生学位论文创新基金)Received 2007-12-02; Accepted 2008-04-1512Journal of Software 软件学报 V ol.20, No.1, January 2009中图法分类号: TP18 文献标识码: A 约束优化问题(constrained optimization problems,简称COPs)是一类广泛存在于实际工程中但又较难求解的问题,因而对其研究具有十分重要的理论和实际意义.目前,求解约束优化问题的算法有很多,按照性质大体可分为两类:确定性的算法和随机性的算法.确定性的算法通常是基于梯度的搜索方法,如投影梯度法、简约梯度法、各类外点及内点惩罚函数法、Lagrangian 法和序列二次规划法等.这些方法存在的主要问题是,求解需要设置很好的初值点并需要函数的梯度信息,它们对于不可导、可行域不连通、甚至根本没有显式数学表达式等问题无能为力,而且求得的多为局部最优解.随机性的算法主要包括进化算法(evolutionary algorithms,简称EAs)、模拟退火(simulated annealing,简称SA)算法、禁忌搜索(tabu search,简称TS)等.进化算法是一种模拟自然进化过程的全局优化方法,它借用了达尔文“物竞天择、适者生存”的生物进化观点,通过选择、交叉、变异等机制来提高个体的适应性.模拟退火算法利用统计力学中物质退火过程与优化问题求解的相似性,采用Metropolis 接受准则并适当控制温度的下降过程实现模拟退火,从而达到求解全局优化问题的目的.禁忌搜索是对局部邻域搜索的一种扩展,是一种全局逐步寻优的启发式搜索方法.它通过设置禁忌表和禁忌对象来避免迂回搜索,并采用藐视准则来放松禁忌策略.与确定性的优化方法相比,进化算法是一种具有有向随机性的智能优化方法,更适合于求解约束优化问题.此外,与随机性的优化方法(如模拟退火算法、禁忌搜索等)相比,进化算法是一种基于群体的搜索技术,具有鲁棒性强、搜索效率高、不易陷入局部最优等特点.近10年来,利用进化算法求解约束优化问题已有许多学者进行了广泛的研究,并且提出了大量的约束优化进化算法(constrained optimization evolutionary algorithms,简称COEAs)[1,2].特别值得一提的是,2006年~2008年,进化计算国际大会(IEEE Congress on Evolutionary Computation)每年均为约束优化举办了Special Session.进化算法在约束优化问题中的成功应用取决于以下几个主要因素:(1) 进化算法从一个群体即多个点而不是一个点开始搜索,这使得它能够以较大概率找到全局最优解;(2) 进化算法对所优化问题的特征不敏感;(3) 进化算法很容易执行和使用.本文介绍了约束优化进化算法的最新研究成果.从约束处理技术和进化算法两个基本方面出发,对约束优化进化算法的研究及其进展进行了综述.此外,本文对约束优化进化算法中的若干重要问题进行了探讨.最后进行了实验比较,并指出了值得进一步研究的方向.1 约束优化问题及其相关定义不失一般性,一个约束优化问题可描述为如下形式: minimize ()f x 12(,,...,)n n x x x x ℜ=∈ (问题(1)) subject to ()0,j g x ≤ j =1,…,l()0,j h x = j =l +1,…,p 这里,x S Ω∈⊆ 为决策向量,Ω为可行域,S 为决策空间.一般地,S 为ℜn 中的n 维长方体:l (i )≤x i ≤u (i ),l (i ),u (i ) 为常数,i =1,…,n .()f x ,()j g x ,()j h x 均为ℜn 上的n 元函数,()f x 为目标函数,()0j g x ≤ 为第j 个不等式约束条件,()0j h x = 为第j 个等式约束条件.l 表示不等式约束条件的个数,p −l 表示等式约束条件的个数.定义1. Ω为问题(1)的可行域(feasible region)当且仅当 {|()0,1,...,;()0,1,...,}j j x S g x j l h x j l p Ω=∈≤===+ (1) Ω 在S 中的补集为问题(1)的不可行域.可行域中的解称为可行解,不可行域中的解称为不可行解.图1给出 了搜索空间S 及其可行域Ω的示意图.如果任意一个不等式约束条件满足0)(=x g j (j ∈{1,…,l }),则称)(x g j 在x 处活跃(active).显然,所有的等式约束条件)(x h j (j =l +1,…,p )对于可行域Ω中的任意点均活跃.王勇 等:约束优化进化算法13Fig.1 Search space S and its feasible region Ω图1 搜索空间S 及其可行域Ω 因为本文中涉及的一些约束处理方法是基于多目标优化技术的,所以下面给出了多目标优化问题的相关描述和多目标优化中的4个重要定义.不失一般性,考虑以下具有n 个决策变量和m 个目标函数的多目标优化问题(multi-objective optimization problems,简称MOPs): min12()((),(),...,())m y f x f x f x f x == (问题(2)) 其中,12(,,...,)n n x x x x X ℜ=∈⊂ 为决策向量,X 为决策空间,m y Y ℜ∈⊂ 为目标向量,Y 为目标空间. 定义2(Pareto 优超(Pareto dominance )). 决策向量u x X ∈ Pareto 优超决策向量v x X ∈ ,记为u v x x ≺,当且仅当: 1) ∀i ∈{1,…,m }满足()()i u i v f x f x ≤ ; 2) ∃j ∈{1,…,m }满足()()j u j v f x f x < . 此时,也称决策向量v x Pareto 劣于(dominated by)决策向量u x .若决策向量u x 与决策向量v x 不存在Pareto 优超关系,则称它们非劣(non-dominated). 定义3(Pareto 最优解(Pareto optimality )). 决策向量u x X ∈ 称为X 上的Pareto 最优解,当且仅当v x X ¬∃∈ 使得v u x x ≺. 定义4(Pareto 最优解集(Pareto optimal set )). 对于给定的多目标优化问题(),f x Pareto 最优解集(ρ*)定义为{|,}u v v u x X x X x x ρ∗=∈¬∃∈ ≺.Pareto 最优解集中的个体也称为非劣个体.定义5(Pareto 前沿(Pareto front )). 对于给定的多目标优化问题()f x 和Pareto 最优解集(ρ*),Pareto 前沿(ρf *)定义为{()|}u u f u f x x ρρ∗∗==∈ .显然,Pareto 前沿是Pareto 最优解集在目标空间中的像. 2 基于进化算法的约束处理技术进化算法已被广泛应用于求解优化问题.然而,其性能的好坏主要取决于两个因素:1) 进化算法的随机性能;2) 如何将优化问题的目标函数转换为适应值函数,因为适应值函数可以使搜索向着合理的区域进行.当优化问题具有约束条件时,将目标函数转换为适应值函数变得非常困难.这是由于此时适应值函数不仅要评价一个解的好坏,还应描述其与搜索空间中可行域的接近程度.当优化问题具有许多线性和非线性、等式和不等式约束条件时,其求解过程将变得更加复杂.值得注意的是,进化算法是一种无约束的搜索技术,因为它缺乏明确的约束处理机制,这促使研究者开发不同的方法来处理约束条件.一般来说,在进化算法中结合约束处理技术会给算法带来一些额外的参数,这些参数的选取通常由使用者决定.正因为如此,设计具有较好性能的约束处理技术显得尤为重要.一般来说,基于进化算法的约束处理技术将等式约束条件转换为如下的不等式约束条件来处理,即 0|)(|≤−δx h (2) 其中,δ为等式约束条件的容忍值,一般取较小的正数.将等式约束条件转换为不等式约束条件处理后,问题(1)将包含p 个不等式约束条件.14Journal of Software 软件学报 V ol.20, No.1, January 2009通常,群体中的个体x 违反第j 个约束条件的程度可表示为max{0,()},1()max{0,|()|},1j j j g x j l G x h x l j p δ≤≤⎧⎪=⎨−+≤≤⎪⎩(3) 则 1()()p j j G x G x ==∑ (4)表示个体x 违反问题(1)中所有约束条件的程度,也反映了个体x 在群体中的不可行性. 值得注意的是,由于约束条件之间的特征差异,某些约束条件可能对个体的约束违反程度)(x G 起着决定性的作用,此时,可通过标准化来平等地对待每个约束条件.在标准化过程中,首先找出群体中的个体违反每个约束条件的最大值max ({1,...,})jG j p ∈: max 1,,max (())j j i i N G G x == , {1,...,}j p ∈ (5) 其中,N 为群体规模,即群体中所包含的个体数.利用这些max j G 可以标准化个体i x 对每个约束条件的违反值,最 后个体i x 的标准化约束违反程度)(i nor x G 定义为该个体的每个约束违反标准值的平均值: max 1()()p j i j j nor i G x G G x p==∑ , {1,...,}i N ∈ (6) 根据近年来基于进化算法的约束处理技术的研究趋势,本文将它们划分为以下3类[3]:1) 惩罚函数法;2) 多目标法;3) 其他方法.2.1 惩罚函数法惩罚函数法因为执行简单而得到了广泛的应用,其主要思想是,通过对目标函数)(x f 增加惩罚项)(x p 来构造惩罚适应值函数)(x fitness ,将约束优化问题转换为无约束优化问题进行处理. 惩罚项的构造通常基于个体违反约束条件的程度)(x G .同时,惩罚项的形式决定了惩罚函数法的类型,例如若惩罚项中的惩罚系数不依赖于进化代数,则这类方法称为静态惩罚函数法.文献[4]按如下方式构造惩罚适应值函数:2,1()()()p k j j j fitness x f x r G x ==+∑ (7)其中,r k ,j (k =1,…,q ;j =1,…,p )为惩罚系数,q 为用户对每个约束条件定义的约束违反水平数.若惩罚项中的惩罚系数随着进化代数的改变而改变,则这类方法称为动态惩罚函数法.文献[5]提出了如下的惩罚适应值函数:1()()()()p j j fitness x f x Ct G x αβ==+∑ (8)其中,t 是进化代数,C ,α,β是需要调整的参数.Le Riche 等人[6]设计了一种隔离遗传算法,它具有两个惩罚系数,这两个惩罚系数旨在过大与过小的惩罚之间实现平衡.在进化过程中,该方法首先随机产生规模为2m 的初始群体.接着通过两个惩罚系数构造两个惩罚适应值函数,群体中的每个个体分别通过两个惩罚适应值函数进行评价,这样得到两个惩罚适应值列表.然后对两个列表中的惩罚适应值分别排序,最后根据两个排序后的列表,从规模为2m 的群体中选出最好的m 个个体构成下一代群体.死惩罚法[7]是最简单但最严厉的惩罚函数法,它总是拒绝不可行解,不利用可行解提供的任何信息.在死惩罚法中,不可行解的惩罚适应值定义为0.这样当初始群体不包含可行解时,进化过程将会停滞,因为群体中的所有个体具有相同的惩罚适应值,此时需要重新生成初始群体.死惩罚法仅适合于可行域为凸或可行域占搜索空间比例较大的约束优化问题.Huang 等人[8]提出了一种协同进化法,该方法采用两个群体.第1个群体中的个体表示惩罚系数集,第2个群体中的个体表示问题的解.利用第1个群体中的惩罚系数可以进化第2个群体中的解,同时,第2个群体中的个体可以用来调整第1个群体中的惩罚系数.通过协同地进化这两个群体,迭代结束时可以得到满意的解和合理王勇 等:约束优化进化算法15的惩罚系数. 一般来说,自适应惩罚函数法[9,10]具有较好的优化效果,因为它能利用搜索过程中的反馈信息动态地调节参数.Rasheed [11]提出了一种自适应惩罚函数法.该方法在初始阶段具有较小的惩罚系数,这样可以保证群体对搜索空间充分采样.在进化过程中,该方法根据群体状态自适应地决定增加或减少惩罚系数.最近,在文献[12]的基础上,Farmani 和Wright [13]提出了一种自适应适应值表示法,该方法将惩罚分为两个阶段进行:第1个惩罚阶段使得群体中最差的不可行解具有比群体中最好解更高或相等的惩罚适应值,第2个惩罚阶段使得群体中最差的不可行解的惩罚适应值等于群体中具有最大目标函数值的解的惩罚适应值.对于惩罚函数法,具有以下定理.定理1[14]. 令{}∞1t s 为一个非负、严格单调递增趋于无穷大的序列,定义以下函数: )()(),(x sG x f x s L += (9) 其中,s 为惩罚系数.令t x 使得(,)L s x 取最小值,则序列{}∞1t x 的极限即为问题(1)的最优解. 上述定理说明,当s →∞时,(,)L s x 的最小值与)(x f 的最小值等价.虽然惩罚函数法是进化算法求解约束优化问题时最常用的方法,但其仍存在着一定的缺陷.其中最为主要的缺陷是惩罚系数的合理设置十分复杂,往往需要多次实验来不断地进行调整.惩罚系数决定着对不可行解的惩罚程度,过大或过小的惩罚程度可能给进化算法的求解过程带来困难.如果惩罚程度过大,群体将以较快的速度进入可行域,此时忽略了对不可行域的勘探和开采,这样对于最优解位于可行域边界或可行域不连通的约束优化问题求解便会出现困难.另一方面,如果惩罚程度过小,个体的惩罚适应值主要由目标函数决定,此时,群体可能在不可行域产生滞留现象,这样,群体将很难进入可行域,甚至可能收敛于不可行解.Richardson 等人[15]对如何构造惩罚函数提出了以下导向性的准则:1) 基于个体违反约束条件程度构造的惩罚函数比基于个体违反约束条件个数构造的惩罚函数具有更好的性能;2) 对于具有较少约束条件和较少可行解的约束优化问题,如果仅仅基于个体违反约束条件个数来构造惩罚函数,则不可能找到最优解;3) 好的惩罚函数应该从两个量出发来构造:最大完备花费(maximum completion cost)和期望完备花费(expected completion cost).完备花费是指个体违反约束条件的程度.4) 惩罚应该接近期望完备花费,但是不能频繁地低于它.总之,惩罚越精确,得到的解的质量越好.在惩罚函数法中,个体的惩罚适应值由目标函数和惩罚项同时决定,所以在计算个体惩罚适应值时,目标函数和惩罚项具有一定的支配关系.Runarsson 和Yao [16]认为,惩罚函数法试图在目标函数和惩罚项中找到一个好的平衡(trade-off).在文献[16]中,他们将惩罚函数法归结为选取一个合理的惩罚系数r g ,并且系统地分析了在评价个体时,r g 如何影响目标函数和惩罚项之间的支配关系.事实上,对于每个群体,均存在某个区间[r 1,r 2],使得当r g <r 1时,个体惩罚适应值的比较完全由目标函数)(x f 决定;当r g >r 2时,个体惩罚适应值的比较完全由惩罚项)(x p 决定;当r g ∈[r 1,r 2]时,个体惩罚适应值的比较由目标函数)(x f 和惩罚项)(x p 共同决定.值得注意的是,参数r 1和r 2的选取与具体的群体有关,因而是依赖于问题的.同时,Yu 等人[17]指出,即使最具动态性的惩罚函数法,鉴于无约束全局最优解与具有约束条件时的全局最优解相距很远的问题,其优化效果也不可能很好.2.2 多目标法由于惩罚函数法存在着一些缺陷,近年来,研究者提出将约束优化问题转换为多目标优化问题来处理.本文将基于上述思想的方法分为两类:区分可行解与不可行解法和多目标优化法.2.2.1 区分可行解与不可行解法区分可行解与不可行解法通常将约束优化问题转换为具有两个目标的多目标优化问题.一般来说,其中一个目标为原问题的目标函数)(x f ,另一个目标为个体违反约束条件的程度().G x 这类方法的主要特点是,在群16 Journal of Software 软件学报 V ol.20, No.1, January 2009体进化过程中对可行解与不可行解区别对待.区分可行解与不可行解法与惩罚函数法的本质区别在于,后者在评价个体时同时考虑个体的目标函数值和约束违反程度,因而需要通过惩罚系数使目标函数值和约束违反程度具有相同的阶(order),然而,前者有针对性地利用目标函数值或约束违反程度来比较个体.以下介绍几种典型的算法.Powell 和Skolnick [18]将可行解的适应值映射到区间(−∞,1),将不可行解的适应值映射到区间(1,+∞),使得可行解总是优于不可行解.Powell 和Skolnick 使用如下的个体评估方式: (),if feasible ()1(),otherwise f x ftiness x rG x ⎧=⎨+⎩ (10) 其中,)(x f 被缩放到区间(−∞,1),)(x G 被缩放到区间(1,+∞),r 为常数.Deb [19]提出了一种联赛选择算子(也就是每次比较成对的个体),并采用以下准则比较个体:1) 当在两个比较的个体中,一个个体为可行解,另外一个个体为不可行解时,选择可行解;2) 当两个比较的个体均为可行解时,选择目标函数值小的个体;3) 当两个比较的个体均为不可行解时,选择违反约束条件程度小的个体.上述比较准则的主要缺陷是难以发挥不可行解的作用,特别是当群体中的绝大部分个体均为可行解时,不可行解将很难进入群体.为了保持群体的多样性,该文还提出了一种简单的小生态技术.Jiménez 和Verdegay [20]提出了一种类似于多目标优化中使用的min-max 表示方法.该方法中的个体比较准则类似于Deb [19]所提出的个体比较准则:1) 当一个个体为可行解,另外一个个体为不可行解时,可行解总是优于不可行解;2) 当两个个体均为可行解时,目标函数值小的个体占优; 3) 当两个个体均为不可行解时,个体的比较基于最大的约束违反程度1,...,max (),j j pG x = 具有最小的最大约束 违反程度的个体占优.在文献[19]的基础上,Mezura-Montes 和Coello Coello [21]提出了一种简单的多样性操作.该操作以一定的概率(例如0.03)使得群体中最好的不可行解可以继续生存.值得注意的是,这类多样性机制具有十分重要的作用,特别是当全局最优解位于可行域边界上时.林丹等人[22]针对很多约束优化问题的最优解位于可行域边界的特点,提出了一种自适应保持群体中不可行解比例的策略,并将其与文献[19]中的个体比较准则结合起来,得到了一个新的个体比较准则: 1) 当两个个体1x 和2x 都可行时,比较它们的目标函数值,目标函数值小的个体占优; 2) 当两个个体1x 和2x 都不可行时,比较它们违反约束条件的程度,违反约束条件程度小的个体占优; 3) 当1x 可行而2x 不可行时,如果2(),G x ε< 比较它们的目标函数值,目标函数值小的个体占优;否则,1x占优.为了将不可行解的比例保持在一个固定的水平,文献[22]对ε进行了自适应的调整.Runarsson 和Yao [16]提出了随机排序法,它是目前最为经典的基于进化算法的约束处理技术.该方法采用参数p f 表示在不可行域中仅使用目标函数比较个体的概率,也就是说,当比较两个相邻的个体时,若两个个体都是可行解,则比较它们目标函数的概率是1,否则,参数p f 将决定是否采用目标函数或约束违反程度来比较个体.实验结果表明,当p f =0.45时,随机排序法可以产生很好的优化效果.值得注意的是,p f =0.45意味着个体之间的比较更多地依赖于约束违反程度.最近,两位作者结合差异进化对该算法进行了改进[23].需要说明的是,文献[19]中的个体比较准则可视为随机排序法的一个特例.因为当p f =0时,随机排序法中的个体比较准则与文献[19]中的个体比较准则完全等价. Takahama 和Sakai [24]提出了α约束法.该方法采用约束满足水平)(x µ来表示个体x 满足约束条件的程度.为了定义个体x 的约束满足水平)(x µ,首先计算个体x 对每个约束条件的满足水平,接着再将这些满足水平组 合起来.例如,对于个体x ,根据关于)(x g i 和)(x h i 的分段线性函数,每个约束条件可转换为如下的满足水平:王勇 等:约束优化进化算法17⎪⎪⎩⎪⎪⎨⎧≤≤−≤=otherwise ,0)(0if ,)(10)(if ,1)(i i i i i g b x g x g x g x i µ (11) ⎪⎩⎪⎨⎧≤−=otherwise ,0|)(|if ,|)(|1)(j j j j h b x h x h x j µ (12) 其中,b i 和b j 为正常数.通过组合满足水平)(x i g µ和()j h x µ ,个体x 的约束满足水平)(x µ定义为 ,()min{(),()}i j g h i jx x x µµµ= (13) 在定义个体的约束满足水平后,文献[24]采用α水平比较(记为<α)来比较个体的优劣.令f 1,f 2和µ1,µ2分别表示个体1x 和2x 的目标函数值和约束满足水平,α水平比较定义如下:12121122121212,if ,(,)(,),if ,otherwise f f f f f f αµµαµµµµµµ<≥⎧⎪<⇔<=⎨⎪>⎩ (14)其中0≤α≤1.在文献[24]中,α的取值由分段函数控制.通过采用α水平比较替换通常的比较准则,α水平法可将求解无约束问题的算法转换为求解约束优化问题的算法.2.2.2 多目标优化法多目标优化法近年来受到了极大的关注,其主要特点是:1) 将约束优化问题转换为多目标优化问题,2) 利用多目标优化技术来处理转换后的问题.在将约束优化问题转换为多目标优化问题时,通常存在着两种方式.第1种方式将约束优化问题转换为具有两个目标的多目标优化问题.在第2种方式中,约束优化问题的目标函数和约束条件分别作为不同的目标看待.对于第1种方式,第1个目标为原问题的目标函数)(x f ,第2个目标为个体违反约束条件的程度)(x G .令()x f =))(),((x G x f ,此时可以利用多目标优化技术对()x f 进行求解.对于第2种方式,转换后的多目标优化问题将具有p +1个目标,其中p 为原问题的约束条件个数.这样就得到了一个新的待优化的向量 ))(),...,(),(()(1x f x f x f x p =F ,其中)(),...,(1x f x f p 为原问题的约束条件,此时可利用多目标优化技术对)(x F 进行求解.一般来说,以下3种多目标优化技术经常运用于处理转换后的问题:1) 使用Pareto 优超作为一种选择准则;2) 使用Pareto 排序(ranking)来定义个体适应值;3) 将群体划分为若干个子群体,子群体的评估或者基于目标函数,或者基于某个约束条件.这种机制称为基于群体的方法.下面介绍几种典型的算法.Surry 和Radcliffe [25]提出了COMOGA(constrained optimization by multi-objective genetic algorithm)方法.在该方法中,约束优化问题被视作约束满足问题或无约束优化问题来处理.当约束优化问题被视为约束满足问题时,目标函数被忽略,此时,个体之间的比较由Pareto 排序决定,Pareto 排序基于约束违反来定义.当约束优化问题被视为无约束优化问题时,约束条件被忽略,此时,个体之间的比较由目标函数决定.受向量评估遗传算法[26]的启发,文献[25]采用参数p cost 来决定基于目标函数选择个体的概率.为了避免因参数p cost 固定而引发的一些问题,该方法通过对群体中的可行解设置目标比例τ来动态地调节p cost .例如,假设群体中可行解的目标比例为τ=0.1,若当前代群体中的可行解比例没有靠近0.1,则应相应地调节p cost .Camponogara 和Talukdar [27]从Pareto 集合中计算个体的改进方向,Pareto 集合由目标函数和约束违反程度 共同定义.如图2所示,考虑两个Pareto 集合S i 与S j 和两个个体i x 与j x ,其中i <j ,i i S x ∈ ,j j S x ∈ ,j i x x ≺ .通过这两个个体,可以得到如下的改进方向:18Journal of Software 软件学报 V ol.20, No.1, January 2009()/||i j i j d x x x x =−− (15)Pareto 优超i x 和j x . Coello Coello [28]提出了一种基于Pareto 排序过程[29]的方法来定义个体的等级(rank).对于群体中的每个个体i x (1,...,i N =),该方法通过公式(16)计算个体的等级: 1)()(+=i i x count x rank (16) 其中,)(i x count 根据以下准则来计算:初始化)(i x count =0,将i x 与群体中的其他个体j x (i j N j ≠=;,...,1)逐一进行比较: 1) 如果i x 和j x 都为可行解,则i 2) 如果i x 为不可行解,j x 为可行解,则1)()(+=i i x count x count ; 3) 如果i x 和j x 均为不可行解,但i x 比j x 违反更多的约束条件,则1)()(+=i i x count x count ; 4) 如果i x 和j x 均为不可行解,且它们违反相同个数的约束条件,但i x 比j x 具有更大的约束违反程度,则1)()(+=i i x count x count . 然后,对个体的等级按公式(17)进行变换:1(),if is feasible ()1(),otherwise i i i fitness x x rank x rank x ⎧=⎨⎩ (17) 值得注意的是,)(i x fitness 需要经过一定的处理,以使得可行解的等级总是高于不可行解的等级.这样与不可行解相比,可行解更容易进入下一代种群.周育人等人[30]采用Pareto 强度值对个体进行排序选优.Pareto 强度值定义如下: 定义6(Pareto 强度值). 设i x 为群体P 中的一个个体,用S (i x )表示群体中Pareto 劣于i x 的个体总数,称为i x 的强度值,即S (i x )=#{j x |j x ∈P 且j i x x ≺ }.其中,#表示集合的基数.Pareto 强度值反映了个体在群体P 中的强弱程度.Pareto 强度值越大,表示群体中Pareto 劣于该个体的个体越多,则该个体越优秀.该方法在比较个体时,首先比较个体的Pareto 强度值,Pareto 强度值大的个体为优,若个体之间具有相等的Pareto 强度值,则比较它们违反约束条件的程度,违反约束条件程度小的个体为优.通过上述比较方法可以对群体中的个体进行排序.每次遗传操作完成之后,该算法选择Pareto 强度值最大的个体和违反约束条件程度最小的个体同时进入下一代种群.Cai 和Wang 提出了CW 算法[31].CW 算法首先找出子代群体中所有的非劣个体,然后随机选择一个非劣个体,并用该非劣个体随机替换掉父代群体中的一个劣于个体(如果该劣于个体存在).此外,该算法还提出了一种不可行解存档和替换机制,旨在引导群体快速地向可行域逼近.值得注意的是,该算法在不需要将等式约束条件转换为不等式约束条件的情况下,也能搜索到全局最优解.Venkatraman 和Yen [32]提出了一个通用的框架求解约束优化问题,该框架包括两个阶段.第1个阶段将约束优化问题作为约束满足问题进行处理,其目标为至少找到一个可行解.为了实现这个目标,群体基于约束违反程度进行排序.若群体中出现可行解则转入第2个阶段,此时,其目标为找到全局最优解.第2个阶段同时考虑目标函数和约束违反程度,并对群体进行非劣排序[33].此外,第2个阶段还采用小生态策略来保持群体的多样性.Wang 等人[34]认为约束优化问题求解的本质在于如何有效地均衡目标函数和约束违反程度,提出了一种自适应均衡模型.该模型将群体进化分为3种情形,即1) 群体中仅包含可行解;2) 群体由可行解与不可行解联合组成;3) 群体中仅包含不可行解,并针对每种进化情形设计了不同的个体比较和选择准则.当群体处于第1种情形时,提出了一种分层的非劣个体选择机制,其目的在于引导群体从不同的方向朝可行域逼近;当群体处于第2。
