- 學位論文
運用價值密度策略求解零壹背包問題
Applying the Strategy of Value Density to Solve the Zero-One Knapsack Problem
摘要
在本文中，將討論如何設計一個運用物品價值密度的粒子群演算法(Particle Swarm Optimization，PSO)用以解決零壹背包問題(Zero-One Knapsack Problem，Zero-One KP)。零壹背包問題一般定義如下：在符合限制條件下，從n 項物品內選出數項物品，以期達到效益極大化。 粒子群最佳化演算法為人工智慧領域中的一個新興技術，屬於軟性計算(Soft Computing)中演化式演算法(Evolutionary Algorithms)的一個新分支，也是群智慧(Swarm Intelligence)中相當重要的一個方法。由1995年發展至今，逐漸被廣泛應用於最佳化問題。PSO具備快速收斂、較少的參數設定、適用於動態環境的能力等優點，已成為一個熱門的研究主題。其與蟻群演算法、基因演算法、摸擬退火法、類神經網路相同，皆是仿效大自然的行為, 來進行最佳化求解。粒子群演算法除了仿效鳥、魚的覓食行為，也加入了人類社會行為的觀念，粒子移動時僅跟隨個體最佳記憶與群體最佳記憶，而使得粒子群演算法有容易落入區域最佳解的弱點。標準粒子群演算法與各種改進之粒子群演算法，大部份著眼於如何更有效地利用一個粒子群在解空間中搜尋最佳解，但仍舊無法有效避免粒子落入區域最佳解中。 本研究提出粒子群演算法結合貪婪演算法求解最佳化的特性，期待運用最直接的解法，亦即每次求解決策都是選取對目前“最佳”解，這樣的決策方式，後增加執行求解的速度，與其他的啟發式解法相比較，貪婪演算法在執行的時間效率上，佔有很大的優勢。故在許多的參考文獻中，貪婪演算法常被使用來解決組合最佳化的問題。
並列摘要
Here, we are going to discuss how to programming a Particle Swarm Optimization ( PSO ) in order to solve the Zero-One Knapsack Problem( Zero-One KP ), General definition of Zero-One Knapsack Problem as below: Under the fulfillment of certain limited conditions, pick up several objects from “n” objects to get the maximum benefit/ efficiency. Particle Swarm Optimization is a brand new skill in the Artificial Intelligence category; It’s a new branch divided from Evolutionary Algorithms of Soft Computing. Meanwhile, it also plays a important role in Swarm Intelligence. Developing form 1995 till now broadly applied to optimization problems. PSO maintain several advantages such as rapid convergence, less parameters setting, and capable dynamic environment etc. Thus, it becomes popular study subject. Similar to Ant Colony Optimization, Genetic Algorithm, Simulated Annealing, Artificial Neural Network, all imitated from natural behavior to process optimization. Particle Swarm Optimization not merely imitated birds, fish foraging but also add in concept of human social activity. Movement of particles only follow the individual best memory ( pbest ) and the group best memory ( gbest ) will cause weakness of the tendency of enforce the particles fall into local optimal solution. Standard Particle Swarm Optimization likewise numerous evolutionary Particle Swarm Optimization, mainly focus on how to use a particle swarm effectively searching the optimal solution in solution space, still cannot fully prevent from particles fall into local optimal solution. This research propose combining the characteristics of optimal solution both on Particle Swarm Optimization and Greedy Algorithm to approach the most directly solution---pick up the best solution strategy to the current status of each solving process; then accelerate the execution speed. Compare with other heuristic solution, Greedy Algorithm has great strength on the time efficiency while executing. Therefore, Greedy Algorithm often apply for solving combinatorial optimization problem in many reference documents.