School Seminars and Colloquia

Genetic Algorithms and Configurations of Points

Discrete Structures and Algorithms (Seminar)

by Ruy Fabila-Monroy


Institution: Departamento de Matematicas, Cinvestav, Mexico
Date: Mon 28th February 2011
Time: 4:15 PM
Location: Hercus Theatre (L105, 1st floor) David Caro Building (Physics), The University of Melbourne

Abstract: Let S be a set of n points in general position in the plane (no three on a line). Many problems in combinatorial geometry deal with counting the number of certain geometric configurations in S. For example, if we draw all the line segments joining pair of points, how many of them will cross? Of course this number will vary depending on the actual choice of S. So normally lower and upper bounds are sought. A part of this process involves searching for sets of points achieving (or being close as possible) to these bounds. For example, searching for the set that minimizes the number of crossings in the above problem. This is in general a difficult task. Few techniques are known and in many cases there is a big gap between the theoretical bound and the best example. In this presentation, I will talk about how I have been using genetic algorithms to search for these extreme examples and the results obtained so far.

For More Information: contact: David Wood. email: woodd@unimelb.edu.au