臺灣博碩士論文加值系統

高效率模擬退火演算法的建構，乃是以傳統模擬退火法為基礎，運用各種不同的擾亂機制，使它可系統化的將現有的解，產生一組含有多個擾亂運算的可能解。再藉由直交實驗設計的因子分析，從一組可能的解，推理出一組含有多個擾亂運算的一個更佳的智慧型(IGM)新解。而採用適合直交實驗的擾亂機制，才能夠正確及快速的推理出鄰近區域好的擾亂組合，導引找到最佳值。
本論文中，我們選用了十種不同難度之因子程式來做實驗，經實驗結果顯示，使用直交模擬退火演算法所得到的解，確實較佳於傳統模擬退火法。然後再將它用於解VLSI 之平面規劃問題上。因此本篇論文，將以直交模擬退火演算法為主要演算架構，再以序對排列表示法，來描述模組的放置及改善糧]方式，最後實際達到 VLSI 最佳平面規劃之應用。本篇論文將採用MCNC 【Apte、Xerox、Hp、Ami33、Ami49】等模組電路的標準測試問題進行實驗，結果顯示本篇論文所提出的方法，與相關文獻的探討，在解大型的平面規劃問題上，將可有效的提升傳統式模擬退火法之效能。

Based on the conventional simulated annealing algorithm, the construction of high efficient orthogonal simulated annealing algorithm is proposed in this thesis that makes use of various perturbation mechanisms and systematizes the current solutions into a group of possible solutions with a few perturbation operations required. By using the factorial analysis in the orthogonal experimental design, an Intelligent generation mechanisms for new solution contained with a group of perturbation operations will be deduced from the former operation results. Eventually an accurate and best perturbation group in vicinity will quickly come into being and we can get the optimal solution.
In order to disclose the differences between the orthogonal and the conventional simulated annealing algorithm, This thesis first of all, has done severval experiments with operating ten factorial formulae with varied difficulties. It shown that the results from the former algorithm are better than from the latter one. Secondly, sequence pair representation is introduced into the VLSI floorplanning to reflect the placement of each construction group. Finally, five standard testing modules such as MCNC (Apte, Xerox, Hp, Ami33, Ami49)are evaluated. These results shown that the measures put forward in this thesis and other research products in related works will perfect the current measures effectively on the solution of grand floorplanning.

誌謝--------------------------------------------i
中文摘要---------------------------------------ii
英文摘要--------------------------------------iii
目錄----------------------------------------- iv
表目錄--------------------------------------- v
圖目錄--------------------------------------- vi
第一章 導 論--------------------------------- 1
1.1 研究背景及動機-------------------------- 1
1.2 研究的目的------------------------------ 1
1.3 文獻資料探討---------------------------- 1
1.4 論文的架構------------------------------ 2
第二章 模擬退火演算法理論與研究方法之探討---- 3
2.1 梯度搜尋法------------------------------ 3
2.2 機率函數-------------------------------- 3
2.3 模擬退火演算法的操作步驟---------------- 5
2.4 直交實驗設計---------------------------- 5
2.5 直交表的產生步驟------------------------ 6
2.6 直交因素實驗-----------------------------8
2.7 高效率的直交模擬退火法-------------------8
2.8 影響模擬退火演算法效率的因素------------ 8
2.9 直交模擬退火演算法的搜尋技巧------------ 8
2.10 智慧型新解產生機制(IGM)步驟------------- 11
2.11 高效率直交退火演算法的執行步驟---------- 11
第三章 平面規劃理論與研究方法之探討---------- 13
3.1 平面規劃結構的表示方式------------------ 13
3.2 兩者結構性之比較------------------------ 14
3.3 非分割性結構的表示法種類---------------- 14
3.4 擾亂的機制------------------------------ 16
3.5 序對的表示法---------------------------- 16
3.5.1 序對的編碼方式------------------------- 16
3.5.2 序對表示法對應平面之規劃--------------- 17
3.6 序對(Sequence pair)的擾亂方式----------- 19
3.7 設計合適擾亂方式------------------------ 21
3.8 使用IGM的swap 擾亂---------------------- 22
3.9 平面規劃演算法-------------------------- 22
第四章 實驗結果與分析------------------------ 24
4.1 測試的電路與環境設備之條件-------------- 24
4.1.1 實驗符號的定義------------------------- 24
4.1.2 因子測試程式實驗之條件----------------- 24
4.2 因子測試例實驗結果---------------------- 27
4.3 以MCNC標準測驗模組數目進行平面規劃測試-- 40
4.4 實驗結果分析---------------------------- 52
4.5 本文實驗測試結果與現今參考文獻最佳解比較表54
4.6 本文實驗測試結果與現今參考文獻最佳解改進比較圖--------------------------------------------54
第五章 結 論------------------------------- 55
5.1 結論------------------------------------ 55
5.2 未來之展望------------------------------ 55
參考文獻------------------------------------- 56

