Preying on optima: a predatory search strategy for combinatorial problems

One of the greatest testimonies to the power of natural selection comes from convergent evolution: nature has been able to find, over and over, given different `materials´, remarkable life-enhancing features like eyesight. The reason for the emergence of similar phenotypes in distinct species is simple: these designs have a high cost/benefit ratio for their owners. But evolutionary convergence is not restricted to physiological and anatomical features. Some behavioral sequences have also emerged many times across the animal spectra. A case in point: the area-restricted search behavior of predators. A great number of predators that are search-intensive display this behavior. We have developed a similar combinatorial area restricted search for optimization problems, referred to as predatory search. This strategy consists of scanning the solution space in a straightforward manner, but, as each new optima is found, restricting the consequent search to a very small area, probing for a consecutive optimization within the boundaries of that area. Numerical results are presented for the traveling salesman problem, and also for a new application on VLSI layouts. The results up to this point are encouraging. For instance, TSPs of up to 400 cities are optimally solved by predatory search. Furthermore, the vast majority of improvements are found within area-restricted search. Some additional aspects of this approach, such as the cycling behavior displayed, are also discussed