Lec 21 : Non-Dominated Genetic Algorithm: NSGA-II: Introduction

Introduction to EC Techniques for Multi Objective Optimization

Overview of the Session

• The session focuses on multi-objective optimization, specifically discussing the NSGA-II algorithm as a benchmark method.

• Previous sessions covered classical methods and introduced multi-objective optimization concepts.

Multi Objective Optimization Problem

• A multi-objective optimization problem aims to minimize multiple conflicting objectives under various constraints (inequality, equality, variable bounds).

• The formulation includes vectors for conflicting objectives and decision variables.

Approaches to Solve Multi Objective Problems

Preference-Based Approach

• This approach converts multi-objective problems into single-objective ones using higher-level information. It allows the use of any single objective optimizer for solutions.

Ideal Approach

• The ideal method generates multiple optimal solutions that lie on the Pareto front, allowing higher-level information to identify final optimal solutions for decision-making.

• Evolutionary computation (EC) techniques are suitable for this approach due to their population-based nature.

Framework for Multi Objective Optimization

Generalized Framework Steps

• Step 1: Solution representation is performed.

• Step 2: Various inputs like generation counter and maximum allowed generations are defined.

• Step 3: Random population initialization occurs, referred to as parent population.

• Step 4: Population evaluation involves assessing objective functions and constraints. Fitness assignment is crucial here due to multiple objectives involved.

Introduction to NSGA-II Algorithm

Features of NSGA-II

• Developed by Professor Deb and co-authors, NSGA-II stands for Non-dominated Sorting Genetic Algorithm II; it is a fast elitist multi-objective genetic algorithm.

• Key features include:

• Fast non-dominated sorting with computational complexity of O(MN²).

• Crowding distance measure preserves diversity with complexity O(MN log N).

• Modified crowded tournament selection operator integrates rank and diversity in selection processes.

Algorithmic Representation of NSGA-II

Steps in NSGA-II Algorithm

1. Initialization: Randomly initialize parent population.

2. Evaluation: Calculate all objectives and constraints; assign ranks using dominance depth method.

3. Selection: Use crowded binary tournament selection incorporating both rank and diversity.

4. Crossover & Mutation: Generate offspring population through these operations.

5. Merging Populations: Combine parent and offspring populations; re-evaluate fitness based on merged data before applying survival strategies until termination conditions are met.

Example of Biobjective Optimization Problem

Problem Definition

• The example involves minimizing two objectives:

• f_1(x) = x_1

• f_2(x) = 1 + x_2 - x_1^2

• Decision variable ranges are x_1 in [0, 1] , x_2 in [0, 3] .

• The problem has a non-convex Pareto optimal front which classical methods struggle with but EC techniques can handle effectively without limitations.(948)(992)

Dominance Depth Method in Fitness Assignment

Process Overview

• Assign fitness using Non-Dominated Sorting (NDS); rank each solution based on dominance depth across different fronts (F1, F2,...).

• Solutions ranked as non-dominated will be assigned rank one while others follow sequentially based on remaining members after removal from previous fronts.(1158)(1250)

Fast Non-Dominated Sorting Method

Stages Explained

Stage 1:

• For each member in the population:

• Identify dominated solutions (S_p).

• Count how many dominate it (n_p).

• Rank those with n_p = 0 as front one solutions.

Stage 2:

• Using previously identified fronts:

• Update counts based on dominated sets S_p from stage one.

• Assign new ranks iteratively until all fronts are established.(1348)(1608)

This structured markdown file provides an organized overview of key concepts discussed in the transcript regarding EC techniques for multi-objective optimization focusing primarily on the NSGA-II algorithm while ensuring easy navigation through timestamps linked directly to relevant sections of content within the video transcript provided above.

Understanding Multi-Objective Optimization and NSGA-II

Incrementing Solutions and Front Members

• The process begins with incrementing the index i to 2, leading to the identification of front members: 2, 4, 6, and 7 associated with step number 5.

• The algorithm then copies the current solution into front 3, marking its rank as 3. This indicates that three solutions have been sorted into different fronts.

Objective Space Arrangement

• A visual representation shows the arrangement of solutions across fronts: front 1 contains members (3, 8, and 5), while front 2 includes (2, 6, 7, and 4). Solution number 1 is categorized under front 3.

• Non-dominated sorting is crucial for identifying good versus bad solutions by categorizing them into different fronts. This method enhances convergence in multi-objective optimization.

Preserving Diversity in Solutions

• NSGA-II introduces crowding distance as a measure to maintain diversity among solutions within the same front. Different color codings are used to distinguish between various solution groups.

• Crowding distance assesses how crowded a solution is relative to its neighbors on the same front. Identifying neighbors is essential for this measurement.

Calculating Crowding Distance

• Step one involves determining how many solutions belong to a specific front (denoted as F). The cardinality of F is represented by small r.

• In step two, initial distances for each solution in F are set to zero. This establishes a baseline for further calculations.

Steps for Normalization and Distance Calculation

• Each objective is processed individually; extreme solutions receive an infinite crowding distance value to ensure their preservation during selection processes.

• For calculating distances between neighboring solutions based on objective function values, differences are measured along each objective axis.

Finalizing Crowding Distances

• Normalization occurs by dividing calculated distances by the range of values (f_max - f_min), ensuring unbiased results across varying scales of objectives.

• The cumulative crowding distance for each solution reflects its overall position within the hyper-cuboid formed by neighboring solutions.

Applying Crowding Distance Calculation

Example Application on Front Solutions

• An example illustrates applying crowding distance calculations specifically for front one containing three solutions: (3, 5, and 8).

Sorting Based on Objective Values

• For objective f1 values of these three solutions (0.139, 0.885, and 0.342), they are sorted from minimum to maximum resulting in order: (3 -> d_3 = ∞), (8), (5 -> d_5 = ∞).

Calculating Remaining Distances

• For solution number eight's crowding distance calculation using neighbors' values leads to d_8 being computed as equal to one after normalization steps.

Continuing with Second Objective Calculations

• Similar procedures apply when evaluating f2 values where sorting yields new extremes requiring infinite assignments again due to their positions.

Finalizing Crowd Distances Across Objectives

• After calculating both objectives’ contributions towards d_6 and d_7 respectively through neighbor assessments ensures comprehensive coverage across all dimensions.

Completing Crowd Distance Evaluation

Moving Forward with Other Front Solutions

• Transitioning focus onto front two which consists of four identified solutions requires initializing their crowd distances at zero before proceeding with calculations similar to previous examples.

Repeating Sorting Procedures

• As seen previously with f1 evaluations yielding sorted orders allows identification of extreme cases once more leading back into infinite assignments accordingly.

Detailed Neighbor Assessments

• Following through neighbor-based calculations provides final numerical outputs reflecting respective contributions towards overall diversity measures within selected populations.

Conclusion & Next Steps

Summary of Key Features Discussed

• Conclusively summarizing discussions around non-dominated sorting methods alongside crowding distance highlights critical features integral towards effective implementation strategies within NSGA-II frameworks moving forward into future iterations or simulations planned ahead .