Experiments in (distributed) evolutionary graph optimization

Dec.2004

The problem of planning an efficient rapid transit system for a city can be abstractly outlined using the language and tools of graph theory. The city area can be thought of as a collection of locations, or vertices. Every 10x10m square (for instance) on the city's territory can be assigned a vertex in a large graph. Edges in this graph will connect places between which it is possible to move quickly. For instance, adjacent vertices are connected by edges because one can easily walk from one place to the one next to it.

A rapid transit network can be represented as a set of edges in this graph, superimposed on the grid linking adjacent vertices. Each edge is a portal between two points, and can be thought of as corresponding to a stretch of rapid transit with no stops, like a subway line between two stations.

Most people's transport needs can be represented as a relatively small set of edges (source/destination pairs), each corresponding to a route which a person often needs to travel. The most common routes would be home-work, home-school, or those connecting home to concentrations of shopping and entertainment. In practice, such a set of routes can be acquired through a poll of the public.

The problem of measuring the efficiency of a rapid transit system now becomes a simple problem of graph theory. We need to add up the shortest paths taken to accomplish each of our set of common routes, and produce a score. To this score we can add the sum of edge lengths in the transit system. The lower this score, the more efficient the transit system is (common routes can be traveled faster, and total length of the system is less).

Problems which are difficult to programatically find an optimal solution for, but the fitness of whose solutions can be measured, are good candidates for evolutionary approaches. Given a set of routes and a graph representing a territory, we start with a random transit network and produce mutations based on simple transformations. Every subsequent generation starts with the previous generation's best scoring network.

In these visualizations of some early runs of a network-distributed evolutionary transit optimization system, red lines represent common routes and black ones represent rapid transit line stretches.

Generation 100 |
1000 |
10000 |

The distributed client-server model can be used to harness potentially vast computational power, and empower a city to find solutions for its problems using its own combined computational potential.