一类求解带时间窗的团队定向问题的改进蚁群算法

带时间窗的团队定向问题是一类重要的物流配送路径优化问题,其优化目标是制定最优可行车辆路线,在规定的时间窗内服务一组顾客,以获得最大的总收益。提出了一类改进蚁群算法,用以求解该问题。为了提高解构造质量与效率,使用一种快速的方法来确定动态候选链表,并且利用串行法和贪婪法构造解。与迭代局部搜索相比,所提算法能够在12s内得到更好的解。     

A modified particle swarm optimization with multiple subpopulations for multimodal function optimization problems

In this paper, a modified particle swarm optimization (PSO) algorithm is developed for solving multimodal function optimization problems. The difference between the proposed method and the general PSO is to split up the original single population into several subpopulations according to the order of particles. The best particle within each subpopulation is recorded and then applied into the velocity updating formula to replace the original global best particle in the whole population. To update all particles in each subpopulation, the modified velocity formula is utilized. Based on the idea of multiple subpopulations, for the multimodal function optimization the several optima including the global and local solutions may probably be found by these best particles separately. To show the efficiency of the proposed method, two kinds of function optimizations are provided, including a single modal function optimization and a complex multimodal function optimization. Simulation results will demonstrate the convergence behavior of particles by the number of iterations, and the global and local system solutions are solved by these best particles of subpopulations.     

Integrating public transportation in personalised electronic tourist guides

Personalised electronic tourist guides (PETs) are mobile hand-held devices able to create tourist routes matching tourists' preferences. Transportation information has been identified as one of the most appreciated functionalities of a PET. We model the tourist planning problem, integrating public transportation, as the time-dependent team orienteering problem with time windows (TD-TOPTW) in order to allow PETs to create personalised tourist routes in real-time. We develop and compare two different approaches to solve the TD-TOPTW. Experimental results for the city of San Sebastian show that both approaches are able to obtain routes in real-time.     

非线性TP的PSO求解

运输问题自提出后,人们因其在各个领域的广泛应用进行了大量研究.尤其是线型运输问题,已经设计出了多种有效解法,但它们均不能直接处理非线性运输问题.本文在经典粒子群算法PSO的基础上设计了新算法PSO-NLTP,它通过改进PSO的粒子飞行速度和飞行位置更新方程,及设计出负修复算子,既满足TP的约束条件,又扩大了搜索空间.针对经典PSO算法容易在局部最优解过早停止搜索的不足,我们添加了自适应的变异算子,以防止PSO-NLTP过早停止搜索.通过仿真实例证明,与遗传算法GA-NLTP和带惩罚策略的EP进行比较,PSO-NLTP能在较短的时间内找到更优解,结果验证了新算法的有效性.     

群核进化粒子群优化方法

粒子群优化方法（PSO Particle Swarm Optimization）是由Kennedy和Eberhart于1995年提出的进化计算技术,并成功应用于各类优化问题。其基本思想源于对鸟群捕食等群体行为的研究。本文对标准PSO方法进行了分析,给出了“群核”（Swarm-Core）的概念,并在此基础上,提出了群核进化粒子群优化方法（Swarm-Core Evolutionary Particle Swarm Optimization,SCEPSO）,同时把该方法与其它版本PSO方法进行了比较。试验结果表明：在相同环境下,SCEPSO方法能较好地克服传统PSO方法中的不足,测试结果较其它几个版本的PSO方法有很大提高,是非常有效的。     

A hybrid particle swarm optimization for job shop scheduling problem

A hybrid particle swarm optimization (PSO) for the job shop problem (JSP) is proposed in this paper. In previous research, PSO particles search solutions in a continuous solution space. Since the solution space of the JSP is discrete, we modified the particle position representation, particle movement, and particle velocity to better suit PSO for the JSP. We modified the particle position based on preference list-based representation, particle movement based on swap operator, and particle velocity based on the tabu list concept in our algorithm. Giffler and Thompson’s heuristic is used to decode a particle position into a schedule. Furthermore, we applied tabu search to improve the solution quality. The computational results show that the modified PSO performs better than the original design, and that the hybrid PSO is better than other traditional metaheuristics.     

基于Java多线程技术实现的粒子群优化算法

在研究粒子群优化算法生物特征的基础上,提出了粒子群优化算法的异步模式。在异步模式的程序实现上,采用Java多线程技术,使每个粒子的行为成为一个独立的线程,进化中的粒子个体充分表现出独立性,种群表现出异步性。最后利用一些经典的标准测试函数,与经典PSO算法(可称为同步模式)进行了比较分析,结果表明：异步模式的收敛速度较同步模式有显著的提高;同时,在一个较小时间段(一般小于整个运算时间的5％)之后,异步模式在寻优效果上也明显优于同步模式。     

一种优化高维复杂函数的PSO算法

对于高维复杂函数,一般粒子群优化算法收敛速度慢,易早熟收敛。本文重构一个适合高维复杂函数惯性权重函数,使粒子群算法寻优过程中的全局收搜能力和局部收搜能力良好平衡,以达到快速收敛,高效避免早熟问题,获得最优解。对典型高维复杂函数的仿真表明：算法在求解质量和求解速度两方面都得到了好的结果。     

