Combinatorial optimization by stochastic evolution with applications to the physical design of VLSI circuits

In this thesis, a new general adaptive algorithm for solving a wide variety of NP-Complete combinatorial problems is developed. The new technique is called Stochastic Evolution (SE). The SE algorithm is applied to Network Bisection, Vertex Cover, Set Partition, Hamilton Circuit, Traveling Salesman, Linear Ordering, Standard Cell Placement, and Multi-way Circuit Partitioning problems. It is empirically shown that SE out-performs the more established general optimization algorithm, namely, Simulated Annealing.U of I OnlyETDs are only available to UIUC Users without author permissio