Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (7): 1908-1912.DOI: 10.11772/j.issn.1001-9081.2019122237

• Artificial intelligence • Previous Articles     Next Articles

Improved hybrid cuckoo search-based quantum-behaved particle swarm optimization algorithm for bi-level programming

ZENG Minghua, QUAN Ke   

  1. School of Transportation and Logistics, East China JiaoTong University, Nanchang Jiangxi 330013, China
  • Received:2020-01-07 Revised:2020-03-09 Online:2020-07-10 Published:2020-04-13
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (51468020), the Key Research and Development Program of Jiangxi Province (20192BBG70076), the Natural Science Foundation of Jiangxi Province (20181BAB206044).

双层规划的改进混合布谷鸟搜索量子行为粒子群优化算法

曾明华, 全轲   

  1. 华东交通大学 交通运输与物流学院, 南昌 330013
  • 通讯作者: 全轲
  • 作者简介:曾明华(1977-),男,湖南邵阳人,副教授,博士,主要研究方向:交通系统建模、智能交通系统工程;全轲(1995-),男,浙江杭州人,硕士研究生,主要研究方向:交通系统建模与优化。
  • 基金资助:
    国家自然科学基金资助项目(51468020);江西省重点研发计划项目(20192BBG70076);江西省自然科学基金资助项目(20181BAB206044)。

Abstract: Because the Particle Swarm Optimization (PSO) algorithm is easily trapped into local optimal solutions when solving the bi-level programming problems, an Improved hybrid Cuckoo Search-based Quantum-behaved Particle Swarm Optimization (ICSQPSO) algorithm based on Simulated Annealing (SA) Metropolis criterion was proposed. Firstly, the Metropolis criterion of SA algorithm was introduced into the hybrid algorithm to enhance the global optimization ability by accepting good solutions as well as bad solutions with a probability during solving process. Secondly, a Lévy flight with dynamic step size was designed for cuckoo search algorithm in order to maintain the high diversity of particle swarm during optimization, so as to guarantee search range. Finally, the preference random walk mechanism in the cuckoo algorithm was used to help the particles jump out of local optimal solutions. The numerical results of 13 bi-level programming cases including nonlinear ones, fractional ones, and those with multiple lower levels show that the objective functions optimal values of 12 cases obtained by ICSQPSO algorithm are significantly better than those of the algorithms for comparison in literatures, only the result of 1 case is slightly worse, and the results of half of the 13 cases are 50% better than those of the algorithms to be compared. Therefore, the ICSQPSO algorithm is superior to the algorithms to be compared on the optimization ability for bi-level programming.

Key words: Bi-Level Programming (BLP), quantum-behaved particle swarm optimization algorithm, Simulated Annealing (SA), Cuckoo Search (CS), Lévy flight

摘要: 为解决粒子群优化(PSO)算法求解双层规划问题时易陷入局部最优解的问题,提出了一种基于模拟退火(SA)Metropolis准则的改进混合布谷鸟搜索量子行为粒子群优化(ICSQPSO)算法。首先,该混合算法引入SA算法中的Metropolis准则,在求解过程中既能接受好解也能以一定的概率接受坏解,增强全局寻优能力;接着,为布谷鸟搜索算法设计一种改进动态步长Lévy飞行,以保持粒子群在优化过程中较高的多样性,保证搜索广度;最后,利用布谷鸟搜索算法中的偏好随机游走机制帮助粒子跳出局部最优解。通过对13个涵盖非线性规划、分式规划、多个下层规划的双层规划实例的数值实验,结果表明:ICSQPSO算法所得12个双层规划的目标函数最优值显著优于对比算法,只有1例的结果稍差,并且有半数实例的结果优于对比算法50%。由此可见,ICSQPSO算法对双层规划的寻优能力明显优于对比算法。

关键词: 双层规划, 量子行为粒子群优化算法, 模拟退火, 布谷鸟搜索, Lévy飞行

CLC Number: