This paper deals with the problem of linear gate assignment in two layout styles: one-dimensional logic array and gate matrix layout. The goal is to find the optimal sequencing of gates in order to minimize the required number of tracks, and thus to reduce the overall circuit layout area. This is known to be an NP-hard optimization problem, for which no absolute approximation algorithm exists. Here we report the use of a new optimization heuristic derived from statistical mechanics-the microcanonical optimization algorithm, /spl mu/0-to solve the linear gate assignment problem. Our numerical results show that /spl mu/0 compares favorably with at least five previously employed heuristics: simulated annealing, the unidirectional and the bidirectional Hong construction methods, and the artificial intelligence heuristics GM Plan and GM Learn. We also show how the algorithm is able to outperform microcanonical annealing. Moreover, in a massive set of experiments with circuits whose optimal layout is not known, our algorithm has been able to match and even to improve, by as much as seven tracks, the best solutions known so far.

When searching for prey, many predator species exhibit a remarkable behavior: after prey capture, the predators promptly engage in "area-restricted search", probing for consecutive captures nearby. Biologists have been surprised with the efficiency and adaptability of this search strategy to a great number of habitats and prey distributions. We propose to synthesize a similar search strategy for the massively multimodal problems of combinatorial optimization. The predatory search strategy restricts the search to a small area after each new improving solution is found. Subsequent improvements are often found during area-restricted search. Results of this approach to gate matrix layout, an important problem arising in very large scale integrated (VLSI) architectures, are presented. Compared to established methods over a set of benchmark circuits, predatory search is able to either match or outperform the best-known layouts. Additional remarks address the relation of predatory search to the "big-valley" hypothesis and to the field of artificial life.

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.