Djinni
2.2
|
Djinni is a set of C++ templates, source code and Python bindings which implements various things of use in the field of heuristic research. It was originally developed as a testbed for the Ohlmann-Thomas compressed annealing algorithm, and over time grew to be a general framework supporting annealing methods, direct computation, straight hill-climbing algorithms, and even the beginnings of genetic algorithms.
Unfortunately, in the never-ending war against code cruft we realized that we were adding cruft in the name of limiting it. Djinni 1.0 and 1.1 suffered from this, but with 2.0 we undertook a major rearchitecturing to clean up the code.
It almost succeeded. The limitations of 2.0 led us back to the drawing board for our 2.1 release, where we ditched much of the less interesting heuristics and instead focused on annealing methods.
Djinni is a set of C++ templates, source code and Python bindings to support the use of various kinds of annealing algorithms in an educational environment. It aims to be efficient, clean, and easy to understand. We hope it will be useful to students not only for the study of annealing methods in heuristic research, but as an example of a clean and extensible software architecture.
Djinni is small, weighing in at only about a thousand lines of code (and considerably more than that in documentation). We have deliberately avoided design decisions which would have increased its size. We understand that most of the UI students assigned to hack on Djinni are not computer science students, and for that reason we've done our level best to keep the codebase small enough so that a student can keep the entire thing in their heads at once. We are proud of Djinni's small size. When we started a couple of years ago it was hovering around 5000 lines of unmaintainable, inextensible, brittle and slow code. Today it's a fifth the size, an order of magnitude faster, and far easier to extend.
We hope Djinni will help you in your studies here at UI, and that you have as much fun learning it as we did in making it.
Robin Williams as a big blue cartoon guy living in a magic lamp, for starters. It's been Latinized, badly, as "genie". Early in development one of the developers was certain his computer was infested with a malevolent prankster that was making all the code malfunction. From there it was pretty easy to start anthropomorphizing bugs as Robin Williams comedy routines, and thus the name.
Djinni's annealing algorithms are built around two concepts: that of the penalty function and the solution type. In its broadest outlines, you create a penalty function object and a solution object, you pass them to the annealer, and then you call Annealer.solve(). From that point it's just a simple matter of getting answers out of it.
For instance, in C++:
#include "Annealer.h" #include "Penalties.h" #include "TSPRoute.h" int main() { // Create a new solution out of a solution space defined by a Dumas // dataset TravelingSalesman tsp("Dumas-1.set"); // Create a new Simulated penalty function Simulated sim(); // Create a new Annealer out of the two Annealer<Simulated, TravelingSalesman> annealer(sim, tsp); // Approximate a solution to the Traveling Salesman annealer.solve(); // Output the solution cout << annealer << endl; // ... and finally, return 0 and end. return 0; }
In Python it's almost as easy. It's complicated somewhat by the fact Python doesn't understand C++ template syntax, but we manage to make do. To see how C++ template types correspond with Python types, please see the file swig.i.
from Djinni import TSP, SA_TSP, Simulated tsp = TSP("Dumas-1.set") sim = Simulated() annealer = SA_TSP(sim, tsp) annealer.solve() print annealer.solution()
Because Python is t3h h4ppy. Because Python makes us smile. Because Python is a lot friendlier to program in than C++. And because we just think it's groovy.