集值向量优化中精确罚函数稳定性研究

吴功跃

集值向量优化问题作为约束优化问题之一，在工程、管理、科学、经济以及军事等众多领域中发挥极其重要的作用，因此对集值向量优化问题进行求解一直是国内外相关专家和学者研究的重點项目。经过多年的研究，目前常用的求解方法有可行点法，Lagrange 乘子法，共轭梯度法，罚函数法和信赖域法等几种。本次就对其中的罚函数法进行研究。罚函数求解的主要思路是将一个约束优化问题转化为一系列易于求解的无约束优化问题。在罚函数中又包括精确罚函数和序列罚函数两种，而所谓精确罚函数法是当罚参数足够大时，求得的罚问题的解就是原问题的解或原问题的解是罚问题的解，精确罚函数概念是由Zangwill第一个提出来的，由于其在求解集值向量优化问题上， 不需要罚因子无穷大， 即可以通过求解有限个罚问题来得到原问题的最优解，因此与上述几种其余求解方法相比， 是简单的、精确的，但是也因此是非稳定和非平静的，所以精确罚函数中的三个关键问题：平静、稳定和精确就成为近几年来被广泛研究的对象。经过研究得出一种结论，如果惩罚函数满足平静或稳定条件，就可以认定它是精确的，反推理，如果它是精确的，那么它一定是精确的。在此背景下，研究精确罚函数的平静性、稳定性具有十分重要的意义，但由于目前对平静性研究的比较多，而稳定性研究比较少，因此本文就仅对其中的稳定性进行研究，弥补精确罚函数研究中的不足，强化其中的薄弱环节，为集值向量优化求解问题的解决提供参考。

1 精确罚函数稳定性研究

精确罚函数的主要功能是将难解决或无法解决的约束化问题转换成易于解决的无约束化问题，从而通过求解无约束化问题解决集值向量优化问题。精确罚函数不需要求解多个罚优化问题，只需要在一个规定的区间内选取几个罚参数就可以得到想要求得的最优解，从而解决原集值向量优化问题。精确罚函数是罚函数的改进和优化，能极大减少计算量，但是有利就有弊，少量罚参数，无法确定得出的解是最优解，降低了罚函数的稳定，因此如何增强罚函数的稳定性成为研究的重点。

1.1 精确罚函数

罚函数的精髓是通过寻找一个容易求解的问题代替原问题，使得求解变得简单、容易。

首先构造一个具有罚性质的函数，如下：

在精确罚函数的概念下，转化为相应无约束化问题，其求得的解需要满足一下条件：求得最优解是原问题（集值向量优化问题）的最优解，实现精确罚函数的稳定。

1.2 求取满足稳定性条件的最优解

假定：r是无约束化问题的最优解，且迭代次数满足达到最小值，认为精确罚函数是稳定的。

求取满足稳定性条件的最优解的方法有很多，如遗传算法、神经网络算法等。下面就这针对这两种方法进行稳定性求解研究。

1.2.1 遗传算法

遗传算法，简称GA，最早是在1975年由美国密歇根州立大学J.Holland教授提出来的，其最大的优点是计算简单、适用性广、功能强，已被广泛应用于各个优化求解领域。其具体过程如下：

1）设置初始子群。子群是影响是遗传算法求取最优解的关键因素，子群规模越大，最优解求取效率越高，但与此同时也增加了计算量，因此只要以精确罚函数的规定区间内所有罚参数作为初始子群即可。为方便计算，对子群的所有罚参数进行标准化处理，计算与中间值的标准差值，然后对以上得到的标准化罚参数结果进行随机采样，即得到初始化子群，也就是多条染色体，每条染色体代表一个罚参数。

2）编码。在这里采用一种新的编码方式对每个染色体进行编码，即让每条染色体都有一个相对应的配置结构，然后利用M×N 的二维布尔矩阵对其进行表示，以此省略每条染色体的解码过程，直接就可以进行费用值评估，然后进行适应值计算。

3）计算适应值。适应值是衡量子群中每条染色体的生存能力的标准，适应值越高，该条染色体就越有可能是无约束化问题的最优解，但是在精确函数中，由于目标函数是不确定的，因此为了计算出每条染色体的的数值，需要先设定染色体适应值为非负数，然后在映射关系规则下，得出映射后的染色体适应值。

