粒子群演算法於離散最佳化問題之研究

Abstract

粒子群演算法(Particle Swarm Optimization, PSO)是一種群體搜尋最佳化演算法，於1995年被提出。原始的PSO是應用於求解連續最佳化問題。當PSO用來求解離散最佳化問題時，我們必須修改粒子位置、粒子移動以及粒子速度的表達方式，讓PSO更適於求解離散最佳化問題問題。本研究之主要貢獻為提出數種適合求解離散最佳化問題之PSO設計。這些新的設計和原始的設計不同且更適合求解離散最佳化問題。 在本篇論文中，我們將分別提出適合求解零壹多限制式背包問題(Multidimensional 0-1 Knapsack Problem, MKP)、零工式排程問題(Job Shop Scheduling Problem JSSP)以及開放式排程問題(Open Shop Scheduling Problem, OSSP)的PSO。在求解MKP的PSO中，我們以零壹變數表達粒子位置，以區塊建立(building blocks)的概念表達粒子移動方式。在求解JSSP的PSO中，我們以偏好列表(preference-list)表達粒子位置，以交換運算子(swap operator)表達粒子移動方式。在求解OSSP的PSO中，我們以優先權重(priority)表達粒子位置，以插入運算子(insert operator)表達粒子移動方式。除此之外，我們在求解MKP的PSO中加入區域搜尋法(local search)，在求解JSSP的PSO與塔布搜尋(tabu search)混合，以及將求解OSSP的PSO與集束搜尋法(beam search)混合。計算結果顯示，我們的PSO比其它傳統的啟發式解法要來的好。

Particle Swarm Optimization (PSO) is a population-based optimization algorithm, which was developed in 1995. The original PSO is used to solve continuous optimization problems. Due to solution spaces of discrete optimization problems are discrete, we have to modify the particle position representation, particle movement, and particle velocity to better suit PSO for discrete optimization problems. The contribution of this research is that we proposed several PSO designs for discrete optimization problems. The new PSO designs are better suit for discrete optimization problems, and differ from the original PSO. In this thesis, we propose three PSOs for three discrete optimization problems respectively: the multidimensional 0-1 knapsack problem (MKP), the job shop scheduling problem (JSSP) and the open shop scheduling problem (OSSP). In the PSO for MKP, the particle position is represented by binary variables, and the particle movement are based on the concept of building blocks. In the PSO for JSSP, we modified the particle position representation using preference-lists and the particle movement using a swap operator. In the PSO for OSSP, we modified the particle position representation using priorities and the particle movement using an insert operator. Furthermore, we hybridized the PSO for MKP with a local search procedure, the PSO for JSSP with tabu search (TS), and the PSO for OSSP with beam search (BS). The computational results show that our PSOs are better than other traditional metaheuristics.