约束优化问题算法研究综述

朱清园

摘 要：约束优化问题是控制和决策领域的重要问题，也是智能算法领域的研究热点之一。本文对约束优化问题的相关概念进行了介绍，详细阐释了求解约束优化问题的四种主要智能算法：教与学优化算法、进化算法、粒子群算法和差分进化算法，对其算法思想、流程和特征进行了总结，并对其在工程中的主要应用进行了介绍，提出了求解约束优化问题的算法发展前景和面临的问题。

关键词：约束优化问题；TLBO；遗传算法；粒子群算法；差分进化算法

中图分类号：TP18 文献标识码：A 文章编号：1671-2064（2018）01-0013-04

1 引言

所有的控制与决策问题都可以归结为优化问题[1]，优化问题在冶金过程、化工管理、作业调度和其它工程应用等领域中广泛存在，相关优化算法得到了广泛应用。优化问题一般可分为无约束优化和约束优化两类，过去数十年来，无约束优化研究的成果多，其技术已经较为成熟，能解决绝大多数的无约束问题。

相较而言，约束优化问题比无约束优化问题更复杂，因为存在约束，导致搜索空间中不可行域增加；搜索时需要平衡约束和优化，某些问题的最优解往往在可行域的边界，特别是一些强约束问题，寻找到可行解已经非常困难，找到最优的可行解更是艰难[2]。

现有的解约束优化问题的传统方法主要是解析法和数值法[4][5]，其存在目标函数要求高、算法对初始值依赖性强、简单性和通用性差等缺点，因此，智能算法对于约束优化问题求解的发展至关重要。

2 约束优化问题算法综述

智能算法通过对动物智能行为进行模仿来解决实际生活中的问题，在智能算法中，种群个体代表搜索空间中的解，不要求连续或可导，也无需目标函数的梯度信息，更适合求解约束优化问题。下面介绍求解约束问题的常见的几种智能算法。

2.1 GA算法

在达尔文遗传学和进化论的启发下，Holland提出了进化算法（Genetic Algorithm，GA）。该算法在群体遗传学机理和自然选择基础上进行随机迭代和进化，具有很强的全局优化搜索能力和广泛适用性。进化算法对自然选择和遗传过程中发生的交配、繁殖和变异现象进行模拟，以优胜劣汰、适者生存的自然法则为依据，对选择、交叉和变异的进化算子加以利用，逐代产生候选解即优选个体，最终搜索得到较优的个体。进化算法是一种以种群中的所有个体为对象的种群型操作[6]。

遗传算法的基本步骤包括：

步骤1：随机生成初始种群，评价每个个体适配值；

步骤2：算法是否收敛判断，如果是，则输出搜索结果，如果否，执行以下操作；

步骤3：按照某一规则执行复制操作；

步骤4：以概率Pc执行个体间交叉操作；

步骤5：以概率Pm进行个体变异操作；

步骤6：然后转向步骤2。

流程图如下图1所示。

遗传算法具有以下特征：

（1）算法不被函数的可导性或连续性所限制，从一个问题解的集合开始进行搜索，搜索可以并行进行，速度得以提高；

（2）算法具有较强的全局寻优能力，对求解非线性复杂问题效果显著；

（3）进行算法的交叉、复制等操作都带有随机性，将个体的适应度值结合在探索过程。

2.2 TLBO算法

2010年，Rao等针对机械设计优化问题提出了一种新的高效优化算法——教与学优化算法（Teaching-Learning-Based Optimization，TLBO），其属于基于种群的启发式智能算法[7]。

TLBO基于老师对学生的影响，其算法流程大致为：在限制约束空间中随机生成一系列解，将这些解视为一个班级的“学生”，每个学生都有不同的科目，根据适应度值评价学生表现，其中表现最好的一位学生被任命为“老师”。算法分为教学阶段和学习阶段等两个阶段。在教学阶段，老师向学生“授课”，学生通过在“授课”中向老师“学习”来增加自己科目的知识水平；在学习阶段，类似于课后学生们相互交换学习心得，学生间进行学习交流，从而促进每个学生的成绩提高。在经过多次老师的“教学”过程和学生之间相互的“学习”过程之后，班级学生的知识水平得到提高，从而等同于在整个限制约束空间中，可行解的搜索空间不断地趋近于最优解。由于TLBO算法具备收敛能力强、收敛速度快、不需特定信息、且算法简易、所需参数少等优点，引起了广大研究者的研究与关注，并已经在多个领域得到了较好的应用。算法具体步骤如下：

步骤1：初始化优化模型参数和优化算法参数，包括种群规模（Population size）Pn，迭代次数Gn，待优化变量维数Dn和变量约束条件等；

