自適應慣性權重改良粒子群演算法之研究

A Study on Modified Particle Swarm Optimization by Adaptive Inertia Weight

黃郁授(Yu-Shou Hwang)

指導教授 ： 李維平

中原大學/商學院/資訊管理學系/碩士(2007年)

https://doi.org/10.6840/cycu200700439

摘要

粒子群演算法（Particle Swarm Optimization Algorithm，PSO）[1]為演化式計算領域的一門新技術，其特色在於「較少的參數設定」、「收斂速度快」。其與蟻群演算法、基因演算法、摸擬退火法、類神經網路相同，皆是仿效大自然的行為, 來進行最佳化求解。粒子群演算法除了仿效鳥、魚的覓食行為，也加入了人類社會行為的觀念，粒子在飛行時會追隨兩個值，一是個體最佳適應值記憶pbest，一是群體最佳適應值記憶gbest，藉由這兩個值計算出下一代飛行的位置，如此透過疊代的運算尋找最佳解。粒子群演算法已被廣泛的運用於各種領域，如旅行家銷售問題、排程問題等。
雖然粒子群演算法有「收斂速度快」的特性，但隨之而來的問題，則是會落入「區域最佳解」，尤其在多峰函數問題的求解上。目前各種改進PSO演算法，大部份著眼於如何更有效利用一個粒子在解空間搜尋最佳解。本研究認為演算法本身應能針對不同的問題做自適應的分析，再以適合的探索方式進行飛行，較能有效的對空間進行探索。
本研究提出利用粒子一開始分成兩群，並且給予兩群不同的慣性權重，來找出適合目標問題的慣性權重，以期能提升粒子群的求解品質。
研究中與其它較常見的慣性權重相互比較，如線性遞減型、線性遞增型、指數型、開口向上拋物線型、曲線型、Fuzzy型、隨機型等進行比較。

關鍵字

粒子群演算法 ； 自適應 ； 慣性權重

並列摘要

Particle Swarm Optimization Algorithm (PSO) is a new technology in evolution computing. PSO has many advantages, such as fewer parameters needed to be adjusted and the rapid convergence speed. It is the same as Ant Colony Optimization Algorithm. PSO finds the best solution by studying the nature. In addition to study birds and fishes forage, PSO also join the human social science. Each particle is following personal best solution and global solution when moving. Each particle computes new flying location to find the best answer by searching pbest and gbest after generations.
Even though PSO can rapid converge, but it also has the problem such as local best solution especially in multi-model functions. At present, many PSO improved studies focus on that how to use each particle to find the best solution effective in the space. We consider that the algorithm should estimation which inertia weight is better for the problems.
In this paper, we propose a method that using two different inertia weight particle swarms to test which inertia weight is better for the target function for improving the precision.
In this study, we compared with other inertia weight methods such as, decrease linerly, increase linerly, exponent, parapola with open up, curve, Fuzzy and random.

並列關鍵字

Inertia Weight ； Adaptive ； Particle Swarm Optimization

參考文獻

[1] Eberhart, R.C., and Kennedy, J., new optimizer using particle swarm theory, Proc. Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan, 1995, pp.39-43.

[2] Reynolds, R.G. and Sverdlik, W., problem sloving using cultural algorithms, Evolutionary computation. IEEE World Congress on Computational Intelligence, Proceedings of the First IEEE Conference, Vol. 2, 1994, pp.645-650.

[3] Eberhart, R.C., and Shi. Y., comparison between genetic algorithms and particle swarm optimization, 1998 Annual Conference on Evolutionary Programming, San Diego, 1998.

[10] Reynolds, C.W., Flock, Herds, and Schools: A Distributed Behavioral Model, Computer Graphics, Vol. 21, No. 4, 1987, pp.25-34.

[12] PSO Tutorial, Online Available at: http://www.swarmintelligence.org/index.php