0-1非线性规划问题改进的教与学优化算法∗

0-1非线性规划问题改进的教与学优化算法∗

张林李会荣

（商洛学院数学与计算机应用学院商洛726000）

将0-1非线性规划问题转化为约束优化问题，采用动态双目标的约束处理方法，对教与学优化算法的迭代方程进行改进，提出了一种求解0-1非线性规划问题的改进教与学优化算法。数值实验表明，新算法具有较快的收敛速度和较好的全局寻优能力，显示了算法的有效性和通用性。

0-1非线性规划；约束优化；教与学优化算法

Class NumberTP18

1 引言

教与学优化（Teaching-learning-based optimi⁃zation，TLBO）算法是一种新型的群体智能优化算法，由印度学者Rao R V等于2011年提出，主要模拟教师的教学过程和学生之间的相互学习与交流过程［1～2］。TLBO算法结构简单，易于实现，参数少，有极强的收敛能力和较好的全局搜索能力，所以自算法提出以来已经涌现出许多对算法的改进和应用方面的研究。例如：文献［3］将差分进化算法的交叉操作引入到TLBO算法中，提出了一种带有交叉操作的教－学优化算法，有效地融合了教学阶段和学习阶段，增强了算法的局部搜索；文献［4］将差分进化算法中变异策略融入到TLBO中，对学习阶段迭代方程进行改进，提出了一种融合差分变异的教－学优化算法；文献［5］提出了一种融合模拟退火的改进的教与学优化算法，文献［15］引入反馈阶段和准确性因子，提出了一种改进的教与学的优化算法等等，目前TLBO已经成功应用到很多工程实际问题，例如非线性连续大规模优化［1］、约束优化问题［6］、多目标优化问题［7］等。

本文考虑0-1非线性规划问题如下：

其中f(x):Rn→R; gi(x):Rn→R, i=1,…m; hk(x):Rn→R,k=1,…,l是Rn上的可微函数。

非线性约束优化问题广泛存在于科学与工程领域，是一类比较难以解决的优化问题，没有普遍适用的解法。0-1非线性规划应用很广，很多问题可以归结为0-1非线性规划问题，例如指派问题、资本预算问题、背包问题、旅行商问题等［8～10］。

本文首先把0-1非线性规划问题转化为约束优化问题，采用动态双目标的约束处理方法，提出了一种求解0-1非线性规划问题的改进教与学优化算法，数值结果表明，提出的算法简单，易于实现，具有较快的全局搜索能力。

2 基本TLBO算法

基本TLBO算法模拟了班级教学的过程，通过教师的讲授和学生之间的相互学习，来达到班级整体成绩上升的目的。在该算法中，学生的人数代表种群的规模，学生学习的科目个数表示优化问题搜索空间的维数，学生学习成绩类似于优化问题的适应度，在整个群体中教师被认为学习的最好者，代表最优解。TLBO算法的搜索过程分为教学阶段和学习阶段具体如下。

2.1教学阶段

教师通过提高班级平均成绩的方式来达到教育学生的目的。假设m表示班级学习的科目（空间的维数），n表示班级的学生人数（种群规模），Mi,j表示班级在第i次迭代中第j门课程平均值，Xi,kbest,j表示到第i次迭代班级中第j门课程中学习成绩最好者作为教师。则学生与教师之间的差异可以表示为

其中k=1,2,…,n，j=1,2,…,m，ri表示[0,1]之间的随机数，TF称为教学因子，表示平均值的变化程度，通常设置为1或2。TF按照下式随机地等概率的变化［1-2］：

其中rand表示[0,1]之间产生的随机数，round[]表示四舍五入取整。

在教学阶段，新产生的学习者主要使得每门课程的平均值向教师的知识水平移动，所以在Difference_Meani,k,j基础之上，第k个学习者在教学阶段按照下式产生新的学习者：

其中Xi,k表示第i次迭代中第k个学习者的学习能力。如果X′i,k优于Xi,k，则更新Xi,k，如果X′i,k优于Xi,kbest，则更新Xi,kbest（其中Xi,kbest表示直到第i次迭代中最好的学习者）。

f(Xi,k)表示第i次迭代中第k个学习者的适应值。如果xnewi,k优于Xi,k，则更新Xi,k，如果xnewi,k优于Xi,kbest，则更新Xi,kbest。

2.2学习阶段

班级学生之间可以相互学习。随机选择两个学习者k,k′，且k≠k′，第i次迭代中由学习者k,k′相互影响而产生新的学习者如下式：

3 改进的TLBO算法（ITLBO）

3.1线性递减的教学因子

在基本的教与学优化算法中，教学因子TF的大小决定着平均值的变化情况，由式（4）可以看出，TF要么取值为1，或者取值为2，即表示学习者从教师那里没有学到知识，要么学习者从教师那里学到全部知识。但是在实际的教学中而是介于两者之间。TF越小则表示搜索的步长较小，收敛速度比较慢；而TF越大则加速算法的收敛速度，但减少算法局部探测能力。为此将TF设置随着迭代次数而自适应变化如下：

