7

I am struggling to create a simple example of a CMA-ES optimization algorithm in python. What is the most streamlined way to optimize the function x**2 + 2*y**2 -4*x*y - 0.5*y, subject to constraints -2<x<2 and -1<2*(x**2)*y<1, using the CMA-ES algorithm?

I looked into the DEAP library, but was not able to develop a cohesive attempt. I found their documentation less than intuitive. I also looked into the cma package, but it is not clear to me how I can implement constraints.

kilojoules
  • 9,768
  • 18
  • 77
  • 149

2 Answers2

4

In the python cma package you can specify bound constraints:

import cma
opts = cma.CMAOptions()
opts.set("bounds", [[-2, None], [2, None]])
cma.fmin(cost_function, x_start, sigma_start, opts)

For the second constraint, as it has been said before, it is not straightforward, but you can indeed assign high fitness values to out-of-domain candidate solutions. You would just have to tune cost_function here. These values can be very high (higher than any function value in the feasible domain) or depend on the constraint violation value.

There are several methods to handle constraint with penalties. In you case (small dimension) you can try with the simplest one.

paulduf
  • 163
  • 2
  • 14
3

I see your struggle with the DEAP docs. Nevertheless, I have written my own Evolutionary Computing library, and lately I have been using DEAP for many proof-of-concepts and I think they did a good job with it.

Going on, Let's take a look at the complete example. If you read the docs you will be confortable looking at the code. The problem size is the number of variables, so in your case if I understand correctly you would have N = 2 (x and y).

And you need your custom fitness function instead of benchamrks.rastrigin:

toolbox.register("evaluate", myownfunction)

The constraints are not implemented, but are an easy task. In the fitness function you can invalidate the individuals that violate the constraints (for instance by assigning a very high fitness, if minimizing) and in few generations your population should be free of invalids.

This would be the simplest approach with DEAP, but the deap.cma.Strategy class can be extended in order to override/extend any method, for instance, the generate method so that all the individuals in the initial population are valid.

rll
  • 5,509
  • 3
  • 31
  • 46
  • Can you elaborate a little more on how to implement constraints for someone who is not familiar with genetic algorithms, specifically CMAES? For instance, I would like to use pybrain to implement [CMAES optimization](http://pybrain.org/docs/tutorial/optimization.html#continuous-optimization), but it does not tell how to do constrained optimization that involves something like `1 - sum(x_guess)>0` –  Dec 13 '16 at 21:17
  • What I suggest is to implement the constraints on the fitness evaluation (on which you can deem an individual as invalid if some constraint is not met, by attributing for instance a very high fitness). You can also implement custom operators that will variate the individuals inside given boundaries only. The former is preferable in my opinion, and should be less expensive. – rll Dec 14 '16 at 14:12