學位論文

Permanent URI for this collectionhttp://rportal.lib.ntnu.edu.tw/handle/20.500.12235/73912

Browse

Subject: search.filters.subject.平行化

Search Results

Now showing 1 - 3 of 3
  • No Thumbnail Available
    Item
    使用KataGo方法及迫著空間搜尋提升AlphaZero在六子棋的訓練成效
    (2023) 林育璋; Lin, Yu-Chang
    自從Google DeepMind提出AlphaZero演算法之後，許多使用傳統搜尋法的電腦對局程式都被AlphaZero作法取代。然而AlphaZero作法需要非常大量的算力，才能夠達到頂尖的水準，因此我們希望透過程式效能改進及傳統做法的輔助，提升AlphaZero在六子棋遊戲的訓練效率，讓我們可以使用個人電腦達到頂尖水準。本篇論文使用Alpha-Zero-General開源程式碼作為基礎，研發一支AlphaZero的六子棋程式。我們參考galvanise_zero的做法修改MCTS的搜尋方式、參考OOGiveMeFive提出的通用型Bitboard，將其進行修改後用於六子棋程式中，並且參考陽明交通大學的CZF_Connect6提出的六子棋強度改進方式。本篇論文從三個面向來加速AlphaZero的訓練效率。第一個是提升程式效能，我們分析Alpha-Zero-General的一個效能瓶頸是MCTS的部分，因此透過C++及平行化的方式重新實作MCTS，大幅提升AlphaZero的訓練效率。第二個是提升神經網路的性能，使用KataGo提出的Global Pooling及Auxiliary Policy Targets方法修改神經網路，並套用於六子棋程式中。第三個是提升訓練資料的品質，使用KataGo提出的Forced Playout and Policy Target Pruning方法及傳統的迫著空間搜尋提升訓練資料的品質。另外本篇論文提出一種新的訓練方式，提升AlphaZero加入heuristics的訓練效果。我們使用C++、平行化及批次預測的方式可以讓MCTS的搜尋效率達到26.4的加速比，並且使用Bitboard的方式可以讓迫著空間搜尋達到6.03的加速比。在短時間的訓練中，雖然使用相同時間AlphaZero方法可以訓練更多個迭代，不過使用相同時間訓練的KataGo方法與原始AlphaZero方法相比依然可以取得57.58%的勝率，且使用相同時間訓練的KataGo-TSS Hybrids方法與原始AlphaZero方法相比也可以取得70%的勝率。並且這三種作法訓練到500個迭代後與NCTU6_Level3對戰，都可以取得超過65%的勝率。
  • No Thumbnail Available
    Item
    以變化分配島嶼式MOEA/D求解多目標問題
    (2013) 李鼎基
    在日常生活中，我們時常面臨最佳化問題，例如最小化交通的時間與成本，這兩項目標存在著衝突，此類問題稱為多目標最佳化問題，因應每人需求不同，會有不同的最佳解。一般解多目標最佳化問題是找出一組最佳解集合，集合中會有不同的目標取捨方式供使用者挑選，然而解決此類問題是相當耗時的，為了在有效時間內找出不錯的解，使用演化式演算法是廣受好評的方式。 演化式演算法本身存在著許多可切割平行的要素，因此許多平行架構的演化式演算法因應而生，本論文嘗試將知名的多目標演化式演算法 MOEA/D 進行平行化，除了基本的平行要素外，尚有其他因平行化被破壞的 MOEA/D 之要素需要修補。本論文針對17個多目標最佳化問題進行測試，並慢慢調整島嶼式 MOEA/D，一一討論各要素之影響，最後與 MOEA/D 進行比較成效與差異性，並且運用 OpenMP 進行平行加速。
  • No Thumbnail Available
    Item
    強化親代選擇機制之平行化高目標演化式演算法
    (2013) 陳少文; sao-wen chen
    當一個最佳化問題的求解目標數為兩個以上時，我們稱其為多目標最佳化問題 (multi-objective optimization problems)，若目標數為四或四個以上時，則稱其為高目標最佳化問題 (many-objective optimization problems)。現實世界的最佳化問題中存在著許多高目標最佳化問題，傳統的多目標最佳化演算法只適合求解目標數四以下的問題，設計一個能夠求解高目標最佳化問題的演算法是目前演化式領域中的研究重點。 我們以非凌越性排序基因演算法 (NSGA-III) 為基底，深入觀察該演算法特性，改善親代選擇機制 (mating selection) 中選取親代的方式，優先改進族群中相對較差的區域，並搭配鄰域選取 (neighborhood-based selection) 概念，得到不錯的成效；在環境選擇機制 (environmental selection) 中，我們嘗試同時維持族群在目標空間與決策空間中的分散度，並使用其他方法替代原本 NSGA-III 演算法的選取機制，雖然成效不彰，但在實驗中我們觀察到了一些有趣的現象；我們更以島嶼模型 (island model) 將演算法平行化，透過預先分配給各島嶼屬於邊框權重向量的機制，在維持演算法原本求解能力的同時，還能加快整體的執行速度。 本論文所提出的各種改進機制可以互相搭配使用，以最佳版本的親代選擇機制配合平行化機制的狀況下 (ESP-NSGA-III)，與原版的 NSGA-III相比，求解 DTLZ1~4 並改變其問題目標數共 15 個測試問題中，在 Mann Whitney U 統計檢定下，我們的演算法有著 11 勝 3 和 1 負的優良表現。