0

I have a problem I want to solve using genetic algorithms (GA). You can simplify it to the following problem:

I want to optimize the car pool of a company, which means, the number of cars and car models. I already have a fitness function calcFitness(carList) which evaluates given setups like 'business car, transporter' or 'business car, business car, transporter'. Now, the question is, how do I solve this variable length problem using GA.

I have four ideas how you could tackle these problems generally:

  1. Perhaps somehow implement a GA allowing variable length chromosomes and solve the problem in a single run (Not sure if possible?)
  2. Estimate a maximum feasible number of cars (e.g. 20) and run a fixed-length GA for each car slot number from 1 to 20 and compare the 20 results
  3. Similar to #2, but without a fixed upper limit: You start off with 1 car and increase the number of slots until the best solution for the incremented number is worse than the preceding solution (gradient-based approach)
  4. Two stacked fixed-length GAs: A parent GA is solely responsible for optimizing the number of car slots and in its fitness function another GA optimizing the assignement of these slots is called

What do you think about these general approaches? Any other ideas or perhaps alternatives to GA for these variable length cases?

nkxandroid
  • 659
  • 1
  • 5
  • 14

1 Answers1

1

Variable length is certainly possible, and the most natural representation of this problem, it seems. Why would it be an issue? The only substantial difference will be in the crossover operation. While a single-point is trivial (you just pick a point within a, a point within b, and automatically get a variable-length offspring), it is often better to have continuous crossover which requires some more intuition with variable lengths. But that can be implemented later following a thorough separate testing.

Be prepared that your algorithm may find out that the better the chromosome the better results (under some combination of circumstances) it can produce. You don't get exponential bloat like in genetic programming (where the genotypes are trees rather than linear sequences) but still the chromosome length may start growing uncomfortably. You may need to account for that in the fitness function, or you may model a solution like #2 by rejecting candidates surpassing some limit right away.

The Vee
  • 11,420
  • 5
  • 27
  • 60
  • Thank you for your answer. What exactly do you mean with continuous crossover? And would you allow mutations to change the chromosome length? – nkxandroid Dec 05 '16 at 10:53
  • 1
    Yes, but the particular form that will be helpful depends on the problem. For example in my current GA I have multiple gene additions, deletions, replacement of k genes by l genes, ... but much of that is specific to the domain. Normally it should suffice to modify (mutate, add, remove) one at a time. – The Vee Dec 05 '16 at 11:12
  • 1
    Continuous crossover = without a predetermined number of crossing points. In fixed length, this would be flipping a biased coin at each position whether to cross or not. – The Vee Dec 05 '16 at 11:14