Search code examples
searchoptimizationgenetic-algorithmmutationcrossover

Searching 3D locations with genetic algorithms

I have a problem in which I want to search the best location in 3D space using a genetic algorithm, according to some fitness function. Because I am searching for a location, my chromosomes are represented by 3 floating point numbers. Currently, crossing over is done by taking 1 or 2 numbers from one parent and the remainder from the another parent.

When crossing over like this the next generation will only consist of positions that have a similar X, Y or Z coordinate as a chromosome in the starting population. Thus, not much variation is possible. My question is if this is best solved by using another representation for my chromosomes (eg. bits) so more crossover points are possible (also inside a floating point number), or is the better solution to set the mutation rate higher and let mutation add more variation in the next generation?

Solution

  • Assuming that there is spatial-correlation among the points in the 3D-space and the value of the fitness function, it would seem that your cross-over approach doesn't sound like it preserves the attributes of the parents that resulted in a good phenotype. Combining some of the axis coordinates at random is likely to result in a point that is placed far away from both parents, and it is thus worth as much as a random mutation step.

    I would to the following things:

    1. parthegenesis : allow single-parent to produce with probability p a child located in a random position within a 3D sphere of ray r centred on the parent. Useful for local adjustments

    2. crossover : the child is positioned on the straight line that joins the two parents, at a random percentage % value position.

      • depending on what you do, it might be useful to allow negative and >100% percentage values with small probability p'
      • you can apply the same sphere principle in this case too, either on the starting position of both parents or on the final position of the child, this would account for some randomness

    3. combination : with probability p'' the child follows your current crossover rule rather than my crossover definition

    4. random mutations : with probability p''' the child is the result of completely change one or more value of the parent at random

      • alternative: introduce new points at random locations along the search, to keep the diversity around a certain minimum value

    In some practical applications I preferred to not getting rid of the best 1% of the current population, just to keep the best genotypes so far around in the genepool.