关于线性约束问题的最优化方法外文翻译资料

英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料

关于线性约束问题的最优化方法

关键词

惩罚函数法

约束优化

四杆机构

马尔科夫预测模型

摘要

存在涉及不同约束的各种优化问题。 在这项研究中，我们提出了一种优化方法，称为误差反馈方法 (EFM)，用于解决线性约束问题。 该方法用于计算违反约束的误差，然后将误差按比例分配给每个参数，以使新的后代满足约束。 与惩罚函数法相比，EFM具有节省计算资源、收敛速度快的优点。 为了验证 EFM 的性能，我们使用一个典型的基准函数和三个工程模型作为示例。 这些模型包括一个复杂的线性不等式约束、一个具有线性等式约束的马尔科夫预测模型和两个具有不等式约束的数学平面四连杆模型。 为了优化每个模型，我们选择了三种流行的算法，即粒子群优化、基于教学的优化和差分进化。 我们将 EFM 与罚函数法和其他处理线性约束问题的方法进行了比较。 实验结果表明，EFM比比较方法具有明显更好的稳定性和更快的收敛速度。

1. 简介

在处理实际的科学和工程优化问题时，我们可能会发现各种约束。 示例包括线性等式约束下的卡尔曼滤波 [1]、线性约束下的调度问题 [2] 以及非线性约束下的自适应控制移动机器人 [3]。 通常，我们将约束分类为线性 [4] 或非线性 [5]。 一些复杂的非线性约束[6]可以简化为线性约束，使得求解方程更方便。 例如，单个目标优化问题可以用以下公式表示：

在这个约束问题中，变量的个数用 n 表示，不等式和等式约束的个数分别用 I 和 J 表示。 f(x→)是目标函数，gi(x→)是第i个不等式约束，hj(x→)是第j个等式约束。 第 k 个变量在 [xlk, xuk] 范围内变化。 约束总数为 m = I J n。

通常，使用群体智能优化算法来求解所需的模型。 研究人员开发了著名的优化算法，如粒子群优化 (PSO) [7]、遗传算法 [8]、布谷鸟算法 [9]、差分进化 (DE) 算法 [10]、模拟退火算法 [11]、 磷虾群算法 [12] 和基于教学的优化 (TLBO) [13]。 对于一些复杂的数学模型，存在各种约束，不方便解决相关的优化问题。 目前，解决此类问题的主要方法是构建各种惩罚函数[14]，将有约束的问题转化为无约束的问题。 此外，还有处理约束问题的方法，如单纯形法[15]、Hooke-Jeeves搜索法[16]和拉格朗日乘子法[17]。

采用上述方法的一个限制是必须知道模型的景观才能得出其中一个参数。然而，由于大多数工程模型是离散的、随机的，甚至是迭代的，因此无法获得有关感兴趣参数的导数信息。 在这种情况下，最广泛使用的是惩罚。

惩罚函数方法可以涉及外部惩罚函数[18]或内部惩罚函数[19]。 外部惩罚函数的基本思想是在求解约束优化问题时对不可行的迭代点施加惩罚。 通过迭代过程增加惩罚，迫使迭代点逐渐接近可行区域。 内部惩罚函数的基本思想是迭代点必须严格移动到可行区域。 当迭代点接近可行域的边界时，施加的惩罚迫使该点返回内部可行域。

研究人员采用了各种改进的惩罚函数方法。Deb[20]提出了一种不带惩罚因子的惩罚函数方法，有效解决了遗传算法中可行解与不可行解之间的关系，迫使模型算法趋于可行解。林[21]提出了粗罚遗传算法来解决约束问题。 这个想法是通过计算违反约束的程度来改变惩罚。该算法被证明具有良好的收敛速度，可以得到模型的最优解。Sorkhab等人[22]提出了将惩罚函数与约束规划相结合的方法，以平衡局部和全局搜索以找到可行的解决方案。 该方法有效解决了不同机组、不同土地利用水平下的风电场布局优化问题。任等人[23] 提出了一种新的惩罚函数方法来解决线性多目标优化的半向量双层规划问题。Chen [24]通过用改进的惩罚函数方法代替传统的外部梯度方法，将变分不等式问题转化为非线性规划问题。乔[25]提出了一种基于角度自适应惩罚的多目标进化算法。在进化过程中，算法可以动态调整惩罚因子，对测试函数取得较好的效果。李[26]利用罚函数法解决了重力坝滑动稳定性分析中涉及因子标定的非线性优化问题。 得到的校准结果具有较高的准确性。Clempner [27]为多线性函数提出了一种新的正则化惩罚方法。使用两个参数来保证约束问题的强凸性和解集存在性的唯一性，也证明了算法的稳定性和收敛性。

