Title | ||
---|---|---|
An evolutionary strategy for the multidimensional 0-1 knapsack problem based on genetic computation of surrogate multipliers |
Abstract | ||
---|---|---|
In this paper we present an evolutionary algorithm for the multidimensional 0–1 knapsack problem. Our algorithm incorporates a heuristic operator which computes problem-specific knowledge. The design of this operator is based on the general technique used to design greedy-like heuristics for this problem, that is, the surrogate multipliers approach of Pirkul (see [7]). The main difference with work previously done is that our heuristic operator is computed following a genetic strategy -suggested by the greedy solution of the one dimensional knapsack problem- instead of the commonly used simplex method. Experimental results show that our evolutionary algorithm is capable of obtaining high quality solutions for large size problems requiring less amount of computational effort than other evolutionary strategies supported by heuristics founded on linear programming calculation of surrogate multipliers. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1007/11499305_7 | IWINAC (2) |
Keywords | Field | DocType |
surrogate multiplier,evolutionary strategy,greedy-like heuristics,knapsack problem,computational effort,dimensional knapsack problem,evolutionary algorithm,surrogate multipliers approach,genetic computation,large size problem,heuristic operator,evolutionary computation,simplex method,linear program,genetic algorithm,combinatorial optimization,evolutionary computing,genetic algorithms,genetics | Mathematical optimization,Evolutionary algorithm,Change-making problem,Computer science,Algorithm,Evolutionary computation,Continuous knapsack problem,Greedy algorithm,Knapsack problem,Evolutionary programming,Genetic algorithm | Conference |
Volume | ISSN | ISBN |
3562 | 0302-9743 | 3-540-26319-5 |
Citations | PageRank | References |
3 | 0.42 | 8 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
César L. Alonso | 1 | 27 | 4.69 |
Fernando Caro | 2 | 6 | 0.81 |
Josè L. Montaña | 3 | 82 | 15.50 |