Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-26T23:08:23.226Z Has data issue: false hasContentIssue false
  • English
  • Français

Solving the 0/1 knapsack problem using an adaptive genetic algorithm

Published online by Cambridge University Press:  17 May 2002

ZOHEIR EZZIANE
ZOHEIR EZZIANE
Affiliation:
Faculty of Science Research Laboratory, Mathematics & Computer Science Department, United Arab Emirates University, United Arab Emirates
Get access Rights & Permissions [Opens in a new window]

Abstract

Probabilistic and stochastic algorithms have been used to solve many hard optimization problems since they can provide solutions to problems where often standard algorithms have failed. These algorithms basically search through a space of potential solutions using randomness as a major factor to make decisions. In this research, the knapsack problem (optimization problem) is solved using a genetic algorithm approach. Subsequently, comparisons are made with a greedy method and a heuristic algorithm. The knapsack problem is recognized to be NP-hard. Genetic algorithms are among search procedures based on natural selection and natural genetics. They randomly create an initial population of individuals. Then, they use genetic operators to yield new offspring. In this research, a genetic algorithm is used to solve the 0/1 knapsack problem. Special consideration is given to the penalty function where constant and self-adaptive penalty functions are adopted.

Keywords

0/1 Knapsack ProblemGenetic ProgrammingOptimizationSelf-Adaptive Penalty Functions
Type
Research Article
Information
AI EDAM , Volume 16 , Issue 1 , January 2002 , pp. 23 - 30
Copyright
© 2002 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)