引用本文

董易, 施心陵, 王霞, 王耀民, 吕丹桔, 张松海, 李孙寸. 斐波那契树优化算法求解多峰函数全局最优解的可达性分析. 自动化学报, 2018, 44(9): 1679-1689. doi: 10.16383/j.aas.2017.c160703

DONG Yi, SHI Xin-Ling, WANG Xia, WANG Yao-Min, LV Dan-Ju, ZHANG Song-Hai, LI Sun-Cun. On Accessibility of Fibonacci Tree Optimization Algorithm for Global Optima of Multi-modal Functions. ACTA AUTOMATICA SINICA, 2018, 44(9): 1679-1689. doi: 10.16383/j.aas.2017.c160703

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

关键词

斐波那契树优化算法，可达性，多峰函数优化，全局最优解 

摘要

为分析和验证斐波那契树优化算法（Fibonacci tree optimization algorithm，FTO）求解多峰函数全局最优解的算法性能，对算法的可达性问题进行研究.本文基于斐波那契法构造一个斐波那契树结构，在搜索空间中进行全局、局部交替搜索，不易陷入局部最优解.对斐波那契树优化算法基于该结构的可达性进行分析和证明.通过跟踪算法求解过程中坐标点的累积分布仿真实验和到达率的对比实验，分析和验证了算法求解多峰函数全局最优解的可达性.

文章导读

经典的智能优化算法在求解多峰函数全局最优解时, 存在易陷入局部最优解的早熟收敛问题[1-3].例如作为典型代表的遗传算法(Genetic algorithm, GA)[4-5]和粒子群算法(Particle swarm optimization, PSO)[6-9].因此, 算法求解全局最优解的可达性是一项重要的评价指标.对GA算法的理论研究表明其单点交叉运算只是在已有空间的一个特定局部上做非均匀搜索, 对于搜索空间是非均匀可达的, 而且不是全空间可达的[10]; 而对于变异运算, 可达性的下降与染色体长度的增加几乎呈线性关系[11].对PSO的拓扑结构分析表明最优的粒子数量的增长不严格依赖于有效计算量的增长[12].这一结论反应出在相同的计算参数配置下, PSO对于多峰函数全局最优解的求解能力是受限的.对PSO粒子轨迹在离散和连续时间上的模型分析表明, 对于求解多峰函数等较复杂的测试函数, 并不需要制定针对性的参数设置, 最重要的影响是粒子之间的交互性[13].对PSO算法的交互性和随机性分析表明, 对于多峰函数的优化, PSO算法能依概率收敛到群体最优位置, 但无法保证对全局最优解可达[14].一种结合演化博弈理论的PSO改进算法[15], 从理论上保证了收敛性并提高了收敛速度, 但对于多峰函数的搜索性能并未进行验证.

为解决求解多峰函数全局最优解时存在的早熟收敛问题, 本文基于斐波那契法的思想, 在n 维欧氏空间中构造一个斐波那契树结构.每次迭代都生成全局随机点, 在搜索空间中进行全局、局部交替搜索.使得斐波那契树优化算法在求解多峰函数全局最优解时, 不易陷入局部最优解, 具有良好的可达性指标.

本文首先简要介绍斐波那契法, 然后详细说明斐波那契树的生成规则和斐波那契树优化算法流程, 分析和证明斐波那契树优化算法的可达性.通过两个实验来分析和验证斐波那契树优化算法求解多峰函数全局最优解的可达性: 1)跟踪算法求解过程中坐标点的累积分布仿真实验; 2)独立重复求解实验, 计算到达率, 并对算法收敛曲线进行分析.

图 1  FTO算法基本结构

图 2  斐波那契树生成过程示意图

图 3  FTO算法流程图

本文描述了FTO算法的基本结构和斐波那契树的生成规则, 证明了FTO算法是以概率1全局最优解可达的.对于求解多峰函数全局最优解的优化问题, FTO算法不易陷入局部最优解.通过跟踪解坐标累积分布的可达性仿真实验, 验证了FTO算法的可达性.通过50次独立重复求解8个多峰函数的对比实验, 计算算法的到达率, 与GA, PSO和CLPSO算法进行对比, 并对一组收敛曲线进行分析, 验证了FTO算法全局最优解的可达性.

作者简介

施心陵

云南大学信息学院教授.主要研究方向为智能优化算法, 自适应信号处理与信息系统, 医学电子学.E-mail:xlshi@ynu.edu.cn

王霞 

云南大学信息学院博士研究生.2010年获得中南大学物理科学与技术学院硕士学位.主要研究方向为智能优化算法.E-mail:wangxiacsu@163.com

王耀民 

云南大学信息学院博士研究生.2013年获得南京邮电大学通信与信息工程学院硕士学位.主要研究方向为智能优化算法.E-mail:18988081898@189.cn

吕丹桔 

云南大学信息学院博士研究生.2013年获得云南大学信息学院硕士学位.主要研究方向为智能林业信息处理.E-mail:lvdanjv@hotmail.com

张松海

云南大学信息学硕士研究生.主要研究方向为智能优化算法.E-mail:hai_zs@sina.com

李孙寸 

云南大学信息学院硕士研究生.主要研究方向为智能优化算法.E-mail:lisuncun@outlook.com

董易 

云南大学信息学院博士研究生.2009年获得云南大学信息学院硕士学位.主要研究方向为智能优化算法.本文通信作者.E-mail:yeo003@163.com