The quadratic assignment problem (QAP) is one of the most challenging combinatorial optimization problems in existence and is known for its diverse applications. In this paper, we propose an evolutionary search heuristic (ESH) with population size equal to two, for solving QAPs and reported its performance on solution quality. The ideas we incorporate in the ESH is iterated self-improvement with evolutionary based perturbation tool, which includes (i) recombination crossover as perturbation tool and (ii) self improvement in mutation operation followed by a local search. Three schemes of ESH are proposed and the obtained solution qualities by the three schemes are compared. We test our algorithm on the benchmark instances of QAPLIB, a well-known library of QAP instances. The performance of proposed recombination crossover with sliding mutation (RCSM) scheme of ESH is well superior to the other two schemes of ESH. © 2007 IEEE.