﻿ 求解约束优化问题的协同进化教与学优化算法
 首页 关于本刊 编 委 会 期刊动态 作者中心 审者中心 读者中心 下载中心 联系我们 English
 自动化学报  2018, Vol. 44 Issue (9): 1690-1697 PDF

1. 西安电子科技大学数学与统计学院 西安 710126

A Co-evolutionary Teaching-learning-based Optimization Algorithm for Constrained Optimization Problems
LIU San-Yang1, JIN An-Zhao1
1. Department of Mathematic Science, Xidian University, Xi'an 710126
Manuscript received : February 14, 2017, accepted: June 22, 2017.
Foundation Item: Supported by National Natural Science Foundation of China (61373174)
Corresponding author. JIN An-Zhao Master student at Xidian University. His research interest covers optimization algorithms and their application. Corresponding author of this paper.
Abstract: In order to avoid the inconvenience of penalty factors and the tolerance amount during transforming equality constraints into inequality constraints, the self-learning process is combined with teaching-learning-based algorithm, and a co-evolutionary teaching-learning-based algorithm is thus proposed, which makes the penalty factors and tolerance amounts dynamically adjust along with the population evolution. Numerical experiments on seven common test functions verify the effectiveness of the algorithm to solve optimization problems with equality and inequality constraints.
Key words: Teaching-learning-based optimization algorithm     co-evolutionary     penalty factor     tolerance amount     population diversity

 $\mid h(x) \mid-\delta\leq 0$ (1)

1 基本教与学优化算法

1.1 教学阶段

 ${\rm Difference\_Mean}_k=r_k(T_k-T_FM_k)$ (2)

 $T_F=\text{round}[1+\text{rand}(0, 1)\{2-1\}]$ (3)

 $X_{\rm new}=X_{{\rm old}}+{\rm Difference\_Mean}_k$ (4)

1.2 学习阶段

 $X_{{\rm new}, i}=X_{{\rm old}, i}+r_i(X_i-X_j), \\i, j=1, 2, \cdots, NP$ (5)

 $X_{{\rm new}, i}=X_{{\rm old}, i}+r_i(X_j-X_i), \\i, j=1, 2, \cdots, NP$ (6)

2 协同进化教与学约束优化算法(CTLBO) 2.1 算法模型

Coello[16]提出了一种求解约束优化问题的协同进化遗传算法, He等[17]提出了求解约束优化问题的协同进化粒子群算法, Huang等[18]提出了求解约束优化问题的协同进化差分进化算法(Co-evolutionary differential evolution, CDE).这些算法在求解工程约束优化问题时取得了较好的结果.本文基于这些算法提出一种协同进化教与学约束优化算法, 图 1展示了算法模型.

 图 1 算法模型 Figure 1 Algorithm model

2.2 自我学习过程

 x{\rm new}1_{i, k}= \left\{ \begin{aligned} &x_{i, k}, &k \neq j \\ &x_{i, j}+{\rm rand}(x\max(j)-x_{i, j}), &k=j \\ \end{aligned} \right.

 x{\rm new}2_{i, k}= \left\{ \begin{aligned} &x_{i, k}, &k \neq j \\ &x_{i, j}+{\rm rand}(x_{i, j}-x\min(j)), &k=j \\ \end{aligned} \right.

2.3 进化班级C1

 \begin{align} &\text{min}~ f(x) \\ &\text{s. t.}\quad\! g_i(x)\leq 0, \quad i=1, 2, \cdots, n \\ &~~~~~\quad h_j(x)=0, \quad j=1, 2, \cdots, p \end{align} (7)

 \begin{align} {\rm fitness}(x)= &f(x)+\omega_1\times sum\_{viol}(x)+\\&\omega_2\times num\_{viol}(x) \end{align} (8)

 $sum\_{viol}(x)=\sum\limits_{i=1}^Ng_i(x), \forall g_i(x)>0$ (9)

2.4 进化班级C2

1) 当子班级$C_{1, j}$ 中至少含有一个可行解时, $B_j$ 称为有效学员, 适应度值可以分两个阶段计算:进化初期阶段和进化后期阶段.进化初期阶段, 算法目标是增加可行解数量的同时增加种群多样性, 此时$B_j$ 的适应度值函数可以表示为

 \begin{align} &{\rm fitness}(B_j)=\\&\qquad-\frac{\sum ({\rm objective}_{j, i}-{\rm mean}\_{{\rm objective}_j})^2}{\rm num\_{\rm feasible}}-\\&\qquad{\rm num\_ feasible} \end{align} (10)

 \begin{align} {\rm fitness}(B_j)&=\\&\frac{\sum ({\rm objective}_{j, i}-{\rm mean}\_{{\rm objective}_j})^2}{\rm num\_{\rm feasible}}-\\&{\rm num\_feasible} \end{align} (11)

 ${\rm fitness}(B_j)=-\frac{\sum {\rm feasible}}{\rm num\_{\rm feasible}}-\\ {\rm num\_feasible}$

2) 当子班级$C_{1, j}$ 中不存在可行解时, 则称$B_j$ 为无效学员, 此时$B_j$ 适应度值函数如下

 \begin{align} {\rm fitness}(B_j)=&{\max}(P_{\rm valid})+\frac{\sum sum\_{viol}}{\sum num\_{viol}}+\\&\sum num\_{viol} \end{align} (12)

