區域限制型螞蟻演算法設計及其在流量控制的應用

Design of Area-Restricted Ant Colony Optimization Algorithm and Its Application to Flow Control

黃仕宏(Shih-Hun Hung)

指導教授 ： 曾傳蘆

國立臺北科技大學/電資學院/電機工程系所/碩士(2008年)

摘要

本論文的目的在提出一個改良型的螞蟻演算法，並將此演算法應用至模糊流量控制。由於傳統螞蟻演算法在搜索目標的過程中，必須對所處的環境進行偵測，因此初期收斂速度較慢，若能降低空間的複雜度，將有助於提升螞蟻的搜索效率。因此本論文引入分區概念來設計演算法的搜索空間。
傳統的螞蟻演算法擅長求解旅行商問題(Traveling Salesman Problem, TSP)，與控制器設計所著重的方向不同。因此，本論文以PID控制器參數調整為例，說明改良式螞蟻演算法使用特性。調整比例、積分、微分參數時，因為各參數的對控制結果的靈敏度不同，在賦予費洛蒙更新時若直接以一組數值為單位則不符合PID調整特性。因此本論文將高靈敏度與低靈敏度的參數分別給予不同的費洛蒙更新係數。除此之外，本論文針對網際網路中的流量控制問題，以控制系統傳輸協定(Control System Transfer Protocol, CSTP)為基礎，引入本論文提出的演算法調整模糊流量控制器的比例因子，進而達到自我調節流量的能力。
最後，使用軟體MATLAB與網路模擬軟體NS2為平台，分別進行PID控制器參數設計與網路流量控制的模擬。經由模擬驗證發現，本論文提出的區域限制型螞蟻演算法有較好的性能表現並使網路延遲時間變動量較小。

關鍵字

螞蟻演算法 ； 螞蟻最佳化 ； PID控制器 ； 網際網路 ； 流量控制

並列摘要

The objective of this thesis is to propose a modified ant colony algorithm and apply it to fuzzy flow control. When executing the conventional ant algorithm to search the optima for the objective function, the convergence is slow during initial stage. The algorithm must detect the environment in the unknown space thoroughly. If the complexity of the space can be reduced, the searching efficiency is thus increased. To meet this requirement, this thesis adopts the area restricted concept to partition into the searching space.
Moreover, the conventional ant colony algorithm is suitable for solving a TSP-like problem. The main concern of the algorithm is different from that of designing a controller. To emphasize the characteristic of the proposed method, numerical examples are given via PID controller design. While tuning the proportional, integral, and derivative parameters, the conventional algorithm uses the same value to update the pheromone. It is not reasonable because different parameter sensitivity results in different control result. To solve this problem, the proposed method assigns different update coefficients according to the parameter sensitivity. In addition, based on Control System Transfer Protocol (CSTP), this thesis uses the proposed algorithm to regulate the scaling factors of the fuzzy controller for the Internet flow control problem.
Finally, this thesis utilizes MATLAB and NS2 software as a simulation platform to fulfill the PID controller and network flow control design, respectively. From the simulation results, it could be found that the area-restricted ant colony optimization algorithm has better performance and can reduce the variation of the transmission delay.

並列關鍵字

Ant colony algorithm(ACA) ； Ant colony optimization(ACO) ； PID controller ； Internet ； Flow control

參考文獻

[2] L. A. Zadeh, “Fuzzy sets,” Information and Control, vol. 8, 1965, pp. 338-353.

[5] Marco Dorigo and S. Thomas, Ant Colony Optimization, England: The MIT Press, 2004.

[7] Ping Wei and Wei-Qing Xiong, “Ant colony algorithm for general function optimization problems,” Journal of Ninbo university, vol. 14, no. 4, Dec. 2001, pp. 52-55.

[9] Hai-Bin Duan, Guan-Jun Ma, Dao-Bo Wang and Xiu-Fen Yu, “Improved ant colony algorithm for solving continuous space optimization problems,” Journal of System Simulation, vol. 19, no. 5, 2007, pp. 974-977.

[10] Zhi-Wei Ye and Zhao-Bao Zheng, “Configuration of parameters α, β, ρ in ant algorithm,” Geomatics and Information Science of Wuhan University, vol. 29, no. 27, 2004, pp. 597-601.