How to perform genetical evolution of python list's elements combination?

Question

I am a Python programmer that came to a situation in which i have to simulate genetical evolution of list's elements combination. The idea is presented below:

li #initial list
combinations=get_combinations(li) #not all possible combinations
results=[]
for c in combinations: results.append(do_stuff(li)) #do_stuff returns percantage of accuracu

At the end I have 2 lists: combinations, that keeps some of the combinations of li elements and results, that keeps a percantage value o accuracy for each combination. The idea is to select a combination with the highest accuracy.

It is impossible to check all combinations of li - that would take months of computing. I have to start from some random (I guess?) and then work my way to the best. What library should I use ? How to symulate evolution here ?

EDIT:

Alternatively: The set of elements evolves until it gets more than k% accuracy.

Answer 1

You have basically four possibilites:

1. Explore all combinations

This is, however, intractable as the number of combinations grows exponentially.

2. Random search

Generate random combinations until you get one good enough.

3. Local search

Start with some combination. Then make a small change to it. If the new one is better than the current one, make it the current one and repeat the process.

The above method can be vastly improved. One of the best such improvements (from my experience) is the Simmulated Annealing

4. Evolutionary algorithm

Use an algorithm that simulates the natural evolution. The most basic evolutionary algorithm looks something like this:

• Initialize a population of candidate solutions.

• Until the stopping condition is not met:

  1. Select two candidate solutions from the population with the better solutions having higher chance of being selected.
  2. (optional*) Recombine the two solutions (somehow, depends on the representation), i.e. put them together to create new solution(s).
  3. (optional*) Slightly change (or mutate) the new solution(s).
  4. Put the new solution(s) back into population, discarding some other solutions which are not good enough (to keep the population size constant).

• Either recombination or mutation must be present. Typically each is performed with some probabilty.

The challenge is to find a good representation allowing efficient recombination and mutation.