4）遗传算子。在遗传算子环节，主要由三个步骤：选择、交叉好变异。选择：遗传算法是根据达尔文的进化论提出的，因此其中心思想就是优胜劣汰，适者生存，剩到最后的就是最优的，这正是求取最优解的目的。选择，即从已经存在的子群中选择适应值高的个体作为基体，然后将该基体与子群中的其它个体进行交叉和变异操作。交叉：将选出的适应值高的染色体与其它染色体进行换组操作，其过程如下：选取固定一个点，每次两个染色体进行交叉操作时都以这个点为原点，按照一定的交叉概率进行操作，以此来避免出现重复情况。变异：为保证最优解质量，需要从交叉后的染色体子群中任意选取出若干个变异染色体进行变异操作，例如原染色体的位置数值为0 ，变异后的位置数值就应该是1，而原为1，变异后则为0。这样做的目的是增加子群多样性，从而增强精确罚函数求解过程的稳定性的。变异操作的关键是如何选择变异概率，变异概率的大小直接关系着变异得次数量，过小，求取的的解就有可能达不到最优，过大就有可能增加迭代次数，加大计算量，因此为保证结果最优，可以根据精确罚函数的规定区间进行确定，一般选择其中间数量所对应的概率。

利用遗传算法求取精确罚函数最大优势在于精度较高，能最大程度保证结果的准确性，而最大劣势在于计算量相比后面的神经网络较大，迭代次数较高。

1.2.2 神经网络

神经网络，顾名思义就是根据人体大脑神经网络构而模拟出的一种智能算法，主要作用是模拟大脑功能进行复杂信息处理。神经网络实际上是一个非线性动力学数学模型，在求取最优解中具有重要作用。神经网络最大的优点在于具有极强的鲁棒性、容错性、自适应性以及学习能力，所以本次研究利用神经网络对精确罚函数进行求解，以规定区间内罚参数为输入项输入到神经网络组织中，之后通过学习训练获得最优解，保证精确罚函数的稳定性。利用神经网络求取最优解的基本思路：遵循一定的法则，选择合适的网络结构以及精确罚函数的权值，使得求得的解达到最优。在这一过程中，最困难的部分在于能量函数的构造，使得构造出来的神经网络能最大限度的保证精确罚函数的稳定。这里的能量函数不具有任何的物理意义，只是在表达形式上与物理意义上的能量概念一致，所以需要依靠Hopfield提出的工作运行规则完成模型迭代，使得能量函数达到极小值。

神经网络求取最优解流程如下：

1）从各种神经网络结构中选取一个合适的运行结构，使神经元输出与精确罚函数的最优解相对应;

2）建立一个能量函数，使其求得的最小值对应精确罚函数的最优解;

3）通过能量函数推理出神经网络与精确罚函数之间的联系权重;

4）根据权重计算出精确罚函数中所有解;

5）由解建立一组以稳定性为约束条件的方程;

6）求解方程组，得出精确罚函数的最优解。

从上述过程中可以看出利用神经网络解决优化问题的过程实质上就是通过引进一个神经网络，这个网络对应一个精确罚函数和一个能量函数，当这两个函数的解相对性，二者就达到了相对平衡，从而保持精确罚函数稳定的过程。其重点是如何构造一个准确有效的能量函数。下面为一个典型的能量函数，其定义如下：

2 结束语

在约束优化问题中集值向量优化问题是其中最常见的，对于其解决方法有很多种，本次就其中的罚函数法进行深入研究。在罚函数中，精确罚函数作为其中的一类，如何保证其平静性、稳定性一直是未解决的重点问题之一，缺乏稳定行动精确罚函数是无法有效解决集值向量优化问题的，所以本次研究从求取精确罚函数最优解的角度入手，最大程度的确保其稳定性，主要介绍了两种方法，一是遗传算法;一是神经网络算法。这两种算法哪一种性能最佳或者如何将两种算法结合在一起使用，成为下一步研究的重点工作。通过本次研究期望为以上众多领域中约束优化问题的解决提供一些借鉴。

基金项目：国家自然科学基金（10461007）， 江西省自然科学基金（0611081）。

（作者单位：南昌大学科学技术学院基础部）