1
$\begingroup$

I'm working in a project to create levels for a videogame using genetic algorithms.

I'm using a undirected graph to represent the level, each node represent a room and each room have a maximum of four possible connections (north, south, east, west). Also each connection just have one compatible connection (North <=> South , East <=> West), this mean you can't connect North with East for example, or North with North (Also a room can't be connected with itself).

Anyway, I already have a way to create the initial population with thoses restrictions, but now I'm thinking about the crossover function.

Let's say I crossover two graphs by cutting them in half and merging those halves, there are chances for a room to have more than four connection or using the same connection to connect two differents rooms.

So my question is, Should I create a crossover method to respect thoses restrictions or just to lower the score of thoses individuals?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Try out both. With genetic algorithms, is usually all but impossible to tell what will work beforehand. $\endgroup$
    – Raphael
    Commented Sep 11, 2017 at 5:47
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    Commented Sep 11, 2017 at 5:47

1 Answer 1

Reset to default
1
$\begingroup$

In my experience, a well crafted operator that avoids or repairs constraint violations is nearly always far preferable to one that relies on selection alone to find feasible solutions.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I completely agree. In many combinatorial optimization problems it's relatively easy to repair an infeasible solution. As a side note, it's interesting to note that using repaired solutions is related with Lamarckian evolution (which assumes that an individual can pass on characteristics that it has acquired during its lifetime to its offspring). $\endgroup$
    – manlio
    Commented Jan 9, 2018 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.