《计算机应用研究》|Application Research of Computers

实数编码量子共生演算法及其在云任务调度中的应用

Real-coded quantum SOS algorithm and its application in cloud task scheduling

免费全文下载 (已被下载 次)  
获取PDF全文
作者 李昆仑,关立伟
机构 河北大学 电子信息工程学院,河北 保定 071000
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2019)03-029-0786-06
DOI 10.19734/j.issn.1001-3695.2017.10.0977
摘要 针对共生演算法收敛慢和易陷入局部最优的问题,结合量子遗传算法理论,提出一种实数编码的量子共生演算法(real-coded quantum symbiotic organisms search,RQSOS)。首先依据三角模糊数提出差异度概念,并依此构造一个以自变量向量的分量和一对概率幅为等位基因的三倍染色体,使一条染色体携带更多信息并增强解的多样性;然后提出一种基于阿基米德螺旋线的探索学习模式,加强对解空间的探索精度;最后使用共生演算法更新差异度值并依据差异度值对种群进行学习和变异操作,促使整个种群快速向最优方向进化且减小了陷入局部最优的概率。利用数值优化问题和云任务调度问题对算法进行验证,仿真结果表明,RQSOS算法在收敛速度和寻优能力上均有明显提升,是一种可行有效的算法。
关键词 量子遗传算法;共生演算法;差异度;数值优化;任务调度
基金项目 国家自然科学基金资助项目(61672205)
本文URL http://www.arocmag.com/article/01-2019-03-029.html
英文标题 Real-coded quantum SOS algorithm and its application in cloud task scheduling
作者英文名 Li Kunlun, Guan Liwei
机构英文名 CollegeofElectronicInformationEngineering,HebeiUniversity,BaodingHebei071000,China
英文摘要 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.
英文关键词 genetic quantum algorithm; symbiotic organisms search; difference degree; numerical optimization; task sche-duling
参考文献 查看稿件参考文献
  [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 a class of combination optimization[J] . IEEE Trans on Evolutionary Computation, 2002, 6(6):580-593.
[3] Yang Shuyuan, Jiao Licheng. The quantum evolutionary programming[C] //Proc of the 5th International Conference on Computational Intelligence and Multimedia Applications. Piscataway, NJ:IEEE Press, 2003:362-367.
[4] Sun Jun, Xu Wenbo, Feng Bin. A global search strategy of quantum behaved particle swarm optimization[C] //Proc of IEEE Conference on Cybernetics and Intelligent Systems. Piscataway, NJ:IEEE Press, 2004:325-331.
[5] 李盼池, 李世勇. 求解连续问题空间优化问题的量子蚁群算法[J] . 控制理论与应用, 2008, 25(2):237-240. (Li Panchi, Li Shiyong. Quantum ant colony algorithm for space optimization of continuous problems[J] . Control Theory and Applications, 2008, 25(2):237-240. )
[6] Luciano R S, Ricardo T, Marley M V. Quantum inspired evolutionary algorithm for ordering problems[J] . Expert Systems with Applications, 2017, 67:71-83.
[7] Pavithr R, Gursaran S. Quantum inspired social evolution(QSE) algorithm for 0-1 knapsack problem[J] . Swarm and Evolutionary Computation, 2016, 29(8):33-46.
[8] Liu Min, Zhang Feng, Ma Yunlong, et al. Evacuation path optimization based on quantum ant colony algorithm[J] . Advanced Engineering Informatics, 2016, 30(3):259-267.
[9] Yuan Xiaohui, Wang Pengtao, Yuan Yanbin, et al. A new quantum inspired chaotic artificial bee colony algorithm for optimal power flow problem[J] . Energy Conversion and Management, 2015, 100(8):1-9.
[10] Konar D, Bhattacharyya S, Sharma K, et al. An improved quantum-inspired genetic algorithm(HQIGA) for scheduling of real-time task in multiprocessor system[J] . Applied Soft Computing, 2017, 53(4):296-307.
[11] Zhao Shuanfeng, Xu Guanghua, Tao Tangfei, et al. Real-coded chaotic quantum inspired genetic algorithm for training of fuzzy neural networks[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 Decision, 2008, 23(1):87-90. )
[13] 高辉, 张锐. 改进实数编码量子进化算法及其在参数估计中的应用[J] . 控制与决策, 2011, 26(3):418-422. (Gao Hui, Zhang Rui. Improved real-coded quantum evolutionary algorithm and its application in parameter estimation[J] . Control and Decision, 2011, 26(3):418-422. )
[14] Cheng Minyuan, Doddy P. Symbiotic organisms search:a new metaheurstic 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 based explanation of opposition-based sampling[J] . Applied Soft Computing, 2012, 12(9):2828-2839.
[17] 刘会超, 吴志健. 基于旋转学习机制的差分演化算法[J] . 电子学报, 2015, 43(10):2040-2046. (Liu Huichao, Wu Zhijian. Differential evolution algorithm based on rotation learning mechanism[J] . Journal of Electronics, 2015, 43(10):2040-2046).
收稿日期 2017/10/24
修回日期 2017/12/19
页码 786-791
中图分类号 TP393
文献标志码 A