# Genetic Algorithm

November 18, 2016

I created a program to solve the knapsack problem with genetic algorithm.

Genetic Algorithm (GitHub)

#### What is Genetic Algorithm?

Genetic algorithm is an algorithm which prepares a plurality of “individuals” which represent data (candidate solutions) by genes, and selects individuals with high fitness preferentially and searches for solutions while repeating operations such as crossover (recombination) and mutation.

Genetic Algorithm

#### What is Knapsack problem?

The knapsack problem is a problem to find the maximum sum of the value of items that can be packed into knapsack when packing multiple items of which value and weight are fixed in a certain knapsack.

Knapsack Problem

#### How to use?

This is easy to use.

#### Data Input

The data of items are entered in the following format. Enter one item per line, first enter the weight, then the value.

$cat data.txt 168 496 10 45 145 325 60 347 10 61 124 486 124 446 105 22 126 110 184 475 #### Program usage Just pass the item data and some parameters simply. 1. Initialize GeneticAlgorithm with data of items and some parameters. 2. Call fit to solve a knapsack problem. 3. Call result to show related information of the solution. #### Parameter Parameter Meaning Mandatory Default data Information on candidate goods to be put in the knapsack. The format of the data is as described above. true - LIMIT The maximum weights which can be packed in knapsack true - POOLSIZE The number of genes false 50 LAST The count of genetic manipulation false 100 RATE Probability of mutation false 0.01 #### Example A concrete example is as below. const fs = require("fs") const GeneticAlgorithm = require("./genetic-algorithm") const LIMIT = 300 const POOLSIZE = 50 const LAST = 100 const RATE = 0.05 const data = fs.readFileSync("data.txt").toString() const ga = new GeneticAlgorithm(data, LIMIT, POOLSIZE, LAST, RATE) ga.fit() console.log(ga.result()) When executed, information of the solution is shown as below. $ node example.js
{
maxValue: 1038,
totalWeight: 268,
parcels: [
{ weight: 10, value: 45 },
{ weight: 10, value: 61 },
{ weight: 124, value: 486 },
{ weight: 124, value: 446 }
]
}