求解等圓Packing問題的快速優(yōu)化算法研究.pdf

1、華中科技大學碩士學位論文求解等圓Packing問題的快速優(yōu)化算法研究姓名：吳慶華申請學位級別：碩士專業(yè)：計算機軟件與理論指導(dǎo)教師：許如初20090525II華 中 科 技 大 學 碩 士 學 位 論 文 Abstract The congruent circles packing problem is a very typical layout optimization problem as well as a very repres

2、entative NP-hard problem, NP-hard problem is a very difficult problem to solve in modern computer science. Modern scientific research shows that there is no precision and strict integrity algorithm as required by classic

3、al mathematical for solving the NP-hard problem. Therefore, high performance heuristic approximation algorithm is designed to solve NP-hard problem. Research on this issue has very important practical application value.

4、Quasi-Physical algorithm is designed for solving the congruent circles packing problem instead of using other international popular algorithm. A physical motion model is taken to solve the congruent circles packing probl

5、em. According to our experiments, the Quasi-Physical algorithm is very effective in solving the congruent circles packing problem. Some methods are proposed to further improve the performance of the Quasi-Physical algori

6、thm. The local search forecast strategy is introduced on the basis of the Quasi-Physical algorithms. In the process of executing the local search forecast strategy, the possibility of obtaining the optimal solution is fo

7、recasted constantly. If the current pattern is judged as a local minimal pattern, the current searching path will be ended and a new searching path will be restarted. With this strategy, a lot of unnecessary calculation

8、is avoided. Using the optimal step size strategy, step size is adjusted continually to make the calculation obtain a faster convergence rate. On how to escape from the trap of local minimum of the congruent circles packi

9、ng problem, several Quasi-Physical-Human strategies are proposed on the basis of the Quasi-Physical algorithm. The Quasi-Physical algorithm is combined with the Quasi-Physical-Human strategies. A specific Quasi-Physical-

10、Human strategy is selected to use by probability according to the current pattern feature. The benchmark of the circles packing problem and the performance of the Quasi-Physical-Human algorithm on the benchmark are intro