Genetic algorithm on a knapsack-alike optiproblem

Question

I have a optimzation problem i'm trying to solve using a genetic algorithm. Basically, there is a list of 10 bound real valued variables (-1 <= x <= 1), and I need to maximize some function of that list. The catch is that only up to 4 variables in the list may be != 0 (subset condition).

Mathematically speaking: For some function f: [-1, 1]^10 -> R min f(X) s.t. |{var in X with var != 0}| <= 4

Some background on f: The function is NOT similar to any kind of knapsack objective function like Sum x*weight or anything like that.

What I have tried so far:

Just a basic genetic algorithm over the genome [-1, 1]^10 with 1-point-crossover and some gaussian mutation on the variables. I tried to encode the subset condition in the fitness function by using just the first 4 nonzero (zero as in close enough to 0) values. This approach doesn't work that well and the algorithm is stuck at the 4 first variables and never uses values beyond that. I saw some kind of GA for the 01-knapsack problem where this approach worked well, but apparently this works just with binary variables.

What would you recommend me to try next?

Lorola

I have no idea about genetic algorithms but you could try to encode the problem differently: selecting 4 real values and 4 distinct integers in the range 0-9. – Shf

The total number of solution is less than 10^4, why not use enumeration? Is this homework? – Pylorus

Answer 1

If your fitness function is quick and dirty to evaluate then it's cheap to increase your total population size.

The problem you are running into is that you're trying to select two completely different things simultaneously. You want to select which 4 genomes you care about, and then what values are optimal.

I see two ways to do this.

1. You create 210 different "species". Each specie is defined by which 4 of the 10 genomes they are allowed to use. Then you can run a genetic algorithm on each specie separately (either serially, or in parallel within a cluster).

2. Each organism has only 4 genome values (when creating random offspring choose which genomes at random). When two organisms mate you only cross over with genomes that match. If your pair of organisms contain 3 common genomes then you could randomly pick which of the genome you may prefer as the 4th. You could also, as a heuristic, avoid mating organisms that appear to be too genetically different (i.e. a pair that shares two or fewer genomes may make for a bad offspring).

I hope that gives you some ideas you can work from.

Bamberg

Answer 2

You could try a "pivot"-style step: choose one of the existing nonzero values to become zero, and replace it by setting one of the existing zero values to become nonzero. (My "pivot" term comes from linear programming, in which a pivot is the basic step in the simplex method).

Simplest case would be to be evenhandedly random in the selection of each of these values; you can choose a random value, or multiple values, for the new nonzero variable. A more local kind of step would be to use a Gaussian step only on the existing nonzero variables, but if one of those variables crosses zero, spawn variations that pivot to one of the zero values. (Note that these are not mutually exclusive, as you can easily add both kinds of steps).

If you have any information about the local behavior of your fitness score, you can try to use that to guide your choice. Just because actual evolution doesn't look at the fitness function, doesn't mean you can't...

Sizing

This sounds interesting, i suppose I could encode it as (list of positions, list of values) and use the crossover method suggested by @Bamberg above. – Lorola

Answer 3

Does your GA solve the problem well without the subset constraint? If not, you might want to tackle that first.

Secondly, you might make your constraint soft instead of hard: Penalize a solution's fitness for each zero-valued variable it has, beyond 4. (You might start by loosening the constraint even further, allowing 9 0-valued variables, then 8, etc., and making sure the GA is able to handle those problem variants before making the problem more difficult.)

Thirdly, maybe try 2-point or multi-point crossover instead of 1-point.

Hope that helps.

-Ted

Snatch