文章基本信息

标题：APPLICATION OF FITNESS SWITCHING GENETIC ALGORITHM FOR SOLVING MULTIDIMENSIONAL KNAPSACK PROBLEM
本地全文：下载
作者：KIM JUN WOO
期刊名称：Journal of Theoretical and Applied Information Technology
印刷版ISSN：1992-8645
电子版ISSN：1817-3195
出版年度：2019
卷号：97
期号：18
页码：4837-4849
出版社：Journal of Theoretical and Applied
摘要：Combinatorial optimization problems with constraints typically have many infeasible solutions, which cannot be used as a final solution. Therefore, metaheuristic algorithms for such problems must be carefully designed so that the infeasible solutions are dealt with appropriately. For example, repair and penalization are well-known feasibility handling approaches for genetic algorithm. However, those conventional approaches are problem-specific, which means that they must be appropriately tailored in order to be applied for solving a specific problem. On the contrary, fitness switching strategy is a general search strategy that can be used to develop genetic algorithms for solving a wide range of combinatorial optimization problems with constraints. Genetic algorithms based on fitness switching strategy need not to be equipped with repair or penalization procedures. Moreover, the strategy enables to utilize the infeasible solutions, typically ignored in conventional genetic algorithms. In order to investigate the usefulness of fitness switching strategy, this paper aims to extend the existing fitness switching strategy and develop a fitness switching genetic algorithm for multidimensional knapsack problem, which is a generalization of classical 0-1 knapsack problem. The experiment results demonstrate that fitness switching strategy can be used to develop effective metaheuristic algorithms for solving combinatorial optimization problems with multiple constraints.
关键词：Fitness Switching Strategy; Genetic Algorithm; Infeasible Solution; Multidimensional Knapsack Problem; Metaheuristic