然而，当使用惩罚函数方法处理约束时，就会出现问题。 首先，惩罚函数方法评估约束之外的解决方案，浪费计算资源。其次，约束之外的解决方案在相应的进化算法中没有起到帮助的作用。第三，对于下一代，可以选择约束之外的解作为父母，从而降低产生有效后代的概率。

因此，我们提出了一种解决线性约束问题的方法。 主要思想如下：在获得最优解的过程中，如果后代不在约束范围内，则计算新解与约束边界之间的误差。 然后使用归一化的思想将误差按比例分布在模型的参数中，并在约束边界内获得新的后代。 然后新的后代代替先前的后代参与优化进化算法的操作。 该方法的优点如下：一是保证所有后代都满足约束条件，节省计算资源； 第二，如果新生成的子代比之前的子代好，则可以继续参与子代的生成； 第三，因为所有后代都满足约束条件，所以这种方法保证了所有的函数适应度值都是有效的。

为了测试 EFM 的性能，以复杂的基准函数、马尔可夫预测模型和平面四杆机构的轨迹分析为例。 首先介绍基准功能； 它的目标函数有明确的表达。 我们使用 EFM 和其他方法来处理约束行为。 其次，介绍了马尔可夫预测模型和平面四杆机构模型。 这些模型的目标函数是未知的，因此其他约束处理方法不再适用。 为此，我们使用惩罚函数法和 EFM 来处理约束问题。 然后使用 PSO [7]、DE [10] 和 TLBO [13] 优化模型参数。 结果表明，EFM可以有效提高算法的性能并获得更好的解决方案。

本文的其余部分安排如下。 第2节简要介绍了 PSO、DE、TLBO 和外部惩罚方法。 第3节给出了误差反馈过程的具体计算方法。第4节详细介绍了惩罚函数方法、其他约束处理方法和 EFM 在处理约束问题中的性能比较和分析。 第5节提供了结论。

1. 相关理论

2.1.粒子群优化算法

我们假设优化问题可以描述为：minf(x) = f(x1, x2,hellip;, xD) s.t.xi isin; [Li, Ui] (i = 1,hellip;, D)。

如果一个粒子被描述为 Xi = (xi1, xi2,hellip;, xiD)，那么最佳位置是 Pi = (pi1, pi2,hellip;, piD)。 粒子 i 的速度由 Vi = ( vi1, vi2,hellip;, viD,) 描述。 它的第d维迭代函数为vi d(t 1) = wvi d(t) c1s1(pi d(t) - xi d(t)) c2s2( pg d(t) - xi d(t) ) (1) xi d(t 1) = xi d(t) vi d(t 1), (2) 其中 s1 和 s2 是从 0 到 1 的随机数，c1 和 c2 是学习因子 由用户定义，t为当前迭代次数，w为惯性权重，vid为第i个粒子的第d维速度。

2.2.DE

DE 包括四个主要部分：初始化、变异、交叉和选择 [28]。

2.2.1初始化

DE 的总体由 N 个 D 维参数向量组成，即 xi = [x1, xi2,hellip;, xiD],i = 1,hellip;,N。 初始种群中个体的参数如公式 1 所示生成。 (3): xi,j = (xmu;j p minus; xlj ow) lowast; r an d(0, 1) xjl ow (3) 其中 xlj ow, xu pj 是第 j 维的上下边界搜索空间。

2.2.2 突变

突变向量 vchild i 由以下突变操作生成： vchild i= xra F( xrb minus; xrc) (4) 其中 F 是用户在范围 (0 , 2)。

ra、rb 和 rc 是从 (1, 2, ..., N) 中随机选择的彼此不同的数字。

2.2.3. 交叉

