# Constrained optimization

The goal of this lab exercise is to implement an evolutionary algorithm for constrained optimization problems. Likewise in NSGA-II, also here the whole task consists of only a few modifications to the standard genetic algorithm. In particular, you should implement two variants of the adaptive penalty:

If you do not complete all parts during the lab time, finish the work at home.

## Penalty weight adaptation

The weight $r_g(t)$ is adapted in time as follows:

• if the best solution in the last $k$ generations was always feasible, then the weight decreases as $r_g(t+1) = (1/\beta_1) * r_g(t)$
• if the best solution in the last $k$ generations was always infeasible, then the weight increases as $r_g(t+1) = \beta_2 * r_g(t)$
• otherwise, the weight remains the same, $r_g(t+1) = r_g(t)$

$\beta_1, \beta_2 > 1$ a $\beta_1 \neq \beta_2$

Implement this adaptive method.

 Input Current $r_g(t)$ Information about feasibility of the best solution in the last $k$ generations Updated weight $r_g(t+1)$

Implement a method for computing the overall fitness of the individual in the form $fitness(x) = f(x) + r_g(t)*\sum_{i=1}^{m+p}G_i(x)$, where

• $f(x)$ is the objective function value
• $G_i(x)$ is the size of the $i$-th constraint's violation
 Input $f(x)$ $G_i(x)$ pro $i = 1 \ldots m+k$ $r_g(t)$ fitness

Use the implemented adaptive penalty method within an evolutionary algorithm with the generational replacement strategy.

## Stochastic Ranking

This method first sorts individuals in the current population from the best to the worst one using a stochastic Bubble-sort-like procedure. On such a population, a standard tournament selection method can be applied to choose an individual on the basis the lower rank of the individual, the better the individual is.

Implement the stochastic Bubble-sort method, for details see the lecture slides.

 Input Population of individuals; each assigned its values $f(x)$ a $\sum_{i=1}^{m+p}G_i(x)$ Population sorted from the best to the worst one

Use the implemented stochastic ranking procedure together with the rank-based tournament selection within an evolutionary algorithm with the generational replacement strategy.

## Experimental evaluation

As the test problem we will use real-valued function optimizations. In particular, problems g06, g08, g11 a g24 from problem_definitions.

Use the already implemented operators for real-valued representation.

Problem g06:

• two non-linear inequality constraints $g_1(x)$ a $g_2(x)$
• optimum solution (the red point) is on the border between the areas of feasible and infeasible solutions
• areas of the constraints are shown in green

Problem g08:

• two non-linear inequality constraints $g_1(x)$ a $g_2(x)$
• optimum solution lies inside the feasible area

Problem g11:

• one non-linear equality constraint $h(x)$
• use the relaxation of the equality constraint in the form $g \equiv |h(x)|-\epsilon \leq 0$
• recommended value $\epsilon = 0.0015$, but you are free to try others as well

Problem g24:

• two non-linear inequality constraints $g_1(x)$ a $g_2(x)$
• area of feasible solutions consists of two disjoint parts
• optimum solution lies on the border of the feasible area

courses/a0m33eoa/labs/week_07.txt · Last modified: 2021/09/20 12:14 by xposik