具選擇性重新產生機制之群體粒子最佳化演算法 於連續型問題之應用

Particle Swarm Optimization with Selective Regeneration Mechanism for Continuous Problems

高逸瑋(I-WEI KAO)

指導教授 ： 蔡啟揚

元智大學/工程學院/工業工程與管理學系/博士(2011年)

https://doi.org/10.6838/YZU.2011.00067

摘要

隨著科學的進步，人類所面臨的問題更加複雜，因此需要更強而有力的方法來解決，近年來啟發式演算法(Meta-Heuristic)已不斷的被提出與改良，並廣泛的應用到多種領域，綜觀其中，群體粒子最佳化演算法(Particle Swarm Optimization, PSO)為一新穎且高效率的方法，迄今已有許多學者以提升求解品質與收斂速度為其目標，提出改良型或是整合型PSO。本研究首先以提升群體粒子最佳化演算法的收斂效率為目的，因而對於演算法中的自我認知與社會化參數設定加以調整，並且提出”選擇性重新產生機制(Selective Particle Regeneration Mechanism)”，以改善求解品質。為了驗證其演算法效果，選擇性重新產生群體粒子最佳化演算法(Selective Regenerated Particle Swarm Optimization, SRPSO)應用於處理Multimodal Function問題，並與PSO以及其他改良型PSO相比較。
本研究的第二個部分為方法的實際應用，首先將SRPSO應用於處理分割式資料分群(Partition Data Clustering)問題，並且與K-mean整合為KSRPSO以提升分群效率。在本研究的第三個部分，探討以存貨分類(Inventory Classification)的方法來降低企業在供應鏈中的相關總成本(Total Relevant Cost, TRC)，在此，SRPSO將被發展為一高效率之存貨分類方法，並能自動決定最佳存貨分類數目，且以實際案例來驗證其存貨分類效果，並且討論在不同的成本結構下之供應聯合作模式。經過一系列的連續型問題之測試與應用，SRPSO除了能夠達到本研究之預期效果外，與其他傳統方法和改良型最佳化演算法相比，其結果亦證明SRPSO為一穩定且高效率之最佳化演算法。

關鍵字

群體粒子最佳化演算法 ； 自我認知與社會化參數 ； 選擇性重新產生機制 ； 資料分群 ； 存貨分類

並列摘要

In recent years, meta-heuristic algorithms have been applied to a variety of complex problems in order to obtain quality solutions within acceptable computation time. Particle swarm optimization (PSO) is an efficient meta-heuristic algorithms based on the movement and intelligence of swarms. There were many researchers who developed improved or hybridized PSO algorithms. Most of them attempted to improve solution quality, robustness or efficiency. This research proposes an improved particle swarm optimization with novel mechanism. In order to increase efficiency, suggestions on algorithm’s parameter settings are proposed. In addition, “Selective Particle Regeneration” mechanism is designed to prevent the search from falling into local optima. To evaluate its effectiveness and efficiency, this approach is applied to multimodal function optimizing tasks and the performance is compared with PSO and other modified algorithms.
In the second part of this research, the application of the proposed algorithm is presented and discussed. First, SRPSO is applied to partition data clustering problems. The datasets with a variety of complexity are utilized for testing. In addition, SRPSO is combined with K-mean (KSRPSO) to increase the efficiency. Furthermore, SRPSO is employed to solve the inventory classification problem in a two-stage supply chain system. This algorithm automatically determines the optimal number of inventory groups and aim to minimize the total related costs in the supply chain. The total related cost, item classification and replenishment strategy in supply chain are compared and explained. After thorough tests and experiments on the above-mentioned continuous problems, the results fully demonstrate that SRPSO is a highly effective, efficient, and robust algorithm for continuous problems.

並列關鍵字

Inventory Classification ； Particle Swarm Optimization ； Cognition and Social Parameters ； Selective Particle Regeneration Mechanism ； Data Clustering

參考文獻

Abhay, K. S., Rajendra, S. and Shalini, B. (2010). "Portfolio evaluation using OWA-heuristic algorithm and data envelopment analysis," Journal of Risk Finance, vol.11, pp.75-88.

Adib, A. B. (2005). “NP-hardness of the cluster minimization problem revisited,” Journal of Physics A: Mathematical and General, vol.40, pp.8487-8492.

Alper, U. (2008). “Improvement of energy demand forecasts using swarm intelligence: The case of Turkey with projections to 2025,” Energy Policy, vol.36, pp.1937-1944.

Bandyopadhyay, S., Maulik, U. and Malay, K. P. (2001). “Clustering using simulated annealing with probabilistic redistribution,” International Journal of Pattern Recognition and Artificial Intelligence, vol.15, no.6, pp.269-285.

Bandyopadhyay, S. and Maulik, U. (2002). “An evolutionary technique based on K-means algorithm for optimal clustering in RN,” Information Science, vol.146, pp.221-237.