求解Web服务选取问题的粒子群算法研究

发布时间：2018-07-26 20:39

【摘要】：随着云计算及“软件作为服务理念”的扩散,互联网环境下软件系统的主要形态、运行方式、生产方式和使用方式正发生着巨大的变化。通过服务重用及动态聚合以构建随需应变的松耦合的分布式应用系统成为未来网络软件开发的重要趋势。服务聚合过程实现由服务本体到具体服务的绑定,其中,服务选择直接关系到服务聚合的全局质量以及绑定关系是否需要动态调整,因此对该问题的研究一直倍受关注。近来随着服务数量的爆炸性增长,网络上分布着大量功能相同、非功能特性各异的服务。如何在规模较大的功能相当的服务集合中选择质量较优且能够可靠运行的满足用户需求服务成为一个亟待解决的问题。在很多服务系统中存在多个服务等级,而已有的研究大都针对单个服务等级的情况,对同时考虑多个服务等级的情况研究还很少,因此如何选择出满足多个SLA等级约束条件同时使系统的整体效用最佳的服务实例也需要进一步研究。针对上述问题,本文分别从面向业务、面向功能、面向非资源共享的多SLA及面向资源共享的多SLA等角度对服务选取问题展开研究。此外已有研究表明专注于单独使用一种算法解决问题具有非常大的局限性,将元启发式算法与其它优化算法或元启发式算法之间有效结合,即混合元启发式算法,能够更加有效、更加灵活地处理实际问题。而作为一种高效的元启发式算法,粒子群算法已被成功应用于解决多个领域中的问题。因此,针对上述不同情况的服务选择问题所建立的优化模型,本文都研究采用粒子群算法与其它技术相结合的方式对其进行求解,并且通过实验对所提算法效果进行验证,具体包括：(1)研究了面向业务的服务选取问题,建立了该问题的单目标优化模型,并采用启发式局部搜索策略与粒子群算法相结合的方式提出了求解该问题的HEU-PSO算法。在该算法中,将粒子群算法的全局搜索能力与启发式算法的局部优化能力相结合,通过粒子群算法找到的有希望的局部区域,然后利用启发式局部搜索策略对局部区域进行深入搜索；从而实现对解空间全面深入地搜索。实验表明算法HEU-PSO在求解速率和求解质量方面优于其它对比算法。(2)研究了面向功能的大规模服务选取问题,在对该问题进行优化建模的基础上,根据该问题的特点通过将蚁群算法与粒子群算法相结合的方式提出了求解该问题的ACO-PSO算法。该算法先利用α-支配服务skyline搜索策略缩减问题规模,利用k-聚类设计蚁群构造图,在此基础上,将蚁群算法灵活搜索的特点与粒子群搜索策略(HEU-PSO)的深入搜索特点相结合,以实现对解空间快速有效地搜索。实验表明算法ACO-PSO求解效果显著。(3)从非资源共享的角度研究了SLA等级感知服务组合问题,建立了该问题的多目标离散优化模型,通过将变异操作结合到粒子群算法中提出了求解该问题的混合多目标离散粒子群算法(HMDPSO)。该算法中,根据该问题的特征,重新设计粒子更新策略,并且利用群体多样性指标提出了粒子变异策略以增加群体的多样性。另外,通过将一种基于候选服务约束支配关系的局部搜索策略结合到与算法HMDPSO,形成算法HMDPSO+,以进一步提高求解的性能。实验表明算法HMDPSO+能对解空间进行深入全面的搜索,并且求解性能突出。(4)从资源共享的角度研究了SLA等级感知服务组合问题,将该问题建模为多目标优化问题,并提出了基于资源共享的多目标粒子群算法(SMOPSO)。根据问题的特点,在算法中定义了粒子位置的形式和粒子部署策略,以体现相同具体服务实例的共享关系；沿用了传统粒子更新策略以实现对全局的搜索；设计了局部搜索策略以此来提高搜索的精度；提出了粒子变异策略来抑制算法的早熟收敛。实验表明算法(SMOPSO)能很好地对问题进行求解,并且具有强大的搜索能力和稳定的收敛特征。
[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.
【学位授予单位】：东北大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TP393.09;TP18

【参考文献】