改良粒子群演算法以解決背包問題

粒子群演算法為一具有群體智慧概念的最佳化方法，也是演化式計算中的新分支，其具有較少參數設定、快速收斂等優點，但在粒子移動時僅跟隨個體最佳記憶與群體最佳記憶，而使得粒子群演算法有容易落入區域最佳解的弱點。標準粒子群演算法與各種改進之粒子群演算法，大部份著眼於如何更有效地利用一個粒子群在解空間中搜尋最佳解，仍舊無法有效避免粒子落入區域最佳解中。本研究首先透過加速度概念及三種改良策略，提出「加速度粒子群演算法」。再結合演化策略與加速度粒子群演算法於文化演算法架構，提出「雙演化策略」架構。藉此，以期擴大粒子全域最佳解搜尋範圍及有效增加區域最佳解搜尋能力，並應用於零壹背包問題。期盼透過加速度粒子群演算法與雙演化策略架構求解零壹背包問題，達到提高收斂精度。本研究結果顯示，在物品較少的背包問題中，透過雙演化策略架構可有效達到最佳解並提升最佳解次數。在物品較多的背包問題中，透過加速度粒子群演算法與雙演化策略架構均能找到相較於以往文獻的更好最佳解並且在較小代數與平均代數上，也均能得到相較以往文獻的較少代數。所以本研究所提出的演算法，不僅在找到新的最佳解上有好的效能表現，在代數的快速收斂上也有好的效率表現。

關鍵字

演化策略；粒子群演算法；文化演算法；零壹背包問題

並列摘要

Particle Swarm Optimization (PSO), an algorithm with the concept of swarm intelligence, also a new branch in evolutionary computing, possesses the merits of fast converging, as well as the simplification in parameter setting. Although the standard PSO algorithm and other modified algorithms has attempted to enhance the efficiency in utilizing a swarm to search global best, they still fall in avoiding particles falling into local optima. In this paper, we propose a general idea of acceleration and three kinds of strategies ,we call it Acceleration Particle Swarm Optimization algorithm (APSO). Also, we combine Evolutionary Strategy (ES) with APSO in Culture Algorithm (CA) , we call it Dual Evolutionary Strategy (DES) framework. In short, this proposal purposes to increase the search area of global optimal and the search ability of local optimal and apply to Zero-One Knapsack Problem (KP). We expect to increase the convergent velocity and precision in KP through APSO and DES framework. The experiment presents DES framework can effectively achieve the best soultion and advance the numbers of the best solution in the fewer objects Zero-One KP. APSO and DES framework can both find a better solution, fewer minimum iterant times and average iterant times. Therefor APSO and DES framework can not only find the better solution but also use fewer iterant times.

並列關鍵字

Zero-One Knapsack Problem ； Culture Algorithm ； Particle Swarm Optimization ； Evolution Strategy

參考文獻

[21]林豐澤，2005，演化式計算上篇：演化式演算法的三種理論模式，智慧科技與應用統計學報，3（1）：1-28

[2]Eberhart, R.C., and Kennedy, J., (1995) “A new optimizer using particle swarm theory,” Proc.Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan, , pp.39-43.

[4]Fogel, L. J., Owens, A. J., and Walsh, M. J., (1966) Artificial Intelligence through Simulated Evolution, New York: Wiley.

[6]Holland, J. H., (1975) Adaptation in natural and artificial systems, Ann Arbor, MI: The University of Michigan Press.

[7]Kiefer J., (1961). “On large deviations of the empiric of vector chance variable and a law of the iterated logarithm,” Pactific J. Math, Vol.11(3) pp. 649-660.

國際替代計量

改良粒子群演算法以解決背包問題

未授權

主題瀏覽