混合蛙跳算法改进及控制参数优化仿真研究
|
摘要
2000年提出的混合蛙跳算法是一种新的智能优化算法,它的基本思想来源于文化基因传承,其显著特点是具有局部搜索与全局信息混合的协同搜索策略。经过大量仿真测试表明,解决高维、病态、多局部极值等函数问题混合蛙跳算法具有优越性,是一种行之有效的优化技术。
本文从基本混合蛙跳算法的原理、步骤以及参数选择对算法的影响等方面出发,通过多个具有典型特征的无约束基准测试函数对混合蛙跳算法进行仿真测试,并与粒子群算法、遗传算法两经典算法对比,来考查算法的优化性能。
混合蛙跳算法虽然具有易理解,参数少等优点,但是存在不易跳出局部最优,收敛速度慢等问题。针对这些不足,本文对算法提出三种改进思想:
首先设计了两种基于算法局部搜索策略的改进算法。一种是利用种群最优个体和局部最优个体二者以一定的随机比例同时影响文化基因体中的最差青蛙个体,建立新的个体进化公式,来更新最差个体位置。另一种针对局部搜索的每次独立进化同时更新几个适应度较差的个体,使文化基因体整体快速的到达最优位置。这两种算法均针对局部搜索部分的单一进化给予改进,仿真结果表明,两种改进策略提高了算法的求解速度,有效性也有所加强。
然后将量子算法与混合蛙跳算法相结合,提出了量子蛙跳算法。它用量子位的概率幅构造青蛙个体,量子旋转门改变量子比特的相位以更新个体,量子非门对种群最优个体进行变异,最终实现寻优。经过测试认为它的收敛速度快,求解成功率高,有效性好。
为了验证量子蛙跳算法和基本混合蛙跳算法在控制工程领域的优化性能,用它们解决PID控制器参数整定和模糊控制器参数优化问题。通过与粒子群算法、遗传算法的仿真结果对比,认为量子蛙跳算法在控制领域的应用具有让人满意的表现。
Shuffled Frog Leaping Algorithm which proposed on the 2000-year, is a new kindof intelligent optimization algorithm. Its basic idea comes from the cultural geneticinheritance and its notable feature is a collaborative search strategy that is a mixture oflocal search and global information. Lots of simulation tests show that, Shuffled FrogLeaping Algorithm is a superlative and effective optimization technology when thefunction is high-dimension, sick, and more local optimum.
The paper describes the principles of the algorithm, steps, and key parameters,verifies the algorithm by use of the typical characteristics of unconstrained testfunction, and compares advantageously with particle swarm algorithm and geneticalgorithms.
Shuffled frog leaping algorithm, while having the advantages of easy tounderstand and fewer parameters, is not easy to jump out of local optimum, andconverges slowly. So three improved methods are proposed:
Firstly, two improved algorithms based on the local search strategy are designedin the paper. One is using of the optimal crop individual and local population, bothaffect the worst frog genome individual at a certain proportion, the individualevolution formula is established and updates the worst individual location. The other,some poor fitness individuals are updated by use of independent evolution of localsearch. Two algorithms both improve against the single evolutionary of the localsearch part. The simulation results show that the two strategies improve the algorithmsolution speed. Certainly, the effectiveness has also been strengthened.
Then, combined with the quantum algorithm and shuffled frog leaping algorithm,the quantum leapfrog algorithm is proposed. It uses the probability of the quantum bitto structure the frog individual, the revolving door changes quantum bit phase toupdate the individual, the quantum NOT gate to verify the optimal individual, andultimately achieve the optimization. It has a high convergence speed, a high solvingsuccess rate and good effectiveness.
To verify the capability of the quantum leapfrog algorithm and the basic mixedleapfrog algorithm to optimize the control engineering problems, the paper use them to tuning PID controller parameter and optimize fuzzy controller parameters. Comparedwith particle swarm optimization and genetic algorithms simulation results, thequantum leapfrog algorithm has satisfactory performance in control engineering field.
本文从基本混合蛙跳算法的原理、步骤以及参数选择对算法的影响等方面出发,通过多个具有典型特征的无约束基准测试函数对混合蛙跳算法进行仿真测试,并与粒子群算法、遗传算法两经典算法对比,来考查算法的优化性能。
混合蛙跳算法虽然具有易理解,参数少等优点,但是存在不易跳出局部最优,收敛速度慢等问题。针对这些不足,本文对算法提出三种改进思想:
首先设计了两种基于算法局部搜索策略的改进算法。一种是利用种群最优个体和局部最优个体二者以一定的随机比例同时影响文化基因体中的最差青蛙个体,建立新的个体进化公式,来更新最差个体位置。另一种针对局部搜索的每次独立进化同时更新几个适应度较差的个体,使文化基因体整体快速的到达最优位置。这两种算法均针对局部搜索部分的单一进化给予改进,仿真结果表明,两种改进策略提高了算法的求解速度,有效性也有所加强。
然后将量子算法与混合蛙跳算法相结合,提出了量子蛙跳算法。它用量子位的概率幅构造青蛙个体,量子旋转门改变量子比特的相位以更新个体,量子非门对种群最优个体进行变异,最终实现寻优。经过测试认为它的收敛速度快,求解成功率高,有效性好。
为了验证量子蛙跳算法和基本混合蛙跳算法在控制工程领域的优化性能,用它们解决PID控制器参数整定和模糊控制器参数优化问题。通过与粒子群算法、遗传算法的仿真结果对比,认为量子蛙跳算法在控制领域的应用具有让人满意的表现。
Shuffled Frog Leaping Algorithm which proposed on the 2000-year, is a new kindof intelligent optimization algorithm. Its basic idea comes from the cultural geneticinheritance and its notable feature is a collaborative search strategy that is a mixture oflocal search and global information. Lots of simulation tests show that, Shuffled FrogLeaping Algorithm is a superlative and effective optimization technology when thefunction is high-dimension, sick, and more local optimum.
The paper describes the principles of the algorithm, steps, and key parameters,verifies the algorithm by use of the typical characteristics of unconstrained testfunction, and compares advantageously with particle swarm algorithm and geneticalgorithms.
Shuffled frog leaping algorithm, while having the advantages of easy tounderstand and fewer parameters, is not easy to jump out of local optimum, andconverges slowly. So three improved methods are proposed:
Firstly, two improved algorithms based on the local search strategy are designedin the paper. One is using of the optimal crop individual and local population, bothaffect the worst frog genome individual at a certain proportion, the individualevolution formula is established and updates the worst individual location. The other,some poor fitness individuals are updated by use of independent evolution of localsearch. Two algorithms both improve against the single evolutionary of the localsearch part. The simulation results show that the two strategies improve the algorithmsolution speed. Certainly, the effectiveness has also been strengthened.
Then, combined with the quantum algorithm and shuffled frog leaping algorithm,the quantum leapfrog algorithm is proposed. It uses the probability of the quantum bitto structure the frog individual, the revolving door changes quantum bit phase toupdate the individual, the quantum NOT gate to verify the optimal individual, andultimately achieve the optimization. It has a high convergence speed, a high solvingsuccess rate and good effectiveness.
To verify the capability of the quantum leapfrog algorithm and the basic mixedleapfrog algorithm to optimize the control engineering problems, the paper use them to tuning PID controller parameter and optimize fuzzy controller parameters. Comparedwith particle swarm optimization and genetic algorithms simulation results, thequantum leapfrog algorithm has satisfactory performance in control engineering field.
引文
[1]王凌,刘波.微粒群优化与调度算法[M].清华大学出版社, 2008.
[2] Holland, J.H. Adaptation in Natural and Artificial Systems, lst ed. 1975,2nd ed.Cambridge, MA: MIT press,1992.
[3]席裕庚,柴天佑,恽为民.遗传算法综述.控制理论与应用[J]. 1996,13(6)：697-708.
[4] Glover F. Heuristics for integer programming using surrogate constraints[J].Decision Science, 1977,8(1): 156-166.
[5] Kirkpatrick S, Gelatt C, Vecchi P. Optimization by simulated annealing[J].Science,1983,220:671-679.
[6] Kennedy J, Eberhart R. Particle swarm optimization [C]. Proceedings of IEEEInter- national Conference on Neural Networks, Piscataway, 1995: 1942-1948.
[7] Colorni A,Dorigo M,Maniezzo V.Distributed Optimization by Ant Colonies[C].In: The First European conference on Artificial Life. France: Elsevier, 1991:134-142．
[9] M. Eusuff , K. Lansey. Optimization of Water Distribution Network DesignUsing the Shuffled Frog Leaping Algorithm. JOURNAL OF WATERRESOURCES PLANNING AND MANAGEMENT-ASCE [J] . 2003, 129(3):210–225.
[10] Moscato P.On evolution, search, optimization, genetic algorithms and martialarts: toward memetic algorithms. Rep. 826, Pasadena, CA: California Inst.Techonl,1989.
[11] Elbeltagi E, Hegazy T, Grierson D.Comparison among five evolutionary-basedoptimization algorithms[J].Advanced Engineering Informatics,2005,19 (1)：43- 53.
[12]李英海,周建中,杨俊杰,等.一种基于阈值选择策略的改进混合蛙跳算法.计算机工程与应用[J]. 2007, (35): 19–21.
[13] M. Eusuff, K. Lansey, F. Pasha. Shuffled Frog-leaping Algorithm: A MemeticMetaheuristic for Discrete Optimization. ENGINEERING OPTIMIZATION[J].2006, 38(2):129–154.
[14] Elbeltagi Emad，Hegazy Tarek，Grierson Donald．A modified shuffledfrog-leaping optimization algorithm：Applications to project management[J]．Structure & Infras- tructure Engineering：Maintenance，Management，Life-Cycl，2007，3(1)：53-60．
[15]赵鹏军.一种新的仿生优化算法及其改进.商洛学院学报[J]. 2009,23(2):19-22.
[16]赵鹏军,刘三阳.求解复杂函数优化问题的混合蛙跳算法.计算机应用技术[J]. 2009, 26 (7):2435-2437.
[17]薛丽萍,尹俊勋等.混合粒子对优化算法在说话人识别中的应用.电子与信息学报[J]. 2009, 31(6):1359-1362.
[18]王亚敏,潘金科,冀俊忠.求解考试时间安排问题的离散蛙跳算法.计算机工程与应用[J]. 2009,45(36):40-46.
[19] J. Luo, M.-R. Chen, X. Li. A Novel Hybrid Algorithm for Global OptimizationBased on Eo and Sfla. ICIEA: 2009 4TH IEEE CONFERENCE ONINDUSTRIAL ELECTRONICS AND APPLICATIONS, VOLS 1-6[C]. 2009:1926–1930.
[20]岳克强,赵知劲,尚俊娜.基于改进蛙跳算法的盲均衡技术研究.信号处理[J]. 2009,8A: 348-352.
[21]岳克强,赵知劲,赵治栋.基于神经网络离散混合蛙跳算法的多用户检测.计算机工程[J]. 2009,35(19):184-186.
[22] A. Bhaduri. A Clonal Selection Based Shuffled Frog Leaping Algorithm [C].2009: 125–130.
[23]罗雪晖,杨烨,李霞.改进混合蛙跳算法求解旅行商问题.通信学报[J].2009,20(7): 130- 135.
[24] A. Rahimi-Vahed, M. Dangchi, H. Rafiei, et al. A Novel HybridMulti-objective Shuffled Frog- leaping Algorithm for a Bi-criteria PermutationFlow Shop Scheduling Problem. INTERNAT IONAL JOURNAL OFADVANCED MANUFACTURING TECHNOLOGY[J]. 2009, 41(11-12):1227–1239.
[25] Y. Li, J. Zhou, Y. Zhang, et al. Novel Multiobjective Shuffled Frog LeapingAlgorithm with App- lication to Reservoir Flood Control Operation.JOURNAL OF WATER RESOURCES PLANNING ANDMANAGEMENT-ASCE[J]. 2010, 136(2): 217–226.
[26]王柏,李芳花.基于免疫蛙跳算法优化的投影寻踪水质评价模型.中国农村水利水电[J]. 2010,5:5-7.
[27] Y.-C. Ho, D. Pepyne. Simple Explanation of the No Free Lunch Theorem ofOptimization.[C]. 2001: 4409–4414 vol.5, 5.
[28] Shie Y H, Atiquzzaman M. Optimal design of water distribution network usingshuffled complex evolution[J]. The institution of Engineers,2004,44(1):93-107.
[29]轩宗怡,张翠军.基于混合蛙跳算法的背包问题求解.科学技术与工程[J].2009,9(15): 4363-4365.
[30]李梁,陈建勋.基于二值图像的线检测法——蛙跳算法.计算机工程与设计[J]. 2009, 30(10):2477-2479.
[31] B. Amiri, M. Fathian, A. Maroosi. Application of Shuffled Frog-leapingAlgorithm on Clustering. INTERNATIONAL JOURNAL OF ADVANCEDMANUFACTURING TECHNOLOGY[J]. 2009, 45(1-2): 199–209.
[32] T.-H. Huynh. A Modified Shuffled Frog Leaping Algorithm for Optimal Tuningof Multivariable Pid Controllers. 2008 IEEE INTERNATIONALCONFERENCE ON INDUSTRIAL TECHNOLOGY, VOLS 1-5[C]. 2008:693–698.
[33] D.-H. Nguyen, T.-H. Huynh. A Sfla-based Fuzzy Controller for Balancing aBall and Beam System. 2008 10TH INTERNATIONAL CONFERENCE ONCONTROL AUTOMATION ROBOTICS & VISION: ICARV 2008, VOLS1-4[C]. 2008: 1948–1953.
[34]朱光宇,林蔚清.基于改进混合蛙跳算法的贴片机贴装顺序优化.中国工程机械学报[J]. 2008, (04): 428–432.
[35]吴丽华,汪玉春等.基于混合蛙跳算法的成品油管网优化设计.石油工程建设[J]. 2008, 34(1):14-16.
[36]陈功贵,李智欢等.含风电厂电力系统动态优化潮流的混合蛙跳算法.电力系统自动化[J]. 2009, 33(4):25-30.
[37]张逸达.混合蛙跳算法应用及仿真研究.哈尔滨工业大学本科论文.2010.
[38]刘漫丹.文化基因算法（memetic Algorithm）研究进展[J].自动化技术与应用,2007,11:1-4+18.
[39] Duan Q,Gupta V K,Sorooshian S.A shuffled complex evolution approach foreffective and efficient global minimization. Journal of Optimization Theoryand Applications,1993,76(3):501-521.
[40] Nunoo, Jolibois Jr Agyei. Oprimization of pavement preservationprogrammingusing shuffled complex evolution algorithm.TRB AnnualMeeting CD-ROM,2002:6-7.
[41] A.Carlisle,G.Dozier.An Off-the-shelf Pso[C]//Proceedings of the Workshop onParticle Swarm Optimization.Indianapolis,In:IUPUI,2001.
[42]李士勇,李盼池.量子计算与量子优化算法[M].哈尔滨工业大学出版社2008. 12-13.
[43] Narayanan A, Moore M. Quantum-inspired genetic algorithms[C]// Proceed.ings of IEEE International Conference on Evolutionary Computation, Nagoya,Japan, 1996:61-66.
[44] HAN K H, KIM J H. Genetic quantum algorithm and its application tocombinational optimization problem[C]//Proceedings of the internationalCongress on Evolutionary Computation. IEEE Press, 2000, 1354-1360.
[45]李士勇.模糊控制·神经控制和智能控制论[M]. 2版.哈尔滨：哈尔滨工业大学出版社，1998. 254-292.
[46]黄友锐.智能优化算法及其应用[M].北京：国防工业出版社，2008：44-45.
[2] Holland, J.H. Adaptation in Natural and Artificial Systems, lst ed. 1975,2nd ed.Cambridge, MA: MIT press,1992.
[3]席裕庚,柴天佑,恽为民.遗传算法综述.控制理论与应用[J]. 1996,13(6)：697-708.
[4] Glover F. Heuristics for integer programming using surrogate constraints[J].Decision Science, 1977,8(1): 156-166.
[5] Kirkpatrick S, Gelatt C, Vecchi P. Optimization by simulated annealing[J].Science,1983,220:671-679.
[6] Kennedy J, Eberhart R. Particle swarm optimization [C]. Proceedings of IEEEInter- national Conference on Neural Networks, Piscataway, 1995: 1942-1948.
[7] Colorni A,Dorigo M,Maniezzo V.Distributed Optimization by Ant Colonies[C].In: The First European conference on Artificial Life. France: Elsevier, 1991:134-142．
[9] M. Eusuff , K. Lansey. Optimization of Water Distribution Network DesignUsing the Shuffled Frog Leaping Algorithm. JOURNAL OF WATERRESOURCES PLANNING AND MANAGEMENT-ASCE [J] . 2003, 129(3):210–225.
[10] Moscato P.On evolution, search, optimization, genetic algorithms and martialarts: toward memetic algorithms. Rep. 826, Pasadena, CA: California Inst.Techonl,1989.
[11] Elbeltagi E, Hegazy T, Grierson D.Comparison among five evolutionary-basedoptimization algorithms[J].Advanced Engineering Informatics,2005,19 (1)：43- 53.
[12]李英海,周建中,杨俊杰,等.一种基于阈值选择策略的改进混合蛙跳算法.计算机工程与应用[J]. 2007, (35): 19–21.
[13] M. Eusuff, K. Lansey, F. Pasha. Shuffled Frog-leaping Algorithm: A MemeticMetaheuristic for Discrete Optimization. ENGINEERING OPTIMIZATION[J].2006, 38(2):129–154.
[14] Elbeltagi Emad，Hegazy Tarek，Grierson Donald．A modified shuffledfrog-leaping optimization algorithm：Applications to project management[J]．Structure & Infras- tructure Engineering：Maintenance，Management，Life-Cycl，2007，3(1)：53-60．
[15]赵鹏军.一种新的仿生优化算法及其改进.商洛学院学报[J]. 2009,23(2):19-22.
[16]赵鹏军,刘三阳.求解复杂函数优化问题的混合蛙跳算法.计算机应用技术[J]. 2009, 26 (7):2435-2437.
[17]薛丽萍,尹俊勋等.混合粒子对优化算法在说话人识别中的应用.电子与信息学报[J]. 2009, 31(6):1359-1362.
[18]王亚敏,潘金科,冀俊忠.求解考试时间安排问题的离散蛙跳算法.计算机工程与应用[J]. 2009,45(36):40-46.
[19] J. Luo, M.-R. Chen, X. Li. A Novel Hybrid Algorithm for Global OptimizationBased on Eo and Sfla. ICIEA: 2009 4TH IEEE CONFERENCE ONINDUSTRIAL ELECTRONICS AND APPLICATIONS, VOLS 1-6[C]. 2009:1926–1930.
[20]岳克强,赵知劲,尚俊娜.基于改进蛙跳算法的盲均衡技术研究.信号处理[J]. 2009,8A: 348-352.
[21]岳克强,赵知劲,赵治栋.基于神经网络离散混合蛙跳算法的多用户检测.计算机工程[J]. 2009,35(19):184-186.
[22] A. Bhaduri. A Clonal Selection Based Shuffled Frog Leaping Algorithm [C].2009: 125–130.
[23]罗雪晖,杨烨,李霞.改进混合蛙跳算法求解旅行商问题.通信学报[J].2009,20(7): 130- 135.
[24] A. Rahimi-Vahed, M. Dangchi, H. Rafiei, et al. A Novel HybridMulti-objective Shuffled Frog- leaping Algorithm for a Bi-criteria PermutationFlow Shop Scheduling Problem. INTERNAT IONAL JOURNAL OFADVANCED MANUFACTURING TECHNOLOGY[J]. 2009, 41(11-12):1227–1239.
[25] Y. Li, J. Zhou, Y. Zhang, et al. Novel Multiobjective Shuffled Frog LeapingAlgorithm with App- lication to Reservoir Flood Control Operation.JOURNAL OF WATER RESOURCES PLANNING ANDMANAGEMENT-ASCE[J]. 2010, 136(2): 217–226.
[26]王柏,李芳花.基于免疫蛙跳算法优化的投影寻踪水质评价模型.中国农村水利水电[J]. 2010,5:5-7.
[27] Y.-C. Ho, D. Pepyne. Simple Explanation of the No Free Lunch Theorem ofOptimization.[C]. 2001: 4409–4414 vol.5, 5.
[28] Shie Y H, Atiquzzaman M. Optimal design of water distribution network usingshuffled complex evolution[J]. The institution of Engineers,2004,44(1):93-107.
[29]轩宗怡,张翠军.基于混合蛙跳算法的背包问题求解.科学技术与工程[J].2009,9(15): 4363-4365.
[30]李梁,陈建勋.基于二值图像的线检测法——蛙跳算法.计算机工程与设计[J]. 2009, 30(10):2477-2479.
[31] B. Amiri, M. Fathian, A. Maroosi. Application of Shuffled Frog-leapingAlgorithm on Clustering. INTERNATIONAL JOURNAL OF ADVANCEDMANUFACTURING TECHNOLOGY[J]. 2009, 45(1-2): 199–209.
[32] T.-H. Huynh. A Modified Shuffled Frog Leaping Algorithm for Optimal Tuningof Multivariable Pid Controllers. 2008 IEEE INTERNATIONALCONFERENCE ON INDUSTRIAL TECHNOLOGY, VOLS 1-5[C]. 2008:693–698.
[33] D.-H. Nguyen, T.-H. Huynh. A Sfla-based Fuzzy Controller for Balancing aBall and Beam System. 2008 10TH INTERNATIONAL CONFERENCE ONCONTROL AUTOMATION ROBOTICS & VISION: ICARV 2008, VOLS1-4[C]. 2008: 1948–1953.
[34]朱光宇,林蔚清.基于改进混合蛙跳算法的贴片机贴装顺序优化.中国工程机械学报[J]. 2008, (04): 428–432.
[35]吴丽华,汪玉春等.基于混合蛙跳算法的成品油管网优化设计.石油工程建设[J]. 2008, 34(1):14-16.
[36]陈功贵,李智欢等.含风电厂电力系统动态优化潮流的混合蛙跳算法.电力系统自动化[J]. 2009, 33(4):25-30.
[37]张逸达.混合蛙跳算法应用及仿真研究.哈尔滨工业大学本科论文.2010.
[38]刘漫丹.文化基因算法（memetic Algorithm）研究进展[J].自动化技术与应用,2007,11:1-4+18.
[39] Duan Q,Gupta V K,Sorooshian S.A shuffled complex evolution approach foreffective and efficient global minimization. Journal of Optimization Theoryand Applications,1993,76(3):501-521.
[40] Nunoo, Jolibois Jr Agyei. Oprimization of pavement preservationprogrammingusing shuffled complex evolution algorithm.TRB AnnualMeeting CD-ROM,2002:6-7.
[41] A.Carlisle,G.Dozier.An Off-the-shelf Pso[C]//Proceedings of the Workshop onParticle Swarm Optimization.Indianapolis,In:IUPUI,2001.
[42]李士勇,李盼池.量子计算与量子优化算法[M].哈尔滨工业大学出版社2008. 12-13.
[43] Narayanan A, Moore M. Quantum-inspired genetic algorithms[C]// Proceed.ings of IEEE International Conference on Evolutionary Computation, Nagoya,Japan, 1996:61-66.
[44] HAN K H, KIM J H. Genetic quantum algorithm and its application tocombinational optimization problem[C]//Proceedings of the internationalCongress on Evolutionary Computation. IEEE Press, 2000, 1354-1360.
[45]李士勇.模糊控制·神经控制和智能控制论[M]. 2版.哈尔滨：哈尔滨工业大学出版社，1998. 254-292.
[46]黄友锐.智能优化算法及其应用[M].北京：国防工业出版社，2008：44-45.