基于粒子群算法的非线性方程组求解

将非线性方程组的求解问题转化为无约束极大极小优化问题,并应用一种新的进化计算（EC）方法——粒子群算法（PSO）求解此优化问题。数值实验的结果验证了该方法的可行性和有效性。     

基于时变系数与社会认知模拟的粒子群优化

粒子群优化算法利用一群在可行区域内飞行的粒子来搜索最优解,具有易实现、收敛速度快的特点,然而也面临\"早熟\"的问题.提出了一种基于时变系数与社会认知模拟的粒子群优化算法.实验结果显示,在5种不同的标准化测试函数下,新算法较另外3种常用的算法优越.     

基于改进的离散PSO算法的FJSP的研究

柔性作业车间调度问题(Flexible Job-shop Scheduling Problem,FJSP)是经典作业车间调度问题的一个扩展,前者更接近于实际生产。以最小化最大完工时间为目标,提出了一种改进的离散粒子群优化算法。传统粒子群优化算法一般适用于优化连续模型问题,FJSP作为复杂度比较高的组合优化问题,是一种典型的离散模型。提出的算法采用机器负荷平衡机制初始化粒子种群,在粒子的更新过程中引入了3个操作算子来更新粒子的工序排序部分和机器分配部分,这3个算子分别为基于工序排序或机器分配的变异、与个体最优位置之间进行工序先后顺序保留的交叉(POX)操作、与全局最优位置进行随机点保存的交叉(RPX)操作。先后执行以上3个算子以完成粒子的一次更新。这种操作能够使种群较快地收敛于最优解。对标准测试案例进行实验的结果表明,所提算法对解决FJSP具有有效性,并且能够快速地搜索到近似最优解;与其他同类算法相比,所提算法在求解效果和收敛速度上均具有优越性。     

Vehicle routing problem with uncertain demands: An advanced particle swarm algorithm

The Vehicle Routing Problem (VRP) has been thoroughly studied in the last decades. However, the main focus has been on the deterministic version where customer demands are fixed and known in advance. Uncertainty in demand has not received enough consideration. When demands are uncertain, several problems arise in the VRP. For example, there might be unmet customers’ demands, which eventually lead to profit loss. A reliable plan and set of routes, after solving the VRP, can significantly reduce the unmet demand costs, helping in obtaining customer satisfaction. This paper investigates a variant of an uncertain VRP in which the customers’ demands are supposed to be uncertain with unknown distributions. An advanced Particle Swarm Optimization (PSO) algorithm has been proposed to solve such a VRP. A novel decoding scheme has also been developed to increase the PSO efficiency. Comprehensive computational experiments, along with comparisons with other existing algorithms, have been provided to validate the proposed algorithms.     

A hybrid particle swarm optimization approach for the sequential ordering problem

The sequential ordering problem is a version of the asymmetric travelling salesman problem where precedence constraints on vertices are imposed. A tour is feasible if these constraints are fulfilled, and the objective is to find a feasible solution with minimum cost.     

Solving shortest path problem using particle swarm optimization

This paper presents the investigations on the application of particle swarm optimization (PSO) to solve shortest path (SP) routing problems. A modified priority-based encoding incorporating a heuristic operator for reducing the possibility of loop-formation in the path construction process is proposed for particle representation in PSO. Simulation experiments have been carried out on different network topologies for networks consisting of 15–70 nodes. It is noted that the proposed PSO-based approach can find the optimal path with good success rates and also can find closer sub-optimal paths with high certainty for all the tested networks. It is observed that the performance of the proposed algorithm surpasses those of recently reported genetic algorithm based approaches for this problem.     

基于蚁群算法的m–团队定向问题求解

介绍了m–团队定向问题的特性及目标,提出了基于蚁群算法的问题求解算法。在该算法中同种群不同个体之间采用访问禁忌表方式交换信息、相互协作共同完成路径优化,不同种群间通过“信息素”控制每个种群中个体的行为。计算结果表明了算法和模型的有 效性。     

Iterated local search for the team orienteering problem with time windows

A personalised electronic tourist guide assists tourists in planning and enjoying their trip. The planning problem that needs to be solved, in real-time, can be modelled as a team orienteering problem with time windows (TOPTW). In the TOPTW, a set of locations is given, each with a score, a service time and a time window. The goal is to maximise the sum of the collected scores by a fixed number of routes. The routes allow to visit locations at the right time and they are limited in length. The main contribution of this paper is a simple, fast and effective iterated local search meta-heuristic to solve the TOPTW. An insert step is combined with a shake step to escape from local optima. The specific shake step implementation and the fast evaluation of possible improvements, produces a heuristic that performs very well on a large and diverse set of instances. The average gap between the obtained results and the best-known solutions is only 1.8% and the average computation time is decreased with a factor of several hundreds. For 31 instances, new best solutions are computed.