A hybrid ant colony optimization algorithm for the knapsack problem with a single continuous variable
Authors:
Open Access
- 26 June 2021
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 57-65
Abstract
Knapsack problem with a single continuous variable (KPC) is a natural extension of the standard 0-1 knapsack problem. In the KPC, the capacity of the knapsack is not fixed, so it becomes more difficult to solve. Although several metaheuristics have been proposed to solve the KPC, their performances are not stable enough. This paper proposes a hybrid ant colony optimization (HACO) algorithm to solve the KPC. In the HACO algorithm, a simplified ACO algorithm is designed to search the optimal subset of items, and the mutation operator of differential evolution algorithm is used to search the optimal value of continuous variable. The parameter of the mutation operator is adaptively configured via an ACO algorithm. In the simplified ACO algorithm, an independent selection strategy and a pheromone-based selection strategy are designed to speed up the algorithm and simplify the tuning of parameters respectively. Personal best solutions constructed by each ant are used to deposit pheromone. Furthermore, a value-based greedy optimization strategy is introduced to enhance the solutions. The HACO algorithm is experimentally analyzed on 40 KPC instances. The experimental results show that the HACO algorithm is better than other competitors in terms of obtaining the best solution and the mean solution.Keywords
This publication has 15 references indexed in Scilit:
- List-Based Simulated Annealing Algorithm With Hybrid Greedy Repair and Optimization Operator for 0–1 Knapsack ProblemIEEE Access, 2018
- Structural test data generation using a memetic ant colony optimization based on evolution strategiesSwarm and Evolutionary Computation, 2018
- A Hybrid Lagrangian Search Ant Colony Optimization Algorithm for the Multidimensional Knapsack ProblemProcedia Computer Science, 2015
- Approximation algorithms on 0–1 linear knapsack problem with a single continuous variableJournal of Combinatorial Optimization, 2013
- Fusing ant colony optimization with Lagrangian relaxation for the multiple-choice multidimensional knapsack problemInformation Sciences, 2012
- An exact algorithm for the 0–1 linear knapsack problem with a single continuous variableJournal of Global Optimization, 2011
- A new ant colony optimization algorithm for the multidimensional Knapsack problemComputers & Operations Research, 2008
- An ant colony optimization approach for the multidimensional knapsack problemJournal of Heuristics, 2008
- Solution to 0/1 Knapsack Problem Based on Improved Ant Colony Algorithm2006
- The 0-1 Knapsack problem with a single continuous variableMathematical Programming, 1999