一個基因演算法在瓶頸選擇內部節點最小生成樹問題上; A genetic algorithm for the bottleneck selected-internal minimum spanning tree problem

uTaipei > College of Science > Department of Computer Science > Proceedings > Item 987654321/16009

Please use this identifier to cite or link to this item: http://utaipeir.lib.utaipei.edu.tw/dspace/handle/987654321/16009

Title:	一個基因演算法在瓶頸選擇內部節點最小生成樹問題上;A genetic algorithm for the bottleneck selected-internal minimum spanning tree problem
Authors:	Ho, Chien-Yuan;何健源;Chen, Yen-Hung;陳彥宏
Contributors:	臺北市立大學資訊科學系
Date:	2014-04
Issue Date:	2017-07-31 13:50:57 (UTC+8)
Abstract:	本文探討一個組合最佳化問題：瓶頸選擇內部節點最小問題（bottleneck selected-internal minimum spanning tree problem）。給定一個無向完全圖G=(V,E)，一個非負數的權重函數在邊上及一個節點的集合RV，選擇內部節點生成樹為一棵生成樹連通V內的所有節點，但是在R內的節點不能是樹葉（\|V\R\|2）。瓶頸選擇內部節點最小生成樹問題定義為找出一棵選擇內部節點最小生成樹使得樹上最大邊的權重要最小。此研究已被證明為NP-Complete，此問題可應用在廣播資源配置 (broadcast resource allocation) 。本研究設計一個基因演算法來解決問題，並透過隨機產生的亂數數據模擬測試，實驗結果顯示我們的基因演算法所得的解與最佳解的倍率大約為1.0至1.2之間，最高到1.15倍。在執行效率上，我們的基因演算法所用之時間平均為2至3毫秒（ms）。
Relation:	第31屆組合數學與計算理論研討會 (The 31st Workshop on Combinatorial Mathematics and Computational Theory)，臺北市立大學，P.291，2014/04/25~26
Appears in Collections:	[Department of Computer Science] Proceedings

Files in This Item:

There are no files associated with this item.

Loading...