引用本文

刘三阳, 靳安钊. 求解约束优化问题的协同进化教与学优化算法. 自动化学报, 2018, 44(9): 1690-1697. doi: 10.16383/j.aas.2017.c170076

LIU San-Yang, JIN An-Zhao. A Co-evolutionary Teaching-learning-based Optimization Algorithm for Constrained Optimization Problems. ACTA AUTOMATICA SINICA, 2018, 44(9): 1690-1697. doi: 10.16383/j.aas.2017.c170076

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2017.c170076

关键词

教与学优化算法，协同进化，罚因子，约束容忍度，种群多样性 

摘要

对约束优化问题，为了避免罚因子和等式约束转化为不等式约束时引入的约束容忍度参数所带来的不便，本文在基本教与学优化（Teaching-learning-based optimization，TLBO）算法中加入了自我学习过程并提出了一种求解约束优化问题的协同进化教与学优化算法，使得罚因子和约束容忍度随种群的进化动态调整.对7个常见测试函数的数值实验验证了算法求解带有等式和不等式约束优化问题的有效性.

文章导读

约束优化问题是科学研究和工程应用领域经常遇到的一类数学规划问题, 它广泛存在但又难以求解, 因此对求解约束优化问题有效方法的研究具有重要的理论和实际意义.目前存在的约束优化算法大致可以分为两类:传统优化算法和现代智能优化算法.传统优化算法大多是基于梯度信息的寻优方法, 如可行方向法、投影梯度法和既约梯度法等[1].它们对于不可导, 可行域不连通, 甚至没有显式表达式的问题束手无策.现代智能优化算法主要包括差分进化算法(Differential evolutionary, DE)[2]、粒子群算法(Particle swarm optimization, PSO)[3-5]、遗传算法(Genetic algorithm, GA)[6]、蚁群算法(Ant colony optimization, ACO)[7]、人工蜂群算法(Artificial bee colony, ABC)[8]等.近年来, 现代智能算法得到了广泛的研究, 在求解约束优化问题方面取得了显著的成效.

大多数现代智能优化算法都是一种无约束搜索技术, 将其与约束处理技术结合的过程中需要引入一些额外的参数, 这些参数通常由使用者决定, 选取合适的参数一般需要经过多次试验不断调节.

罚函数法是应用最广泛的约束处理技巧, 其主要思想就是通过对目标函数f(x) 增加惩罚项p(x)来构造适应度值函数fitness(x).惩罚适应度值函数的构造过程会引入参数罚因子w , 罚因子选取太小则个体的适应度值主要由目标函数决定, 此时群体可能滞留在不可行区域, 很难找到最优解; 罚因子选取太大则种群快速进入可行域, 从而忽略了对不可行区域的搜索, 这样就不能充分利用不可行解提供的信息[9], 从而很难找到最优解.

此外, 还有很多约束优化问题带有等式约束, 等式约束的出现使得约束优化问题的求解变得更加困难.等式约束的出现极大地缩小了可行区域的范围, 对搜索最优解带来了极大的困难[10].一般的等式约束处理技术都是将等式约束转化为不等式约束, 即将等式约束h(x)=0转化为

∣h(x)∣−δ ≤ 0                              (1)

其中, δ 为等式约束的约束容忍度参数, 一般取较小的正数.这一转化过程改变了可行域的拓扑结构, δ 的大小直接决定了这种拓扑结构改变程度, 也决定了可行区域的大小.因此设置合适的约束容忍度参数δ 是十分必要的, 然而参数δ 的合理设置是一项十分困难的工作.

基于以上的这些不足, 本文提出了一种求解约束优化问题的协同进化教与学优化算法(Co-evolutionary teaching-learning-based optimization algorithm, CTLBO).该方法在基本教与学优化算法过程中加入了一个随机变异搜索的自我学习机制, 增强了算法局部搜索能力.文章首次提出将约束容忍度参数加入进化参数集中和罚因子一起自动进化, 避免了人工调节约束容忍度参数的困难, 同时也实现了约束容忍度参数自适应地进化, 有效地提高了求解约束优化问题的效率, 尤其是含有等式约束的优化问题.同时在计算个体适应度时, 将已有协同进化算法适应度值公式中的可行个体均值项替换为可行个体的方差, 并根据进化时期的不同阶段, 采用不同的适应度值计算公式, 有效地保证了种群的多样性.

图 1  算法模型

图 2  算法流程

图 3  焊接梁模型图

本文在基本教与学优化算法中加入了一种自我学习机制, 然后对已有协同进化算法的适应度值函数进行改进, 提出了一种可以增加种群多样性的适应度值函数, 并首次提出将等式约束对应的约束容忍度参数加入到协同进化参数集来实现参数自适应进化, 避免了人工调整参数的困难.在此基础上提出了一种求解约束优化问题的协同进化教与学约束优化算法(CTLBO), 该算法结合了协同进化算法和教与学优化算法的优良特性, 在算法过程中没有引入额外的参数, 保持了教与学优化算法参数较少这一特点.对三个等式约束优化问题和4个不等式约束优化问题进行了仿真分析, 并与其他一些算法进行比较, 结果表明本文所提出的算法在求解带有等式约束和不等式约束的优化问题时具有较好的性能, 其求解精确度和稳定性较文中列出的算法也有所提高.

作者简介

刘三阳

西安电子科技大学教授.主要研究方向为应用数学, 最优化, 运筹学.E-mail:liusanyang@126.com

靳安钊 

西安电子科技大学硕士研究生.主要研究方向为最优化算法与应用.本文通信作者.E-mail:jinanzhao@stu.xidian.edu.cn