›› 2015, Vol. 35 ›› Issue (2): 49-.doi: 10.3780/j.issn.1000-758X.2015.02.007

• 研究探讨 • 上一篇    下一篇

一种基于有限K近邻的强度帕累托进化算法

  

  1. (1北京控制工程研究所,北京100190)(2中国空间技术研究院,北京100094)(3 空间智能控制技术重点实验室,北京100190)
  • 出版日期:2015-04-25 发布日期:2015-04-25

An Improved Strength Pareto Evolutionary Algorithm Based onthe Limited K-Nearest Neighbor Method

  1. (1 Beijing Institute of Control Engineering, Beijing 100190)(2 China Academy of Space Technology, Beijing 100094) (3 Science and Technology on Space Intelligent Control Laboratory, Beijing 100190)〖JZ)〗〖HQK〗
  • Online:2015-04-25 Published:2015-04-25

摘要: 在航天器控制计算机的软硬件协同设计过程中,需要解决多目标优化问题。当前的强度帕累托进化算法在求解高维多目标优化问题时具有优势,但是在环境选择阶段的计算时间复杂度仍然较大。文章针对这一问题,提出了一种改进算法。新的算法采用有限K近邻方法,减少了原算法中K近邻策略的比较次数,使时间复杂度由O(M3)下降为O(max(l,logM)M2。试验结果表明文中算法的计算速度更快,并且具有更优的收敛性和分布多样性特征。

关键词: 软硬件协同设计, 多目标优化, 帕累托最优, 强度帕累托进化算法, 星载计算机, 航天器控制

Abstract: In the process of Hardware/software co-design of spacecraft control computers, the multi-objective optimization is a key problem. The current strength Pareto evolutionary algorithm has some advantages in solving high-dimensional multi-objective optimization problems, but the computing time-complexity during the step of environmental selection is still very large. Aiming at this point, an improved algorithm was proposed. With the finite K-nearest neighbor method, new algorithm reduces the number of comparisons to lower the time-complexity from O(M3) down to O(max(l,logM)M2 . The experimental results show that the proposed algorithm not only improves the running speed, but also acquires better convergence and distribution diversity than the original one.

Key words: Hardware/software co-design, Multi-objective optimization, Pareto optimization, Strength Pareto evolutionary algorithm, On-board computer, Spacecraft control