Scalability problems of genetic search

In this paper, we study the efficacy of genetic search in the context of combinatorial optimization as the problem size and the difficulty of the problem instances are varied. In particular, we compare the performance of genetic algorithms at solving “simple” MAX-CLIQUE problem instances versus “difficult” ones, and show a pronounced qualitative difference in their typical behavior as the problem size is increased. We further investigate the sensitivity of genetic search to different resource-bound combinations, and their effects on the quality of the solution found. For difficult optimization problems where the building-block hypothesis may not be readily applicable, this yields a negative characterization of cross-over as a viable search procedure, given its high computational cost, but without clear benefit. This is compounded by the fact that for difficult problems, larger population sizes may be needed to exploit any structure that may be amenable to cross-over-driven search. As a reference point, performance results using simulated annealing are included in the paper