Quasi-Physical Algorithm Based on Action Space for Solving the Circles Packing Problem with Equilibrium Constraints
Author:
Affiliation:

Clc Number:

Fund Project:

National Natural Science Foundation of China (61173180, 61272014)

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    This paper proposes a Quasi-physical algorithm based on action space (QPAS) for an NP-hard global optimization problem-the circle packing problem with equilibrium constraints (CPPEC). The algorithm has important applications for the layout design of the satellite modules. A key issue in designing a good basin hopping strategy for CPPEC is how to find the most vacant areas such that the searching procedure can jump from a local minimum basin to a promising area. By borrowing the concept of "action space" proposed for the rectangular packing problem, the new algorithm approximates each circle as a rectangle and the irregular vacant areas are viewed approximately as regular rectangular areas. Consequently the most vacant areas can be found efficiently and accurately. In addition, three quasi-human strategies, namely early termination, coarse-to-fine and adaptive step length, are combined with the quasi-physical approach to speed up the potential energy descending process. Experiments are performed on 13 benchmark instances, and computational results demonstrate the high efficiency of the proposed approach. QPAS achieves the first or the second best results on most instances compared with other algorithms, and in some configurations, it has smaller container radius than the current best results. Meanwhile, QPAS obtains very small equilibrium deviations.

    Reference
    Related
    Cited by
Get Citation

何琨,杨辰凯,黄梦龙,黄文奇.动作空间带平衡约束圆形Packing问题的拟物求解算法.软件学报,2016,27(9):2218-2229

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:February 18,2014
  • Revised:April 17,2014
  • Adopted:
  • Online: September 02,2016
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063