实数编码量子共生演算法及其在云任务调度中的应用
|
摘要
针对共生演算法收敛慢和易陷入局部最优的问题,结合量子遗传算法理论,提出一种实数编码的量子共生演算法(real-coded quantum symbiotic organisms search,RQSOS)。首先依据三角模糊数提出差异度概念,并依此构造一个以自变量向量的分量和一对概率幅为等位基因的三倍染色体,使一条染色体携带更多信息并增强解的多样性;然后提出一种基于阿基米德螺旋线的探索学习模式,加强对解空间的探索精度;最后使用共生演算法更新差异度值并依据差异度值对种群进行学习和变异操作,促使整个种群快速向最优方向进化且减小了陷入局部最优的概率。利用数值优化问题和云任务调度问题对算法进行验证,仿真结果表明,RQSOS算法在收敛速度和寻优能力上均有明显提升,是一种可行有效的算法。
In order to solve the problem that symbiotic organisms search algorithm converge slowly and easy to fall into the local optimum,combining quantum genetic algorithm theory,this paper proposed a real-coded quantum symbiotic organisms search algorithm( RQSOS). First,this paper presented the concept of the difference degree based on the principle of triangular fuzzy number,and constructed a variable component vector and a pair of probability amplitude of a allele in a chromosome that could carry more information and enhance the diversity of the solutions. Then it proposed the mode of rotary learning based on the Archimedes spiral,which strengthened the exploration ability of the solution space. Finally it updated the difference degree based on SOS,and carried out the population learning and mutation operations based on the value of the difference degree which could make the whole population evolution rapidly towards the optimal direction and reduced the probability of falling into local optimum. It was verified by numerical optimization and cloud task scheduling problem,and the simulation results show that the RQSOS algorithm can significantly improve the convergence speed and optimization ability,which is a feasible and effective algorithm.
In order to solve the problem that symbiotic organisms search algorithm converge slowly and easy to fall into the local optimum,combining quantum genetic algorithm theory,this paper proposed a real-coded quantum symbiotic organisms search algorithm( RQSOS). First,this paper presented the concept of the difference degree based on the principle of triangular fuzzy number,and constructed a variable component vector and a pair of probability amplitude of a allele in a chromosome that could carry more information and enhance the diversity of the solutions. Then it proposed the mode of rotary learning based on the Archimedes spiral,which strengthened the exploration ability of the solution space. Finally it updated the difference degree based on SOS,and carried out the population learning and mutation operations based on the value of the difference degree which could make the whole population evolution rapidly towards the optimal direction and reduced the probability of falling into local optimum. It was verified by numerical optimization and cloud task scheduling problem,and the simulation results show that the RQSOS algorithm can significantly improve the convergence speed and optimization ability,which is a feasible and effective algorithm.
引文
[1] Narayanan A,Moore M. Quantum-inspired genetic algorithm[C]//Proc of IEEE International Conference on Evolutionary Computation.Piscataway,NJ:IEEE Press,1996:61-66.
[2] Han K H,Jong H K. Quantum-inspired evolutionary algorithm for aclass of combination optimization[J]. IEEE Trans on EvolutionaryComputation,2002,6(6):580-593.
[3] Yang Shuyuan,Jiao Licheng. The quantum evolutionary programming[C]//Proc of the 5th International Conference on Computational In-telligence and Multimedia Applications. Piscataway,NJ:IEEE Press,2003:362-367.
[4] Sun Jun,Xu Wenbo,Feng Bin. A global search strategy of quantumbehaved particle swarm optimization[C]//Proc of IEEE Conferenceon Cybernetics and Intelligent Systems. Piscataway,NJ:IEEE Press,2004:325-331.
[5]李盼池,李世勇.求解连续问题空间优化问题的量子蚁群算法[J].控制理论与应用,2008,25(2):237-240.(Li Panchi,LiShiyong. Quantum ant colony algorithm for space optimization of con-tinuous problems[J]. Control Theory and Applications,2008,25(2):237-240.)
[6] Luciano R S,Ricardo T,Marley M V. Quantum inspired evolutionaryalgorithm for ordering problems[J]. Expert Systems with Applica-tions,2017,67:71-83.
[7] Pavithr R,Gursaran S. Quantum inspired social evolution(QSE)algo-rithm for 0-1 knapsack problem[J]. Swarm and Evolutionary Com-putation,2016,29(8):33-46.
[8] Liu Min,Zhang Feng,Ma Yunlong,et al. Evacuation path optimizationbased on quantum ant colony algorithm[J]. Advanced EngineeringInformatics,2016,30(3):259-267.
[9] Yuan Xiaohui,Wang Pengtao,Yuan Yanbin,et al. A new quantum in-spired chaotic artificial bee colony algorithm for optimal power flowproblem[J]. Energy Conversion and Management,2015,100(8):1-9.
[10]Konar D,Bhattacharyya S,Sharma K,et al. An improved quantum-in-spired genetic algorithm(HQIGA)for scheduling of real-time task inmultiprocessor system[J]. Applied Soft Computing,2017,53(4):296-307.
[11]Zhao Shuanfeng,Xu Guanghua,Tao Tangfei,et al. Real-coded chaoticquantum inspired genetic algorithm for training of fuzzy neural net-works[J]. Computers and Mathematics with Applications,2009,57(11-12):2009-2015.
[12]高辉,徐光辉,张锐,等.实数编码量子进化算法[J].控制与决策,2008,23(1):87-90.(Gao Hui,Xu Guanghui,Zhang Rui,et al.Real coded quantum evolutionary algorithm[J]. Control and Deci-sion,2008,23(1):87-90.)
[13]高辉,张锐.改进实数编码量子进化算法及其在参数估计中的应用[J].控制与决策,2011,26(3):418-422.(Gao Hui,ZhangRui. Improved real-coded quantum evolutionary algorithm and its ap-plication in parameter estimation[J]. Control and Decision,2011,26(3):418-422.)
[14] Cheng Minyuan,Doddy P. Symbiotic organisms search:a new meta-heurstic optimization algorithm[J]. Computer and Structures,2014,139(7):98-112.
[15]赵克勤.集对分析及其初步应用[M].杭州:浙江科技出版社,2000.(Zhao Keqin. Set pair analysis and its preliminary application[M]. Hangzhou:Zhejiang Science and Technology Press,2000).
[16]Rahnamayan S,Wang G G,Ventrescaet M. An intuitive distance basedexplanation of opposition-based sampling[J]. Applied Soft Compu-ting,2012,12(9):2828-2839.
[17]刘会超,吴志健.基于旋转学习机制的差分演化算法[J].电子学报,2015,43(10):2040-2046.(Liu Huichao,Wu Zhijian. Differen-tial evolution algorithm based on rotation learning mechanism[J].Journal of Electronics,2015,43(10):2040-2046).
[2] Han K H,Jong H K. Quantum-inspired evolutionary algorithm for aclass of combination optimization[J]. IEEE Trans on EvolutionaryComputation,2002,6(6):580-593.
[3] Yang Shuyuan,Jiao Licheng. The quantum evolutionary programming[C]//Proc of the 5th International Conference on Computational In-telligence and Multimedia Applications. Piscataway,NJ:IEEE Press,2003:362-367.
[4] Sun Jun,Xu Wenbo,Feng Bin. A global search strategy of quantumbehaved particle swarm optimization[C]//Proc of IEEE Conferenceon Cybernetics and Intelligent Systems. Piscataway,NJ:IEEE Press,2004:325-331.
[5]李盼池,李世勇.求解连续问题空间优化问题的量子蚁群算法[J].控制理论与应用,2008,25(2):237-240.(Li Panchi,LiShiyong. Quantum ant colony algorithm for space optimization of con-tinuous problems[J]. Control Theory and Applications,2008,25(2):237-240.)
[6] Luciano R S,Ricardo T,Marley M V. Quantum inspired evolutionaryalgorithm for ordering problems[J]. Expert Systems with Applica-tions,2017,67:71-83.
[7] Pavithr R,Gursaran S. Quantum inspired social evolution(QSE)algo-rithm for 0-1 knapsack problem[J]. Swarm and Evolutionary Com-putation,2016,29(8):33-46.
[8] Liu Min,Zhang Feng,Ma Yunlong,et al. Evacuation path optimizationbased on quantum ant colony algorithm[J]. Advanced EngineeringInformatics,2016,30(3):259-267.
[9] Yuan Xiaohui,Wang Pengtao,Yuan Yanbin,et al. A new quantum in-spired chaotic artificial bee colony algorithm for optimal power flowproblem[J]. Energy Conversion and Management,2015,100(8):1-9.
[10]Konar D,Bhattacharyya S,Sharma K,et al. An improved quantum-in-spired genetic algorithm(HQIGA)for scheduling of real-time task inmultiprocessor system[J]. Applied Soft Computing,2017,53(4):296-307.
[11]Zhao Shuanfeng,Xu Guanghua,Tao Tangfei,et al. Real-coded chaoticquantum inspired genetic algorithm for training of fuzzy neural net-works[J]. Computers and Mathematics with Applications,2009,57(11-12):2009-2015.
[12]高辉,徐光辉,张锐,等.实数编码量子进化算法[J].控制与决策,2008,23(1):87-90.(Gao Hui,Xu Guanghui,Zhang Rui,et al.Real coded quantum evolutionary algorithm[J]. Control and Deci-sion,2008,23(1):87-90.)
[13]高辉,张锐.改进实数编码量子进化算法及其在参数估计中的应用[J].控制与决策,2011,26(3):418-422.(Gao Hui,ZhangRui. Improved real-coded quantum evolutionary algorithm and its ap-plication in parameter estimation[J]. Control and Decision,2011,26(3):418-422.)
[14] Cheng Minyuan,Doddy P. Symbiotic organisms search:a new meta-heurstic optimization algorithm[J]. Computer and Structures,2014,139(7):98-112.
[15]赵克勤.集对分析及其初步应用[M].杭州:浙江科技出版社,2000.(Zhao Keqin. Set pair analysis and its preliminary application[M]. Hangzhou:Zhejiang Science and Technology Press,2000).
[16]Rahnamayan S,Wang G G,Ventrescaet M. An intuitive distance basedexplanation of opposition-based sampling[J]. Applied Soft Compu-ting,2012,12(9):2828-2839.
[17]刘会超,吴志健.基于旋转学习机制的差分演化算法[J].电子学报,2015,43(10):2040-2046.(Liu Huichao,Wu Zhijian. Differen-tial evolution algorithm based on rotation learning mechanism[J].Journal of Electronics,2015,43(10):2040-2046).