非线性约束优化

本章讨论非线性约束优化问题。在SVM的拓展模型中，很多也属于非线性约束优化问题。非线性约束优化在最优化领域一直是一类非常难处理的问题，但各种解决方案仍然层出不穷。进化算法以其能够解决大规模、复杂函数优化的巨大潜力使人眼前一亮，它被大量用来解决非线性规划领域内的各种问题。但对于非线性约束优化问题，目前的约束处理技术还不能系统有效地对任何情况都有效解决。

近些年来，利用进化算法求解约束优化问题也取得了很大的得进展（见文献［159－163］）。已有的常用的方法大致分为四类：（1）用专门设计的算法使容许解个体变为新的容许解个体；（2）降低非容许解个体适应值的罚函数法；（3）修改非容许个体的方法；（4）其他混合方法。文献［159］对已有的大多数方法进行了评述，并指出这些方法存在的一些弊端以及对一些测试函数所得结果不令人满意的地方。

本章的研究主要是通过模型转换，把原目标函数作为第一个目标函数，把约束优化问题中约束函数值最大的约束与零作比较，取较大者作为第二个目标函数，由这两个函数组成一个多目标函数向量，从而将原问题转化为一个有两个目标函数的多目标优化问题。然后运用多目标遗传算法，通过设计新的杂交、变异、选择等遗传算子进行遗传操作，最终可得原问题的最优解。

目前已经有很多学者运用类似的方法对约束优化问题进行了较好的操作。文献［164］中提出了COMOGA（Constrained Optimization by Multi－Objective Genetic Algorithms）算法，该算法在进化算法的基础上，把约束优化问题转化为多目标优化问题，同时结合了传统的罚函数法，但比传统罚函数法少了许多对参数的需求。它从两个方面去考虑，有时把约束优化问题看作是约束满足问题，有时看作是无约束优化问题，在单一种群上两种模式同时作用，选择机制既考虑到目标函数值的大小又照顾到对约束的违反度。该算法成功地应用于工业问题中并取得显著效果。文献［165］设计的算法使用了处理多目标优化问题的VEGA［166］，通过把约束优化问题中的约束全部转化为目标函数，和原函数组成一个目标函数向量，然后设计了专门的遗传算子，使得在每一个容许点附近产生一个大小变化的超立方体，整个算法一直在容许域中搜索。由于算法的重点在于搜索到约束优化问题的容许域，对一些容许域及其不规则的函数，算法效果不佳。文献［167］、［168］提出了协同进化遗传算法（Coevolutionary Genetic Algorithm，CGA）

CGA最早将一种寄生虫和寄生主协同进化的机制应用到优化搜索的改进中。与常规遗传算法不同的是，CGA有两个协同进化种群，两个种群中存在着相悖的适应度评价，即一方的成功正好成为另一方的失败。这样的评价机制会导致两个种群相互竞争，使得种群集体行为的复杂性在进化模拟中得到进一步发展。在处理约束优化问题中，一个种群是解种群，另一种群是由约束组成的测试种群。两个种群相互竞争，相互促进进化，从而确定满足约束的最优解。文献［169］设计的算法运用了混合策略，分两个阶段处理约束优化问题，第一个阶段是标准的进化算法，对于处理非凸的优化问题提供了较大的潜能。在假使第一阶段进化算法已经找到了全局最优解附近的一个解的基础上，第二阶段引入了拉各朗日乘子，结合罚函数的思想，使得算法迅速地找到另一个精确解。

Jimenez and Verdegay提出了处理约束的极大极小逼近法，该算法的利用下面的选择机制使得整个种群逐步逼近可行解，它的选择规则是：

（1）如果两个解都是可行解，则选择使得原目标函数值最小的个体；

（2）如果一个为可行解，一个为不可行解，则选择可行解；

（3）如果两个都为不可行解，则选择违反约束轻的个体。该算法的缺点是容易陷入可行域的局部跳不出来。

上面列出的是部分学者做出的一些较好的相关算法，对于用遗传算法解约束优化问题，现有的算法大部分能够有效地解决一类问题。本文利用遗传算法通过目标函数的变形将原约束优化问题转换为只有两个目标的多目标优化问题，再运用新设计的交叉、变异、选择等算子实现种群的可行化和最优化，以下将具体加以论述。