Page 91 - 49A Field Guide to Genetic Programming
P. 91

9.2 Keeping the Objectives Separate                            77


                                       Pareto Front


                   y   A                      1     Non dominated
                                                         points
                                                  2


                                            B            3
                                                                      x



            Figure 9.1: Two-dimensional example of Pareto optimality and the Pareto
            front, where the goal is to maximise along both the x and y axes. Solutions
            A and B do not dominate each other. However, solution B is dominated by
            solution 2. (Adapted from (Langdon, 1998).)


               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 sys-
            tem 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 (Gold-
            berg, 1989) was also performed. Preference information was also included
   86   87   88   89   90   91   92   93   94   95   96