Evolutionary Multi-Objective Optimization with Rake Selection
Multi-objective optimization is a critical area of research that has wide-ranging applications in various fields, including engineering, finance, and biology. It involves optimizing multiple objectives simultaneously, where the objectives may be conflicting, and it is not possible to improve one objective without compromising the other. In recent years, many new methods have been developed to solve multi-objective optimization problems. In this blog post, we introduce a new method called "rake selection," which is designed to efficiently solve multi-objective optimization problems.
Genetic algorithms (GAs) are well-suited for multiobjective optimization, as they operate based on a population of solutions rather than a single solution. This feature allows them to explore a larger search space and capture a diverse set of solutions that can cover a wide range of objectives.
In a typical GA, a population of potential solutions is generated and evaluated for their fitness based on multiple objectives. The fittest individuals are then selected to breed and produce a new generation of solutions, which undergo further selection and breeding until a satisfactory solution is found.
In multiobjective optimization, the fitness of each individual in the population is evaluated based on multiple objectives simultaneously. This allows the GA to capture a set of solutions that are not dominated by any other solution in the population, known as the Pareto-optimal front.
A solution is said to be Pareto-optimal if no other solution in the solution space dominates it. Figure 1 illustrates how a single solution can divide the objective space into four quadrants. The lower left quadrant contains solutions that dominate the considered solution; all solutions in this quadrant perform better with respect to both objectives. Solutions in the upper right quadrant are dominated by the considered solution. The upper left and lower right quadrants contain solutions that are not comparable to the considered solution. The set of non-dominated solutions consists of solutions that reside in these quadrants with respect to all other solutions.
Non-dominated Sorting
Most multi-objective optimization approaches, such as NSGA-II, rake selection, and selection based on the hypervolume indicator, begin with non-dominated sorting. This process involves sorting the population of the GA based on their non-domination rank. A solution is considered non-dominated if it is not dominated by any other solution. The first rank consists of all non-dominated solutions, and if these solutions are removed, the second rank is formed by solutions that are not dominated by any remaining solutions. This process continues until all solutions have been ranked. Figure 2 provides an illustration of how solutions are sorted into different ranks, with pink squares representing non-dominated solutions, orange squares representing solutions in the second rank, and grey squares representing solutions in the third rank. The non-dominated solutions in the first rank serve as the basis for a secondary selection process.
Rake Selection
One effective method for maintaining a uniform spread of solutions in objective space is known as rake selection. It is based on rakes that are positioned orthogonally on a rake base and extend into the area of the objective space where non-dominated solutions are located, see Figure 3. The rake base connects the optimal solutions with regard to the single objectives. For each rake, the closest point among the solutions with rank one is selected. If there are too few non-dominated solutions, solutions from the next rank may also be considered. The distances between points and lines can be computed efficiently, regardless of the dimensions of the objective space.
The optimal points that form the basis of the rake base can be computed by optimizing each objective individually and then computing the additional coordinate points in objective space using the fitness values for the remaining objectives. Alternatively, the rake base can be computed using the best solutions for each objective from the current population. This on-the-fly computation of the rake base can result in varying positions.
The efficacy of the rake approach is most pronounced when the Pareto front has a linear shape. As the front becomes more curved, the rakes become less effective in cutting it in parallel lines. However, an adaptation of the rake approach based on the shape of the current set of non-dominated solutions is possible. A similar mechanism has been proposed in [2] where a ratio is computed to adjust the rake distances at each step based on the connection between the rakes and the selected solutions. This approach allows for greater flexibility and effectiveness in handling Pareto fronts that are more complex in shape.
Experiments
The experimental results from typical runs of Rake Selection on multi-objective problems ZDT1 to ZDT4 are shown in Figure 4. The rake base connects the corner points, and the perpendicular lines define the rakes in the objective space. It is important to note that the rakes may not appear perpendicular to the rake base in this figure due to the unequal scaling of the axes.
After 1,000 iterations, corresponding to 50,000 objective function evaluations, the solutions are located on the rakes and the curves of the Pareto fronts. This demonstrates the effectiveness of the Rake Selection method in identifying solutions that are non-dominated and represent the best trade-offs between multiple objectives.
Conclusion
In summary, multi-objective optimization is a critical area of research with a wide range of applications. GAs are an effective tool for multi-objective optimization, as they operate based on a population of solutions and can explore a diverse set of solutions to capture the trade-offs between multiple objectives. Non-dominated sorting and rake selection are techniques that can be used to efficiently identify the Pareto-optimal front and select the best trade-off solutions. The experimental results show that the Rake Selection method is effective in identifying non-dominated solutions and achieving the best trade-offs between multiple objectives. Overall, multi-objective optimization is a powerful approach that can provide valuable insights into complex systems and inform decision-making processes.
All images unless otherwise noted are by the author.
References
- K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182–197, 2002.
- O. Kramer and P. Koch. Rake selection: A novel evolutionary multi-objective optimization algorithm. In Advances in Artificial Intelligence (KI), pages 177–184, 2009.
