0
$\begingroup$

I'm trying to use GA solve the quadratic assignment problem (QAP). We're planning on using it to be able to provide good solutions when using branch and bound becomes impossible, and as a requirement, I have to make it work as if it "improved" an existing solution.

The problem is of course in generating the initial population. I want to ensure diversity as well as good fitness, but the starting individuals, somehow, have to come from a single input individual (it's going to be a good one, in terms of fitness).

How should I go about this? I've thought about creating an initial population consisting on half (or some proportion) of individuals similar to the initial one, and then adding the other half of new randomly (using some heuristic) generated individuals, to combine my solution with other parts of the solution space. Is this a good approach? If so, anny recommendations on the random heuristic to search for the new random individuals?

$\endgroup$
1
$\begingroup$

One nice thing about QAP is that local search methods can take advantage of incremental evaluation of modified solutions, and GAs typically can't. So a pure GA needs O(n^2) time for every fitness evaluation, but a local search can do many fitness calculations in O(1) time, and the rest in O(n).

What I've often done for QAP is to employ something like a tabu search method to do much of the search. See Eric Taillard's paper on Robust Tabu Search for a good example of how to apply it to QAP in particular, including how to do the incremental fitness update.

You can generate multiple good initial points by running multiple tabu searches from random starting points, or you can integrate it directly into the GA as a hybrid method.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ We're leaving the genetic algorithm aside as this is a school project and we felt that going that way was a little risky. Although this article on the robust tabu search has been very helpful. Maybe if we have time we'll end up using both, but anyway that answered the question. Thanks! $\endgroup$ – Setzer22 Apr 20 '14 at 9:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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