Distribution-based Grammatical Evolution of L-system Plants

Abstract

This thesis explores how to improve L-system plant generation using evolutionary algorithms (EAs). The plants should be aesthetically pleasing, varied, and have the ability to be combined with other plants.

Previous work has shown that simple D0L-systems, PD0L-systems and PDIL-systems can be evolved using EAs both autonomously and interactively. The L-system grammar used is simple, restricting the possible solutions. Additionally, often only parts of the grammar is represented in the genotype that is used in the EA, thus limiting the evolution.

More complex L-systems are required to generate aesthetically pleasing and varied plants, but this also complicates the generator and therefore also the evolution. To mitigate this issue, distribution-based grammatical evolution of L-systems (DGEL) is introduced and implemented. It is based on grammatical evolution (GE) of L-systems, but introduces a grammar distribution to control what parts of the grammar that should have a higher priority. Simulated annealing (SA) is used to optimize this grammar distribution so that DGEL can produce well performing plants in a more efficient manner. Additionally, using different optimized grammar distributions could allow for a larger variety of plants, while still keeping the quality up. Fitness metrics used were both adapted from the reviewed literature and created from scratch to assess the pleasingness of the generated L-system plants.

DGEL was evaluated in three parts: GE, SA and fitness function. Plain GE was tested against random brute-force to see if it has any benefit. SAs progress and produced grammar distribution was studied, and its performance was compared using both GE and random brute-force. The fitness metric was compared to human evaluations of generated L-system plants through analytical hierarchy process (AHP) and rank correlation statistics. Additionally, it was analyzed what factors humans think are important for distinguishing good from bad plants. GE was found to be superior to brute-force. SA was found to improve the efficiency of both brute-force and GE. Finally, the fitness function was found to not match the human evaluation, but a small correlation was still present.

The findings suggest that DGEL can improve the efficiency of generating L-system plants in a complex space. In a more general sense, the findings suggest that accompanying an EA with a probability distribution, and optimizing it using optimization techniques, can improve its efficiency in complex spaces, allowing for faster searches and more varied solutions.