Name
Title | ||
|---|---|---|
Efficiency of adaptive genetic algorithm with mutation matrix in the solution of the knapsack problem of increasing complexity |
Abstract | ||
|---|---|---|
An adaptive genetic algorithm using mutation matrix is introduced for the solution of a series of zero/one knapsack problems of increasing complexity and structure. The evolution of the population in our adaptive genetic algorithm is based on a time dependent mutation matrix that is co-evolving, guided by the locus statistics and the fitness distribution of the population. This co-evolution of the mutation matrix provides a parameter free framework for the adaptive genetic algorithm, but different implementations of the mutation matrix have different performance for the knapsack problem. Here three structures of the knapsack problems are used as the benchmark tests: simple knapsack, parallel knapsack, and hierarchical or layer knapsack. For each type of knapsack structure, an index of difficulty is constructed based on the number of items and constraints. Numerical experiments are performed to test three models of implementation of the mutation matrix corresponding to three different way of controlling the number of mutation operations used. The numerical results for the three different knapsack problems using these three different implementations are discussed, along with a heuristic explanation for their different efficiencies. The conclusion is that an adaptive mutation matrix is best, where adaptation is based on the fitness distribution of the population, so that the mutation probability is implicitly time dependent. Furthermore, a directed mutation greatly improves the performance of all three models of implementation as this involves the imitation of the best chromosome by the less fit ones. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/CEC.2015.7256871 | 2015 IEEE Congress on Evolutionary Computation (CEC) |
Keywords | Field | DocType |
Genetic Algorithm,Mutation Matrix,Adaptive,Knapsack | Population,Mathematical optimization,Heuristic,Adaptive mutation,Computer science,Matrix (mathematics),Continuous knapsack problem,Artificial intelligence,Knapsack problem,Machine learning,Polynomial-time approximation scheme,Genetic algorithm | Conference |
ISSN | Citations | PageRank |
1089-778X | 1 | 0.39 |
References | Authors | |
1 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Qing Jie Li | 1 | 1 | 0.39 |
| Kwok Yip Szeto | 2 | 64 | 21.47 |