Homework 2: EA for constrained optimization

The goal of this homework is to implement and compare two EA-based approaches for solving constrained optimization problems. In fact, you will mostly just reuse the implementations you have already coded within the past two lab exercises.

1. Implement the following two approaches, if you have not done yet.
   1. Stochastic Ranking method. You should already have an implementation of this method.
   2. Reformulate the constrained optimization problem as a bi-objective unconstrained optimization and solve the problem using NSGA-II algorithm that you have already implemented. The two objectives (both to be minimized) shall be
      • the original objective function,
      • sum of all constraint violations.
2. Compare the two approaches on the real-valued function optimizations g06, g08, g11 a g24 that you used in the lab exercise about constraints, problem_definitions.

Add to the comparison another MOEA approach that works with the following objectives

• the original objective function,
• $M$ other objectives, where each of them represents a size of a violation of one particular constraint.

When solving the transformed MO problem, you shall realize that each front of non-dominated solutions in NSGA-II may contain at most a single solution with zero constraint violation. I.e., in the whole NSGA-II population, there will be only a few feasible individuals. Propose, implement and test a method that allows a higher proportion of feasible individuals to be present in the population. (E.g., introduce some archive of feasible individuals and modify the breeding such that part of the new offspring uses only feasible parents, another part uses one feasible and one infeasible, etc.).

Implement a function that will graphically display the best obtained solutions in relation to the optimum solution and to the feasible and infeasible areas.

Compare the methods on at least one problem with more than 3 variables and more than 3 constraints such as g04, g05, g09 and g21.

Implement modified binary tournament operator for NSGA-II that takes into account feasibility of solutions, see slide “NSGA-II: Constraint Handling Approach” in MOEA slides. Compare NSGA-II using the modified binary tournament with the original two approaches.

Implement and test some other constraint handling method of your choice.

Implement and test other MOEA than the NSGA-II (e.g., MOEA/D) and use it in the bi-objective or multi-objective mode.

Likewise the first homework, also this homework has some minimal requirements: if you fulfill only them, you will still get the points required for this homework. Anything beyond these minimal requirements will bring you some additional points up to the maximum number of 10 points.

We shall deem this homework fulfilled, if you

• implement the two required approaches,
• compare the two required approaches on the problems g06, g08, g11 a g24,
• describe these algorithms and the achieved results concisely (in a report, in an Jupyter notebook, …).

Also, keep in mind that we primarily seek for the best feasible solution, i.e., the presented results shall not contain quality/objective value of infeasible candidates (or they shall be at least visibly marked as such). But of course, the algorithm can use quality of infeasible individuals quite freely.

You should submit your solution to task DU2 via a ZIP archive using BRUTE. The ZIP archive shall contain

• source codes of your implementation,
• README file, where you describe how to compile and run the code to get the results of algorithm A on a problem instance B,
• a short report with the description of your solution (see below).

During the evaluation, we may require you to demonstrate the functionality of your implementation of certail lab exercise (or via an online meeting). If you chose a programming languge other than Python, Julia, Java, or C/C++, the demonstration will be probably required.

Expected form of the report:

• It can be a PDF document with text and graphs, but
• a Jupyter (or Marimo or Pluto.jl) notebook as also acceptable, and
• it can be also a well-commented script that generates the outputs you want to show and describe.
• It should contain all results, tables, and graphs you want to show. It shall not require us to run the whole set of experiments to see the results. (But running a script to just load pre-computed experiment results and generate tables/graphs is acceptable.)

Expected contents of the report:

• Adequate description (not a source code listing) of used algorithms and operators.
• Description of the experimental setup (what parameter values were used for individual algorithms, how many evaluations/generations/minutes they were allowed to run, how many repetitions did you run, etc.)
• Reasonable comparison of the algorithms in tabular or graphical form and a short discussion of the results.
• Warning regarding possible imperfections of the experimental procedure.
• Explicit list of things done beyond the minimal requirements with the links to the places in your source code where their implementations can be found, and a proposal of their point evaluations.

For this homework, you can get up to 10 points.