基于旅行商问题的粒子群优化算法

旅行商问题(Traveling Salesman Problem,TSP)是一类离散的、NP(Non-deterministic Polynomial)完全的组合优化问题,有着广泛的应用背景和许多的求解方法。该文介绍了用粒子群优化算法求解旅行商问题,并与模拟退火算法和遗传算法相比较,通过实验结果说明了粒子群优化算法在解决大规模组合优化问题上的有效性和可行性。     

粒子群算法求解旅行商问题程序设计

粒子群优化算法是一种具备全局搜索能力的群集智能优化算法,针对一类离散的、NP完全的组合优化问题——旅行商问题．该文介绍了用粒子群算法求解旅行商问题的改进策略和主要模块的程序设计思想。将算法应用到20个城市的解旅行商问题所得到的结果与遗传算法进行比较,数字仿真与结果比较表明了改进粒子群算法求解该问题的有效性。     

利用粒子群优化算法求解圆排列问题

针对已有算法搜索时间较长,且易于过早地收敛于非最优解的缺陷,利用粒子群优化算法给出了圆排列问题的求解方法.首先,在分析了圆排列问题与旅行商问题关系的基础上,将圆排列问题转化为旅行商问题,从而得到一个相应的组合优化问题.然后,利用粒子群优化算法进行了求解.接着,为了进一步提高算法的精度,文中给出了一种利用混合粒子群优化算法的方案.最后,在仿真实验中,与已有算法进行了比较,实验结果表明,文中所给方法是有效的.     

蚁群算法及其在求解旅行商问题中的应用

蚁群算法是一种求解组合优化问题较好的方法。在蚁群算法的基本原理基础上,以旅行商问题为例,介绍了该算法求解TSP的数学模型及具体步骤,并通过仿真实验与粒子群优化算法等方法比较分析,表明了该算法在求解组合优化问题方面具有良好的性能。     

粒子群算法求解旅行商问题程序设计

粒子群优化算法是一种具备全局搜索能力的群集智能优化算法,针对一类离散的、NP完全的组合优化问题——旅行商问题,该文介绍了用粒子群算法求解旅行商问题的改进策略和主要模块的程序设计思想。将算法应用到20个城市的解旅行商问题所得到的结果与遗传算法进行比较,数字仿真与结果比较表明了改进粒子群算法求解该问题的有效性。     

蚁群算法及其在求解旅行商问题中的应用

蚁群算法是一种求解组合优化问题较好的方法。在蚁群算法的基本原理基础上,以旅行商问题为例,介绍了该算法求解TSP的数学模型及具体步骤,并通过仿真实验与粒子群优化算法等方法比较分析,表明了该算法在求解组合优化问题方面具有良好的性能。     

基于离散粒子群优化算法的含权旅行商问题新解法

考虑现有旅行商问题常忽略车辆载重对运输费用的影响,建立含权旅行商问题模型。在分析含权旅行商问题性质的基础上,提出离散粒子群优化算法求解含权旅行商问题。重新定义问题域的粒子速度、粒子位置等运算规则,引入惯性系数线性下降策略。实验表明,该算法可以有效用于含权旅行商问题的求解,并且对含权旅行商问题的求解性能优于遗传算法和模拟退火算法。     

求解TSP问题的模糊自适应粒子群算法

由于惯性权值的设置对粒子群优化（PSO）算法性能起着关键的作用，本文通过引入模糊技术，给出了一种惯性权值的模糊自适应调整模型及其相应的粒子群优化算法，并用于求解旅行商（TSP）问题。实验结果表明了改进算法在求解组合优化问题中的有效性，同时提高了算法的性能，并具有更快的收敛速度。     

一种改进的求解TSP混合粒子群优化算法

为解决粒子群算法在求解组合优化问题中存在的早熟性收敛和收敛速度慢等问题,将粒子群算法与局部搜索优化算法结合,可抑制粒子群算法早熟收敛问题,提高粒子群算法的收敛速度。通过建立有效的局部搜索优化算法所需借助的参照优化边集,提高了局部搜索优化算法的求解质量和求解效率。新的混合粒子群算法高效收敛于中小规模旅行商问题的全局最优解,实验表明改进的混合粒子群算法是有效的。     

