Maximal Coverage Problems with Routing Constraints using Cross-Entropy Monte Carlo Tree Search

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/90062

Title:	Maximal Coverage Problems with Routing Constraints using Cross-Entropy Monte Carlo Tree Search
Authors:	林寶德;Lin, Pao-TE
Contributors:	數學系
Keywords:	次模性;最大覆蓋問題;交叉熵;蒙地卡羅搜尋樹演算法;Submodularity;Maximal coverage problem;Cross-Entropy;Monte-Carlo Tree Search
Date:	2022-07-25
Issue Date:	2022-10-04 12:09:49 (UTC+8)
Publisher:	國立中央大學
Abstract:	最大覆蓋問題在路徑限制下是NP-hard問題。廣義成本收益演算法(GCB)能解決這樣的問題，並達到1/2(1-1/e)的近似最佳值。但是GCB和近似最佳解仍有有一段差距。此研究提出基於交叉熵的蒙地卡羅搜尋樹演算法 (CE-MCTS) 來解決這個問題。這個演算法包含三個部分: 演化演算法 (EA) 用於採樣分支、信賴上界策略 (UCB) 用於選擇展開和估計分布演算法 (EDA) 用於模擬。實驗證實了CE-MCTS在不同地圖及成本限制底下的效能比其他兩個演算法(GCB、EAMC)更好。 ;The maximal coverage problems with routing constraints are NP-hard problems. The generalized cost-benefit algorithm (GCB) is able to solve this problem with a $\frac{1}{2}(1-\frac{1}{e})\widetilde{OPT}$ guarantee. There is a space between the approximation optimal solution $(\widetilde{OPT})$ and GCB performance. In this research, the cross-entropy based Monte Carlo Tree Search algorithm (CE-MCTS) is proposed to solve this problem. It consists of three parts: the evolutionary algorithm (EA) for sampling the branches, the upper confidence bound (UCB) policy for selections, and the estimation of distribution algorithm (EDA) for simulations. The experiments demonstrate that the CE-MCTS outperforms benchmark approaches (e.g., GCB, EAMC) in different maps with various budget constraints.
Appears in Collections:	[Graduate Institute of Mathematics] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	116	View/Open

社群 sharing

Loading...