Homework 2: EA for constrained optimizations

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.

Minimal requirements

Implement the following two approaches, if you have not done yet.

First approach uses the Stochastic Ranking method. You should already have an implementation of this method.

Second approach is based on the idea that the constrained optimization problem can be cast as a bi-objective optimization one with the following two optimization objectives:

  • the original objective function,
  • sum of all constraint violations.

Both objectives to be minimized.

Implement this approach with the use of the NSGA-II algorithm that you have already implemented.

Compare the two approaches on the real-valued function optimizations g06, g08, g11 a g24 that you used on the last lab exercise, problem_definitions.

Tasks beyond minimal requirements

Multi-objective approach with more objectives

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.

Vizualization

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

Comparison of the methods on more complex problems

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.

NSGA-II with modified tournament operator

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

Other constraint handling method

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

Other MOEA than the NSGA-II

Implement and test other MOEA than the NSGA-II and use it in the bi-objective or multi-objective mode.

Homework evaluation

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.

Minimal requirements

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, …).

What to submit

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 TSP 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 Pythou, 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 notebook (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.

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.

Scoring

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

Points For what
5 For fulfilling minimal requirements.
+1 For implementing the multi-objective (not only bi-objective) approach.
+1 For visualizing the achived results.
+1 For comparing the algorithms on more complex problems.
+1 For implementing the NSGA-II with the modified binary tournament operator.
+1 For comparing with some other constraint handling approach of your choice.
+1 For comparing with other than the NSGA-II multi-objective algorithm.
+1 … for any other interesting extension.
courses/a0m33eoa/hw/hw2.txt · Last modified: 2021/12/15 15:02 by xposik