Analyzing Directed Acyclic Graph Recombination

C. Cotta, J.M. Troya

Computational Intelligence: Theory and Applications, B. Reusch (ed.), Lecture Notes in Computer Science 2206, pp. 739-748, Springer-Verlag Berlin, 2001

© Springer-Verlag Berlin Heidelberg 2001. All rights reserved.


This work studies the edge-based representation of directed acyclic graphs, as well as the properties of recombination operators working on it. It is shown that this representation is not separable, and the structure of the basic information units that must be processed in order to maintain feasibility of the solutions is described. As an experimental analysis indicates, a recombination operator using these units has sub-quadratic complexity in the graph size. It is also shown that a standard gene-transmission recombination operator is biased to produce solutions of lower edge-density than the parents' average. An unbiased allelic recombination operator provides better results on an ad-hoc test problem.

Download BibTEX entry
Download PDF version (279K)
[Back to publications page].