仿頻寬限制資料傳輸之離散優化演算法

Bandwidth Restricted Transmission-Simulated Discrete Optimization Algorithm

李仁富(Ren-Fu Li)

指導教授 ： 楊烽正

國立臺灣大學/工學院/工業工程學研究所/碩士(2011年)

https://doi.org/10.6342/NTU.2011.01030

摘要

本研究提出一個創新的啟發式演算法名為「仿頻寬限制資料傳輸優化演算法」(Bandwidth Restricted Transmission-Simulated Optimization Algorithm, BRT-S)。BRT-S的演算機制是仿網路資料傳輸的過程。BRT-S針對解代理人求解所使用的資源加以限制，代理人須彼此競爭搶占資源才能進行解建構。當先行代理人佔用了某建構步驟上的資源，後續代理人將避開資源不足的建構步驟，改選其他尚有資源的建構步驟，保持迭代中求得解的多樣性。演算系統只針對搶得資源且成功建構解的代理人進行解評估，節省評估解所花費的運算資源。並記錄成功建構解的代理人所選擇的建構步驟，根據其解品質的優劣，添加或扣減建構步驟上的資源，加速解的演化收斂。
本研究提出的BRT-S是以離散優化問題為求解對象設計演算流程。研究內容並針對物件排序優化問題中的旅行銷售員問題(Traveling Salesman Problem, TSP)及物件分群優化問題中的裝箱問題(Bin Packing Problem, BPP)建立BRT-S求解模式再藉以開發出BRTSDOS求解系統。再以開發的求解系統求解TSPLIB和BPPLIB中的標竿問題，並和其他啟發式演算法比較求解結果。在求解TSP範例中，BRT-S能在公平的停止條件下求得品質比其他演算法好的解，且在目標函數呼叫次數花費上較為精簡。在求解BPP範例中，能針對一系列不同容量屬性的標竿問題求得不違反箱子容量限制的解。本研究創新的仿頻寬限制資料傳輸優化演算法能有效地求解TSP和BPP兩種問題，且能花費較少的運算資源求得品質良好的解。

關鍵字

啟發式演算法 ； 旅行銷售員問題 ； 裝箱問題 ； 仿頻寬限制資料傳輸優化演算法

並列摘要

This research presents an innovative heuristic algorithm called “Bandwidth Restricted Transmission-Simulated Optimization Algorithm” (BRT-S) for solving discrete optimization problems. BRT-S simulates the process of transferring data over the network. BRT-S restricts the resources that the solution agents use for searching solutions, so agents must compete with others to obtain the resources. The preceding agent can obtain more resources than the succeeding agent, so the succeeding agent needs to avoid the construction steps lacking of resources. Only the constructed solutions are subject to objective value evaluations for saving computing resources. Concluding the construction steps selected by successful constructed agents, resources enhancement and deduction are performed based on solution quality.
BRT-S is designed for solving discrete optimization problems. We develop BRTSDOS solving system for Traveling Salesman Problem and Bin Packing Problem through programming language. Using the benchmark of TSPLIB and BPPLIB, we compare results with other heuristic algorithm’s results to verify the feasibility of BRT-S. In the example for TSP, BRT-S can obtain better solutions and call less evolution functions than the others. In the example for BPP, BRT-S can obtain optimum number of bins in the benchmarks which have different capacity attributes items and effectively balance the load between the bins.

並列關鍵字

heuristic algorithm ； traveling salesman problems ； bin packing problems ； bandwidth restricted transmission-simulated optimization algorithm

參考文獻

Bennell, J. A. ,and Dowsland, K. A. (1999), ‘A tabu thresholding implementation for the irregular stock cutting problem.’ Int. J. Prod. Res. 37,4259-4275.

Dorigo, M., and Gambardella, L. M. (1997), “Ant Colony System: A cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, vol.1, no.1, pp. 53-66.

Dowsland, K. A., (1993), “Some experiments with simulated annealing techniques for packing problems.” European Journal of Operational Research 68, 389–399.

Dueck, G., and Scheuer, T. (1990), “Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing.” Journal of Computational Physics, 90(1), 161-175.

Falkenauer, E. (1994), “A new representation and operators for GAs applied to grouping problems.” Evolutionary Computation ,1994(2), 123–144.