步骤2：根据种群规模和变量维数随机生成初始种群，并计算个体的成绩（适应度值）。对于TLBO算法而言，种群规模表示学员的数量，待优化变量表示所提供的课程；

步骤3：教学阶段，计算班级每一维的平均值mi，得到平均个体，将其中的最优解作为教师，教师意图通过教学将均值从xold移至xteacher，通过下式得到新个体xnew：

步驟4：在学习阶段，学员间通过相互交流增长知识。在教师完成教学后，从学员中随机选择两个学员i和学员j，比较二者成绩，成绩较差的学员向成绩好的学员学习；

步骤5：当达到最大迭代次数后，终止迭代，否则重复步骤3和步骤4。

TLBO算法流程图如图2所示。

2.3 PSO算法

粒子群算法（Particle Swarm Optimization， PSO）是由美国社会心理学家James Kennedy和电气工程师Russell Eberhart在1995年共同提出[8]，该算法模仿鸟类群体的觅食行为，进而利用群体智能建立的一个简化模型。粒子群算法模拟鸟类的觅食行为，用鸟类的飞行空间类比问题的搜索空间，把每只鸟抽象成一个没有质量和体积的微粒，用以表示问题的一个候选解，用寻找食物的过程类比寻找问题最优解的过程，从而求解约束优化问题。endprint

粒子群算法的过程包括：

步骤1：种群随机初始化；

步骤2：计算种群内每个个体的适应值，适应值和最优距离相关；

步骤3：种群根据适应值进行更新；

步骤4：判断终止条件，如果满足则停止，否则转向步骤2。

其流程如图3所示：

粒子群算法具有以下特征：

（1）通过群体概念寻求最优值，最优值可以是一个或多个；通过将大量的个体行为聚合成群体行为寻求目标值，这与遗传算法相同；

（2）不依赖于函数本身，通过适应值来表征粒子是否满足条件，适用于生产，这种思想继承了当代算法的特质；

（3）从鸟群栖息出发，充分考虑鸟群的特征，每个鸟都对其他鸟产生直接和间接影响，鉴于这些影响，需要从社会部分和自适应部分这两个部分来改变单个粒子的变化趋势，主要体现在粒子群算法的速度更新模型。

2.4 DE算法

差分进化（Differential Evolution，DE）算法是由Rainer Storn和Kenneth Price在1995年共同提出的一种采用浮点矢量编码在连续空间进行随机搜索的优化算法[9]，初衷是为了求解切比雪夫多项式。差分进化算法是一种求解不可微、非线性、多极值和高维复杂函数的有效、鲁棒的方法，其受控参数少，原理简单，可以实施并行、随机、直接的全局搜索，并且易于理解和实现。差分进化算法基于群体进化，优化问题的求解通过种群内个体间的竞争与合作来实现，具有种群内信息共享和记忆个体最优解等特点，本质是一种基于实数编码的具有保优思想的贪婪遗传算法。差分进化算法应用领域十分广泛，除了约束优化问题，还包括：生物系统建模、模式识别、信号处理、决策和模拟多目标优化问题、神经网络训练、系统设计等。差分进化算法目前已经在模糊控制系统、机器人学、电力系统、函数优化、神经网络训练、组合优化及其它进化算法常用的应用领域得到成功运用。

差分进化算法的具体步骤包括：

步骤1：确定差分进化控制参数和差分参量；

步骤2：初始化种群，进化代数G=0；

步骤3：通过计算初始种群中的每个个体的适应值对其进行评价；

步骤4：判断终止条件满足与否或者进化代数是否达到最大进化代数，若是，则终止迭代，此时输出的最优解即为的最优个体，否则，继续下一步；

步骤5：对个体进行变异和交叉，并处理边界条件，得到试验种群；

步骤6：通过计算试验种群中每个个体的适应值来评价试验种群；

步驟7：进行选择操作，得到下一代种群；

步骤8： G=G+1，转至步骤4。

其流程图如图4所示。

差分进化算法具有以下特征[10]：

（1）算法通用，独立于具体问题条件；

（2）算法原理简单，受控参数少，容易实现；

（3）具有群体搜索能力，并能记忆个体最优解；

（4）具有良好的鲁棒性，对算法稍加改动可以适应不同的应用环境；

（5）算法收敛速度快；

（6）协同搜索，可根据个体局部信息和种群全局信息引导算法进行进一步搜索；

（7）易于与其他算法相结合，因为差分进化算法在本质上为进化算法，因此容易与其他算法相互融合以提高稳定性和算法精度等，构造出更好算法。

3 约束优化算法的工程应用