额外的种群可以通过方程式给出的交叉操作产生。 (5)。 由交叉操作生成的群体表示为 uci hi ld = (uci,1 hi ld, ..., uci,D hi ld)。

uchild i,j = { uchild i,j if(rand(0, 1) lt; CR)or(j = jrand) xi,j else (5) 其中 CR 是交叉率，范围从 0 到 1，定义为 用户。 jrand 是从 (1, 2, ..., D) 中随机选择的数字。

2.2.4. 选择

在评估目标函数时，较差的种群会被较好的种群取代。 选择过程可以表示为：

2.3. TLBO

假设一个学生在课堂上的表现符合正态分布，概率密度函数为

其中sigma;2是方差 , mu; 是均值，x 是满足正态分布的任意值。

TLBO 由两部分组成。 第一个是“教师阶段”，第二个是“学习者阶段”[13]。

2.3.1. 教师阶段

在教学阶段，每个学生通过寻找教师和学生的平均分之间的差异来提高自己的表现。“教师阶段”表示为

其中 Xiold 和 Xinew 分别表示第 i 个学生在教学前后的表现。 Mn ew 是教学后班级的平均值，meani 是全班所有学生的平均值，ri d(0, 1)]。 = rand(0, 1)，T F 是教学因子：T F = round[1 rand(0,1)]。

2.3.2. 学习阶段

教学结束后，每个学生的成绩都会更新为

其中两个学生 Xj 和 Xi 从班级中随机选择，并且功能适应度较差的学生 Xj 向更好的 Xi 学习。

2.4. 外罚函数法

外罚函数法是处理约束问题的一种方法。 其基本原理如下：如果解不满足约束，则对目标函数施加惩罚，迫使得到的解在可行域内。 外部惩罚函数的计算公式为 F( x→) = f( x→) P1i sdot; gi( x→) P2j sdot; hj( x→)，其中 gi( x→) 是第 i 个不等式约束 , hj( x→) 是第 j 个等式约束。 P1i 是不等式约束的第 i 个惩罚因子，P2j 是等式约束的第 j 个惩罚因子。 F(x→)是处理约束后的目标函数。

1. 有建设性的方法

3.1.动机

在求解模型的过程中，存在一些不满足约束的解。如上所述，如果使用惩罚函数方法处理约束问题，则会浪费计算资源。理想情况下，所有的操作步骤都应该对获得最优解起到有益的作用。然而，当一个解超出约束时，它产生的后代几乎没有机会产生最优解。因此有必要通过映射将这样的解映射到约束内的位置。这样，新的映射位置可以被认为是新的解决方案，而不是之前的不受约束的解决方案。如何确定映射？神经网络中使用的经典 EFM可以提供灵感。在训练神经网络的过程中，当处理目标值的误差时，误差按照每个节点的权重按比例分配，然后反馈给所有层中的每个节点。受此过程的启发，在我们的方法中，通过将当前值与约束进行比较来捕获错误。将每个参数的当前解的值作为权重。然后按比例重新分配误差。其次，提出了一种优化方法来处理线性约束问题。

3.2. 提出的约束处理方法

如图 1 所示，可行空间由 y1、y2 和 y3 组成。 点 A 在不可行区域内：它在 y2 和 y3 之内，但不在 y1 之内。 在这种情况下，我们将 A 沿 y1 法线方向投影到 C，其中 AB 是约束违反程度，BC 是随机距离。 但是，由于伪逆矩阵误差，A 可能会投影到 D。在这种情况下，D 通过映射投影到 E。 假设点 E 仍然不满足约束：通过上述投影方法，我们总能在可行空间中找到对应点。

我们假设 x1, x2, ..., xn 是模型参数； 模型约束条件为线性约束，写为 A sdot; x le; b，

其中 ci = Ai sdot; xi, i = (1, 2,hellip;, m)，Ai 表示 A 的第 i 行的所有列元素，step ge; 0。当约束条件为线性等式约束时，step = 0; 当约束条件为线性不等式约束时，stepgt;0。在本研究中，处理线性不等式约束问题时，wetake step = 1.5。

我们可以通过方程找到矩阵 A、B 的伪逆。 (11)。 然后我们可以通过方程获得误差 xei 和新种群 xi new

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[587831]，资料为PDF文档或Word文档，PDF文档可免费转换为Word