粒子群演算法結合模擬退火法求解背包問題

Combined Particle Swarm Optimization and Simulated Annealing for Solving the Knapsack Problem

康芳維(Fang-Wei Kang)

指導教授 ： 李維平

中原大學/商學院/資訊管理研究所/碩士(2009年)

https://doi.org/10.6840/CYCU.2009.00762

摘要

粒子群演算法是一種具有記憶性的演算法，初期粒子會隨機分佈求解，根據粒子本身的記憶找尋粒子最佳解，但是經過一段時間疊代演化過後，大部分的粒子就會開始將自己位置集中到區域最佳解的週遭，且同時也會形成粒子本身的群體，並開始趨近於全域最佳解，但所找到的解有可能為區域最佳解而非全域最佳解。

本研究提出的混合演算法，將模擬退火法概念加入粒子演化流程中去改良傳統粒子演化缺點以提升粒子搜索空間能力與求解的精準度。本研究除了粒子本身的自我學習及記憶較佳的解空間分佈性、且可快速在空間中做搜尋，再引入模擬退火法的成本解與接受法則概念並給於粒子隨機加速度加強粒子在空間中搜尋的彈性化，並強化鄰近搜尋空間的能力，在擴大範圍搜尋中使其有機會跳出局部最佳解而往全域最佳做搜尋。期盼透過粒子演算法結合模擬退火法互相搭配並應用於求解零壹背包問題，以提高空間搜尋及收斂的精準度解。

關鍵字

粒子群演算法 ； 模擬退火法 ； 零壹背包問題

並列摘要

Partical Swoarm Optimization (PSO) is one kind memory of algorithm. The initial random distribution of particles may be solved in accordance with their own memory to find particle particles optimal solution, but after a period of time after the generations evolution, most of the particles will begin to position themselves into the global best solution of the surrounding and At the same time, particles will form their own groups and began to approach the global best solution, but these particles groups may find the solution for the region best rather than the global best solution.

This study proposes a Combined Optimization, the concept of simulated annealing optimization (SA) by adding particles to the evolution of process improvement evolution of the shortcomings of the traditional particle particles to enhance the capacity of search space and solution accuracy. In this study，in addition to particle's own self-learning and memory of a better distribution of the solution space and can be done quickly in the space searchingand then introduce a simulated annealing acceptance of the law to strengthen the particles in space search of flexibility, and strengthen the adjacent the ability of the search space in the expansion of the scope of the search space have the opportunity to jump out of a local optimal solution and to do a search for the global best. Look through the particles simulated annealing optimization combined with each other and applied to zero-one knapsack problem to solve in order to enhance spatial accuracy of search and convergence solutions.

並列關鍵字

Simulated Annealing ； Partical Swoarm Optimization ； Zero-One Knapsack Problem.

參考文獻

[1] Chang, Y. C., Chang, Y. W., Wu, G. M. and Wu, S. W. “B*-Tree： A new representation for nonslicing floorplans,” in Proc. Design Automation Conference, pp. 458-563. 2000

[3] 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

[5] Fatih M, LIANG Y. A binary particle swarm optimization algorithem for lot sizing problem[J]. Journal of Economic and Social Research, 2003,5(2)：1-20.

[7] Goldberg, D. E., Genetic Algorithms in Search Optimization and Machine Learning, Addison Wesley, 1989.

[8] HE Yi-chao, LIU Kun-qi, Greedy genetic algorithm for solving knapsack problems and its applications[J], Computert Engineering and Design, 2007,11:2655-2657,2681