[1]林益廣(2002)以直交退火演算法解VLSI之平面規劃問題，逢甲大學資訊工程研究所碩士論文。
[2]Wong D.F.,and Xiaoping,T.,“FAST-SP:a fast algorithm for block placement based on sequence pair,”in Proc.Design Automation Conf.,2001.
[3]Xiaoping,T.,Ruiqi,T.,and Wong,D.F.,“Fast evaluation of sequence pair in block placement by longest common subsequence computation,”IEEE Trans.Computer-Aided Design of Itegrated Circuits and Systems,vol.20,no.12,2001.
[4]Zhang,O.,and Leung,Y.W.,“An Orthogonal Genetic Algorithm for Multimedia Multicast Routing,”IEEE Trans.On Evolutionary Computation, Vol.3,No.1,pp.53-62,1999.
[5]Tsai,J.T.,Liu,T.K.,and Chou,J.H.,“Hybrid Taguchi-Genetic Algorithm for Global Numerical Optimization,”IEEE Trans.On Evolutionary Computation, Vol.8,No.4,pp.365-377，2004.
[6]Ho,S.Y.,Shu,L.S.,and Chen,J.H.,“Intelligent Evolutionary Algorithms for Large Parameter Optimization Problems,”IEEE Trans.On Evolutionary Computation,Vol.8,No.6，pp.522-541,2004.
[7]Adler,D.,“Genetic Algorithms and Simulated Annealing:A Marriage Proposal,” IEEE Int.conf.Neural Networks, San Francisco,pp.1104-1109,1993.
[8]Mahfound,S.W.,and Golderg,D.E.,“Parallel Recombinative Simulated Annealing:A Genetic Algorithm,”Parallel Computing,Vol.21,pp.1-28,1995.
[9]Koakutsu,S.,and Kang,M.,“Genetic Simulated Annealing and Application to Non-slicing Floorplan Design,”5th ACM/SIGDA Physical Design workshop,Virginia,USA,Technical Report,1996.
[10]黃鈺婷(2005)使用模擬退火法-基因演算法結何部份因子設計法求解全域最佳化問題，立德管理學院應用資訊研究所碩士論文。
[11]Kirkpatrick,S.,Gelatt,C.D.,and Vecchi,M.P.,“Optimization by Simulated Annealing,”Science,Vol.220,pp.671-680,1983.
[12]Park,S.H.,Robust Design and Analysis for Quality Engineering. Chapman & Hall, 1996.
[13]Wong ,D.F., and Liu,C.L.,“A new algorithm for floor plan design, ”in Proc. ACM/ IEEE Design Automation Conf.,1986.
[14]Lai,M.,and Wong,D.F.,“Slicing tree is a complete floor plan representation,” in Proc.Design,Automation and Test in Europe Conf.,2001.
[15]Ginneken van, L.P.P.P., and Otten,R.H.J.M.,“Optimal slicing of plane point placements,”in Proc.Design Automation Conf.,1990.
[16]Chang,Y.C.,Chang,Y.W.，Wu, G.M.,and Wu,S.W., B*-trees:a new representation for nonslicing floor plan,”in Proc.Design Automation Conf.,1999.
[17]Mmurata,H.,Fujiyosh,K.,Nakatake,S.,and Kajitani,Y.,“VLSI module placement base on rectangle-packing by the sequence pair,”IEEE Trans. Computer-Aided Design,vol.15,1996.
[18]Guo,P.N.,Cheng,C.K.,and Yoshimura,T.,“An O-tree representation of non-slicing floor plans and its applications, ”in Proc.Design Automation Conf.,1999.
[19]Homaifar, A.A., Lai, S.H.Y., and Qi, X.,“Constrained Optimization via Genetic Algorithms,”Simulation,vol.62,N0.4,1994.
[20]林良哲(2002)以序列對表示法解非切割性結構叢聚限制的平面規劃問題，南華大學資訊管理學系碩士論文。
[21]Adya,S.N.,and Markov,I.L.,“Fixed-outline floor planning through better local search Computer Design, ”in Proc.Int.Conf.Computer Design,2001.
[22]蔡明豪(2000)以基因演算法為主的巨型模組平面規劃，逢甲大學資訊工程研究所碩士論文。
[23]劉冠群(2000)基於基因演算法的標準元件排列置放，逢甲大學資訊工程研究所碩士論文。
[24]Leung,Y.W.，Wang,Y.,“An Orthogonal Genetic Algorithm with Quantization for Global Numerical Optimization,”IEEE Trans.On Evolutionary Computation, Vol.5, No.1,pp.41-53,2001.
[25]Rebaudengo, M.，and Reorda,M.S.,“Floor plan area optimization using genetic algorithms,”in proc. Design Automation of High performance VLSI Systems,1994.
[26]Ohmura,T.,Fujiyoshi,K.,and Kodama,C.,“Area optimization of packing represented by sequence-pair, ”in Proc.Circuit and Systems Conf.,2000.
[27]Lin,C.“Amore efficient sequence pair perturbation scheme,”in Proc. ProRISC99,1999.
[28]Kiyota K.,and Fujiyoshi,K.,“Simulated annealing search through general structure floor plans using sequence-pair,”in Proc.Circuit and Systems,vol.3,2000.
[29]URL:http://www.cse.ucsc.edu/research/surf/GSRC/prograss.html
[30]URL:http://www.itl.nist.gov/div898/handbook/index.html
[31]Ho, S.Y., and Lin, Y.K.,“Orthogonal Simulated Annealing for Floorplaning,”7th Artificial Intelligence and Applications Conference,Taichung,R.O.C,2002.