A New Grouping Genetic Algorithm for the Multiple Knapsack Problem

被引：18

作者：

Fukunaga, Alex S. ^{[1
]}

机构：

[1] Tokyo Inst Technol, Global Edge Inst, Meguro Ku, Tokyo 152, Japan

来源：

2008 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-8 | 2008年

关键词：

D O I：

10.1109/CEC.2008.4631094

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The Multiple Knapsack Problem (MKP) is the problem of assigning (packing) objects of various weights and values (profits) to a set of containers (bins) of various capacities, in order to maximize the total profit of the items assigned to the containers. We propose a new genetic algorithm for the MKP which searches a space of undominated candidate solutions. We compare the new algorithm to previous heuristics for the MKP, as well as alternative evolutionary algorithms, and show experimentally that our new algorithm yields the best performance on difficult instances where item weights and profits are highly correlated.

引用

页码：2225 / 2232

页数：8

共 16 条

[1]

[Anonymous], 1999, APPROXIMATION ALGORI

[2] LOADING PROBLEM [J].

EILON, S ;

CHRISTOF.N .

MANAGEMENT SCIENCE SERIES A-THEORY, 1971, 17 (05) :259-268

[3]

Falkenauer E., 1996, Journal of Heuristics, V2, P5, DOI 10.1007/BF00226291

[4] A New Representation and Operators for Genetic Algorithms Applied to Grouping Problems [J].

Falkenauer, Emanuel .

EVOLUTIONARY COMPUTATION, 1994, 2 (02) :123-144

[5] Bin completion algorithms for multicontainer packing, knapsack, and covering problems [J].

Fukunaga, Alex S. ;

Korf, Richard E. .

JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2007, 28 :393-429

[6] Computational Aspects of Clearing Continuous Call Double Auctions with Assignment Constraints and Indivisible Demand [J].

Kalagnanam, Jayant R. ;

Davenport, Andrew J. ;

Lee, Ho S. .

Electronic Commerce Research, 2001, 1 (03) :221-238

[7]

Kellerer Hans, 2004, KNAPSACK PROBLEMS

[8] Upper bounds and algorithms for the maximum cardinality bin packing problem [J].

Labbé, M ;

Laporte, G ;

Martello, S .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2003, 149 (03) :490-498

[9] HEURISTIC ALGORITHMS FOR THE MULTIPLE KNAPSACK-PROBLEM [J].

MARTELLO, S ;

TOTH, P .

COMPUTING, 1981, 27 (02) :93-112

[10]

Martello S., 1990, KNAPSACK PROBLEMS AL

← 1 2 →