【摘要】：組合優(yōu)化問題是典型的NP-hard問題,本文將改進的粒子群算法分別應用于無序組合優(yōu)化和有序服務組合優(yōu)化領域。現(xiàn)有的改進粒子群算法存在一些不足,大多數(shù)是針對某一具體場景提出不具有普適價值;粒子群算法在搜索最優(yōu)解的過程中,具有隨機性,不能保證組合方案的多樣性;大多數(shù)算法沒有提供個性化接口,且粒子群算法隨著粒子的維數(shù)變大,其計算量是成指數(shù)增長,求解粒子維數(shù)大的組合優(yōu)化問題效率低等問題。本文在面向無序組合優(yōu)化問題時,在粒子群算法中引入混沌搜索方法,提出一種新型混沌粒子群算法(Chaos Particle Swarm Optimization,CS-PSO)。通過在粒子群算法中引入混沌理論,改進算法的初始化階段和更新階段,使用一套全新的初始化和更新規(guī)則,使得算法整體搜索效率提高,具有良好的全局搜索能力和適應性,有效的解決粒子早熟問題,并保證最終組合方案的多樣性。在算法的適應度函數(shù)中,引入個性化約束和一般約束的概念,使算法具有個性化接口,可以用來求解具有個性化的組合優(yōu)化問題。本文在面向有序服務組合優(yōu)化問題時,所選擇的應用場景是Web服務組合優(yōu)化領域。Web服務組合優(yōu)化不僅是NP-hard問題,服務和服務之間還需要考慮邏輯順序關系,因此要找到最佳服務組合方案是難上加難。本文針對具有邏輯順序關系的Web服務組合優(yōu)化問題提出一種基于捕食搜索的混沌粒子群算法(Predatory Search-Based Chaos Particle Swarm Optimization,PS-CTPSO),通過在粒子群優(yōu)化算法中引入捕食搜索策略和具有混沌性質(zhì)的余切序列方法,根據(jù)Web服務的特點,進一步優(yōu)化初始化和更新階段,并且通過邏輯優(yōu)化,確保了算法的搜索效率和Web服務組合的多樣性。最終,本文針對兩個算法,分別構建個性化早餐推薦系統(tǒng)(Friend)和最佳Web服務組合推薦系統(tǒng)(Best Web Service Combination Recommendation System,BestWS),并通過和主流算法進行實驗對比,實驗表明,本文算法推薦的組合方案更高效、合理,本文算法在組合優(yōu)化領域具有一定的應用價值。
[Abstract]:The combinatorial optimization problem is a typical NP-hard problem. In this paper, the improved particle swarm optimization algorithm is applied to the field of disordered composition optimization and ordered service composition optimization, respectively. The existing improved particle swarm optimization (PSO) algorithm has some shortcomings, most of which are not of universal value for a specific scenario, PSO algorithm has randomness in the process of searching for the optimal solution, so it can not guarantee the diversity of the combination scheme. Most algorithms do not provide a personalized interface and particle swarm optimization algorithm increases exponentially with the particle dimension and the efficiency of solving combinatorial optimization problem with large particle dimension is low. In this paper, a new chaotic particle swarm optimization (Chaos Particle Swarm Optimization,CS-PSO) is proposed by introducing chaotic search method into particle swarm optimization (PSO) for disordered combinatorial optimization problems. By introducing chaos theory into particle swarm optimization algorithm, the initialization and update stages of the algorithm are improved, and a new set of initialization and update rules are used to improve the overall search efficiency of the algorithm, and the algorithm has good global search ability and adaptability. Effectively solve the problem of particle precocity and ensure the diversity of the final portfolio. In the fitness function of the algorithm, the concepts of personalized constraint and general constraint are introduced to make the algorithm have a personalized interface, which can be used to solve the combinatorial optimization problem with individuation. In order service composition optimization problem, the application scenario chosen in this paper is that Web service composition optimization domain. Web service composition optimization is not only a NP-hard problem, but also needs to consider the logical sequence relationship between service and service. So finding the best service composition is even more difficult. In this paper, a predatory search based chaotic particle swarm optimization (Predatory Search-Based Chaos Particle Swarm Optimization,PS-CTPSO) algorithm is proposed for the Web service composition optimization problem with logical sequence relationship. The predation search strategy and chaos are introduced into the particle swarm optimization algorithm. Cotangent sequence method of properties, According to the characteristics of Web services, the initialization and update phases are further optimized, and the search efficiency of the algorithm and the diversity of Web service composition are ensured by logic optimization. Finally, this paper constructs the personalized breakfast recommendation system (Friend) and the best Web service composition recommendation system (Best Web Service Combination Recommendation System,BestWS) according to the two algorithms. The combination scheme recommended by this algorithm is more efficient and reasonable, and the algorithm in this paper has certain application value in the field of combinatorial optimization.
【學位授予單位】：南京郵電大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：TP18

【參考文獻】

相關期刊論文 前10條

1 王瑞;陳永剛;;基于捕食搜索策略的粒子群算法求解高鐵閉塞分區(qū)劃分問題[J];鐵道標準設計;2016年01期

2 楊慶;陳強;李珍珍;;帶時間窗車輛路徑問題的混沌粒子群優(yōu)化算法[J];計算機技術與發(fā)展;2015年08期

3 張燕平;荊紫慧;張以文;錢付蘭;石磊;;基于離散粒子群算法的動態(tài)Web服務組合[J];計算機科學;2015年06期

4 唐崇;;Web服務組合QoS優(yōu)化問題綜述[J];信息技術與信息化;2015年04期

5 趙新超;劉國蒞;劉虎球;趙國帥;;基于非均勻變異和多階段擾動的粒子群優(yōu)化算法[J];計算機學報;2014年09期

6 郭通;蘭巨龍;李玉峰;陳世文;;自適應的分數(shù)階達爾文粒子群優(yōu)化算法[J];通信學報;2014年04期

7 朱喜華;李穎暉;李寧;范炳奎;;基于群體早熟程度和非線性周期振蕩策略的改進粒子群算法[J];通信學報;2014年02期

8 溫濤;盛國軍;郭權;李迎秋;;基于改進粒子群算法的Web服務組合[J];計算機學報;2013年05期

9 劉冬華;甘若迅;樊鎖海;楊明華;;基于捕食策略的粒子群算法求解投資組合問題[J];計算機工程與應用;2013年06期

10 胥小波;鄭康鋒;李丹;武斌;楊義先;;新的混沌粒子群優(yōu)化算法[J];通信學報;2012年01期

相關碩士學位論文 前5條

1 劉暢;基于混合啟發(fā)式算法的單線公交車輛調(diào)度問題研究[D];北京交通大學;2016年

2 荊紫慧;基于改進離散粒子群算法的Web服務組合研究[D];安徽大學;2016年

3 尹徐珊;基于改進PSO算法的投資組合優(yōu)化方法的設計和實現(xiàn)[D];東南大學;2015年

4 劉長彬;基于粒子群和人工魚群混合優(yōu)化排課系統(tǒng)研究[D];成都理工大學;2015年

5 王濤;基于捕食搜索策略的自適應混沌粒子群算法的研究及應用[D];暨南大學;2013年

，

本文編號：2207517