3 算法流程图

 图 2 算法流程 Figure 2 Flow chart of CTLBO
4 仿真分析

 图 3 焊接梁模型图 Figure 3 Model of welded beam

 \begin{align*} &{\min} f(x)=1.10471x_1^2x_2+0.04811x_3x_4(14.0+x_2) \\ & \text{s. t.}\ \ g_1(x)=\tau(x)-\tau_{\max}\leq 0 \\ & \hskip8mm g_2(x)=\sigma(x)-\sigma_{\max}\leq 0\\ & \hskip8mm g_3(x)=x_1-x_4\leq 0 \\ &\hskip8mm g_4(x)=0.10471x_1^2+\\ &\hskip8mm 0.04811x_3x_4(14.0+x_2)-5.0\leq0 \end{align*}
 \begin{align*} g_5(x)&=0.125-x_1\leq 0 \\g_6(x)&=\delta(x)-\delta_{\max}\leq 0 \\ g_7(x)&=P-P_c(x)\leq 0 \end{align*}

 图 4 压力容器模型 Figure 4 Model of pressure vessel

 $\begin{split} {\min} f(x)&=0.6224x_1x_3x_4+1.7781x_2x_3^2+\\&3.1661x_1^2x_4+19.84x_1^2x_3 \\ \text{s. t.}\quad g_1(x)&=-x_1+0.0193x_3\leq 0 \\ g_2(x)&=-x_2+0.00954x_3\leq 0 \\g_3(x)&=-\pi x_3^2x_4-\frac{4}{3}\pi x_3^3+1296000\leq 0 \\ g_4(x)&=x_4-240\leq0 \end{split}$

 图 5 最小化张力弦模型 Figure 5 Model of tension string

 $\begin{split} {\min} f(x)&=(x_3+2)x_2x_1^2 \\ \text{s. t.}\quad g_1(x)&=1-\frac{x_2^3x_3}{71 785x_1^4}\leq 0 \\ g_2(x)&=\frac{4x_2^2-x_1x_2}{12 566(x_2x_1^3-x_1^4)}+\frac{1}{5 108x_1^2}-1\leq 0 \\ g_3(x)&=1-\frac{140.45x_1}{x_2^2x_3}\leq 0 \\ g_4(x)&=\frac{x_1+x_2}{1.5}-1\leq0 \end{split}$

