Metameric Representations in Evolutionary Algorithms

Optimization problems traditionally involve fixed-length representations to specify a description of a solution. Every solution defines the same number of design variables, resulting in a search space of fixed dimensionality. However, there also exist a large number of variable-length problems, many of which share a common representation. A set of design variables is repeatedly defined, giving the solution vector a segmented structure. Each segment encodes a portion, frequently a single component, of the solution. For example, in a wind farm design problem each segment may encode the position of a single turbine.We have proposed that such optimization problems, and their solution representation, be described as metameric. In biology this term describes anatomies that are composed of structurally similar, but not necessarily identical, segments. The term metavariable is used to describe a single segment of the encoded solution. Solution length, or the number of defined metavariables, can vary. Finding optimal solutions requires determining both the optimal length and metavariable composition.Using standard approaches to solve these problems requires an assumption of a fixed number of metavariables, in fact, no theory exists to define optimality for metameric problems. If the optimal number of metavariables is not known \textit{a priori}, this will lead to a sub-optimal solution. A better method is to allow the number of metavariables to vary. As the number varies, so does the dimensionality of the search space, making the use of gradient-based methods difficult. Evolutionary algorithms, using segmented variable-length genomes, are viable and frequently applied to such problems. This dissertation contributes in the following ways. First, specific definitions for metameric representations and problems are proposed, followed by an extensive survey of metameric problems in literature. It is demonstrated that many practical optimization problems have already been approached using evolutionary algorithms with metameric representations. While there is little cross-referencing among the cited articles, it is demonstrated that there is already a strong overlap in their methodologies. We propose that by considering problems using a metameric representation as a single class, greater recognition of commonalities and differences among these works can be achieved. A greater level of knowledge dissemination would increase the overall quality of the studies.This is followed by a study of the modifications required to adapt traditional evolutionary algorithms to metameric problems. A set of 6 benchmark metameric problems are created to assess the effectiveness of the new algorithms. First, several specific metameric representations observed in literature are explored. Variable-length genomes, where metavariables can be freely added or removed, are found to provide the greatest level of flexibility to the other evolutionary operators. Second, several crossover operators, used to generate new candidate solutions, are compared. The best operators are those which minimize the amount of disruption that occurs. Finally, length niching selection is proposed to guarantee diversity of solution lengths in the population. This increases the ability of the algorithm to identify optimal solution lengths. A new selection operator is also developed to be used in conjunction with length niching. It significantly improves the overall algorithm performance and has also been found to be effective on non-metameric optimization problems.The findings of these studies are used to create a general metameric evolutionary algorithm. This algorithm uses no problem-specific heuristics and can be applied to a broad range of metameric problems. Compared to traditional, fixed-length algorithms this is expected to provide a much better starting point for studies of metameric problems. It is applied to the design of an object with a lattice microstructure and found to improve on the results from the initial studies.