A Master-Slave Model NGA and its Application in the Multidimensional 0-1 Knapsack Problem

Zi Bin Man; Ting Hong Zhao

doi:10.4028/www.scientific.net/AMM.433-435.566

Paper Titles

Demand Forecasting Model of Port Critical Spare Parts Based on PSO-LSSVM
p.545

Evaluation Study of Grounding Grids Based on Gray Clustering
p.550

A MSVM Quality Pattern Recognition Model for Dynamic Process
p.555

The Research of Timing-Optimal Trajectory Planning Based on Improved Genetic Algorithms
p.562

A Master-Slave Model NGA and its Application in the Multidimensional 0-1 Knapsack Problem
p.566

An Idea of the Topological Inductive Logic under the Inadequate-Cognition-Oriented
p.570

Some Applications of the Causal Statement Logic Programming in Machine Language
p.574

An Idea of Dynamics Inductive Logic in Complex Cognition
p.579

The Research of PID Controller Tuning Based on Parallel Particle Swarm Optimization
p.583

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 433-435A Master-Slave Model NGA and its Application in...

A Master-Slave Model NGA and its Application in the Multidimensional 0-1 Knapsack Problem

Abstract:

The Multidimensional 0-1 knapsack problem is a NP hard problem, though there are many algorithm is used to solve the problem, but there is still not a good solution to solving the problem. This paper improved niche genetic algorithm, established a master-slave mode niche genetic algorithm, and carried on adaptive setting the individual Euclidean distance criterion, making it can changed with the evolving algebra incremental. At last, used master-slave niche genetic algorithm to solve the Multidimensional 0-1 knapsack problem, test results showed, the algorithm has good applicability and superiority in solving the Multidimensional 0-1 knapsack problem.

You might also be interested in these eBooks

Advances in Mechatronics and Control Engineering II

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 433-435)

Pages:

566-569

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.433-435.566

Citation:

Cite this paper

Online since:

October 2013

Authors:

Zi Bin Man, Ting Hong Zhao

Keywords:

Adaptive, Euclidean Distance, Multi-Dimensional 0-1 Knapsack Problem, Niche Genetic Algorithm

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] GAvish B, Pirkul H. Efficient algorithms for solving multiconstraint 0-1 knapsack problems to optimality. Mathematical Programming, 1985, 31: 78-105.

DOI: 10.1007/bf02591863

Google Scholar

[2] Balas E, Martin C. Pivot and Complement a Heuristic for 0-1 Programming. Manegement Science, 1980, 26(1): 86-96.

DOI: 10.1287/mnsc.26.1.86

Google Scholar

[3] Freville A. The multidimensional 0-1 knapsack problem：An overview. European Journal of Operational Research. 2004, 155: 1-21.

Google Scholar

[4] Lorie J, Savage L, Three Problem in capital rationing. Journal of Business, 1955, 28: 229_239.

Google Scholar

[5] Manne A, Markowitz H. On the solution of discrete programming problem. Econometrica, 1957, 25: 84-110.

DOI: 10.2307/1907744

Google Scholar

[6] Fu Xiaowei, Gao Xiaoguang, Kuang Aixi. Flight Path Planning Based on Niche Genetic Algorithm. Journal of System Simulation. 2008, 20(21): 5940-5944.

Google Scholar