I'm currently working on my undergraduate thesis where I develop a genetic algorithm that finds suboptimal 2D positions for a set of buildings. The solution representation is a vector of real numbers where every three elements represents the position and angle of one building. In that every three elements, the first element represents the x position, the second represents the y position, and the third represents the angle. A typical solution representation would look like:
[ building 0 x position, building 0 y position, building 0 angle, building 1 x position, ... ]
I have already managed to create a genetic algorithm that produces suboptimal solutions and it uses uniform crossover and discards infeasible solutions. However, it is only fast for small problems (e.g. 4 buildings), and adding more buildings makes it too slow to the point that I think it devolves into brute force, which is definitely not what we want. I tried to keep infeasible solutions into the population but with a poorer fitness before, but that only results in best solutions that is worse than when I threw away the infeasible ones.
Now, I am looking for a crossover operator that can help me speed up the genetic algorithm and allow it to scale to more buildings. I have already experimented arithmetic crossover and box crossover but to no avail. So, I am hoping that the community can suggest crossovers that I could try. I would also appreciate any suggestions to improve my genetic algorithm (and not just for the crossover operator).
Thanks!
Why not try a simple local search, where the moves allowed are (i) swapping the position of two buildings and (ii) rotating a single building?
What is the optimality criterion of building positions? In what sense one position/set of positions is better/worse from another?
Hello Sean Francis Nierva Ballais ,
as you want to speed up the algorithm, did you investigate which parts of the GA are causing the highest computational burden? Sometimes, checking the feasibility of the chromosomes can be time-consuming (depending on the problem setting). Thus, you may check if reducing the frequency of feasibility check to every X generations would help to reduce the computing time, while the infeasibility solutions would still bring additional genetic diversity to your population.
If you want to change your crossover operator, you may have a look at heuristic crossover as described in below paper. This approach could help to smooth the effect of the arithmetic operator when the two parent chromosomes are having very different values. Thus, the candidates with already a good fitness could be further improved by small increments in their direct solution space.
I hope it helps you. Let us know, how you solved the problem :)
Regards,
Thomas
Article CROSSOVER OPERATORS IN GENETIC ALGORITHMS: A REVIEW
Hi,
Since your representation is in R^d, I strongly advice you to look into Evolution Strategies (ES) instead of GAs.
ES are evolutionary algorithms that are naturally suited to evolve real-valued solutions and are state-of-the-art. They operate by updating a distribution and sampling new real-valued solutions from it.
The most famous approach is Hansen's CMA-ES:
https://en.wikipedia.org/wiki/CMA-ES
Chapter The CMA Evolution Strategy: A Comparing Review
A modern approach that can operate very efficiently if linkage structure is known (e.g., what variables should be sampled at the same time) is Bouter's RV-GOMEA:
Conference Paper Exploiting linkage information in real-valued optimization w...
If your problem has many local minima and you want to explore them, you can look into Maree's Hill valley clustering-based ES:
Conference Paper Real-Valued Evolutionary Multi-Modal Optimization driven by ...
- Badges
- Science topic
- Similar topics
- Computer Science