跳到主要內容

臺灣博碩士論文加值系統

(18.208.126.232) 您好!臺灣時間:2022/08/12 00:56
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:張幼蘭
研究生(外文):Yu-Lan Chang
論文名稱:動態平行模擬退火法
論文名稱(外文):Dynamic Parallel Simulated Annealing
指導教授:洪一峰洪一峰引用關係
指導教授(外文):Yi-Feng Hung
學位類別:碩士
校院名稱:國立清華大學
系所名稱:工業工程與工程管理學系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:37
中文關鍵詞:模擬退火法多向試驗叢集演算法循序平行運算平行模擬退火法
外文關鍵詞:simulated annealingsequentialparallel computingparallel simulated annealingmultiple trialsclustering algorithm
相關次數:
  • 被引用被引用:2
  • 點閱點閱:376
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
塔布搜尋(tabu search)、模擬退火法(simulated annealing)和基因演算法(genetic algorithm)是我們常用的搜尋方法。為了縮短演算時間,近年來,多處理器的平行演算理論衍生而出。
多向試驗(multiple trials)為眾多平行模擬退火法理論依據,而叢集演算法(clustering algorithm),它的要義就是讓所有處理器以共同一個目前解來產生很多鄰近解,並同時各自試驗其接受性。然後,依據某些事先訂定的規則,從這些可接受的鄰近解之中挑選一個來取代目前解。
叢集演算法的目的是增加找到可接受解的機率以加快演算。然而也可能找到比預期還多的可接受解,尤其當冷卻溫度很高的時候。而捨棄這些已計算出來卻沒有被挑選到的可接受解是一種浪費。另外,模擬退火法欠缺搜尋的廣泛性,這是叢集演算法所無法改善的。
本論文所提出的方法乃一開始使用數個獨立的循序(sequential)模擬退火法搜尋序列(search sequence)同時進行,當演算進行到某個條件時,即將這些獨立序列轉換成一個叢集(cluster)以從事多向試驗的叢集平行模擬退火法。我們期望這將會改善舊有平行模擬退火法的問題。
因為本論文所提出的方法可以動態分配運算資源,因此將之命名為動態平行模擬退火法(dynamic parallel simulated annealing, DPSA)。
Tabu search, simulated annealing and genetic algorithms are commonly used heuristic search methods. People attempt to improve these methods to reduce computation time. Therefore, multiple processors computation platform using parallel searching algorithms have been used and studied in recent decades.
One of the parallel simulated annealing algorithms is the clustering algorithm. The main idea of this method is to make each processor generate its own adjacent solution from the same current solution and compute the acceptance probability for each adjacent solution. Then, it decides which adjacent solution should replace the current solution according to pre-specified rules.
The purpose of using clustering parallel simulated annealing is to find an acceptable adjacent solution quickly. However, we may find too many acceptable adjacent solutions, especially when temperature is high. It is wasteful to compute discarded acceptable adjacent solutions except the solution that is chosen to replace the current solution.
Furthermore, simulated annealing somewhat lacks of diversified searching. We attempt to tackle this problem by using multiple processors to perform several simultaneously independent searching sequences at the same time, and later make them to turn to clustering mode at the time when computation process meet a certain criteria.
Because the method we discuss allocates computing resource dynamically, we call it Dynamic Parallel Simulated Annealing Algorithms (DPSA).
第一章 序論……………………………………………1
1.1 研究背景……………………………………1
1.2 研究動機……………………………………1
1.3 研究架構……………………………………2
第二章 文獻回顧………………………………………3
2.1 模擬退火法…………………………………3
2.2 平行模擬退火法……………………………8
2.2.1 分工演算法………………………………10
2.2.2 叢集演算法………………………………12
2.2.3 錯誤演算法………………………………15
第三章 方法建構………………………………………16
3.1 定義…………………………………………16
3.2 改進平行模擬退火法………………………19
3.3 DPSA的實施步驟……………………………21
3.4 DPSA之最佳設定……………………………23
3.5 DPSA的優點…………………………………28
第四章 實驗設計與分析………………………………29
4.1 問題描述……………………………………29
4.2 Message Passing Interface (MPI) ……29
4.3 實驗方法……………………………………30
4.4 結果與討論…………………………………31
第五章 未來展望………………………………………36
參考文獻…………………………………………………37
Aarts, E. and Korst, J. (1989), Simulated Annealing and Boltzmann Machines, New York, Wiley.
Azencott, R. (1992), Simulated Annealing: Parallelization Techniques, Wiley.
Durand, M. D. and White, S. R. (2000), “Trading accuracy for speed in parallel simulated annealing with simultaneous moves”, Parallel Computing, Vol. 26, pp.135-150.
Chu, K. W. , Deng, Y. F. and Reinitz, J. (1999), “Parallel simulated annealing by mixing of states”, Journal of Computational Physics, Vol. 148, pp.646-662.
Meise, C. (1998), “On the convergence of parallel simulated annealing”, Stochastic Processes and their Applications, Vol. 76, pp.99-115.
Janaki, D. , Sreenivas, T. H. and Ganapathy, S. K. (1996), “Parallel simulated annealing Algorithms”, Journal of Parallel and Distributed Computing, Vol. 37, pp.207-212.
林睿暘 (2001), “改進之平行塔布搜尋法”, 國立清華大學工業工程碩士論文.
翁民賢 (2001), “動態需求環境下之產能批量排程”, 國立清華大學工業工程碩士論文.
鄭守成 (2002), “C語言MPI平行計算程式設計”, 中華民國國家高速電腦中心.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top