結合座標旋轉與鐘形機率模型演算法應用於解決方程式最佳化問題

Combine Rotation of Coordinates and Generalized Bell Function Algorithm for Solving Function Optimization Problem

楊宜娟(Yi-Jyuan Yang)

指導教授 ： 周耀新

國立暨南國際大學/科技學院/資訊工程學系/碩士(2013年)

https://doi.org/10.6837/NCNU.2013.00218

摘要

許多人提出的研究都具有創新性，就像量子啟發式禁忌搜尋演算法(QTS)，而這樣的行為常常會引發對於該研究領域更多的新想法，而我們在這個研究中所做的事情就是改良量子啟發式禁忌搜尋演算法，這不僅提升了我們對於演算法的許多啟發也讓我在演算法這門學問中有了更多面向的思考。在這個研究中我們提出了「結合座標旋轉與鐘形機率模型演算法(簡稱RCGBA)」，我們在RCGBA演算法中套用了模擬退火演算法裡有一定機率接受較差的解作為目前最佳解的這個觀念，我們使用的接受機率模型是鐘形機率模型(Generalized bell-shaped membership function)，這個機率模型使RCGBA在解決維度較大的問題的時候，可以有效防止演算法在搜索過程中陷入區域最佳解，進而找到更好的解，而在更新的步驟中，RCGBA除了有趨向最佳解的更新動作之外，還增加了遠離最差解的更新，為了測驗此研究所提出的結合座標旋轉與鐘形機率模型演算法的效能，我們將它應用於解決方程式最佳化問題，而且得到了不錯的結果。

關鍵字

組合最佳化 ； 量子啟發式演化計算 ； 鐘形機率模型 ； 方程式最佳化問題

並列摘要

Many kinds of researches are created and they can create more ideas to others. After we read the paper about quantum-inspired tabu search algorithm (QTS) for solving 0/1 knapsack problems [5], we got many ideas. In this study, we proposed a method which is called Combine Rotation of Coordinates and Generalized Bell Function Algorithm for Solving Function Optimization Problem (RCGBA). In RCGBA, we have two skills. First, we have the probability of taking a second solution become the guide of renewing the populations. Second, we have a step which is turning possible solutions away from the worst solution when algorithm is updating. We use RCGBA for solving function optimization problem to show its performance. The experiment results show that RCGBA performs well in function optimization problem, and RCGBA would not fall into local optimum.

並列關鍵字

Combinatorial Optimization ； Quantum-inspired evolutionary Algorithm ； Generalized bell-shaped membership function ； Function optimization problem

參考文獻

[1] M. Dorigo, M. Birattari, T. Stutzle, “Ant colony optimization,” IEEE on Computational Intelligence magazine, pp28-39, 2006.

[2] J. Kennedy, R. Eberhart, “Particle swarm optimization,” IEEE international conference on Neural Networks, vol. 4, pp.1942-1948, 1995.

[3] H. Talbi, A. Draa and M. Batouche, “A new quantum-inspired genetic algorithm for solving the travelling salesman problem,” IEEE ICIT, vol. 3, pp. 1192 - 1197, 2004.

[4] C. C. Chang, C. Y. Chen, C. W. Fan, H. C. Chao and Y. H. Chou ,“Quantum-Inspired Electromagnetism-Like Mechanism for Solving 0/1 Knapsack Problem ,”in IEEE conference on ITCS, pp.1-6, Aug. 2010.

[5] C. H. Chiu, Y. J. Yang and Y. H. Chou, “Quantum-inspired Tabu search for solving 0/1 knapsack problems ,”in ACM conference on GECCO, pp 55-56, 2011.