面向组合优化问题的粒子群算法的研究
发布时间：2018-08-27 14:07
【摘要】：组合优化问题是典型的NP-hard问题,本文将改进的粒子群算法分别应用于无序组合优化和有序服务组合优化领域。现有的改进粒子群算法存在一些不足,大多数是针对某一具体场景提出不具有普适价值;粒子群算法在搜索最优解的过程中,具有随机性,不能保证组合方案的多样性;大多数算法没有提供个性化接口,且粒子群算法随着粒子的维数变大,其计算量是成指数增长,求解粒子维数大的组合优化问题效率低等问题。本文在面向无序组合优化问题时,在粒子群算法中引入混沌搜索方法,提出一种新型混沌粒子群算法(Chaos Particle Swarm Optimization,CS-PSO)。通过在粒子群算法中引入混沌理论,改进算法的初始化阶段和更新阶段,使用一套全新的初始化和更新规则,使得算法整体搜索效率提高,具有良好的全局搜索能力和适应性,有效的解决粒子早熟问题,并保证最终组合方案的多样性。在算法的适应度函数中,引入个性化约束和一般约束的概念,使算法具有个性化接口,可以用来求解具有个性化的组合优化问题。本文在面向有序服务组合优化问题时,所选择的应用场景是Web服务组合优化领域。Web服务组合优化不仅是NP-hard问题,服务和服务之间还需要考虑逻辑顺序关系,因此要找到最佳服务组合方案是难上加难。本文针对具有逻辑顺序关系的Web服务组合优化问题提出一种基于捕食搜索的混沌粒子群算法(Predatory Search-Based Chaos Particle Swarm Optimization,PS-CTPSO),通过在粒子群优化算法中引入捕食搜索策略和具有混沌性质的余切序列方法,根据Web服务的特点,进一步优化初始化和更新阶段,并且通过逻辑优化,确保了算法的搜索效率和Web服务组合的多样性。最终,本文针对两个算法,分别构建个性化早餐推荐系统(Friend)和最佳Web服务组合推荐系统(Best Web Service Combination Recommendation System,BestWS),并通过和主流算法进行实验对比,实验表明,本文算法推荐的组合方案更高效、合理,本文算法在组合优化领域具有一定的应用价值。
[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
本文编号：2207517
[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 王瑞;陈永刚;;基于捕食搜索策略的粒子群算法求解高铁闭塞分区划分问题[J];铁道标准设计;2016年01期
2 杨庆;陈强;李珍珍;;带时间窗车辆路径问题的混沌粒子群优化算法[J];计算机技术与发展;2015年08期
3 张燕平;荆紫慧;张以文;钱付兰;石磊;;基于离散粒子群算法的动态Web服务组合[J];计算机科学;2015年06期
4 唐崇;;Web服务组合QoS优化问题综述[J];信息技术与信息化;2015年04期
5 赵新超;刘国莅;刘虎球;赵国帅;;基于非均匀变异和多阶段扰动的粒子群优化算法[J];计算机学报;2014年09期
6 郭通;兰巨龙;李玉峰;陈世文;;自适应的分数阶达尔文粒子群优化算法[J];通信学报;2014年04期
7 朱喜华;李颖晖;李宁;范炳奎;;基于群体早熟程度和非线性周期振荡策略的改进粒子群算法[J];通信学报;2014年02期
8 温涛;盛国军;郭权;李迎秋;;基于改进粒子群算法的Web服务组合[J];计算机学报;2013年05期
9 刘冬华;甘若迅;樊锁海;杨明华;;基于捕食策略的粒子群算法求解投资组合问题[J];计算机工程与应用;2013年06期
10 胥小波;郑康锋;李丹;武斌;杨义先;;新的混沌粒子群优化算法[J];通信学报;2012年01期
相关硕士学位论文 前5条
1 刘畅;基于混合启发式算法的单线公交车辆调度问题研究[D];北京交通大学;2016年
2 荆紫慧;基于改进离散粒子群算法的Web服务组合研究[D];安徽大学;2016年
3 尹徐珊;基于改进PSO算法的投资组合优化方法的设计和实现[D];东南大学;2015年
4 刘长彬;基于粒子群和人工鱼群混合优化排课系统研究[D];成都理工大学;2015年
5 王涛;基于捕食搜索策略的自适应混沌粒子群算法的研究及应用[D];暨南大学;2013年
，本文编号：2207517
本文链接：https://www.wllwen.com/kejilunwen/zidonghuakongzhilunwen/2207517.html