其中Imax表示最大的迭代次数，i表示当前的迭代次数。从式（7）可以看出，教学因子随着迭代次数的增加由2逐渐减小到0，表示随着迭代的进行，知识难度的逐渐增加，学习者学习知识的能力开始下降，有利于加强算法的局部搜索能力。

3.2TLBO算法的改进策略

由于TLBO算法主要针对连续函数进行搜索运算，不能直接应用于0-1非线性规划问题，所以必须对其进行改进。为此，首先引入Sigmoid函数［11］求参数s，Sigmoid函数是神经网络中常用的一种模糊函数，形式如下

当Xmax=6时，参数s的取值范围为[0.0025, 0.9975]。对TLBO算法中每次迭代所产生的学习者的每个分量进行改进，形式如下其中rand为(0,1)中的随机数。这样，改进后的TLBO算法就可以应用求解0-1非线性规划问题。为了进一步改进粒子的全局搜索能力，按照一定的概率pm对当前学习者在{0,1}空间进行随机赋值。

4 0-1非线性规划问题的改进TLBO算法

4.1约束的处理技术

用粒子群优化算法求解约束优化问题时，处理约束条件是关键。本文采取动态双目标的处理方法［12］来求解0-1非线性规划问题，它的主要思想是将约束违反度函数作为优化的第一个目标，将目标函数作为第二个目标进行优化。为此定义约束违反度函数：

显然，φ(x)是所有违反约束的和，φ(x)≥0，并且φ(x)=0当且仅当x∈F（F表示非线性约束优化问题（2）的可行域）。因此求解约束优化问题（COP）就可以转化为无约束双目标优化问题：

由式（10）可以看出，φ(x)=0的所有解构成了约束优化问题的可行域，因此只有当φ(x)=0时，才开始优化min f(x)。但是许多优化问题的最优解就在可行域的边界附近，位于最优解附近的不可行解对于寻找最优解是很有帮助的。为此，本文设置一个约束容忍度δ≥0，使得φ(x)≤δ时，就开始优化f(x)。如果一个粒子在可行域的外面，即φ(x)＞δ，则这个粒子以φ(x)为其优化目标，否则的话，粒子以目标函数f(x)进行优化。

4.2改进TLBO算法的描述（ITLBO）

由此，求解0-1非线性规划问题（1）的改进TL⁃BO算法（ITLBO）的流程如下：

步骤1（初始化）设置当前迭代代数t=1，确定种群的大小N，搜索空间的维数M，在｛0，1｝空间内初始化班级和优化问题f(x)。

步骤2按照式（10）计算每个学生的约束违反度φ(Xk)≤δ，如果A={Xk|φ(Xk)≤δ}≠ø，则当前群体中最优个体（即教师）gbest=argf(x)，否则gbest=argφ(x)。

步骤3教学阶段。根据式（5）、式（11）更新每个学习者和教师的知识水平。

步骤4学习阶段。根据式（6）在班级中随机选择两个学习者，通过对比差异进行相互学习。

步骤5变异阶段。按照概率pm对当前学习者在{0,1}空间进行随机赋值。

步骤6让t=t+1，返回到步骤3，直到获得一个预期的适应值或达到设定的最大迭代次数停止。

5 数值实验

文献［13］利用最速下降法来求解0-1非线性规划问题，为了比较仍采用文献［13］中的例子来说明算法的有效性。其中例1～2为0-1线性规划问题，例3～4为0-1非线性规划问题，例题如下：

例4［14］：求0-1二次规划min f(x)=xTQx, x∈{0,1}5，其中

数值实验在Matlab2014a中进行，在计算中，学生的规模N=20，最大的迭代次数为200，教学因子TF从2线性递减到0。约束容忍度δ=10-10，变异概率pm=0.3。每组实验在相同的条件下独立运行30次，30次运行的最优解、最优值、成功率、以及运行的平均时间与文献［8］的结果比较结果见下表1（其中“--”表示文献中没有提供数据）。

表1 新算法与文献［8～9］的运行结果比较表

从表1中可以看出ITLBO算法很快找到了最优解，同时也不需要初始点，具有较快的收敛速度和较好的全局寻优能力。与文献［13］中相比特别是例2，文献［13］中利用最速下降法迭代9次时才得到局部最优解x*=(1,1, 0,1,1)，最优值为f(x*)=-2，而利用新算法每次都得到了最优解，得到的全局最优值f(x*)=-6，从而显示了新算法的有效性和通用性。

6 结语

