Applying the Strategy of Value Density to Solve the Zero-One Knapsack Problem
| Autor: | Ming-Jia Hsu, 許銘家 |
|---|---|
| Rok vydání: | 2010 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 98 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. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|