Ant colony optimization algorithm for the 0-1 knapsack problem

Typ: Artykuł

Liczba pobrań: 9056

Pobierz zasób

PDF

Cytuj

BibTeX EndNote

Tytuł: Ant colony optimization algorithm for the 0-1 knapsack problem
Wariant tytułu: Algorytmy mrówkowe dla 0-1 problemu plecakowego
Autor: Schiff, Krzysztof
Opublikowane w: Technical Transactions
Numeracja: Y. 110, iss. 3-AC
Strony: 39-52
Data wydania: 2013
Miejsce wydania: Kraków
Wydawca: Wydawnictwo PK
Język: angielski
Słowa kluczowe: knapsack problem, ant colony optimisation, heuristic algorithm

problem plecakowy, algorytm mrówkowy, heurystyka
Abstrakt: This article describes a new ant colony optimisation algorithm for the discrete knapsack problem with a new heuristic pattern, based on the ratio of the square of the profit coefficient to the square of the weight coefficient of the original problem. This new heuristic is used in order to choose objects that should be packed into the knapsack. This pattern was compared with two used in ant algorithms and which have been presented in the literature on the subject of ant colony optimisation algorithms for the 0-1 Knapsack Problem. The two other patterns are based on the ratio of the profit coefficient to the weight coefficient multiplied respectively by the total and the current knapsack load capacity. Results of tests under a width range of ant algorithm parameters such as the number of cycles, the number of ants, the evaporation rate, and the load knapsack capacity are shown and discussed.

W artykule przedstawiono algorytm mrówkowy dla dyskretnego problemu plecakowego z nową heurystyką wyboru obiektów i został on porównany z dwoma innymi algorytmami spotkanymi w literaturze przedmiotu pod względem uzyskiwanego całkowitego zysku z załadowanych do plecaka przedmiotów. Nowa heurystyka wyboru została wyrażona poprzez stosunek kwadratu zysku do kwadratu wagi wybranego przedmiotu, gdy dwie znane już heurystyki to stosunek zysku do wagi odpowiednio pomnożony przez całkowitą i bieżącą ładowność plecaka. W artykule przedstawiono wyniki przeprowadzonych testów dla szerokiego zakresu parametrów algorytmów mrówkowych takich jak: współczynnik parowania, liczba cykli, liczba mrówek, ładowności plecaka jak i dla różnej liczby dostępnych przedmiotów do załadunku.
Klasyfikacja PKT: 390000 Automatyka
Wydział: Wydział Inżynierii Elektrycznej i Komputerowej
Licencja: Licencja PK
Prawa dostępu: Zasób dostępny dla wszystkich