Ants and multiple knapsack problem

被引：5

作者：

Boryczka, Urszula ^{[1
]}

机构：

[1] Univ Silesia, Inst Comp Sci, Bedzinska 39, Sosnowiec, Poland

来源：

6TH INTERNATIONAL CONFERENCE ON COMPUTER INFORMATION SYSTEMS AND INDUSTRIAL MANAGEMENT APPLICATIONS, PROCEEDINGS | 2007年

关键词：

ant colony optimization; multiple knapsack problem; combinatorial optimization;

D O I：

10.1109/CISIM.2007.12

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper a new optimization algorithm based on ant colony metaphor (ACO)and a new approach for the Multiple Knapsack Problem is presented. The MKP is the problem of assigning a subset of n items to m distinct knapsacks, such that the total profit sum of the selected items is maximized, without exceeding the capacity of each of the knapsacks. The problem has several difficulties in adaptation as well as the trail representation of the solutions of MKP or a dynamically changed heuristic function applied in this approach. Presented results show the power of the ACO approach for solving this type of subset problems.

引用

页码：149 / +

页数：2

共 12 条

[1]

[Anonymous], 2004, Ant colony optimization

[2]

[Anonymous], INT C EVOL COMP, DOI DOI 10.1109/CEC.1999.782655

[3]

[Anonymous], 1999, Swarm Intelligence

[4]

[Anonymous], 1972, COMPLEXITY COMPUTER

[5]

Dorigo M., 1997, IEEE Transactions on Evolutionary Computation, V1, P53, DOI 10.1109/4235.585892

[6]

Dorigo M., 1996, Parallel Problem Solving from Nature - PPSN IV. International Conference on Evolutionary Computation - The 4th International Conference on Parallel Problem Solving from Nature. Proceedings, P656, DOI 10.1007/3-540-61723-X_1029

[7]

Gambardella L.M., 1997, HAS SOP HYBRID ANT S

[8] ALGORITHM FOR 0-1 MULTIPLE-KNAPSACK PROBLEMS [J].

HUNG, MS ;

FISK, JC .

NAVAL RESEARCH LOGISTICS, 1978, 25 (03) :571-579

[9] LOWER BOUNDS AND REDUCTION PROCEDURES FOR THE BIN PACKING PROBLEM [J].

MARTELLO, S ;

TOTH, P .

DISCRETE APPLIED MATHEMATICS, 1990, 28 (01) :59-70

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

MARTELLO, S ;

TOTH, P .

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

← 1 2 →