求解Web服務(wù)選取問題的粒子群算法研究
發(fā)布時(shí)間：2018-07-26 20:39
【摘要】：隨著云計(jì)算及“軟件作為服務(wù)理念”的擴(kuò)散,互聯(lián)網(wǎng)環(huán)境下軟件系統(tǒng)的主要形態(tài)、運(yùn)行方式、生產(chǎn)方式和使用方式正發(fā)生著巨大的變化。通過服務(wù)重用及動(dòng)態(tài)聚合以構(gòu)建隨需應(yīng)變的松耦合的分布式應(yīng)用系統(tǒng)成為未來網(wǎng)絡(luò)軟件開發(fā)的重要趨勢。服務(wù)聚合過程實(shí)現(xiàn)由服務(wù)本體到具體服務(wù)的綁定,其中,服務(wù)選擇直接關(guān)系到服務(wù)聚合的全局質(zhì)量以及綁定關(guān)系是否需要?jiǎng)討B(tài)調(diào)整,因此對該問題的研究一直倍受關(guān)注。近來隨著服務(wù)數(shù)量的爆炸性增長,網(wǎng)絡(luò)上分布著大量功能相同、非功能特性各異的服務(wù)。如何在規(guī)模較大的功能相當(dāng)?shù)姆⻊?wù)集合中選擇質(zhì)量較優(yōu)且能夠可靠運(yùn)行的滿足用戶需求服務(wù)成為一個(gè)亟待解決的問題。在很多服務(wù)系統(tǒng)中存在多個(gè)服務(wù)等級,而已有的研究大都針對單個(gè)服務(wù)等級的情況,對同時(shí)考慮多個(gè)服務(wù)等級的情況研究還很少,因此如何選擇出滿足多個(gè)SLA等級約束條件同時(shí)使系統(tǒng)的整體效用最佳的服務(wù)實(shí)例也需要進(jìn)一步研究。針對上述問題,本文分別從面向業(yè)務(wù)、面向功能、面向非資源共享的多SLA及面向資源共享的多SLA等角度對服務(wù)選取問題展開研究。此外已有研究表明專注于單獨(dú)使用一種算法解決問題具有非常大的局限性,將元啟發(fā)式算法與其它優(yōu)化算法或元啟發(fā)式算法之間有效結(jié)合,即混合元啟發(fā)式算法,能夠更加有效、更加靈活地處理實(shí)際問題。而作為一種高效的元啟發(fā)式算法,粒子群算法已被成功應(yīng)用于解決多個(gè)領(lǐng)域中的問題。因此,針對上述不同情況的服務(wù)選擇問題所建立的優(yōu)化模型,本文都研究采用粒子群算法與其它技術(shù)相結(jié)合的方式對其進(jìn)行求解,并且通過實(shí)驗(yàn)對所提算法效果進(jìn)行驗(yàn)證,具體包括：(1)研究了面向業(yè)務(wù)的服務(wù)選取問題,建立了該問題的單目標(biāo)優(yōu)化模型,并采用啟發(fā)式局部搜索策略與粒子群算法相結(jié)合的方式提出了求解該問題的HEU-PSO算法。在該算法中,將粒子群算法的全局搜索能力與啟發(fā)式算法的局部優(yōu)化能力相結(jié)合,通過粒子群算法找到的有希望的局部區(qū)域,然后利用啟發(fā)式局部搜索策略對局部區(qū)域進(jìn)行深入搜索；從而實(shí)現(xiàn)對解空間全面深入地搜索。實(shí)驗(yàn)表明算法HEU-PSO在求解速率和求解質(zhì)量方面優(yōu)于其它對比算法。(2)研究了面向功能的大規(guī)模服務(wù)選取問題,在對該問題進(jìn)行優(yōu)化建模的基礎(chǔ)上,根據(jù)該問題的特點(diǎn)通過將蟻群算法與粒子群算法相結(jié)合的方式提出了求解該問題的ACO-PSO算法。該算法先利用α-支配服務(wù)skyline搜索策略縮減問題規(guī)模,利用k-聚類設(shè)計(jì)蟻群構(gòu)造圖,在此基礎(chǔ)上,將蟻群算法靈活搜索的特點(diǎn)與粒子群搜索策略(HEU-PSO)的深入搜索特點(diǎn)相結(jié)合,以實(shí)現(xiàn)對解空間快速有效地搜索。實(shí)驗(yàn)表明算法ACO-PSO求解效果顯著。(3)從非資源共享的角度研究了SLA等級感知服務(wù)組合問題,建立了該問題的多目標(biāo)離散優(yōu)化模型,通過將變異操作結(jié)合到粒子群算法中提出了求解該問題的混合多目標(biāo)離散粒子群算法(HMDPSO)。該算法中,根據(jù)該問題的特征,重新設(shè)計(jì)粒子更新策略,并且利用群體多樣性指標(biāo)提出了粒子變異策略以增加群體的多樣性。另外,通過將一種基于候選服務(wù)約束支配關(guān)系的局部搜索策略結(jié)合到與算法HMDPSO,形成算法HMDPSO+,以進(jìn)一步提高求解的性能。實(shí)驗(yàn)表明算法HMDPSO+能對解空間進(jìn)行深入全面的搜索,并且求解性能突出。(4)從資源共享的角度研究了SLA等級感知服務(wù)組合問題,將該問題建模為多目標(biāo)優(yōu)化問題,并提出了基于資源共享的多目標(biāo)粒子群算法(SMOPSO)。根據(jù)問題的特點(diǎn),在算法中定義了粒子位置的形式和粒子部署策略,以體現(xiàn)相同具體服務(wù)實(shí)例的共享關(guān)系；沿用了傳統(tǒng)粒子更新策略以實(shí)現(xiàn)對全局的搜索；設(shè)計(jì)了局部搜索策略以此來提高搜索的精度；提出了粒子變異策略來抑制算法的早熟收斂。實(shí)驗(yàn)表明算法(SMOPSO)能很好地對問題進(jìn)行求解,并且具有強(qiáng)大的搜索能力和穩(wěn)定的收斂特征。
[Abstract]:With the spread of cloud computing and "software as a service concept", great changes have taken place in the main forms, mode of operation, mode of production and use of software systems in the Internet environment. Through service reuse and dynamic aggregation, the construction of an on demand loosely coupled distributed application system becomes the future of the development of network software. Trend. The service aggregation process implements the binding from the service ontology to the specific service, in which the service selection is directly related to the global quality of the service aggregation and whether the binding relationship needs to be dynamically adjusted. Therefore, the research on this problem has been paid much attention. Recently, with the explosive growth of the number of services, a large number of functions are distributed on the network. The same, different non functional services. How to select the better quality and reliable operation of the user needs service in a large and functional service set of large scale is an urgent problem. There are many service levels in many service systems, and the research is mostly aimed at the single service level. There are few studies on the situation of multiple service classes at the same time, so how to choose a service instance that satisfies the multiple SLA level constraints and make the system with the best overall utility needs further study. In this paper, the paper is based on business oriented, function oriented, multi SLA and resource sharing for non resource sharing. The problem of service selection is studied by multi SLA and other angles. In addition, the research has shown that it is very limited to focus on a single algorithm to solve the problem. The combination of meta heuristic algorithm and other optimization algorithms or meta heuristic algorithms, that is, the hybrid element heuristic algorithm, can be more effective and more flexible. As a kind of efficient meta heuristic algorithm, particle swarm optimization has been successfully applied to solve many problems in many fields. Therefore, in this paper, the optimization model based on the problem of service selection in different cases has been studied by using particle swarm optimization and other techniques to solve them. The effect of the proposed algorithm is verified by the experiment. (1) the problem of service oriented service selection is studied, the single objective optimization model of the problem is established, and the HEU-PSO algorithm is proposed by combining the heuristic local search strategy with particle swarm optimization. In this algorithm, the particle swarm optimization algorithm is used. The global search ability is combined with the local optimization ability of the heuristic algorithm. The local region is found by the particle swarm optimization, and then the local region is searched deeply by the heuristic local search strategy, so that the solution space is searched thoroughly and thoroughly. The experiment shows that the algorithm HEU-PSO is solving the rate and the quality of the solution. The aspect is superior to other algorithms. (2) the problem of function oriented large-scale service selection is studied. Based on the optimization modeling of the problem, the ACO-PSO algorithm is proposed to solve the problem by combining ant colony algorithm with particle swarm optimization in the light of the characteristics of this problem. The algorithm first uses alpha dominating service skyline to search the problem. In order to reduce the scale of the cable strategy, the k- clustering is used to design the ant structure map. On this basis, the characteristics of the ant colony algorithm flexible search and the deep search characteristics of the particle swarm search strategy (HEU-PSO) are combined to realize the fast and effective search for the solution space. The experiment shows that the algorithm ACO-PSO has a significant solution effect. (3) from the point of view of non resource sharing. The problem of SLA level perception service composition is studied, and a multi objective discrete optimization model is established. By combining mutation operation to particle swarm optimization, a hybrid multi-objective discrete particle swarm optimization (HMDPSO) algorithm is proposed to solve the problem. In this algorithm, the particle update strategy is redesigned according to the characteristics of the problem, and the population is redesigned with the population. The diversity index proposed the particle mutation strategy to increase the diversity of the group. In addition, by combining a local search strategy based on the candidate service constraint relationship to the algorithm HMDPSO, the algorithm HMDPSO+ is formed to further improve the performance of the solution. The experiment shows that the algorithm HMDPSO+ can search the solution space thoroughly and comprehensively. And the performance of the solution is outstanding. (4) the problem of SLA level perception service composition is studied from the perspective of resource sharing. The problem is modeled as a multi-objective optimization problem, and a multi-objective particle swarm optimization (SMOPSO) based on resource sharing is proposed. According to the characteristics of the problem, the form of particle position and the particle deployment strategy are defined in the algorithm to embody the phase. The sharing relationship with the specific service instances; the traditional particle update strategy is used to achieve the global search; a local search strategy is designed to improve the search accuracy; the particle mutation strategy is proposed to suppress the premature convergence of the algorithm. The experiment shows that the algorithm (SMOPSO) can solve the problem well and is powerful. The search capability and the stable convergence characteristics.
【學(xué)位授予單位】：東北大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2014
【分類號】：TP393.09;TP18
本文編號：2147229
[Abstract]:With the spread of cloud computing and "software as a service concept", great changes have taken place in the main forms, mode of operation, mode of production and use of software systems in the Internet environment. Through service reuse and dynamic aggregation, the construction of an on demand loosely coupled distributed application system becomes the future of the development of network software. Trend. The service aggregation process implements the binding from the service ontology to the specific service, in which the service selection is directly related to the global quality of the service aggregation and whether the binding relationship needs to be dynamically adjusted. Therefore, the research on this problem has been paid much attention. Recently, with the explosive growth of the number of services, a large number of functions are distributed on the network. The same, different non functional services. How to select the better quality and reliable operation of the user needs service in a large and functional service set of large scale is an urgent problem. There are many service levels in many service systems, and the research is mostly aimed at the single service level. There are few studies on the situation of multiple service classes at the same time, so how to choose a service instance that satisfies the multiple SLA level constraints and make the system with the best overall utility needs further study. In this paper, the paper is based on business oriented, function oriented, multi SLA and resource sharing for non resource sharing. The problem of service selection is studied by multi SLA and other angles. In addition, the research has shown that it is very limited to focus on a single algorithm to solve the problem. The combination of meta heuristic algorithm and other optimization algorithms or meta heuristic algorithms, that is, the hybrid element heuristic algorithm, can be more effective and more flexible. As a kind of efficient meta heuristic algorithm, particle swarm optimization has been successfully applied to solve many problems in many fields. Therefore, in this paper, the optimization model based on the problem of service selection in different cases has been studied by using particle swarm optimization and other techniques to solve them. The effect of the proposed algorithm is verified by the experiment. (1) the problem of service oriented service selection is studied, the single objective optimization model of the problem is established, and the HEU-PSO algorithm is proposed by combining the heuristic local search strategy with particle swarm optimization. In this algorithm, the particle swarm optimization algorithm is used. The global search ability is combined with the local optimization ability of the heuristic algorithm. The local region is found by the particle swarm optimization, and then the local region is searched deeply by the heuristic local search strategy, so that the solution space is searched thoroughly and thoroughly. The experiment shows that the algorithm HEU-PSO is solving the rate and the quality of the solution. The aspect is superior to other algorithms. (2) the problem of function oriented large-scale service selection is studied. Based on the optimization modeling of the problem, the ACO-PSO algorithm is proposed to solve the problem by combining ant colony algorithm with particle swarm optimization in the light of the characteristics of this problem. The algorithm first uses alpha dominating service skyline to search the problem. In order to reduce the scale of the cable strategy, the k- clustering is used to design the ant structure map. On this basis, the characteristics of the ant colony algorithm flexible search and the deep search characteristics of the particle swarm search strategy (HEU-PSO) are combined to realize the fast and effective search for the solution space. The experiment shows that the algorithm ACO-PSO has a significant solution effect. (3) from the point of view of non resource sharing. The problem of SLA level perception service composition is studied, and a multi objective discrete optimization model is established. By combining mutation operation to particle swarm optimization, a hybrid multi-objective discrete particle swarm optimization (HMDPSO) algorithm is proposed to solve the problem. In this algorithm, the particle update strategy is redesigned according to the characteristics of the problem, and the population is redesigned with the population. The diversity index proposed the particle mutation strategy to increase the diversity of the group. In addition, by combining a local search strategy based on the candidate service constraint relationship to the algorithm HMDPSO, the algorithm HMDPSO+ is formed to further improve the performance of the solution. The experiment shows that the algorithm HMDPSO+ can search the solution space thoroughly and comprehensively. And the performance of the solution is outstanding. (4) the problem of SLA level perception service composition is studied from the perspective of resource sharing. The problem is modeled as a multi-objective optimization problem, and a multi-objective particle swarm optimization (SMOPSO) based on resource sharing is proposed. According to the characteristics of the problem, the form of particle position and the particle deployment strategy are defined in the algorithm to embody the phase. The sharing relationship with the specific service instances; the traditional particle update strategy is used to achieve the global search; a local search strategy is designed to improve the search accuracy; the particle mutation strategy is proposed to suppress the premature convergence of the algorithm. The experiment shows that the algorithm (SMOPSO) can solve the problem well and is powerful. The search capability and the stable convergence characteristics.
【學(xué)位授予單位】：東北大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2014
【分類號】：TP393.09;TP18
【參考文獻(xiàn)】
相關(guān)期刊論文 前10條
1 溫濤;盛國軍;郭權(quán);李迎秋;;基于改進(jìn)粒子群算法的Web服務(wù)組合[J];計(jì)算機(jī)學(xué)報(bào);2013年05期
2 夏亞梅;程渤;陳俊亮;孟祥武;劉棟;;基于改進(jìn)蟻群算法的服務(wù)組合優(yōu)化[J];計(jì)算機(jī)學(xué)報(bào);2012年02期
3 王尚廣;孫其博;楊放春;;基于全局QoS約束分解的Web服務(wù)動(dòng)態(tài)選擇[J];軟件學(xué)報(bào);2011年07期
4 印瑩;張斌;張錫哲;;面向組合服務(wù)動(dòng)態(tài)自適應(yīng)的事務(wù)級主動(dòng)伺機(jī)服務(wù)替換算法[J];計(jì)算機(jī)學(xué)報(bào);2010年11期
5 吳健;陳亮;鄧水光;李瑩;鄺礫;;基于Skyline的QoS感知的動(dòng)態(tài)服務(wù)選擇[J];計(jì)算機(jī)學(xué)報(bào);2010年11期
6 王顯志;徐曉飛;王忠杰;;面向組合服務(wù)收益優(yōu)化的動(dòng)態(tài)服務(wù)選擇方法[J];計(jì)算機(jī)學(xué)報(bào);2010年11期
7 陳彥萍;張建科;孫家澤;鄭慶華;李增智;;一種基于混合智能優(yōu)化的服務(wù)選擇模型[J];計(jì)算機(jī)學(xué)報(bào);2010年11期
8 胡建強(qiáng);李涓子;廖桂平;;一種基于多維服務(wù)質(zhì)量的局部最優(yōu)服務(wù)選擇模型[J];計(jì)算機(jī)學(xué)報(bào);2010年03期
9 蔣哲遠(yuǎn);韓江洪;王釗;;動(dòng)態(tài)的QoS感知Web服務(wù)選擇和組合優(yōu)化模型[J];計(jì)算機(jī)學(xué)報(bào);2009年05期
10 代鈺;楊雷;張斌;;QoS-Driven Self-Healing Web Service Composition Based on Performance Prediction[J];Journal of Computer Science & Technology;2009年02期
相關(guān)博士學(xué)位論文 前1條
1 夏亞梅;動(dòng)態(tài)服務(wù)組合中的若干關(guān)鍵技術(shù)研究[D];北京郵電大學(xué);2009年
，本文編號：2147229
本文鏈接：http://sikaile.net/guanlilunwen/ydhl/2147229.html
最近更新
教材專著
