What is an evolutionary algorithm for optimizing binary problems?

Question

In our program, we have been using the genetic algorithm since years for the only tasks for n variables, each of which has a fixed set of m possible values. This usually works well for ~ 1000 variables and 10 possibilities.

Now I have a new task in which for each variable there are only two possibilities (on / off), but I will probably have to solve systems with 10,000 or more variables. The current GA works, but the solution improves only very slowly.

All found EAs are designed more for continuous or whole / float problems. Which one is best for binary problems?

Answer 1

Like DonAndre, canonical GA was largely designed for binary problems.

But...

No evolutionary algorithm in itself is a magic bullet (if it does not have billions of years of work). The most important thing is your idea and how it interacts with your mutation and crossover operators: together they determine the “intelligence” of what is essentially a hidden heuristic search. The goal is for each operator to have a good chance of having offspring with similar parental suitability, so if you have domain-specific knowledge that allows you to do better than randomly flip bits or spliced ​​bistrons, use this.

The choice of roulette and tournaments and elitism are good ideas (perhaps preserving more than 1 is a black art that can say ...). You can also take advantage of the adaptive mutation. The old rule of thumb is that 1/5 of the offspring should be better than the parents - keep track of this amount and change the mutation speed accordingly. If the offspring is worse than mutating less; if offspring are consistently better than mutating more. But for the speed of mutation, an inertial component is required, therefore, it does not adapt too quickly, as in the case of any metaparameter, which makes it a black art. Good luck

Answer 2

Well, the genetic algorithm in its canonical form is one of the most suitable metaheuristics for binary solutions. The default configuration that I would like to try is a genetic algorithm that uses 1 elitism, and which is configured with a choice of a roulette wheel, a single-point crossover (100% crossover) and a bit-flip mutation (for example, a 5% chance of mutation ) I would suggest you try this combination with a modest population size (100-200). If this does not work, I would suggest increasing the population, but also changing the selection scheme to the tournament selection scheme (start by authorizing the binary tournament and increasing the size of the tournament group if you need even more pressure to choose). The reason is that with a higher population size, the suitability proportionality selection scheme may not provide the necessary amount of selection pressure in order to search for the optimal area.

As an alternative, we developed an extended version of GA and called it the “Genetic Sibling Selection Algorithm” . You can also try to solve this problem with a trajectory-based algorithm such as Tabu Search or Simulated Annealing, which simply uses a mutation to move from one solution to another by making small changes.

We have GUI-oriented software ( HeuristicLab ) that allows you to experiment with multiple metaheurists on several issues. Your problem, unfortunately, is not included, but it is licensed by the GPL, and you can implement your own problem there (even through the GUI, there is a way for this).

Answer 3

Why not try a linear / whole program?