啟發式演算法之研究與改良

Researches and Improvements on Heuristic Algorithms

江正文(Cheng-Wen Chiang)

中原大學/工學院/電子工程研究所/博士(2011年)

https://doi.org/10.6840/cycu201101125

摘要

啟發式演算法是藉由一些規則(rules)與隨機現象(randomness)以仿效自然現象
(natural phenomena)的方式設計演算法結構，進而透過電腦計算搜尋複雜問題的最佳
解，目前已被大量應用在搜尋(Search)、最佳化(optimization)、排程(scheduling)等各種工
程問題求解。近年來，常被使用的啟發式演算法大致可分為仿效生物演化過程(Biological
evolutionary process)、仿效動物行為(Animal behavior)、仿效物理過程(Physical process)。
啟發式演算法大都著眼於如何更有效地在解空間中搜尋最佳解，因此如何克服避免落入
區域最佳解中是所有演算法都須面對的問題。因此本研究嘗試提出數種策略，用來改良
啟發式演算法的求解能力。首先是提出2-Opt 演算法來改良差分演算法的求解能力。再
來則是提出「限制式隨機策略」、「協同合作」以及「以文化演算法為基礎的活化策略」
來改良粒子群演算法。透過實驗證明，本研究所提出的演算法在求解能力上，均能有良
好的表現。

關鍵字

啟發式演算法 ； 差分演算法 ； 粒子群演算法

並列摘要

Heuristic algorithm is structured by natural phenomena with some rules and randomness.
It helps us to calculate the optimal solution of complex problems by computer. Heuristic
algorithm has been widely used in the search, optimization, scheduling and other engineering
problems. Heuristic algorithms can be divided into three parts, biological evolutionary
process, animal behavior and physical annealing process. Most heuristic algorithms focus on
how to search for optimal solution more effectively in the solution space, thus all algorithms
are faced with how to avoid falling into the local optima. Therefore, we attempt to propose
several strategies to enhance the performance of heuristic algorithms. The first, we proposed
the 2-Opt Algorithm to enhance the performance of Differential Evolution. Besides, we also
proposed restricted randomization, cooperation and cultural activation strategies to enhance
the performance of Particle Swarm Optimization. The experimental results show the
proposals outperform original DE and variant PSO in terms of solution accuracy and
convergence speed.

並列關鍵字

Differential Evolution ； Heuristic Algorithm ； Particle Swarm Optimization

參考文獻

[1] Rainer Storn, Kenneth Price, Differential evolution - a simple and efficient adaptive

scheme for global optimization over continuous spaces, Berkeley, CA, Tech. Rep.

TR-95-012, 1995.

[2] Rainer Storn, Kenneth Price, Differential evolution - a simple and efficient heuristic for

[3] Jakob Vesterstrøm, Rene Thomsen, A comparative study of differential evolution,