Bandwidth Restricted Transmission-Simulated Discrete Optimization Algorithm
Date Issued
2011
Date
2011
Author(s)
Li, Ren-Fu
Abstract
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.
Subjects
heuristic algorithm
traveling salesman problems
bin packing problems
bandwidth restricted transmission-simulated optimization algorithm
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-100-R98546023-1.pdf
Size
23.54 KB
Format
Adobe PDF
Checksum
(MD5):84e1e15a89c9138f2aae7351532499b0