一种求旅行商问题的离散粒子群算法

针对旅行商问题提出一种离散粒子群算法。算法重新定义了速度及其与粒子位置的相关算子,设计了"距离排序矩阵"(保存距离城市由近到远的其他城市的矩阵),并根据它生成可动态变化的优秀基因库来指导粒子高效地进行全局搜索。本文用TSPLIB中的部分案例进行实验,实验结果表明,该算法在求解旅行商问题上有很好的性能,并且具有很好的鲁棒性。     

Set-based discrete particle swarm optimization and its applications: a survey

Particle swarm optimization (PSO) is one of the most popular population-based stochastic algorithms for solving complex optimization problems. While PSO is simple and effective, it is originally defined in continuous space. In order to take advantage of PSO to solve combinatorial optimization problems in discrete space, the set-based PSO (S-PSO) framework extends PSO for discrete optimization by redefining the operations in PSO utilizing the set operations. Since its proposal, S-PSO has attracted increasing research attention and has become a promising approach for discrete optimization problems. In this paper, we intend to provide a comprehensive survey on the concepts, development and applications of S-PSO. First, the classification of discrete PSO algorithms is presented. Then the S-PSO framework is given. In particular, we will give an insight into the solution construction strategies, constraint handling strategies, and alternative reinforcement strategies in S-PSO together with its different variants. Furthermore, the extensions and applications of S-PSO are also discussed systemically. Some potential directions for the research of S-PSO are also discussed in this paper.     

A ranking selection-based particle swarm optimizer for engineering design optimization problems

Particle swarm optimization (PSO) algorithms have been proposed to solve optimization problems in engineering design, which are usually constrained (possibly highly constrained) and may require the use of mixed variables such as continuous, integer, and discrete variables. In this paper, a new algorithm called the ranking selection-based PSO (RSPSO) is developed. In RSPSO, the objective function and constraints are handled separately. For discrete variables, they are partitioned into ordinary discrete and categorical ones, and the latter is managed and searched directly without the concept of velocity in the standard PSO. In addition, a new ranking selection scheme is incorporated into PSO to elaborately control the search behavior of a swarm in different search phases and on categorical variables. RSPSO is relatively simple and easy to implement. Experiments on five engineering problems and a benchmark function with equality constraints were conducted. The results indicate that RSPSO is an effective and widely applicable optimizer for optimization problems in engineering design in comparison with the state-of-the-art algorithms in the area.     

离散微粒群优化算法的研究进展

首先,介绍了近年来出现的５种较为典型的离散ＰＳＯ,并分析了它们与基本ＰＳＯ 之间的联系和区别;然后,归纳了提高离散ＰＳＯ 优化性能的若干途径,并总结了离散ＰＳＯ 的应用现状;最后,探讨了离散ＰＳＯ 有待进一步研究的若干方向和内容．     

Penalty function approach for the mixed discrete nonlinear problems by particle swarm optimization

In this paper, the basic characteristics of particle swarm optimization (PSO) for the global search are discussed at first, and then the PSO for the mixed discrete nonlinear problems (MDNLP) is suggested. The penalty function approach to handle the discrete design variables is employed, in which the discrete design variables are handled as the continuous ones by penalizing at the intervals. As a result, a useful method to determine the penalty parameter of penalty term for the discrete design variables is proposed. Through typical mathematical and structural optimization problems, the validity of the proposed approach for the MDNLP is examined.     

An algorithmic framework of discrete particle swarm optimization

Particle swarm optimization (PSO) was originally developed for continuous problem. To apply PSO to a discrete problem, the standard arithmetic operators of PSO are required to be redefined over discrete space. In this paper, a concept of distance over discrete solution space is introduced. Under this notion of distance, the PSO operators are redefined. After reinterpreting the composition of velocity of a particle, a general framework of discrete PSO algorithm is proposed. As a case study, we illustrate the application of the proposed discrete PSO algorithm to number partitioning problem (NPP) step by step. Preliminary computational experience is also presented. The successful application shows that the proposed algorithmic framework is feasible.     

广义粒子群优化模型

