Shared Crossover Method for Solving Knapsack Problems

A surprising number of everyday problems are difficult to solve by traditional algorithm. A problem may qualify as difficult for a number of different reasons; for example, the data may be too noisy or irregular, the problem may be difficult to model; or it may simply take too long to solve. It’s easy to find examples: finding the shortest path connecting a set of cities, dividing a set of different tasks among a group of people to meet a deadline, or fitting a set of various sized boxes into the fewest trucks. In the past, programmers might have carefully hand crafted a special purpose program for each problem; now they can reduce their time significantly using a Genetic Algorithm (GAs). A Genetic Algorithm is key to solve knapsack problem, the goal of this paper is to show that successful Genetic Algorithm for solving and implementation knapsack problem, Genetic Algorithms are stochastic whose search methods model some natural phenomena. Genetic algorithms are relatively easy for finding the optimal solution, or approximately optimum value of NP-Complete problems, the coding scheme I’ve chosen for the knapsack uses a fixed-length, binary, position-dependent string, from the result, I find that crossover and mutation operation control exploration while the selection and fitness function control exploitation. Mutation increases the ability to explore new areas of the search space but it also disrupts the exploitation of the previous generation by changing them.