algorithmbox

A metaheuristic algorithm development framework for solving discrete optimization problem

AlgorithmBox is an algorithm development toolkit for solving discrete optimization problems. It provides a framework for implementing metaheuristic algorithms in javascript and an empirical experiment library for testing the algorithm against a number of standard optimization problems. It can be installed as a Node.js module via

npm install algorithmbox

With algorithmbox, you can write a few lines of javascript code to implement a local search algorithm and run it against problems such as TSP and SAT. AlgorithmBox defined a number of basic stochastic local search algorithms including

It also provides spec for the following optimization problems

  • Travelling Sales Problem (TSP)
  • Satisfiability Problem (SAT)

To implement a hill climbing algorithm for solving TSP, do the following

//base algorithm definition of hill climbing 
var IIA = require('algorithmbox').IIA;
var defineClass = require('algorithmbox').defineClass;
 
//extend the framework-provided IIA definition 
var MyIIA = defineClass({
    name : "MyIIA",
    extend : IIA, 
    methods : {
        
        //given a candidate solution, return a set of neighborhood 
        //solutions that can be reached by 1-point mutation 
        'neighbors' : function neighbors(candidate) {
        
        }
    }
});

To load a TSP problem instance from a file such as tsplib, do

var TSP = require('algorithmbox').TSP;
 
//load tsp instance from file 
var raw = fs.readFileSync('tsplib/bayg29.xml');
 
//parse data and create a TSP instance  
var instance = new TSP(TSP.parseData(raw));

Now run the algorithm against the problem instance

 
//create a IIA algorithm with predefined terminate condition 
var algs = new MyIIA(instance, {
    'terminate_ls_steps' : 1000  //stop if maximum search steps reached 
});
 
//run the algorithm and monitor progress 
algs.run(function(step){
    console.log("step %d. best found solution: [%s]", step, algs.best_sol);
    if(algs.lo_trap)
        console.log("trapped");  //algorithm trapped in local optima 
});     

AlgorithmBox provides a simple framework for experimenting with different problem instances and algorithm parameter configurations . To define an experiment

var Experiment = require('algorithmbox').Experiment;
 
var config = {
    //test against TSP problem class 
    "tsp": { 
        //run each algorithm against each TSP instance loaded from a file 
        "instances" : ["bayg29.xml", "br17.xml"],   
        
        "algorithms": {
            //setting for a user-defined Simulated Annealing algorithm  
            "tsp_sa": [ 
                {
                    "boltzmanconst": 0.05,
                    "coolingscheme": "geometric"
                }, {
                    "boltzmanconst": 0.005,
                    "coolingscheme": "geometric"
                }, {
                    "boltzmanconst": 0.001,
                    "coolingscheme": "geometric"
                }, 
            ]
            //settings for a user-defined hill climbing algorithm 
            "tsp_iia": []
        },
        
        //total number of independent runs (with random restart) 
        "runs": 100,
 
        //terminate condition for each run 
        "max_ls_steps" : 5000
    }
};
    

To run the experiment and output the raw data result to a folder:

var session = new Experiment(config, "default.box");
session.run();

To analyze the experimental result, use the Analyzer to load the experiment raw data

var Analyzer = require('algorithm').Analyzer;
 
//load runtime quality distribution result for a specific algorithm runed against a specific problem instance 
var rqds = analyzer.get_runtime_quality("sat", "uf20-01.cnf", "gsat_iia", {"terminate_ls_steps" : 30});
var rqds2 = analyzer.get_runtime_quality("sat", "uf20-01.cnf", "gsat_iia", {"terminate_ls_steps" : 10});
var rsd = analyzer.get_runtime_solvability('sat', "uf20-01.cnf", "gsat_iia", {}, 85);
rsd = analyzer.get_runtime_solvability('tsp', "bayg29.xml", "tsp_iia", {}, 1800);
    

AlgorithmBox provides the following experimental analysis matrix

  • Runtime Quality Distribution showing how solution quality changes over local search steps
  • Runtime Solvability Distribution showing the probability of reaching a solution quality over local search steps
  • Problem Solution Quality shows the average solution of the algorithm across mutlitple problem instances over a number of indepedent runs

For further details, please look into the test case examples.

#Visualization and Ploting A sample visualization is provided (test/test_visualization.js) that demonstrate how to use Socket.IO and D3 to visualize the runtime quality distribution of a typical experiment. In the test folder, do

nodeunit test_visualization.js

In the browser, open

localhost:8888

and you would obtain the runtime quality distribution showing how solution quality (Y Axis for minimization problem) improves over runtime (X axis as local search steps)

AlgorithmBox is still a new concept under developement. Contributors are welcomed.

Denny C. Dai (dennycd@me.com http://dennycd.me)

MIT License