Computational Economics - Lecture 3: Multi-objective Algorithms

=multi-objective problem

-> multiple objectives instead of just one

Partial ordering vs. complete ordering

-> with one objective, complete ordering is possible; considering multiple objective, we (usually) cannot compare all

-> larger optimal set

A solution x is said to dominate a solution y if its objective values are all smaller or equal to the objective values of y and for one element (objective value) it is strictly smaller than the objective value of y.

= set of solutions P' that are not dominated by any member of the set of solutions P

= a solution which is not dominated by any other solution in the search space

necessary to distinguish between solutions in a non-dominated set

1. A priori: combine the different criteria into one fixed fitness function - weighted sum method
2. A posteriori: generate alternatives, let user decide afterwards
3. Interactive: involves decision-maker in the search process

= construct a weighted sum of the objectives and optimize

F(x) = sum (w_i * f_i(x))

• several alternatives can be generated using different weight vectors w
• difficulties: need to know w, non-uniformity in pareto-optimal solutions, inability to find some pareto-optimal solutions (concave parts)

1. use pareto-dominance to calculate fitness
2. use specific mechanism to maintain diversity in the population
3. EAs can search for the whole pareto-optimal set in one run

1. several optimal solutions
2. convergence of solutions
3. diversity of solutions
4. low computational time

must be changed a several objectives need to be considered

1. Rank = 1 + number of superior solutions
2. Non-dominated sorting: create subsets (fronts) that do not dominate each other -> non-dominated set = best subset, next one is second best etc.

• d_i = l + s, where s is the distance in x direction and l is the distance in y direction
• density estimation done in a particular front only
• solutions with more crowding distance are preferred

Every solution i has two attributes (used to rank in lexicographic manner):

1. non-dominated rank r_i
2. crowding distance d_i

-> in a binary tournament, a solution i wins a tournament with solution j if its r_i is better (smaller) than r_j or if they have the same rank r_i = r_j but solution i has the better (larger) crowding distance d_i

NSGA-II: = non-dominated sorting genetic algorithm

based on r_i and d_i