Solving the Knapsack Problem with a Genetic Algorithm in Ruby
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.gitignore
README.md
genetic.rb
item.rb
knapsack.rb

README.md

Solving the Knapsack Problem With a Genetic Algorithm in Ruby

Overview

The Knapsack Problem is an optimization problem in which items that have both value and weight are placed into a "knapsack" with a weight limit. The goal is to maximize the value of the items in the bucket while keeping the total weight of the items below the threshold. A maximized solution can be approximated using a genetic algorithm.

Running

$ ruby genetic.rb [num_items] [num_knapsacks] [max_generations] [verbose=true|false]

For example:

$ ruby genetic.rb 100 100 1000 true

This would create an environment with 100 items, 100 knapsacks per generation, a maximum number of generations at 1,000, and would turn on the verbose output option.

Algorithm

Initialization

First the collection of items is generated using random values between 0 and 10 for weight, and random values between 0 and 100 for value. Then the original generation of knapsacks is created, with chromosomes randomly generated by a 10% chance of each gene being 'on' or 1.

Fitness function

The fitness function runs through each knapsack's chromosome, summing the weights and values if the gene is turned on for the current item. If the weight totals more than the maximum threshold then the value is set at zero, otherwise it is the value of the sum of the values of the items in the knapsack.

Roulette wheel

A roulette wheel algorithm is implemented to weight each knapsack proportionately to its part of the overall value of the entire population. Using this algorithm, the next generation is created.

Crossover

Single point crossover occurs at a randomized splice point on two randomly chosen knapsacks for each generation. Currently there is no crossover percentage, it just happens for two randomly chosen members of the population.

Mutation

Each knapsack's chromosome is iterated over and each gene has a 1% chance of flopping from 0 to 1 or 1 to 0.

Elitism

The best knapsack per generation is guaranteed to survive to the next generation, thereby guaranteeing that the best solution is never lost.