直接搜尋法與粒子群演算法之最佳化探討

Abstract

The population-based Particle Swarm Optimizations (PSO), without gradient information during generation, have both exploration and exploitation characteristics for global optimization problems, but don't have good accuracy of the optimum solutions to the higher-dimensional problems. As a result, in this study, PSO and three direct search methods such as Nelder-Mead Simplex Method, Hooke-Jeeves Pattern Search Method, and Powell's Method of Conjugate Directions, are to be examined through five single-modal benchmark problems including sphere, quadric, rosenbrock, and smooth functions with 2, 5, 10, 30 and 100 dimensions. The results show that for searching performance, Hooke-Jeeves Pattern Search Method and Powell's Method of Conjugate Directions are better than others; for computational efficiency, Hooke-Jeeves Pattern Search Method is better than Powell's Method of Conjugate Directions. Meanwhile, we also found that Nelder-Mead Simplex Method and PSO can only find out the optimum solutions of problems of sphere functions.基於不需梯度資訊的粒子群演算法(PSO)，為族群式演算法具有探測與開發的全域性搜尋特性，對較高維數的問題，其搜尋的精確度問題仍有檢討空間。因此，本文以三種直接搜尋法（Nelder-Mead單純形法、Hooke-Jeeves搜尋法與Powell共軛方向法）與PSO，探討2、5、10、30與100維的5種單極值函數問題，進行一系列搜尋特性探討。測試結果發現，Hooke-Jeeves搜尋法與Powell共軛方向法的精確度最佳與函數呼叫次數較少；Nelder-Mead單純形法與PSO只對圓與球函數才能找到全域最佳解。可見PSO的局部區域搜尋能力是不足。