<p>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).</p>

<p>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 <a href="http://www.sciencedirect.com/science/article/pii/S0167819105801474" rel="nofollow">Robust Tabu Search</a> for a good example of how to apply it to QAP in particular, including how to do the incremental fitness update.</p>

<p>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.</p>

CC BY-SA 3.0
2014-04-20T09:57:04.157Z
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!
Setzer22
CC BY-SA 3.0
2014-04-17T13:49:35.217Z
2014-04-17T13:49:35.217Z
deong
<p>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. </p>

<p>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).</p>

<p>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?</p>

<genetic-algorithms>
Initial population for a genetic algorithm from one individual
Setzer22
# Initial population for a genetic algorithm from one individual

(Asked by: username_0 on 2014-04-17)

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?

**Tags:** genetic-algorithms


---

## 1 answers

### Answer by username_1 on 2014-04-17. Score: 1 | Accepted answer

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](http://www.sciencedirect.com/science/article/pii/S0167819105801474) 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.

> **Comments:**
> **username_0**: 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!  

---

