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 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 }
]
}
``````