本文提出了一种求解0-1非线性规划问题的改进教与学优化算法，首先把0-1非线性规划转化为约束优化问题，采用动态双目标的约束处理方法，引入Sigmoid函数，对基本教与学优化算法进行改进，使之适合求解0-1非线性规划问题。最后数值试验说明了提出的算法简单，易于实现，具有良好的收敛性。

［1］Rao R V，Savsani V J，Vakharia D P.Teaching-learn⁃ing-based optimization：A novel method for constrained mechanical design optimization problems［J］.Comput⁃er-Aided Design，2011，43：303-315.

［2］Rao R V，Savsani V J，Vakharia D P.Teaching-Learn⁃ing-Based Optimization：An optimization method for con⁃tinuous nonlinear large scale problems［J］.Information Sciences，2012，183：1-15.

［3］高立群，欧阳海滨，孔祥勇，等.带有交叉操作的教-学优化算法［J］.东北大学学报（自然科学版），2014，35（3）：323-327.

GAO Liqun，OUYANG Haibin，KONG Xiangyong，et al. Teaching-Learning Based Optimization Algorithm with Crossover Operation［J］.Journal of Northeastern University（Natural Science），2014，35（3）：323-327.

［4］李会荣，乔希民，赵鹏军.融合差分变异的教-学优化算法［J］.计算机工程与应用，2016，52（5）：36-40.

LIHuirong，QIAOXimin，ZHAOPengjun.Teach⁃ing-Learning Based Optimization Algorithm by using dif⁃ferential mutation［J］.Computer Engineering and Applica⁃tion，2016，52（5）：36-40.

［5］岳振芳，高岳林.融合模拟退火的改进教与学优化算法［J］.河南师范大学学报（自然科学版），2016，44（1）：149-154.

YUE Zhenfang，GAO Yuelin.Modified Teaching-Learn⁃ing-Based Optimization Algorithm by Using Simulated An⁃nealing［J］.Journal of Henan Normal University（Natural Science Edition），2016，44（1）：149-154.

［6］Rao R V，Patel Vivek.An elitist teaching-learning-based optimization algorithm for solving complex constrained op⁃timization problems［J］.International Journal of Indus-tri⁃al Engineering Computations，2012，3：535-560.

［7］Rao R V，Patel Vivek.Multi-objective optimization of heatexchangersusingamodifiedteaching-learn⁃ing-based optimization algorithm［J］.Applied Mathemati⁃cal Modelling，2013，37：1147-1162.

［8］Bazaraa M S，Sherali H D，Shetty C M.Nonlinear Program⁃ming，Theory and Algorithm，Seconded［M］.New York：Academic Press，1979.

［9］Rao S S.Optimization（Theory and Application）Publica⁃tion，No.161，vol.2，1977.

［10］Hilier F S，Liberman G J.Introduction to Mathematical Programming［M］.New York：Graw-Hill，1981.

［11］纪震，廖惠连，吴青华.粒子群优化算法及应用［M］.北京：科学出版社，2009.

JI Zhen，LIAO Huilian，WU Qinghua.An Improved Teaching-Learning-Based Optimization Algorithm［M］. Beijing：Science press，2009.

［12］Haiyan Lu，Weiqi Chen.Dynamic-objective particle swarm optimization for constrained optimization problems［J］.J Glob Optim，2006，12：409-419.

［13］ANJIDANI M，EFFATI S.Steepest descent method for solving zero-one nonlinear programming problems［J］. Applied Mathematics and Computation，2007，193：197-202.

［14］雍龙泉.一类0-1二次规划最优解的新算法［J］.数学的实践与认识，2009，39（6）：194-197.

YONG Longquan.A New Method for Zero-one Quadratic Programming［J］.Joumal of Mathematics in Practice and Theory，2009，39（6）：194-197.

［15］李会荣，李甜.一种改进的教与学的优化算法［J］.商洛学院学报，2016，30（2）：1-5.

LI Huirong，LI Tian.An Improved Teaching-Learn⁃ing-Based Optimization Algorithm［J］.Journal of Shan⁃gluo University，2016，30（2）：1-5.

Improved Teaching-learning-based Optimization Algorithm for Solving Zero-one Nonlinear Programming Problems

ZHANG LinLI Huirong
（Department of Mathematics and Computer Science，Shangluo University，Shangluo726000）

The zero-one nonlinear programming problems is converted constrained optimization problems，an improved teach⁃ing-learning-based optimization（ITLBO）for solving the zero-one nonlinear programming is proposed using dynamic bi-objection constraint-handling method and modifying the iterative equation of TLBO algorithm.Simulation results show that ITLBO is effective⁃ness in terms of convergence speed and global optimization ability.

zero-one nonlinear programming，constrained optimization，teaching-learning-based optimization

TP18

10.3969/j.issn.1672-9722.2017.05.010

2016年11月20日，

2016年12月27日

张林，男，教授，研究方向：计算机应用，网络安全。李会荣，男，副教授，研究方向：图像处理。