Binary trie coding scheme: an intelligent genetic algorithm avoiding premature convergence

Abstract

The multi-dimensional knapsack problems (MKP) have a landscape called a rugged landscape, which may lead to local optima without any progress to optimal solution. Optimization requirement often involves searching amongst various solutions under multi-objective situations. Maintaining diversity and avoiding premature convergence while keeping the population size small and unique is one of the prime approaches to meet the requirements. In this paper, we propose a practical solution to the duplicity as well as premature convergence problem. We have introduced the concept of virtually compressed binary trie (VCBT) and tried to show that the VCBT can be naturally integrated with the genetic algorithm (GA) so that duplicates are completely eliminated while the trie size is kept reasonably small and practically feasible. Our binary trie coding scheme (BTCS) relies on problem-specific knowledge in fragmenting the search space into feasible and infeasible regions, and thus pruning the infeasible areas. Pruning of the trie occurs frequently and is dependent upon many parameters (other than the infeasibility) and the trie size is kept small throughout the whole process. Comparison tables are given for the performance of the BTCS and other good performing evolutionary algorithms found in literature for the MKP. Here, the optimization ability of the BTCS is compared against the GA given by Chu and Beasley; in particular, on a suite of standard MKP test instances from the OR library. The simulation results show that the proposed strategy significantly improves the computational efficiency of GA and generates robust and near-optimal solutions.

Keywords:

• genetic algorithm
• multi dimensional knapsack problem
• premature convergence
• binary trie coding scheme
• diversity

2000 AMS Subject Classifications :

• 68T20
• 68Q25

Acknowledgements

The revised manuscript is being submitted after incorporating the comments of the three referees. The modification and the improvements asked for have helped in providing a better insight and readability to the proposed BTCS. The algorithmic flow of procedures and the various routines with their dependencies have become more apparent. I would like to thank all the referees for sparing their valuable time and providing relevant comments which have definitely guided me in producing a refined article.