Application of Evolutionary Algorithm Strategies to Entity Relationship Diagrams. Master of Science thesis, Athabasca University.

Abstract

The purpose of this study is to examine programming techniques incorporating evolutionary strategies. It has been proposed that evolutionary strategies may provide alternative programming paradigms for finding solutions to problems of polynomial or NP-complete complexity. Disciplines such as Emergent Behaviour, Cognitive Science, Artificial Life, Complexity, and Bio-Informatics are working out the mechanics of how these systems operate. An attempt is made to demonstrate some of these evolutionary strategies through the creation of a program incorporating a genetic algorithm. The goal of the program is to generate aesthetically pleasing entity relationship diagrams. The crux of any genetic algorithm is to develop an appropriate fitness function. This task proves to be surprisingly difficult. Ironically, the task of finding the appropriate balance in the weighting of different fitness factors is in itself a problem that may be best addressed by an evolutionary algorithm. As a practical tool for the generation of aesthetically pleasing entity relationship diagrams, the ERD Viewer application was not overly successful. However, the implementation did provide a great deal of insight into the difficulties of specifying the rules when attempting to guide evolution. There are many suggestions for further development including a potential method to implement learning. Evolutionary strategies hold promise for exploring problem spaces where the number of potential solutions grows exponentially. The proof that these de-centralized, non-global, emergent processes do actually work surrounds us in the natural world. The prime examples are the two stochastic processes: evolution and learning. We are still in the early stages of determining how these techniques can be practically utilized in a programming environment.