智能优化算法在各个领域的应用中取得了很多研究成果。在机械设计优化中，Rao等人[11]采用TLBO算法分别对机器人机械手、多片离合器制动、锥形滑轮、静压推力轴承以及滚动轴承等机械设计问题进行了优化设计。在热交换器优化设计中，文献[12]采用改进的多目标TLBO算法对二阶段热交换器进行优化设计，分别针对板翅式换热器（plate-fin heat exchanger，PFHE）和管壳式换热器（shell-and-tubeheat exchanger，STHE）两种产品进行了测试，其结果显示TLBO算法对于热交换器优化方面有着很强的优化性能。

生产调度是制造企业的生产计划控制和管理的重要环节。在生产调度优化设计中，Liao等人[13]扩展传统的二元离散粒子群算法用于求解流水车间调度问题，并且和遗传算法进行了对比；Lian等人提出了求解调度问题的一种基于PSO思想的进化算法，他们直接利用GA的交叉和变异操作作为PSO算法中粒子速度和位置的更新操作，并将其用于求解置换流水车间调度问题[14]和作业车间调度问题[15]。

机器人是一类复杂的难以精确建模的系统，在机器人领域的优化设计中，文献[16]中利用DE算法求解复杂环境下的机器人路径规划问题，结果表明该方法对解决大范围、复杂障碍环境下的机器人运动路径规划问题具有普遍适用性。神经网络训练问题是一种高度复杂、非线性的优化问题，在神经网络训练优化设计中，文献[17]将DE算法应用于在线训练神经网络，并在医疗图像识别上得到运用，均取得了满意的结果。

4 结语

本文从约束优化问题的概念出发，对求解约束优化问题的四种主要智能算法，教与学优化算法、进化算法、粒子群算法和差分进化算法的算法思想、主要步骤和特征等进行了介绍，并约束优化问题在工程中的相关应用进行了阐述。尽管近年来学者已经对约束优化问题展开了研究，但是对于非线性多变量多目标的复杂优化问题，目前还缺乏解决有效稳定的方法，因此对此还需要进行更深入研究。

参考文献

[1]王凌，刘波.微粒群优化与调度算法[M].清华大学出版社，2008.

[2]刘云连.求解约束优化问题的智能算法研究[D].湖南科技大学，2014.

[3]Joines J A， Houck C R. On the use of non-stationary penalty functions to solve nonlinear constrained optimization problems with GA's[C]// Evolutionary Computation， 1994. IEEE World Congress on Computational Intelligence.Proceedings of the First IEEE Conference on. IEEE， 1994：579-584 vol.2.endprint

[4]希梅尔布劳.D.M.实用非线性规划[M].科学出版社，1983.

[5]胡一波.求解约束优化问题的几种智能算法[D].西安电子科技大学，2009.

[6]王凌.智能优化算法及其应用[M].清华大学出版社，2001.

[7]Rao R V， Savsani V J， Vakharia D P. Teaching–learning-based optimization： A novel method for constrained mechanical design optimization problems[J]. Computer-Aided Design， 2011， 43（3）：303-315.

[8] Kennedy J， Eberhart R. Particle swarm optimization[C]// IEEE International Conference on Neural Networks， 1995. Proceedings. IEEE， 2002：1942-1948 vol.4.

[9]Storn R， Price K. Differential Evolution A Simple and Efficient Heuristic for global Optimization over Continuous Spaces[J]. Journal of Global Optimization，1997，11（4）：341-359.

[10]赵晓芬.求解约束优化问题的差分进化算法[D]. 西安电子科技大学， 2012.

[11]Rao R V， Savsani V J， Vakharia D P. Teaching–learning-based optimization： A novel method for constrained mechanical design optimization problems[J]. Computer-Aided Design， 2011， 43（3）：303-315.

[12]Rao R V， Patel V. Multi-objective optimization of heat exchangers using a modified teaching-learning-based optimization algorithm[J]. Applied Mathematical Modelling， 2013， 37（3）：1147-1162.

[13] Liao C J， Tseng C T， Luarn P. A discrete version of particle swarm optimization for flowshop scheduling problems[J]. Computers & Operations Research， 2007， 34（10）：3099-3111.

[14] Lian Z， Gu X， Jiao B. A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan[J]. Applied Mathematics & Computation， 2008， 175（1）：773-785.

[15]Lian Z， Gu X， Jiao B. A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan[J]. Applied Mathematics & Computation， 2008， 175（1）：773-785.

[16]Magoulas G D， Plagianakos V P， Vrahatis M N. Neural network-based colonoscopic diagnosis using on-line learning and differential evolution[J].Applied Soft Computing，2004，4（4）：369-379.

[17]馮琦，周德云.基于微分进化算法的时间最优路径规划[J].计算机工程与应用，2005，41（12）：74-75.endprint