粒子群优化算法提出至今一直未能有效解决的离散及组合优化问题．针对这个问题,文中首先回顾了粒子群优化算法在整数规划问题的应用以及该算法的二进制离散优化模型,并分析了其缺陷．然后,基于传统算法的速度一位移更新操作,在分析粒子群优化机理的基础上提出了广义粒子群优化模型（GPSO）,使其适用于解决离散及组合优化问题．GPSO模型本质仍然符合粒子群优化机理,但是其粒子更新策略既可根据优化问题的特点设计,也可实现与已有方法的融合．该文以旅行商问题（TSP）为例,针对遗传算法（GA）解决该问题的成功经验,使用遗传操作作为GPSO模型中的更新算子,进一步提出基于遗传操作的粒子群优化模型,并以Inverover算子作为模型中具体的遗传操作设计了基于GPSO模型的TSP算法．与采用相同遗传操作的GA比较,基于GPSO模型的算法解的质量与收敛稳定性提高,同时计算费用显著降低．     

Modified cuckoo optimization algorithm (MCOA) to solve graph coloring problem

In recent years, various heuristic optimization methods have been developed. Many of these methods are inspired by swarm behaviors in nature, such as particle swarm optimization (PSO), firefly algorithm (FA) and cuckoo optimization algorithm (COA). Recently introduced COA, has proven its excellent capabilities, such as faster convergence and better global minimum achievement. In this paper a new approach for solving graph coloring problem based on COA was presented. Since COA at first was presented for solving continuous optimization problems, in this paper we use the COA for the graph coloring problem, we need a discrete COA. Hence, to apply COA to discrete search space, the standard arithmetic operators such as addition, subtraction and multiplication existent in COA migration operator based on the distance's theory needs to be redefined in the discrete space. Redefinition of the concept of the difference between the two habitats as the list of differential movements, COA is equipped with a means of solving the discrete nature of the non-permutation. A set of graph coloring benchmark problems are solved and its performance is compared with some well-known heuristic search methods. The obtained results confirm the high performance of the proposed method.     

粒子群优化算法的性能分析和参数选择

惯性权重和加速因子是影响粒子群算法优化性能的重要参数.基于常用的12个测试函数,本文通过实验研究了不同参数组合下粒子的探索能力和算法的优化性能,在此基础上推荐了一组固定的参数组合.通过惯性权重和加速因子的不同变化策略组合对算法性能影响的实验分析,推荐了一种变化的参数设置方法.基于CEC2015发布的15个基准函数进一步验证了本文推荐的参数选取方法的有效性.最后讨论了粒子群优化（Particle swarm optimization,PSO）算法在连续优化和离散优化方面的应用问题.     

基于PSO信息传递模式的混合算法

粒子群优化算法（Particle Swarm Optimization，PSO）是一种基于群智能（Swarm Intelligence）的随机优化计算技术。PSO和遗传算法这两种算法相比较，PSO收敛快速准确，但编码形式单一，局限于解决实优化问题，而遗传算法编码形式灵活，解决问题广泛，但执行效率低于PS00。将粒子群算法的信息传递模式与遗传算法的编码和遗传操作相结合，提出一种混合算法。并推导了两个算法之间的密切联系。并通过组合优化和函数优化的基准测试集对算法进行测试，试验结果表明，该算法在收敛精度和速度优于传统遗传算法。同时，也观察到该算法取得了与粒子群算法一致的收敛现象。     

A discrete version of particle swarm optimization for flowshop scheduling problems

Particle swarm optimization (PSO) is a novel metaheuristic inspired by the flocking behavior of birds. The applications of PSO to scheduling problems are extremely few. In this paper, we present a PSO algorithm, extended from discrete PSO, for flowshop scheduling. In the proposed algorithm, the particle and the velocity are redefined, and an efficient approach is developed to move a particle to the new sequence. To verify the proposed PSO algorithm, comparisons with a continuous PSO algorithm and two genetic algorithms are made. Computational results show that the proposed PSO algorithm is very competitive. Furthermore, we incorporate a local search scheme into the proposed algorithm, called PSO-LS. Computational results show that the local search can be really guided by PSO in our approach. Also, PSO-LS performs well in flowshop scheduling with total flow time criterion, but it requires more computation times.