An analysis of evolutionary algorithm parameters to estimate the behavior of the algorithmic evolution: A case study using line following robots and simulations

Date
2018-05
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract

Background

Evolutionary Algorithms (EAs) are nature-inspired multi-objective optimization algorithms that evolve populations of tentative solutions through generations by using the basic principles of evolutionary biology as put forth by Charles Darwin and other evolutionary biologists. Two of the most fundamental problems associated with EAs are the parameter selection and the fitness function design. The former is a problem regarding how the EA parameters are selected, as this selection impacts the behavior and output of evolution. The latter is a problem associated with the level that a fitness function represents the task to be solved, as a higher fitness value should correspond to a better individual, which might not be the case at times. Even if the fitness function, which is a representation or a definition of the problem to be solved by the algorithm, is central to the EAs, its design, as well as the parameter selection, have traditionally been a cumbersome trial-and-error process due to the lack of generalized guidelines. In the literature, there have been many attempts to simplify, guide, or moderate the fitness function design. This dissertation explored these two problems and hence comprised of two major parts: The first part was a rigorous analysis of the interplay between various EA parameters, such as the natural selection rate, mutation rate, and mutation size. The second part is an investigation of a particular subset of the fitness function treatment methods known as “fitness shaping”. We implemented a novel approach to refine the goals of an EA fitness function. Additionally, we developed a task-specific fitness design methodology to simplify the fitness function design process.

Methods

A custom-built, three-wheeled Line Following Robot was used as the real-world robotic test platform. A custom Evolutionary Algorithm, which we called BIOMSEA, was developed in MATLAB™ 2014a environment and was employed to evolve a solution to the problem of line following. This algorithm simulated a kinematic representation of the real-world robot. The platform was tested on multiple real-world and digital tracks. A Java-based interface was developed to communicate the results of the off-line evolution to the robot in the real-world environment. Each individual utilized 8 black-and-white sensors that were connected to each of the right and left motors. The EA was used to evolve the Pulse Width Modulation (PWM) values that was stored in the genes of each individual. These PWM values corresponded to the speed information to be sent to each of the motors when any sensor became active. For the first part of the dissertation, EA parameters such as the natural selection rate, mutation rate, and mode of reproduction was analyzed. Possible correlations between these parameters and the behavior of evolutionary progress were discussed. For the second part, various fitness functions for the same line following task were analyzed to isolate the methodology to simplify the fitness functions in EAs. Task-specific and externally observable modifiers were implemented. The results were verified in the real-world robot to test for the Reality Gap Problem.

Results

In the first part of the dissertation, it was shown that natural selection rates in between 15% to 85% resulted in evolved behaviors that were comparably, if not equally successful, thus showing that a wide range of natural selection rates can be used to evolve similar results, giving flexibility to the selection. It was also shown that under an effective natural selection rate, the mutation rate did not influence the results as much, even if higher rates of mutation resulted in increased uncertainty. The trade-off between natural selection and mutation rates, arising from the mutation-selection balance, was successfully reproduced in algorithmic realm. It was shown that cloning was a more superior method to random filling in searching the fitness landscape, unless the random filling scheme was either supported by unlimited evolution, or limited evolution with backward motion prevention. In the second part of the dissertation, it was shown that fitness shaping can be a simple and efficient way to reduce fitness function complexity and designer bias (a priori knowledge) injection to the evolutionary process. The task-specific, externally observable modifiers were shown to be a simple and effective method to modify the goals of the robot in such way that task completion and speed can be significantly improved, 20-folds and 17-folds, respectively, without sacrificing free evolution. When controllers were implemented on the real-world robot, it was seen that the robot evolved using the simplest fitness function fortified with the modifiers can successfully finish the task, faster than any other robot evolved with other fitness functions, showing that the methodology can surpass the Reality Gap Problem.

Conclusion

Parameter sweep experiments were shown difficult yet enlightening as these types of experiments revealed the most information about the interconnectivity between parameters of an EA. These experiments showed promise in a generalized theory of algorithmic evolution, if they can be performed using more powerful computers, alongside with a well-studied platform. The implementation of parameter sweep experiments led to the realization that the more fundamental parameters of EA impact the behavior and outcome of evolution drastically, pushing our research direction towards a closer examination of the fitness functions. Through further analysis of these fitness functions, we showed that the simplest of fitness functions, known as aggregate functions, could be used with the modifiers that we developed in this study to improve the performance of Line Following Robots, and hopefully other platforms as well. A promising result of these experiments was that a potential simplification of fitness function design through the use of modifiers can potentially result in the ability of connecting the design parameters to the algorithm parameters, effectively generalizing and streamlining the fitness function design. This would accomplish the main goal and motivation of this dissertation. Even if definitive generalizations based on the results of this dissertation would be premature, this research showed that an optimal balance between a priori knowledge injection and free evolution can be achieved by fitness shaping. This was our main contribution to the literature, since the impact of task-specific goal-refiners on EAs have not been explored before. Moreover, this method offered an alternative and complement to the modern search methods, such as the Novelty Search and Surprise Search, without eliminating the use of objective functions.

Description
Keywords
Evolutionary algorithms, behavioral fitness, fitness shaping, tailored fitness, aggregate fitness, task completion, line following robot, evolutionary biology, evolution
Citation