0
$\begingroup$

I'm creating a timetable generator using GA's, and I'm stuck in the crossover part.

Each generation, I just basically copy the best individuals (the 50% fittest individuals inside the population), and perform my crossover operator between them.

I'm using a 2 point crossover. I represent all my TT courses as a List. Each course has an assigned teacher, and an assigned position. The position is the index inside a 2D array. The first dimension represents times and the second represents classrooms.

When I perform the crossover, I choose a middle point inside the Course's list of each parent. Then I create 2 individuals mixing this Course's. If there are overlaps or other constraint violation, I repair the new individual.

My question is this, How can I ensure an optimal offspring?

Sometimes after the crossover and/or after the repair, the new offspring is not better than his parents. This makes the population gets stuck in high fitness values (I'm minimizing the errors, so, a low fitness score means a good individual), so, the GA never reach an optimal solution.

I've been reading an article about copy the fittest individuals in to the next generation, then perform the crossover, but I don't know if this is correct.

Improve this question
$\endgroup$
1
  • $\begingroup$ It's not necessary, but diversity should always be considered. Note that no matter what your replacement strategy is, an optimal solution is never guaranteed. $\endgroup$
    – aaaaajack
    Dec 29, 2016 at 8:57

2 Answers 2

Reset to default
1
$\begingroup$

GAs are heuristic algorithms. They don't guarantee optimality in any but the most trivial problems. Hence there are no strict rules how to implement them. What works and what doesn't depends your exact problem. Tuning the parameters of a GA is somewhat of a dark art and people turn to heuristics for tuning their heuristics.

Improve this answer
$\endgroup$
0
$\begingroup$

Heuristics don't guarantee optimizality, so, there is no way to know if your implementation will find the optimal of your problem everytime, and the only way to know how good is your heuristic, is to compare it against an exact algorithm for a good number of problems.

With that said, there are a lot of variations of Genetic Algorithms, and your first concern is about what is called Elitism, that is carrying over the best individuals from the population into the next generation.

There are other techniques, and varying them may lead you to get better results, but as @adrianN said, it's an art by itself.

For more information, a quick look at Wikipedia Genetic Algorithms page will give you some insight.

Improve this answer
$\endgroup$

Your Answer

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

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