search

CMA-ES / libcmaes

libcmaes is a multithreaded C++11 library with Python bindings for high performance blackbox stochastic optimization using the CMA-ES algorithm for Covariance Matrix Adaptation Evolution Strategy
Other
321 stars 78 forks source link

CMA-ES for mixed-integer optimization #163

Open cmastalli opened 7 years ago

cmastalli commented 7 years ago

I would like to know if this implementation (i.e. libcmaes) is able to solve mixed-integer optimization problems as is described here.

Thanks in advance

beniz commented 7 years ago

Hi, this is not implemented. This would be an interesting feature though. I'm not sure how much work would be required, though from the paper it seems that additions may not be too important.

@cmastalli if you decide to add it, please send a PR!

@nikohansen any advice on this ?

cmastalli commented 7 years ago

@beniz I would like to understand better what it might be the tasks in order to implement such algorithm, note that I'm not fully familiar with the structure of libcmaes.

These are the tasks from what I can understand by reading the code:

  1. Extend the libcmaes::CMAParameters class in order to accept mixed-integer decision variables.
  2. Sampling modification: add the shaded term of eq 1 (from the paper) here.
  3. Covariance modification: add the shaded term of eq. 5 (from the paper) here.
  4. Step-size modification: add the shaded term of eq. 6 (from the paper) here.

Please let me know if I'm right.

Thanks for a quick answer :)

nikohansen commented 7 years ago

My current hunch on the above linked integer handling algorithm is that it could be done simpler without losing too much of performance. I can't be much more specific though and it would need some work to figure out the specifics. This together with this would be a very simple implementation of integer handling by only increasing sigma in case the coordinate-wise standard deviation drops below 1 / (2 * N_int + 1), and I can't even say for sure that it is worse more often than not compared to the above mentioned paper.

EDIT: It would be a simple first step to make at least a direct comparison with the scenarios given in the paper.