Abstract
線路的K 塊分割的VLSI physical design中重要的步驟之一。此一步驟的工作是將一線路分割為K 塊，而且要使各塊之間的連線最少。此篇論文中我們研究了simulated evolution methodology 在partition problem 中的應用。首先我們整理出在設計此類演算法時所需考慮的幾項基本要素，如description of problem，jugement function ，important function，allocation function ，length of generation等。然後依照這些基本要素，設計了一個simulated evolution based K-way partition algorithm 。而且為了使收斂過程更為順利，而不會陷於某一local optimal 而出不來，我們提出了一新的mutation scheme ，以便可以更為有效能由local minimun 跳出。經由實驗的結果顯示，此一演算法所得的解與用simulated annealing algorithm 所得的解近似，然而在執行時間上，前者所需的時間較後者少了很多，近乎為後者所需執行時間的十分之一而已。