Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Simple GA for the knapsack problem
/*
Simple GA for the knapsack problem
Copyright (c) 2014 danglingfarpointer
This program is distributed under the MIT License:
http://opensource.org/licenses/mit-license.php
You need to issue `npm install underscore` before running this.
*/
// check the number of arguments
if (process.argv.length < 4) {
console.log('>>> Usage: node ' + process.argv[1] +
' /path/to/csv/file Capacity-value');
process.exit(1);
}
// parameters
var items = []; // items (price and weight)
var capatity = 0; // capacity
var nPopulation = 10; // # of individuals per generation
var nSurvive = 1; // # of individuals that survive
var nCrossover = 6; // # of individuals under crossover; should be an even number
var nMutation = 2; // # of individuals under mutation
var nGen = 100; // # of repetition
// read csv file
var fs = require('fs');
fs.readFileSync(process.argv[2], 'utf-8').
toString().split('\n').forEach(function (line) {
if (line.trim() === '') return; // ignore empty lines
var item = line.split(',');
if (item.length != 2) {
console.log('>>> The csv is invalid: ' + line);
process.exit(1);
}
var price = parseInt(item[0]);
var weight = parseInt(item[1]);
if (isNaN(price) || isNaN(weight)) {
console.log('>>> The csv is invalid: ' + line);
process.exit(1);
}
items.push({ price: price, weight: weight });
});
// read capacity
capacity = parseInt(process.argv[3]);
if (isNaN(capacity)) {
console.log('>>> The capacity value is invalid: ' + capacity);
process.exit(1);
}
var _ = require('underscore');
var util = require('util');
// make initial generation
var gen = makeInitialGen();
// main loop
var c = 0;
while (true) {
gen = sortByFitness(gen);
process.stdout.write(c + '\'th gen: ');
printStat(gen);
if (nGen == c++) break;
// survivers
var newGen = [];
for (var i = 0; i < nSurvive; ++i)
newGen.push(gen[i]);
// shuffle
gen = _.shuffle(gen);
// crossover
for (; i < nSurvive + nCrossover; i += 2) {
var children = crossover(gen[i], gen[i + 1]);
newGen.push(children[0]);
newGen.push(children[1]);
}
// mutation
for (; i < nSurvive + nCrossover + nMutation; ++i)
newGen.push(mutation(gen[i]));
// reproduction
for (; i < nPopulation; ++i)
newGen.push(gen[i]);
gen = newGen;
}
// here, gen[0] is the best answer.
process.stdout.write("The answer is: ");
printIndividual(gen[0]);
function makeInitialGen() {
var gen = [];
for (var i = 0; i < nPopulation; ++i) {
var individual = [];
for (var j = 0; j < items.length; ++j)
individual.push(0.5 <= Math.random());
gen.push(individual);
}
return gen;
}
function fitness(individual) {
var sumWeight = 0, sumPrice = 0;
for (var i = 0; i < items.length; ++i) {
if (individual[i]) {
sumPrice += items[i].price;
sumWeight += items[i].weight;
if (capacity < sumWeight)
return 0;
}
}
return sumPrice;
}
function sortByFitness(gen) {
return _.sortBy(gen, fitness).reverse();
}
function crossover(individualA, individualB) {
var cut1 = 0, cut2 = 0;
do {
var cuts = [rand(items.length) + 1, rand(items.length) + 1];
cut1 = _.min(cuts);
cut2 = _.max(cuts);
} while (cut1 === cut2);
var individualA1 = individualA.slice(0, cut1);
var individualA2 = individualA.slice(cut1, cut2);
var individualA3 = individualA.slice(cut2);
var individualB1 = individualB.slice(0, cut1);
var individualB2 = individualB.slice(cut1, cut2);
var individualB3 = individualB.slice(cut2);
return [ individualA1.concat(individualB2).concat(individualA3),
individualB1.concat(individualA2).concat(individualB3) ];
}
function mutation(individual) {
var copied = individual.slice(0);
// reverse a bit first
var i = rand(copied.length);
copied[i] = !copied[i];
// reverse all the bits based on probability
return _.map(copied, function (i) {
return rand(100) < 3 ? !i : i;
});
}
function rand(exclusiveMax) {
return Math.floor(Math.random() * exclusiveMax);
}
function printIndividual(individual) {
for (var i = 0; i < items.length; ++i)
process.stdout.write(individual[i] ? '1 ' : '0 ');
process.stdout.write(': ' + fitness(individual) + '\n');
}
function printGen(gen) {
for (var i = 0; i < nPopulation; ++i)
printIndividual(gen[i]);
}
function printStat(gen) {
gen = sortByFitness(gen);
process.stdout.write('max: ' + fitness(gen[0]) + ' ' +
'ave: ' + _.reduce(gen, function(sum, individual) {
return sum + fitness(individual);
}, 0) / gen.length + '\n');
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.