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

University of Taipei > 理學院 > 資訊科學系 > 會議論文 > Item 987654321/16009

請使用永久網址來引用或連結此文件: http://utaipeir.lib.utaipei.edu.tw/dspace/handle/987654321/16009

題名:	一個基因演算法在瓶頸選擇內部節點最小生成樹問題上;A genetic algorithm for the bottleneck selected-internal minimum spanning tree problem
作者:	Ho, Chien-Yuan;何健源;Chen, Yen-Hung;陳彥宏
貢獻者:	臺北市立大學資訊科學系
日期:	2014-04
上傳時間:	2017-07-31 13:50:57 (UTC+8)
摘要:	本文探討一個組合最佳化問題：瓶頸選擇內部節點最小問題（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）。
關聯:	第31屆組合數學與計算理論研討會 (The 31st Workshop on Combinatorial Mathematics and Computational Theory)，臺北市立大學，P.291，2014/04/25~26
顯示於類別:	[資訊科學系] 會議論文

文件中的檔案:

沒有與此文件相關的檔案.

在uTaipei中所有的資料項目都受到原著作權保護.