【摘要】：組合優(yōu)化問題是典型的NP-hard問題,本文將改進(jìn)的粒子群算法分別應(yīng)用于無序組合優(yōu)化和有序服務(wù)組合優(yōu)化領(lǐng)域。現(xiàn)有的改進(jìn)粒子群算法存在一些不足,大多數(shù)是針對某一具體場景提出不具有普適價(jià)值;粒子群算法在搜索最優(yōu)解的過程中,具有隨機(jī)性,不能保證組合方案的多樣性;大多數(shù)算法沒有提供個(gè)性化接口,且粒子群算法隨著粒子的維數(shù)變大,其計(jì)算量是成指數(shù)增長,求解粒子維數(shù)大的組合優(yōu)化問題效率低等問題。本文在面向無序組合優(yōu)化問題時(shí),在粒子群算法中引入混沌搜索方法,提出一種新型混沌粒子群算法(Chaos Particle Swarm Optimization,CS-PSO)。通過在粒子群算法中引入混沌理論,改進(jìn)算法的初始化階段和更新階段,使用一套全新的初始化和更新規(guī)則,使得算法整體搜索效率提高,具有良好的全局搜索能力和適應(yīng)性,有效的解決粒子早熟問題,并保證最終組合方案的多樣性。在算法的適應(yīng)度函數(shù)中,引入個(gè)性化約束和一般約束的概念,使算法具有個(gè)性化接口,可以用來求解具有個(gè)性化的組合優(yōu)化問題。本文在面向有序服務(wù)組合優(yōu)化問題時(shí),所選擇的應(yīng)用場景是Web服務(wù)組合優(yōu)化領(lǐng)域。Web服務(wù)組合優(yōu)化不僅是NP-hard問題,服務(wù)和服務(wù)之間還需要考慮邏輯順序關(guān)系,因此要找到最佳服務(wù)組合方案是難上加難。本文針對具有邏輯順序關(guān)系的Web服務(wù)組合優(yōu)化問題提出一種基于捕食搜索的混沌粒子群算法(Predatory Search-Based Chaos Particle Swarm Optimization,PS-CTPSO),通過在粒子群優(yōu)化算法中引入捕食搜索策略和具有混沌性質(zhì)的余切序列方法,根據(jù)Web服務(wù)的特點(diǎn),進(jìn)一步優(yōu)化初始化和更新階段,并且通過邏輯優(yōu)化,確保了算法的搜索效率和Web服務(wù)組合的多樣性。最終,本文針對兩個(gè)算法,分別構(gòu)建個(gè)性化早餐推薦系統(tǒng)(Friend)和最佳Web服務(wù)組合推薦系統(tǒng)(Best Web Service Combination Recommendation System,BestWS),并通過和主流算法進(jìn)行實(shí)驗(yàn)對比,實(shí)驗(yàn)表明,本文算法推薦的組合方案更高效、合理,本文算法在組合優(yōu)化領(lǐng)域具有一定的應(yīng)用價(jià)值。
[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.
【學(xué)位授予單位】：南京郵電大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP18

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

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

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

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

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

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

6 郭通;蘭巨龍;李玉峰;陳世文;;自適應(yīng)的分?jǐn)?shù)階達(dá)爾文粒子群優(yōu)化算法[J];通信學(xué)報(bào);2014年04期

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

8 溫濤;盛國軍;郭權(quán);李迎秋;;基于改進(jìn)粒子群算法的Web服務(wù)組合[J];計(jì)算機(jī)學(xué)報(bào);2013年05期

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

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

相關(guān)碩士學(xué)位論文 前5條

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

2 荊紫慧;基于改進(jìn)離散粒子群算法的Web服務(wù)組合研究[D];安徽大學(xué);2016年

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

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

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

，

本文編號：2207517