Since selection does not depend upon how the members of the population are represented, the MOO techniques developed for other evolutionary algorithms can be easily adapted to GP.
The main idea in MOO is the notion of Pareto dominance. Given a set of objectives, a solution is said to Pareto dominate another if the first is not inferior to the second in all objectives, and, additionally, there is at least one objective where it is better. This notion can lead to a partial order, where there is no longer a strict linear ordering of solutions. In Figure 9.1 , for example, individual A dominates (is better than) individual B along the y axis, but B dominates A along the x axis. Thus there is no simple ordering between then. The individual marked 2', however dominates B on both axes and would thus be considered strictly better than B.
In this case the goal of the search algorithm becomes the identification of a set of solutions which are non-dominated by any others. Ideally, one would want to find the Pareto front, i.e., the set of all non-dominated solutions in the search space. However, this is often unrealistic, as the size of the Pareto front is often limited only by the precision of the problem representation. If x and y in Figure 9.1 are real-valued, for example, and the Pareto front is a continuous curve, then it contains an infinite number of points, making a complete enumeration impossible.
9.2.1 Multi-objective Bloat and Complexity Control
Rodriguez-Vazquez, Fonseca, and Fleming (1997) performed non-linear system identification using a MO GP system, where individuals were selected based on the Pareto dominance idea. The two objectives used were fitness and model complexity. In each generation individuals were ranked based on how many other individuals dominated them, and fitness was based on their rank. To better cover the Pareto front, niching via fitness sharing (Goldberg, 1989) was also performed. Preference information was also included to focus the selection procedure towards specific regions of the Pareto front. Hinchliffe, Willis, and Tham (1998) applied similar ideas to evolve parsimonious and accurate models of chemical processes using MO GP. Langdon and Nordin (2000) applied Pareto tournaments to obtain compact solutions in programmatic image compression, two machine learning benchmark problems and a consumer profiling task. Nicolotti, Gillet, Fleming, and Green (2002) used multi-objective GP to evolve quantitative structure-activity relationship models in chemistry; objectives included model fitting, the total number of terms and the occurrence of non-linear terms.
Ekart and Nemeth (2001) tried to control bloat using a variant of Pareto tournament selection where an individual is selected if it is not dominated by a set of randomly chosen individuals. If the test fails, another individual is picked from the population, until one that is non-dominated is found. In order to prevent very small individuals from taking over the population in the early generations of runs, the Pareto criterion was modified so as to consider as non-dominated solutions also those that were only slightly bigger, provided their fitness was not worse.
Bleuler, Brack, Thiele, and Zitzler (2001) suggested using the well-known multi-objective optimiser SPEA2 ( ?) to reduce bloat. de Jong, Watson, and Pollack (2001) and de Jong and Pollack ( 2003) proposed using a multi-objective approach to promote diversity and reduce bloat, stressing that without diversity enhancement (given by modern MOO methods) searches can easily converge to solutions that are too small to solve a problem. Tests with even parity and other problems were very encouraging. Badran and Rockett (2007) argued in favour of using mutation to prevent the population from collapsing onto single-node individuals when using a multi-objective GP.
As well as directly fighting bloat, MO GP can also be used to simplify solution trees. After GP has found a suitable (but large) model, for example, one can continue the evolutionary process, changing the fitness function to include a second objective that the model be as small as possible (Langdon, 1998). GP can then trim the trees while ensuring that the simplified program still fits the training data.
9.2.2 Other Objectives
Although much of the use of MOO techniques in GP has been aimed at controlling bloat, there are also genuinely MOO applications.
For example, Langdon ( 1998) made extensive use of Pareto dominance ranking to evolve different types of data structures. Up to six different criteria were used to indicate to what degree an evolved data structure met the requirements of the target data structure. The criteria were used in Pareto-type tournament selection, where, unlike in other systems, a second round of comparisons with the rest of the population was used as a tie breaker. The method successfully evolved queues, lists, and circular lists.
Langdon and Poli (1998b) used Pareto selection with two objectives, fitness and speed, to improve the performance of GP on the Santa Fe Trail Ant problem. Ross and Zhu (2004) used MO GP with different variants of Pareto selection to evolve 2-D textures. The objectives were feature tests that were used during fitness evaluation to rate how closely a candidate texture matched visual characteristics of a target texture image. Dimopoulos ( 2005) used MO GP to identify the Pareto set for a cell-formation problem related to the design of a cellular manufacturing production system. The objectives included the minimisation of total intercell part movement, and the minimisation of within-cell load variation.
Rossi, Liberali, and Tettamanzi (2001) used MO GP in electronic design automation to evolve VHDL code. The objectives used were the suitability of the filter transfer function and the transition activity of digital blocks. Cordon, Herrera-Viedma, and Luque (2002) used Pareto-dominance-based GP to learn Boolean queries in information retrieval systems. They used two objectives: precision (the ratio between the relevant documents retrieved in response to a query and the total number of documents retrieved) and recall (the ratio between the relevant documents retrieved and the total number of documents relevant to the query in the database).
Barlow ( 2004) used a GP extension of the well-known NSGA-II MOO algorithm (Deb, Agrawal, Pratap, and Meyarivan, 2000) for the evolution of autonomous navigation controllers for unmanned aerial vehicles. Their task was locating radar stations, and all work was done using simulators. Four objectives were used: the normalised distance from the emitter, the circling distance from the emitter, the stability of the flight, and the efficiency of the flight.
Araujo ( 2006) used MO GP for the joint solution of the tasks of statistical parsing and tagging of natural language. Their results suggest that solving these tasks jointly led to better results than approaching them individually.
Han, Zhou, and Wang (2006) used a MO GP approach for the identification of chaotic systems where the objectives included chaotic invariants obtained by chaotic time series analysis as well, as the complexity and performance of the models.
Khan ( 2006) used MO GP to evolve digital watermarking programs. The objectives were robustness in the decoding stage, and imperceptibility by the human visual system. Khan and Mirza (2007) added a third objective aimed at increasing the strength of the watermark in relation to attacks.
Kotanchek, Smits, and Vladislavleva (2006) compared different flavours of Pareto-based GP systems in the symbolic regression of industrial data. ? used MO GP to evolve protocols in sensor networks. The goal was to identify one node on a network to act as a communication relay. The following objectives were used: the number of nodes that know the designated node after a given amount of time, the size of the protocol code, its memory requirements, and a transmission count.
Agapitos, Togelius, and Lucas (2007) used MO GP to encourage the effective use of state variables in the evolution of controllers for toy car racing. Three different objectives were used: the ratio of the number of variables used within a program to the number of variables offered for use by the primitive language, the ratio of the number of variables being set within the program to the number of variables being accessed, and the average positional distance between memory setting instructions and corresponding memory reading instructions.
When two or three objectives need to be simultaneously optimised, the Pareto front produced by an algorithm is often easy to visualise. When more than three objectives are optimised, however, it becomes difficult to directly visualise the set of non-dominated solutions. ? proposed using GP to identify similarity mappings between high-dimensional Pareto fronts and 3-D space, and then use virtual reality to visualise the result.
9.2.3 Non-Pareto Criteria
Pareto dominance is not the only way to deal with multiple objectives without aggregating them into a scalar fitness function.
Schmiedle, Drechsler, Grosse, and Drechsler (2001) compared GP with four different MOO selection methods on the identification of binary decision diagrams. Linear weighting of the objectives was compared against: a) Pareto dominance; b) a weaker form of Pareto dominance where a solution is preferred to another if the number of objectives where the first is superior to the second is bigger than the number of objectives where the opposite is true; c) lexicographic ordering (where objectives are ordered based on the user's preference); and d) a new method based on priorities. The lexicographic parsimony pressure method proposed in (Luke and Panait, 2002; Ryan, 1994) is in fact a form of MOO with lexicographic ordering (in which shorter programs are preferred to longer ones whenever their fitness is the same or sufficiently similar). An approach which combines Pareto dominance and lexicographic ordering was proposed in (Panait and Luke, 2004).