摘要
针对多目标优化问题,设计一种基于量子计算和非支配排序遗传算法相结合的智能算法进行求解,综合量子算法和非支配排序遗传算法的优点,在局部搜索和全局搜索之间进行权衡。混合算法采用量子比特对问题的解进行编码,基于量子旋转门算子、分散交叉算子以及高斯变异算子对种群进行更新。进行局部深入搜索时,用一个解在目标空间中跟理想点的距离来评价该解的优劣;进行全局搜索时,基于非支配排序遗传算法中的有效前沿的划分和解之间的拥挤距离来评价某个解。最后,在经典的测试函数ZDT5上对所提混合算法进行了测试。通过对比分析若干项针对有效解集的评价指标,该混合算法在跟最优有效前沿的逼近程度以及有效解集分布的均匀程度上均优于目前得到广泛应用的非支配排序遗传算法。
A hybrid algorithm combining quantum computing and NSGA-Ⅱ is designed for multi-objective optimization problem. It makes use of the advantages of quantum algorithm and NSGA-II to balance between exploitation and exploration. In hybrid algorithm, Qubit is used to encode solutions to the problem into individuals. The population is updated based on operators of Quantum rotation gate, Scattered crossover and Gaussian mutation. When addressing exploitation, a solution＇ s distance to an ideal point in objective space is used to evaluate the solution. While in exploration a solution is evaluated by use of classifications of Pareto fronts and the crowding distance between individuals in NSGA-Ⅱ. Finally the hybrid algorithm is tested on a classic benchmark problem ＂ZDTS＂. By comparing and analyzing several performance metrics for Pareto solution sets, it is demonstrated that the hybrid algorithm is superior to widely used NSGA-Ⅱ in both proximity to optimal Pareto front and the uni- form distribution of solutions.
出处
《运筹与管理》
CSSCI
CSCD
北大核心
2012年第4期15-21,共7页
Operations Research and Management Science
基金
国家自然科学基金资助项目(70902033
71271039)
辽宁省博士启动基金资助项目(20081093)
中央高校基本科研业务费专项基金资助项目(DUT11SX10)
关键词
运筹学
算法改进
量子计算
非支配排序遗传算法
有效解集
operations research
improvement of algorithm
quantum computing
NSGA-Ⅱ
Pareto solution set