5 结论

 1 Chen Bao-Lin. Optimization Theory and Algorithm. Beijing: Tsinghua University Press, 1989.( 陈宝林. 最优化理论与算法. 北京: 清华大学出版社, 1989.) 2 Das S, Mullick S S, Suganthan P N. Recent advances in differential evolution-An updated survey. Swarm & Evolutionary Computation, 2016, 27: 1-30. 3 Duan H B, Li P, Yu Y X. A predator-prey particle swarm optimization approach to multiple UCAV air combat modeled by dynamic game theory. IEEE/CAA Journal of Automatica Sinica, 2015, 2(1): 11-18. DOI:10.1109/JAS.2015.7032901 4 Pan Feng, Chen Jie, Gan Ming-Gang, Cai Tao, Tu Xu-Yan. Model analysis of particle swarm optimizer. Acta Automatica Sinica, 2006, 32(3): 368-377.( 潘峰, 陈杰, 甘明刚, 蔡涛, 涂序彦. 粒子群优化算法模型分析. 自动化学报, 2006, 32(3): 368-377.) 5 Jin Xin-Lei, Ma Long-Hua, Wu Tie-Jun, Qian Ji-Xin. Convergence analysis of the particle swarm optimization based on stochastic processes. Acta Automatica Sinica, 2007, 33(12): 1263-1268.( 金欣磊, 马龙华, 吴铁军, 钱积新. 基于随机过程的PSO收敛性分析. 自动化学报, 2007, 33(12): 1263-1268.) 6 Long Q, Wu C Z. A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization. Journal of Industrial & Management Optimization, 2017, 10(4): 1279-1296. 7 Prakasam A, Savarimuthu N. Metaheuristic algorithms and probabilistic behaviour:a comprehensive analysis of Ant Colony Optimization and its variants. Artificial Intelligence Review, 2016, 45(1): 97-130. 8 Ma L B, Zhu Y L, Zhang D Y, Niu B. A hybrid approach to artificial bee colony algorithm. Neural Computing and Applications, 2016, 27(2): 387-409. DOI:10.1007/s00521-015-1851-x 9 Coello C A C, Carlos A. Constraint-handling Techniques Used with Evolutionary Algorithms. In: Proceedings of the 10th Annual Conference Companion on Genetic and Evolutionary Computation. Atlanta, GA, USA: ACM, 2010. 2445-2466 10 Wu G H, Pedrycz W, Suganthan P N, Mallipeddi P. A variable reduction strategy for evolutionary algorithms handling equality constraints. Applied Soft Computing, 2015, 37: 774-786. DOI:10.1016/j.asoc.2015.09.007 11 Rao R V, Savsani V J, Vakharia D P. Teaching-learning-based optimization:a novel method for constrained mechanical design optimization problems. Computer-Aided Design, 2011, 43(3): 303-315. DOI:10.1016/j.cad.2010.12.015 12 Venkata Rao R. Teaching-learning-based optimization and its engineering applications. Teaching Learning Based Optimization Algorithm: and Its Engineering Applications. Berlin, Heidelberg: Springer Publishing Company, 2015. 13 Venkata Rao R, Patel V. An elitist teaching-learning-based optimization algorithm for solving complex constrained optimization problems. International Journal of Industrial Engineering Computations, 2012, 3(4): 535-560. DOI:10.5267/j.ijiec 14 Patel V K. Teaching Learning Based Optimization Algorithm. Berlin, Heidelberg: Springer International Publishing, 2016. 15 Yu Kun-Jie, Wang Xin, Wang Zhen-Lei. Elitist teaching-learning-based optimization algorithm based on feedback. Acta Automatica Sinica, 2014, 40(9): 1976-1983.( 于坤杰, 王昕, 王振雷. 基于反馈的精英教学优化算法. 自动化学报, 2014, 40(9): 1976-1983.) 16 Coello C A C. Use of a self-adaptive penalty approach for engineering optimization problems. Computers in Industry, 2000, 41(2): 113-127. DOI:10.1016/S0166-3615(99)00046-9 17 He Q, Wang L. An effective co-evolutionary particle swarm optimization for constrained engineering design problems. Engineering Applications of Artificial Intelligence, 2007, 20(1): 89-99. DOI:10.1016/j.engappai.2006.03.003 18 Huang F Z, Wang L, He Q. An effective co-evolutionary differential evolution for constrained optimization. Applied Mathematics & Computation, 2007, 186(1): 340-356. 19 Richardson J T, Palmer M R, Liepins G E, Hilliard M. Some guidelines for genetic algorithms with penalty functions. In: Proceedings of the 3rd International Conference on Genetic Algorithms. George Mason University, USA: Morgan Kaufmann Publishers Inc., 1989. 191-197 20 Runarsson T P, Yao X. Stochastic ranking for constrained evolutionary optimization. IEEE Transactions on Evolutionary Computation, 2000, 4(3): 284-294. DOI:10.1109/4235.873238 21 Kannan B K, Kramer S N. An augmented lagrange multiplier based method for mixed integer discrete continuous optimization and its applications to mechanical design. Journal of Mechanical Design, 1994, 116(2): 405-411. DOI:10.1115/1.2919393 22 Arora J S. Introduction to Optimal Design. New York: McGraw-Hill, 1989. 413-432. 23 Belegundu A D, Arora J S. A study of mathematical programming methods for structural optimization. Part Ⅰ:theory. International Journal for Numerical Methods in Engineering, 1985, 21(9): 1583-1599. DOI:10.1002/(ISSN)1097-0207 24 Brajevic I, Tuba M. An upgraded artificial bee colony (ABC) algorithm for constrained optimization problems. Journal of Intelligent Manufacturing, 2013, 24(4): 729-740. DOI:10.1007/s10845-011-0621-6 25 Yu K J, Wang X, Wang Z L. An improved teaching-learning-based optimization algorithm for numerical and engineering optimization problems. Journal of Intelligent Manufacturing, 2016, 27(4): 831-843. DOI:10.1007/s10845-014-0918-3 26 Mohamed A W, Sabry H Z. Constrained optimization based on modified differential evolution algorithm. Information Sciences, 2012, 194: 171-208. DOI:10.1016/j.ins.2012.01.008 27 Patel V K, Savsani V J. Heat transfer search (HTS):a novel optimization algorithm. Information Sciences, 2015, 324: 217-246. DOI:10.1016/j.ins.2015.06.044 28 Venkata R R. Jaya:a simple and new optimization algorithm for solving constrained and unconstrained optimization problems. International Journal of Industrial Engineering Computations, 2016, 7(1): 19-34.