4

I am trying to use a genetic algorithm with DEAP to solve an optimization problem not all that different from a knapsack problem. A chromosome is represented by a vector of integers and the constraint is that the sum of the vector must be equal to some number X. It seems inefficient to deal with this in the fitness evaluation as there are relatively few crossovers/mutations that will lead to having a vector with sum exactly equal to X.

Instead it seems like I should be remapping crossovers and mutations to be within the bounded set of possible solutions. Should I be implementing this with decorators in DEAP or does anyone know of a better way to deal with this? Does anyone have a link to example code for this type of situation?

mitch
  • 1,870
  • 15
  • 12
scottyaz
  • 722
  • 7
  • 18

1 Answers1

7

One way to deal with this is at the variation level. You can decorate your favourite variation scheme with a decorator that remaps the invalid individuals to a valid domain.

There are multiple ways to efficiently handle numerical constraints when using evolutionary algorithms. I recommend you the following paper by Coello Coello which is an extensive survey on the different methods that can be used. The DEAP documentation has some code examples.

Carlos A Coello Coello, Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art, Computer Methods in Applied Mechanics and Engineering, Volume 191, Issues 11–12, 4 January 2002, Pages 1245-1287, ISSN 0045-7825, http://dx.doi.org/10.1016/S0045-7825(01)00323-1. http://www.sciencedirect.com/science/article/pii/S0045782501003231

Note that the consequences of a remapping should be taken in account as the crossover and mutation should transfer the genetic material from parent to offsprings. If your mapping shuffles too much the values, the result can be more or less a random search. Maybe you should try to define problem specific operators that produce less invalid individuals.

Also, Note that I'm a DEAP developer and the answer can also be found on the mailing list.

badgley
  • 1,657
  • 1
  • 13
  • 19
mitch
  • 1,870
  • 15
  • 12