Demo : Wireless Access Point Configuration Problem

Click here!

Comment: The solution in this demo is evolved using GP, but only for searching the variable number of locations, the connections between access points are created using the minimum spanning tree algorithm. For test problems, we can require GP to find the connections, which is much more challenging.

Brief Introduction to the Problem

A small city is planning to provide wireless Internet service to its citizens, located around the city map below (labeled as circled C). A bunch of wireless access points then need to be placed at several places to cover all the clients since each access point has limited service radius. To reduce the cost, a design solution with minimal number of access points and minimum length of the wires connecting those access points  is regarded as optimal. So the question is, how to decide the number of necessary access points and which place should we put.  To make it harder, we can ask to maximize the average signal strength at all clients, or add some constraints on the location of the access points.

This problem can be addressed using a variable length genetic algorithm. But if we constrain ourselves to Genetic Programming, it is aimed to provide a good benchmark problem for graph synthesis.