引用本文

刘漫丹. 一种新的启发式优化算法——五行环优化算法研究与分析. 自动化学报, 2020, 46(5): 957-970. doi: 10.16383/j.aas.c170657

LIU Man-Dan. Research and Analysis of a Novel Heuristic Algorithm: Five-elements Cycle Optimization Algorithm. ACTA AUTOMATICA SINICA, 2020, 46(5): 957-970. doi: 10.16383/j.aas.c170657

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

关键词

连续函数优化，五行环优化算法，启发式算法，标准测试函数 

摘要

借鉴中国古代哲学理论所描述的系统动态平衡方法, 提出了解决连续函数优化问题的五行环优化算法.首先, 分析了基于五行元素生克原理而建立的五行环模型, 并在该模型基础上, 构建了元素空间结构以及元素更新方法等关键环节, 从而实现了五行环优化算法.随后, 对五行环优化算法进行了性能分析和关键参数比较, 针对标准测试函数, 将五行环优化算法与其他17个机制各异的启发式优化算法进行了比较, 实验结果验证了五行环优化算法的有效性和通用性, 也表明了其在求解连续函数优化问题上具有较好的优化性能.

文章导读

优化问题是工程领域普遍存在且需要解决的问题.最优化方法运用数学方法实现多种搜索策略, 使目标函数达到最优.但是对于复杂工程问题, 由于受到计算时间、算法条件等因素的限制, 很难得到问题的最优解.启发式优化方法则基于问题的直观或先验知识设计各种搜索策略, 获取问题的满意解, 对于解决复杂工程优化问题具有实际意义.大多启发式优化方法源于自然系统、生物系统中一些现象的启示和提炼, 如模拟退火算法[1]、遗传算法[2]、蚁群优化算法[3]、粒子群优化算法[4], 以及各种新兴的群智能算法及其改进, 如人工蜂群算法[5]、萤火虫算法[6]、灰狼优化算法[7]、斑蝶优化算法[8]、鲸鱼优化算法[9]、花朵授粉算法[10]、斑鬣狗优化算法[11]等, 这些算法已成功应用于各应用领域[12], 解决了各种不同的优化问题.研究者们仍在不断寻求自然界中的隐喻机制, 以获取性能更佳的启发式优化方法.

中国古代哲学思想中的阴阳五行学说为人们提供了一种描述系统的方法, 这一学说试图以自然力量来解释自然现象, 代表了一种科学探索的倾向[13].阴阳五行学说将一个系统中的所有元素赋予阴、阳, 以及金、水、木、火、土的属性, 不同属性的元素之间具有不同的作用方式, 这些作用方式相互关联、相互竞争、相互协助, 从而使得系统具有动态平衡的特性, 系统的能量函数随时间变化, 最终达到最小.这一现象启示我们将这种作用方式进行抽象、提炼, 形成一种算法用来求解优化问题.已有一些研究者尝试着实现这个目标, Tam等[14]借鉴《易经》中六爻表示方法提出了AOC (Algorithm of changes)算法, 用于解决装箱问题; Zhao [15]提出了YYO (Yin-yang optimization)算法, 该算法通过平衡个体的阴、阳属性, 使其定义的和谐函数趋于0, 从而实现优化问题的求解; Cui等[16]提出了NFESA (Naïve five-element string algorithm)算法, 该算法借鉴五行相生原理, 采用五进制对个体进行编码, 并基于五进制基因型表达衍生出更多候选解, 从而提高搜索效率, 该算法用于求解连续函数优化问题; Punnathanam等[17]提出了YYPO (Yin-yang-pair optimizer)算法, 该算法基于种群空间中代表对立面阴和阳的两个解进行搜索, 这两个解分别表达了对搜索空间的空间探索性和局域挖掘, 通过分裂操作和存档操作, 实现空间探索与局域挖掘之间的平衡, 算法用于求解连续函数优化问题, 获得了满意的优化性能.

本文作者在文献[18]中提出了用于解决旅行商问题(TSP)的五行环优化算法(Five-elements cycle optimization, FECO), 文献[18]中首次提出了五行环模型(Five-elements cycle model, FECM), 五行环模型建立在五行相生相克原理的基础上, 通过计算个体之间的相互作用关系, 衡量出个体适应值的优劣, 随后根据个体的优劣进行解的更新, 通过迭代找出旅行商问题的最好解.本文在文献[18]和[19]的五行环模型基础上增加了权重系数, 并进行了模型的数值仿真和收敛性验证, 基于该五行环模型, 本文提出了新的解决连续函数优化问题的五行环优化算法, 通过对比实验验证算法的有效性.

图 1  五行元素的相生相克关系

图 5  FECO算法流程图

图 6  在不同迭代次数时的元素xij(k)的分布情况以及最小f(xij(k))的变化曲线

本文拓展并详细分析了基于五行元素生克原理的五行环模型, 基于该模型, 实现了用于求解连续函数优化问题的五行环优化算法(FECO), FECO算法将所有元素划分为若干个环, 每个环中的元素按照五行环模型计算相互之间的作用力, 再根据每个元素受到的作用力来决定元素的更新方式, 经过一定次数的迭代运算后, 获得问题的最优解.通过算法性能分析、参数比较实验, 以及与其他17个启发式算法的比较实验, 验证了FECO算法可以较好地解决连续函数优化问题.

FECO算法作为一种新算法, 在以下方面可以有进一步改进的可能性: 1)五行元素之间的相互作用, 除了相生、相克之外, 还有相乘、相侮等方式, 如将这些作用考虑进去, 可以对五行环模型进一步地改进或完善; 2) FECO算法的关键环节可以有更多实现方式, 例如在种群结构方面, 可以设置多重环嵌套的结构; 在元素的更新方面, 也可以寻找更好的算子来实现; 3) FECO算法除了解决TSP问题外, 还可以进一步研究, 解决更多组合优化问题; 4)可将FECO算法与其他算法结合, 尝试获得更好的优化性能.

作者简介

刘漫丹

华东理工大学信息科学与工程学院自动化系教授. 2000年获得浙江大学控制理论与控制工程博士学位.主要研究方向为工业过程建模与优化, 智能优化算法及其应用. E-mail: liumandan@ecust.edu.cn