Simple GA for the knapsack problem

gaknapsack.js

/*
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');
}