论文部分内容阅读
摘 要：在花朵授粉算法的优化过程中，由于问题本身的局部极小性和复杂性，收敛精度不稳定，为了解决这一问题，本文提出一种新的混合花朵授粉算法，该算法引入Logistic映射，在局部寻优和全局搜索的过程中，周期性添加新的花朵个体，增加原有算法的种群多样性，有助于算法跳出局部极值。将该混合花朵授粉算法在函数优化中与原有基本算法进行仿真对比，结果表明其在收敛精度方面优于原有算法。
关键词：花朵授粉算法;Logistic映射;函数优化;全局最优值
中图分类号：TP301.6 文献标识码：A 文章编号：2096-4706（2019）10-0005-04
Abstract：In the optimization process of the flower pollinate algorithm，the convergence accuracy is unstable because of the local minimum and complexity of the problem itself. In order to solve this problem，this paper proposes a new mixed flower pollinate algorithm. The Logistic mapping is integrated into the algorithm to add periodically new flower individuals. And then，the new flower pollinate algorithm can increase the population diversity in the process of local optimization and global search. In the function optimization simulation process，compared with the original flower pollinate algorithm，the convergence accuracy of this new flower pollinate algorithm has obvious advantages.
Keywords：flower pollinate algorithm（FPA）;Logistic mapping;function optimization;global optimum
0 引 言
花朵授粉算法（Flower Pollinate Algorithm，FPA）是2012年由英国剑桥大学学者Yang提出的一种新颖的寻求全局优化的新方法，其思想来源于自然界中花朵授粉过程，是一种新型的元启发式群智能优化算法。目前，该算法成为群智能优化领域的一个新的研究热点，已经在特征选择[1]、太阳能最大功率点跟踪[2]以及求解无线传感器网络区域范围最大化[3]等方面得到了广泛应用。该算法具有实现简单、参数设定较少、收敛速度快和收敛精度高等优点，但也存在一些问题，和大部分群智能优化算法相似，对于一些复杂的优化求解问题，该算法仍存在收敛速度较低、易陷入局部极值的问题。混沌变量具有随机性、遍历性、规律性等特点[4]，能在一定范围内不重复地遍历所有状态[5]，有助于算法跳出局部极小点，加快收敛速度，基于此思想的各种混沌优化算法不断被提出[6]，取得了较好的效果。受此启发，本文提出一种基于混沌理论的花朵授粉算法，在算法局部寻优和全局搜索的过程中引入混沌变量，周期性添加新的花朵个体，增加原有算法的种群多样性。然后通过三个测试函数进行验证，结果表明，算法有效地避免了陷入局部极小点等缺点，提高了算法的收敛速度和寻优精度。
1 基本概念
1.1 花朵授粉算法
FPA模拟了大自然界中有花植物的授粉行为，花朵授粉行为分为异花授粉和自花授粉。其中，异花授粉行为是指通过昆虫或鸟类进行的远距离的花朵之间的授粉行为，在算法中被视为全局寻优;自花授粉行为是指花粉颗粒传播到自身花朵上的近距离授粉行为，在算法中被视为局部寻优。为了平衡两种搜索过程间的转换，算法利用一个转换因子p∈[0，1]来协调两种过程转换的概率。算法为了更好地模拟有花植物的授粉过程，还需假定如下规则成立[7]。
（1）植物异花授粉被近似视为全局授粉过程，传粉媒介遵循Lévy模式飞行;
（2）植物自花授粉被近似视为局部授粉过程;
（3）花的常性被看作一种繁衍概率，概率值的大小与相邻两朵花的相似性成一定的比例;
（4）异花授粉与自花授粉行为的转换受概率因子p∈[0，1]控制。
以上四条规则转换为相应的数学公式描述如下。
在算法的全局授粉阶段，传粉媒介以Lévy模式飞行的机制進行远范围的传播，可以通过式（1）进行描述：
其中，和分别为花粉xi在t+1和t时刻的位置，g*表示当前种群的最优解。L为控制参数，是服从Lévy模式飞行机制的随机步长，其计算公式如下：
其中，Г=（λ）是gamma函数，多次验证λ=1.5为最优值[8]。
在算法的局部授粉阶段，花粉xi在t时刻的位置为，则其t+1时刻的更新方程表示为：
规则（4）中的转换概率因子，经过大量实验证明p=0.8最为合适。FPA的具体步骤如下：
初始化参数N、p、itermax，分别为算法的种群规模、全局授粉和局部授粉的转换概率因子以及算法的最大迭代次数。初始化种群的g*取值;
while（t if rand>p依据式（3）局部搜索
else 依据式（1）（2）全局搜索
end if
if f（）优于f（），则替换为新解位置，否则放弃;
end for
if f（xnew） end while
1.2 混沌技术
混沌是自然界非线性系统的一种演变现象，其变化过程虽然看似混乱，但却是由具有规律性的规则产生的无固定周期的长期行为[9]。在混沌优化过程中，通常采用Logisitc映射规则，其系统方程为[10]：
2 改进的花朵授粉混合优化算法
鉴于FPA算法本身不具有遍历特性，对于一些复杂的优化问题，通常存在最优解的邻域范围较小，或者最优解被局部极值包围等现象，FPA往往会陷入局部极值，很难获取最优信息[12]。
为了提高算法的寻优能力，本文引入混沌极值，每个花朵个体不仅能够在其他花朵与当前种群最优值的引领下调整当前位置，还将进行混沌演化，使花朵授粉过程尽量遍历整个搜索区间，进而更好地改进种群极值，提高算法全局优化的能力。
再次针对式（4）表示的优化问题，改进的花朵授粉优化算法的主要步骤如下。
（1）种群初始化：给定群体规模N，最大迭代次数itermax，转换概率因子p，随机产生每个花朵个体初始位置xi，计算每个个体的适应值f（xi），经比较得出g*;
（2）将xi的各分量通过式（7）的变换，映射为混沌变量Cxi;
（3）各花朵依据转换概率因子p的取值，分别通过式（1）、式（3）调整个体到新位置xi，并计算适应值f（xi）;
（4）混沌变量Cxi的各分量经式（6）作混沌操作;
（5）经过混沌计算的各分量通过式（8）变换，映射为普通变量∈[ai，bi]，并计算f（）;
（6）比较f（xi）与f（），确定下一步迭代的g*;
（7）判断迭代次数是否等于最大迭代终止次数，若是，输出最优花粉值，否则，返回到步骤（2），继续运行。
3 实验结果与分析
为了验证本文改进算法的性能，将该算法应用在benchmark测试函数求解中，选取Sphere、Rosenbrock和Schaffer3个标准的、常用的测试函数。其中，Sphere与Rosenbrock为单峰基准函数，Schaffer为多峰基准函数，具体如下：
（1）Sphere函数：
-100≤xi≤100
其全局极小点和最优值为：
min（f（x*））=f（0，0，…，0）=0
（2）Rosenbrock函数：
-30≤xi≤30
其全局极小点和最优值为：
min（f（x*））=f（1，1，…，1）=0
（3）Schaffer函数：
-100≤xi≤100
其全局极小点和最优值为：
min（f（x*））=f（0，0，…，0）=0
基于上述3个优化函数，在MATLAB R2012软件环境下，每种算法独立运行50次，取平均值统计运行结果，并与基本FPA算法进行对比。统一算法参数：种群规模n为20，转移概率p为0.8，函数参数个数为4，最大迭代次数itermax为1000。表1-表3分别给出了3个函数采用基本FPA算法和本文算法50次独立运行的结果。
为了进一步比较FPA与本文算法的收敛趋势，在图1-图3中给出分别利用2种算法求解上述3个函数的平均进化曲线。
由图1-图3的进化曲线可以看出，本文提出的混合FPA算法比基本FPA算法在全局寻优方面具有更快的收敛速度和更高的精度，能够及时跳出局部极值，提高算法找到全局最优解的概率。
4 结 论
针对基本FPA算法在处理相对复杂的优化求解问题时，存在收敛速度降低、易陷入局部极值等问题，本文引入混沌理論对算法进行改进，从实验结果可以看出，本文算法的求解精度和收敛效果均优于基本FPA。在算法寻优的过程中引入混沌极值，有效地保证了花粉在整个迭代过程中的多样性，减少陷入局部极值的可能，使得算法加速收敛的同时有更高的概率搜索到全局最优解。由于FPA算法提出时间不长，有关算法的研究还较少，应用领域相对较窄，今后可以在算法参数研究和应用领域方面做进一步的深入研究。
参考文献：
[1] Douglas Rodrigues，YANG X S，André Nunes Souza，et al.Binary Flower Pollination Algorithm and Its Application to Feature Selection [M].Cham：Springer International Publishing，2015：85-100.
[2] J.Prasanth Ram，N.Rajasekar.A novel Flower Pollination based Global Maximum Point method for Solar Maximum Power Point Tracking [J].IEEE Transactions on Power Electronics，2016.
[3] Huynh Thi Thanh Binh，Nguyen Thi Hanh，La Quan，et al.Improved Cuckoo Search and Chaotic Flower Pollination optimization algorithm for maximizing area coverage in Wireless Sensor Networks [J].Neural Computing and Applications，2018，30（7）：2305-2317.
[4] 李兵，蒋慰孙.混沌优化方法及其应用 [J].控制理论与应用，1997（4）：613-615.
[5] 刘振军，杨迪雄.面向工程全局优化的混沌优化算法研究进展 [J].计算力学学报，2016，33（3）：269-286.
[6] 刘竹松，李生.正余混沌双弦鲸鱼优化算法 [J].计算机工程与应用，2018，54（7）：159-163+212.
[7] Yang X Sinshe.Flower pollination algorithm for global optimization.In：Proceedings of the 11th International Conference on Unconventional Computation and Natural Computation.Lecture Notes in Computer Science [J].Orléan，France：Springer，2012：240-249.
[8] Zheng Weijie，Fu Haohuan，Yang Guangwen.Targeted mutation：a novel mutation strategy for differential evolution [C]//Proc of the 27th International Conference on Tools with Artificial Intelligence，2015：286-293.
[9] 卢侃.混沌动力学 [M].上海：上海翻译出版公司，1990.
[10] 莫愿斌，陈德钊，胡上序.混沌粒子群算法及其在生化过程动态优化中的应用 [J].化工学报，2006（9）：2123-2127.
[11] 程慧，刘成忠.基于混沌映射的混合果蝇优化算法 [J].计算机工程，2013，39（5）：218-221.
[12] 王玉鑫，李东生，高杨.基于变异策略的改进型花朵授粉算法 [J].计算机应用研究，2017，34（12）：3594-3598.
作者简介：关心（1980-），女，汉族，辽宁人，讲师，博士，研究方向：智能计算、数据挖掘、人工智能。
关键词：花朵授粉算法;Logistic映射;函数优化;全局最优值
中图分类号：TP301.6 文献标识码：A 文章编号：2096-4706（2019）10-0005-04
Abstract：In the optimization process of the flower pollinate algorithm，the convergence accuracy is unstable because of the local minimum and complexity of the problem itself. In order to solve this problem，this paper proposes a new mixed flower pollinate algorithm. The Logistic mapping is integrated into the algorithm to add periodically new flower individuals. And then，the new flower pollinate algorithm can increase the population diversity in the process of local optimization and global search. In the function optimization simulation process，compared with the original flower pollinate algorithm，the convergence accuracy of this new flower pollinate algorithm has obvious advantages.
Keywords：flower pollinate algorithm（FPA）;Logistic mapping;function optimization;global optimum
0 引 言
花朵授粉算法（Flower Pollinate Algorithm，FPA）是2012年由英国剑桥大学学者Yang提出的一种新颖的寻求全局优化的新方法，其思想来源于自然界中花朵授粉过程，是一种新型的元启发式群智能优化算法。目前，该算法成为群智能优化领域的一个新的研究热点，已经在特征选择[1]、太阳能最大功率点跟踪[2]以及求解无线传感器网络区域范围最大化[3]等方面得到了广泛应用。该算法具有实现简单、参数设定较少、收敛速度快和收敛精度高等优点，但也存在一些问题，和大部分群智能优化算法相似，对于一些复杂的优化求解问题，该算法仍存在收敛速度较低、易陷入局部极值的问题。混沌变量具有随机性、遍历性、规律性等特点[4]，能在一定范围内不重复地遍历所有状态[5]，有助于算法跳出局部极小点，加快收敛速度，基于此思想的各种混沌优化算法不断被提出[6]，取得了较好的效果。受此启发，本文提出一种基于混沌理论的花朵授粉算法，在算法局部寻优和全局搜索的过程中引入混沌变量，周期性添加新的花朵个体，增加原有算法的种群多样性。然后通过三个测试函数进行验证，结果表明，算法有效地避免了陷入局部极小点等缺点，提高了算法的收敛速度和寻优精度。
1 基本概念
1.1 花朵授粉算法
FPA模拟了大自然界中有花植物的授粉行为，花朵授粉行为分为异花授粉和自花授粉。其中，异花授粉行为是指通过昆虫或鸟类进行的远距离的花朵之间的授粉行为，在算法中被视为全局寻优;自花授粉行为是指花粉颗粒传播到自身花朵上的近距离授粉行为，在算法中被视为局部寻优。为了平衡两种搜索过程间的转换，算法利用一个转换因子p∈[0，1]来协调两种过程转换的概率。算法为了更好地模拟有花植物的授粉过程，还需假定如下规则成立[7]。
（1）植物异花授粉被近似视为全局授粉过程，传粉媒介遵循Lévy模式飞行;
（2）植物自花授粉被近似视为局部授粉过程;
（3）花的常性被看作一种繁衍概率，概率值的大小与相邻两朵花的相似性成一定的比例;
（4）异花授粉与自花授粉行为的转换受概率因子p∈[0，1]控制。
以上四条规则转换为相应的数学公式描述如下。
在算法的全局授粉阶段，传粉媒介以Lévy模式飞行的机制進行远范围的传播，可以通过式（1）进行描述：
其中，和分别为花粉xi在t+1和t时刻的位置，g*表示当前种群的最优解。L为控制参数，是服从Lévy模式飞行机制的随机步长，其计算公式如下：
其中，Г=（λ）是gamma函数，多次验证λ=1.5为最优值[8]。
在算法的局部授粉阶段，花粉xi在t时刻的位置为，则其t+1时刻的更新方程表示为：
规则（4）中的转换概率因子，经过大量实验证明p=0.8最为合适。FPA的具体步骤如下：
初始化参数N、p、itermax，分别为算法的种群规模、全局授粉和局部授粉的转换概率因子以及算法的最大迭代次数。初始化种群的g*取值;
while（t
else 依据式（1）（2）全局搜索
end if
if f（）优于f（），则替换为新解位置，否则放弃;
end for
if f（xnew）
1.2 混沌技术
混沌是自然界非线性系统的一种演变现象，其变化过程虽然看似混乱，但却是由具有规律性的规则产生的无固定周期的长期行为[9]。在混沌优化过程中，通常采用Logisitc映射规则，其系统方程为[10]：
2 改进的花朵授粉混合优化算法
鉴于FPA算法本身不具有遍历特性，对于一些复杂的优化问题，通常存在最优解的邻域范围较小，或者最优解被局部极值包围等现象，FPA往往会陷入局部极值，很难获取最优信息[12]。
为了提高算法的寻优能力，本文引入混沌极值，每个花朵个体不仅能够在其他花朵与当前种群最优值的引领下调整当前位置，还将进行混沌演化，使花朵授粉过程尽量遍历整个搜索区间，进而更好地改进种群极值，提高算法全局优化的能力。
再次针对式（4）表示的优化问题，改进的花朵授粉优化算法的主要步骤如下。
（1）种群初始化：给定群体规模N，最大迭代次数itermax，转换概率因子p，随机产生每个花朵个体初始位置xi，计算每个个体的适应值f（xi），经比较得出g*;
（2）将xi的各分量通过式（7）的变换，映射为混沌变量Cxi;
（3）各花朵依据转换概率因子p的取值，分别通过式（1）、式（3）调整个体到新位置xi，并计算适应值f（xi）;
（4）混沌变量Cxi的各分量经式（6）作混沌操作;
（5）经过混沌计算的各分量通过式（8）变换，映射为普通变量∈[ai，bi]，并计算f（）;
（6）比较f（xi）与f（），确定下一步迭代的g*;
（7）判断迭代次数是否等于最大迭代终止次数，若是，输出最优花粉值，否则，返回到步骤（2），继续运行。
3 实验结果与分析
为了验证本文改进算法的性能，将该算法应用在benchmark测试函数求解中，选取Sphere、Rosenbrock和Schaffer3个标准的、常用的测试函数。其中，Sphere与Rosenbrock为单峰基准函数，Schaffer为多峰基准函数，具体如下：
（1）Sphere函数：
-100≤xi≤100
其全局极小点和最优值为：
min（f（x*））=f（0，0，…，0）=0
（2）Rosenbrock函数：
-30≤xi≤30
其全局极小点和最优值为：
min（f（x*））=f（1，1，…，1）=0
（3）Schaffer函数：
-100≤xi≤100
其全局极小点和最优值为：
min（f（x*））=f（0，0，…，0）=0
基于上述3个优化函数，在MATLAB R2012软件环境下，每种算法独立运行50次，取平均值统计运行结果，并与基本FPA算法进行对比。统一算法参数：种群规模n为20，转移概率p为0.8，函数参数个数为4，最大迭代次数itermax为1000。表1-表3分别给出了3个函数采用基本FPA算法和本文算法50次独立运行的结果。
为了进一步比较FPA与本文算法的收敛趋势，在图1-图3中给出分别利用2种算法求解上述3个函数的平均进化曲线。
由图1-图3的进化曲线可以看出，本文提出的混合FPA算法比基本FPA算法在全局寻优方面具有更快的收敛速度和更高的精度，能够及时跳出局部极值，提高算法找到全局最优解的概率。
4 结 论
针对基本FPA算法在处理相对复杂的优化求解问题时，存在收敛速度降低、易陷入局部极值等问题，本文引入混沌理論对算法进行改进，从实验结果可以看出，本文算法的求解精度和收敛效果均优于基本FPA。在算法寻优的过程中引入混沌极值，有效地保证了花粉在整个迭代过程中的多样性，减少陷入局部极值的可能，使得算法加速收敛的同时有更高的概率搜索到全局最优解。由于FPA算法提出时间不长，有关算法的研究还较少，应用领域相对较窄，今后可以在算法参数研究和应用领域方面做进一步的深入研究。
参考文献：
[1] Douglas Rodrigues，YANG X S，André Nunes Souza，et al.Binary Flower Pollination Algorithm and Its Application to Feature Selection [M].Cham：Springer International Publishing，2015：85-100.
[2] J.Prasanth Ram，N.Rajasekar.A novel Flower Pollination based Global Maximum Point method for Solar Maximum Power Point Tracking [J].IEEE Transactions on Power Electronics，2016.
[3] Huynh Thi Thanh Binh，Nguyen Thi Hanh，La Quan，et al.Improved Cuckoo Search and Chaotic Flower Pollination optimization algorithm for maximizing area coverage in Wireless Sensor Networks [J].Neural Computing and Applications，2018，30（7）：2305-2317.
[4] 李兵，蒋慰孙.混沌优化方法及其应用 [J].控制理论与应用，1997（4）：613-615.
[5] 刘振军，杨迪雄.面向工程全局优化的混沌优化算法研究进展 [J].计算力学学报，2016，33（3）：269-286.
[6] 刘竹松，李生.正余混沌双弦鲸鱼优化算法 [J].计算机工程与应用，2018，54（7）：159-163+212.
[7] Yang X Sinshe.Flower pollination algorithm for global optimization.In：Proceedings of the 11th International Conference on Unconventional Computation and Natural Computation.Lecture Notes in Computer Science [J].Orléan，France：Springer，2012：240-249.
[8] Zheng Weijie，Fu Haohuan，Yang Guangwen.Targeted mutation：a novel mutation strategy for differential evolution [C]//Proc of the 27th International Conference on Tools with Artificial Intelligence，2015：286-293.
[9] 卢侃.混沌动力学 [M].上海：上海翻译出版公司，1990.
[10] 莫愿斌，陈德钊，胡上序.混沌粒子群算法及其在生化过程动态优化中的应用 [J].化工学报，2006（9）：2123-2127.
[11] 程慧，刘成忠.基于混沌映射的混合果蝇优化算法 [J].计算机工程，2013，39（5）：218-221.
[12] 王玉鑫，李东生，高杨.基于变异策略的改进型花朵授粉算法 [J].计算机应用研究，2017，34（12）：3594-3598.
作者简介：关心（1980-），女，汉族，辽宁人，讲师，博士，研究方向：智能计算、数据挖掘、人工智能。