以類神經網路作分散式系統中的工作分配

Abstract

模擬生物神經細胞動作的類神經網路模型，在最近的幾年之中常被廣泛地應用在許多 的領域上，而且成功地解決了一些組合最佳化的問題(Combinatorial Optimmization Problem)， 尤其，以赫普菲爾德(J.J.Hopfield)成功地解決了旅行推鎖員問題(Tra velling Salesman Problem) 最為著名。在本論文中，我們嘗試使用類神經網路模型 去解決分散式系統中的工作分配問題 (Task Allocation Problem)，也就是去決定如 何將工作適當地分配到分散式系統中的多個處理機上，使得工作所需要的執行時間最 短。而工作分配正是使用分散式系統時的一項重要步驟。在本論文中, 我們首先將模 擬退火 (Simulated Annealing)的技巧加入到赫普菲爾德類神經網路模型(Hopfield neural network model) 之中，並且提出一個改進的模型。接著再利用此一模型去解 決分散式系統中的工作分配問題。為了簡化此一問題，我們在事前先將工作分配問題 轉換成兩個各自獨立的子問題，求工作模組與處理機之間的對應關係(Task Mappping ) ，以及工作模組間的線性優先順序(Topological Ordering)。這一個新的模型能夠 改善原有模型中部份的缺點而且可以獲得較佳的解。最後，我們利用三個例子去驗證 新模型的實用性，並且將結果與最佳解作一比較，經由實驗證明此一模型確實可以達 到不錯的效果。