README.md

AlgorithmBox

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

How to Use

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

• Simulated Annealing https://en.wikipedia.org/wiki/Simulated_annealing
• Tabu Search https://en.wikipedia.org/wiki/Tabu_search
• Hill Climbing / Iterative Improvement https://en.wikibooks.org/wiki/Artificial_Intelligence/Search/Iterative_Improvement/Hill_Climbing

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
});		

Experiment and Analysis

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)

Roadmap

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

Author

Denny C. Dai ([email protected] http://dennycd.me)

License

MIT License