andrei-straut/gaps

Genetic Algorithm Path Search

GAPS (Genetic Algorithm Path Search)

For a more detailed description, please see Wiki page
See the project in action
And because we shouldn't take anyone's word for it, latest build information

What is GAPS?

A webapp started as a small side project doing path searches in graphs using genetic algorithms

How does it work?

For a description on genetic algorithms, Wikipedia has it (loosely) covered. For graph theory, Wikipedia has it covered again. Putting the two and two together, and combining some great frameworks and technologies (see Thanks section), GAPS was born.

Just like any standard genetic algorithm. Picks a random number of initial paths, then it combines and mutates them until a good solution / stop condition is reached.

How well does it perform?

For small graphs (30 - 100 nodes, 100 - 1000 edges), in ~10% of cases it outperforms JGraphT's KShortestPath algorithm when it concerns path costs. In terms of runtime performance, it is slower, however, there's a chance of finding better paths.

In most cases, it loses to JGraphT, but barely, usually either tied up, or coming close behind.

What are the limits?

Starting from around 100 nodes / 1000 edges, it becomes a bit sluggish client-side due to graph rendering issues. However, if installed and run client-side (web interface is just a wrapper, websocket service means you can use GAPS simply as an API), it performs well even for very large graphs (100k nodes, 1M edges).

What are the future plans?

Please check the issues page for a list of upcoming features.

Special thanks

JGAP helped a lot to get stuff off the ground quickly, and the possibilities of customization are practically endless.

JGraphT, awesome framework for dealing with graphs.

Binary Cart, one of the best bootstrap templates out there, keep it up guys! 👍

Bootstrap - no explanation needed, it just works!

AngularJS was love at first sight, and a lasting relationship since then, 'nuff said

Vis.js, Because rendering graphs and visualizing data in the browser should be this easy

Angular UI notification because users should always be in the loop

Bootstrap slider and Bootstrap toggle two of the few plugins out there that actually work without extensive hacking or adaptation. Nice work!

Also, special special thanks to Pedro Serra for being that wall I could bounce ideas from, and generally for listening to me being geek for hours (ok, minutes at most) on end

gaps's Issues

Allow multiple edges between the same two nodes

Implement possibility of rendering and using multiple edges between the same two nodes (at least conceptually, if not visually as well).

Currently exists on server-side, however Infovis limitations prevent usage; workaround needed

Disable buttons while processing requests

At the moment, the "Generate" and "Evolve" buttons are kept as active when computing graph or evolving paths. This leaves the possibility of sending new processing requests while still computing the old ones, which in turn causes calculation and statistics problems on client side.

Disable the two buttons every time a processing request is sent, and enable them again when request is finished

Update display flags when re-computing graph, paths, or genetics

When (re)-computing and displaying statistics, there's an issue in which, if any statistic is collapsed (hidden), the flags get switched over and "On" state becomes "Off", Make sure to properly update the flags when computing statistics.

Reproduce (1):

• generate graph
• hide graph statistics section
• generate graph again
  Result: statistics show / hide button now has no effect

Reproduce (2):

• generate graph and evolve
• hide path and / or graph statistics
  Result: path statistics show / hide button has no effect.

Reproduce (3):

• generate graph and evolve
• hide path, graph or genetic statistics
• evolve graph
  Result: show / hide button state for any statistic is now flipped (hide does show, and vice-versa)

Reset / reinitiate slider when re-computing genetic evolution

On second or subsequent evolution runs (with graph re-computed or not), genetic statistics slider keeps previous datapoints for reference, which in turn causes JS errors

When re-evolving, first reset the slider

Update style due to small screens issue

On small screens, there is a horizontal scrollbar due 'page-inner' fixed margin-left (current 60px). Replace fixed margin values with auto and add a fixed padding-left. Also, this way the element width can be increased to 100% (current 95). Style should be the following:

#page-inner {
  width: 100%;
  margin: auto;
  background-color: #fff !important;
  padding: 10px;
  padding-left: 60px;
}

Add FAQ / Help page

Add an FAQ / help page with a tutorial, and / or details on application

Allow upload of custom graph

This is prioritary.
Allow the upload of custom graphs (Infovis JSON format) in order to have a possibility of graph re-use, as currently graphs are generated semi-randomly

Abort evolution when no initial population is found

At the moment, if no initial population can be generated (i.e. initial paths from source to destination), the GA still keeps trying to evolve data that isn't there. Make sure that the genetic evolution stage is not called if no initial paths are found.

Also throw an error / warning message if that happes

Add Unit Tests (Server-Side)

Do not limit selectable source and destination to integer

Now that graph upload is operational, remove requirement that source and destination IDs be integers, as we can perfectly have Strings.

Client-side, make a suggestion input text, and server-side should take a simple lookup in graph.getNodeById(string id) to make it work.

Also, nice-to-have would be a right-click on a node in the grap =>, pop-up => select as source / destination

Implement Breadth-First as alternative to current generation of initial populations

Currently, initial population is generated using a Depth-First Search (DFS) approach (no optimal search, we don't care about initial population performance).

However, this leads to little genetic variety (most paths will be approximately equal) and plateaus in genetic evolution. Combine DFS with a Breadth-First Search (BFS) when generating initial populations, in order to have more genetic variety (also, almost by definition, BFS paths should be much closer to optimum, at least in graphs with large number of edges).

An awesome nice-to-have would be a possible customization of the percentage generated with each approach (for instance, a way to specify "Generate 20% of initial pop using BFS, and 80% using DFS")

Request timeout

Some requests silently fail, without reasons why. Implement a timeout so that, when it finishes, the request currently in progress is discarded and an error message is shown

Performance comparisons

Implement performance comparisons for statistics, after evolving the paths and reaching the algorithm end.

A good metric would be comparison with JGraphT's KShortestPath search (already done server-side, data needs to be sent to client). This comparison should be done in both time and cost / fitness dimensions.

Also, mandatory additional metrics should be Djikstra and Bellman-Ford (cost / fitness dimensions)

Allow negative edge weights

Allow negative edge weights in graphs (should work out-of-the-box server side, currently disallowed for simplicity reasons)

Update wiki with new evolve API settings

Genetic Evolve request has changed, extra parameters were added. Document them

Reset comparison statistics when recomputing stuff

Comparison statistics reset was not implemented along with comparison itself, which will cause problems when re-computing genetic evolution without refreshing the page

Customize genetic algorithm parameters

Offer more possibilities of customizing the GA's parameters:

• Choice of crossover / mutator operators, and the order they run in
• Possibility to change crossover / mutator operators rate
• Possibility to change elitism