Recently, Palacky University Open Day happened to take place (20. 11. 2015). Together with colleagues, we decided to create small projects to promote the Computer Science Department in a way to attract high school students. Projects from colleagues included: LEGO-based Turing Machine (performing addition), OpenGL shading methods, Voxel graphics and reimplementation of Worms game among others. I had an idea to visualize the process of learning of solving of the Travelling Salesman Problem (TSP) using simple genetic algorithm (GA).
The developed application is an interactive tool for exploration of behavior of GA for TSP (see video). The left area shows the current state of genes in the population, the right panel consists of interactive control and performance plot.
The left area visualizes the presence of particular genes in population. Each gene corresponds to decision to travel from particular city, say A, to another one, say B. Thickness of blue lines represents the number of genes (in a population) for a given decision. The green line shows the solution by greedy nearest neighbor algorithm. The red line shows the best solution by genetic algorithm. Note that no special effects are used in the animation; it is direct reflection of the state of genes in population.
The right panel consists of configuration of optimization control, algorithm parameters, generation of problems and plot of performance. The meaning of parameters is the same as in standard genetic algorithm. For the crossover, Partially Matched Crossover was used (link; section: Crossover for Ordered Chromosomes). The performance plot shows the mean performance of an individual in GA (blue), performance of best individual in GA (red) and the distance given by nearest neighbor solution (green).
In general, when a new good gene is found (red line without thick blue line support), the good gene is quickly distributed to the population in successive generations. While this is good short-term decision, it is surely not an optimal strategy for larger problems. It can be observed that the diversity of the population is not preserved during evolution; individuals follow very closely the best one. While the algorithm was able to find better solutions than greedy algorithm, it is very likely that it suffers from premature convergence to local minimum. Therefore, it should be expected that in many cases it will be worse (empirically supported), converge too soon and be unable to improve its solution. In summary, it seems that preservation of population diversity should be essential part of standard genetic algorithm.
For interesting connection of genetic algorithms for evolution of neural networks, see Evolving Neural Networks through Augmenting Topologies. The paper shows quite general ideas how to perform meaningful crossover of tree-like structures and to increase the preservation of diversity of population.
hruskam.wordpress.com 