A contribution-guided discrete differential evolution algorithm for the quadratic multiple knapsack problem
| Autor: | Lixin Tang, Yun Dong, Xiangling Zhao |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Mathematical optimization
021103 operations research Optimization problem Continuous knapsack problem 0211 other engineering and technologies Evolutionary algorithm 02 engineering and technology Knapsack problem Cutting stock problem Genetic algorithm 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Evolution strategy Algorithm Generalized assignment problem Mathematics |
| Zdroj: | CEC |
| DOI: | 10.1109/cec.2016.7744119 |
| Popis: | In order to explore and extend the ability and application of Differential Evolution (DE), a Contribution-guided Discrete Differential Evolution (C-DDE) is proposed in this paper for the Quadratic Multiple Knapsack Problem (QMKP), which is a challenging combinatorial optimization problem with NP-Hard and a number of applications. C-DDE extends the traditional standard DE by adopting a novel hybrid mutation operation strategy, which includes “DE/rand/1” mutation and a new contribution-guided mutation operator. They are adopted interchangeably based on a uniform distribution. The definition of contribution for an object to a knapsack is presented, which is applied to guide an individual to evolve into an improved mutant individual and to accelerate the calculation of fitness value for mutant individuals. Traditional “DE/rand/1” is utilized as a dedicated perturbation strategy to ensure a global diversification of the search procedure. The contribution-guided mutation is utilized as self-evolution strategy for intensification of ability in searching for better solutions. The proposed algorithm has been tested on the set of 27 well-known benchmarks. The experimental results demonstrate the efficiency and robustness of our proposed algorithm to reach good results. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|