A novel discrete particle swarm optimization algorithm for meta-task assignment in heterogeneous computing systems

Optimal assignment of a meta-task in heterogeneous computing systems is NP-complete in the general case. Therefore, heuristic approaches must be employed to find good solutions within a reasonable time. We propose a novel discrete particle swarm optimization (DPSO) algorithm for this problem. Firstly, to make particle swarm optimization algorithm more suitable for solving task assignment problems, particles are represented as integer vectors and a new position update method is developed based on discrete domain. Secondly, an effective variable neighborhood descent algorithm is applied to emphasize exploitation. In addition, migration mechanism is introduced with the hope to escape from possible local optimum and to balance the exploration and exploitation. Computational simulations and comparisons based on a set of benchmark instances indicate that the proposed DPSO algorithm is a viable approach for the task assignment problem.     

一种基于可变多簇结构的动态概率粒子群优化算法

针对传统粒子群优化算法中全连接型拓扑和环形拓扑的特点,引入了一种粒子群信息共享方式——多簇结构,进而基于多簇结构提出了动态可变拓扑策略以协调动态概率粒子群优化算法的勘探和开采能力,并从理论上分析了最优信息在各种拓扑中的传播,同时从图论角度分析了几种经典拓扑以及动态可变多簇结构的统计特性.通过典型的Benchmark函数优化问题测试并比较了几种经典拓扑以及可变拓扑在高斯动态粒子群优化算法中的性能.实验结果表明,基于多簇结构的可变拓扑策略在求解复杂优化问题时优势明显,可以有效地避免算法陷入局部最优,在保证收敛速度的同时增强了算法的全局搜索能力.     

基于近邻关系求解TSP的离散PSO算法*

针对NP-hard组合优化问题,提出一种基于启发因子的自适应混合离散粒子群算法对其进行求解。通过改进离散粒子群运动方程,并加入启发因子,从而提高算法的收敛性和稳定性;依据粒子多样性的动态变化,引入自适应扰动算子,以保持种群进化能力。该算法对低、中、高维的TSP数据仿真结果表明,与其他混合离散粒子群算法相比,具有更好的全局收敛性和稳定性。     

认知智能电网邻域网络的频谱分配策略

可靠、高效的通信网络是充分发挥智能电网潜力的前提。针对智能电网的无线通信环境存在频谱短缺、资源利用效率低等问题,文中将认知无线电技术应用于智能电网的邻域网络通信中,引入认知智能电网概念以保证业务传输的公平性和有效性,考虑了通信过程中的信噪比和路径损耗后,选择网络吞吐量作为信道效益,并在拓扑结构固定的城市居民小区进行建模仿真。在此基础上,提出了一种改进二进制猫群(Weight Binary Cat Swarm Optimization,WBCSO)优化的频谱分配算法。首先,在二进制猫群算法(Binary Cat Swarm Optimization,BCSO)的速度更新公式中加入非线性动态的惯性权重,它随着迭代次数的增加而非线性地递减,以防止算法早熟;其次,引入繁殖算子,产生子代猫群以增加种群的多样性,以获取更好的全局最优解;然后,选用了4个常用的基准函数对改进后的算法进行性能测试,测试结果表明WBCSO算法的优化均值和标准差都优于BCSO算法;最后,以系统总效益和用户公平性为优化目标,将其与二进制遗传算法(Binary Genetic Algorithm,BGA)和二进制粒子群算法(Binary Particle Swarm Optimization,BPSO)进行了对比实验,仿真实验表明,WBCSO算法最终的系统总效益和用户公平性指数比BCSO算法分别高出了13.7%和14.6%,且比二进制群算法和遗传算法的性能都要好,进而表明改进二进制猫群算法在认知智能电网邻域网的频谱分配中具有收敛速度快、搜索能力强的特点。     

Application mapping to mesh NoCs using a Tabu-search based swarm optimization

A hybrid optimization scheme is presented that combines Tabu-search, communication volume based core swapping and Discrete Particle Swarm Optimization (DPSO) for NoC (Network-on-Chip) mapping. The main goal of the optimization is to map an application core-graph such that the overall communication latency of the NoC is minimal. It is assumed that the target NoC has a 2D-mesh topology. DPSO is used as the main optimization technique where each swarm particle move is influenced by the global and local best, previous visited search space locations, and a deterministic method to reduce communication volume of existing mapping. We employ a Tabu-list to discourage swarm particles to re-visit the explored search space and propose an alternative direction towards the intended movement direction. The methodology is tested for some multimedia applications as well as randomly generated large network of synthetic cores-graphs. For larger applications, our hybrid scheme generates high quality NoC mapping solutions as compared to DPSO based existing techniques.     

基于Inver-Over算子的改进离散粒子群优化算法

离散粒子群算法能充分利用粒子的局部极值和全局极值信息,但收敛速度慢、精度低;Inver-Over算子收敛速度快、精度高,但学习具有盲目性。结合二者优点,文中提出一种基于Inver-Over算子的改进离散粒子群优化算法。为防止早熟收敛,引入局部最优子群的概念,使粒子向局部最优子群中粒子学习而不是向个体局部最优学习。引入3个参数:学习选择概率用以确定粒子的学习对象,代数阈值确定何时向全局最优粒子学习,局部最优子群比决定最优子群的规模。讨论这些参数的选择原则,并给出相应参考选择范围。研究表明,文中算法与普通离散粒子群优化算法和郭涛算法相比,收敛速度和求解精度都有较大提高。     

直觉模糊离散粒子群算法

在研究和分析离散粒子群算法(DBPSO)的基础上,提出一种基于直觉模糊熵的改进离散粒子群算法(IFDPSO).该算法以直觉模糊熵作为粒子群状态测度和速度变异的基本参数,同时加入了位置变异策略以保证算法在有限时间内尽可能多地遍历到次优位置及其邻域,增强了算法的全局寻优能力.实验数据表明,在求解较大规模整数规划问题(如0-1背包问题)时,IFDPSO比DPSO和蚁群算法(ACO)更为有效,从而为解决这类问题提供了新的途径和方法.     

混合拓扑结构的粒子群算法及其在测试数据生成中的应用研究

粒子群算法(PSO)的拓扑结构是影响算法性能的关键因素,为了从根源上避免粒子群算法易陷入局部极值及早熟收敛等问题,提出一种混合拓扑结构的粒子群优化算法(MPSO)并将其应用于软件结构测试数据的自动生成中。通过不同邻域拓扑结构对算法性能影响的分析,采用一种全局寻优和局部寻优相结合的混合粒子群优化算法。通过观察粒子群的多样性反馈信息,对每一代种群粒子以进化时选择全局拓扑结构模型(GPSO)或局部拓扑结构模型(LPSO)的方法进行。实验结果表明,MPSO使得种群的多样性得到保证,避免了粒子群陷入局部极值,提高了算法的收敛速度。     

Particle swarm optimization with expanding neighborhood topology for the permutation flowshop scheduling problem

This paper introduces a new algorithmic nature-inspired approach that uses particle swarm optimization (PSO) with different neighborhood topologies, for successfully solving one of the most computationally complex problems, the permutation flowshop scheduling problem (PFSP). The PFSP belongs to the class of combinatorial optimization problems characterized as NP-hard and, thus, heuristic and metaheuristic techniques have been used in order to find high quality solutions in reasonable computational time. The proposed algorithm for the solution of the PFSP, the PSO with expanding neighborhood topology, combines a PSO algorithm, the variable neighborhood search strategy and a path relinking strategy. As, in general, the structure of the social network affects strongly a PSO algorithm, the proposed method using an expanding neighborhood topology manages to increase the performance of the algorithm. As the algorithm starts from a small size neighborhood and by increasing (expanding) in each iteration the size of the neighborhood, it ends to a neighborhood that includes all the swarm, and it manages to take advantage of the exploration abilities of a global neighborhood structure and of the exploitation abilities of a local neighborhood structure. In order to test the effectiveness and the efficiency of the proposed method, we use a set of benchmark instances of different sizes and compare the proposed method with a number of other PSO algorithms and other algorithms from the literature.     

A discrete particle swarm optimization algorithm with self-adaptive diversity control for the permutation flowshop problem with blocking

This paper proposes a discrete particle swarm optimization (DPSO) algorithm for the m-machine permutation flowshop scheduling problem with blocking to minimize the makespan, which has a strong industrial background, e.g., many production processes of chemicals and pharmaceuticals in chemical industry can be reduced to this problem. To prevent the DPSO from premature convergence, a self-adaptive diversity control strategy is adopted to diversify the population when necessary by adding a random perturbation to the velocity of each particle according to a probability controlled by the diversity of the current population. In addition, a stochastic variable neighborhood search is used as the local search to improve the search intensification. Computational results using benchmark problems show that the proposed DPSO algorithm outperforms previous algorithms proposed in the literature and that it can obtain 111 new best known upper bounds for the 120 benchmark problems.     

Detecting particle swarm optimization

Here, we propose a detecting particle swarm optimization (DPSO). In DPSO, we define several detecting particles that are randomly selected from the population. The detecting particles use the newly proposed velocity formula to search the adjacent domains of a settled position in approximate spiral trajectories. In addition, we define the particles that use the canonical velocity updating formula as common particles. In each iteration, the common particles use the canonical velocity updating formula to update their velocities and positions, and then the detecting particles do search in approximate spiral trajectories created by the new velocity updating formula in order to find better solutions. As a whole, the detecting particles and common particles would do the high‐performance search. DPSO implements the common particles' swarm search behavior and the detecting particles' individual search behavior, thereby trying to improve PSO's performance on swarm diversity, the ability of quick convergence and jumping out the local optimum. The experimental results from several benchmark functions demonstrate good performance of DPSO. Copyright © 2008 John Wiley & Sons, Ltd.     

基于带近邻因子的粒子群算法的非线性系统辨识

针对非线性系统辨识的问题,提出了一种改进的粒子群算法.该算法引入近邻因子,增加了当前粒子的社会学习功能,可有效克服基本粒子群算法易陷于局部最优解的常见弊病.算法对未知非线性系统具有充分的逼近能力,对噪声不敏感,实现了对一类非线性系统的有效辨识.     

基于动态邻域的粒子群算法的研究

研究了邻域拓扑结构对粒子群算法性能的影响。设计了两种动态邻域生成策略,并基于一组具有代表性的测试函数,对两种典型的算法模型——标准的粒子群算法（CPSO）和充分联系的粒子群算法（FIPS）进行实验。实验结果表明,不同的邻域拓扑结构和不同的算法模型都能够影响粒子群算法的性能。     

A two-stage discrete particle swarm optimization for the problem of multiple multi-level redundancy allocation in series systems

Nowadays, the redundancy allocation problem (RAP) is increasingly becoming an important tool in the initial stages of or prior to planning, designing, and control of systems. The multiple multi-level redundancy allocation problem (MMRAP) is an extension of the traditional RAP such that all available items for redundancy (system, module and component) can be simultaneously chosen. In this paper, a novel particle swarm optimization algorithm (PSO) called the two-stage discrete PSO (2DPSO) is presented to solve MMRAP in series systems such that some subsystems or modules consist of different components in series. To the best of our knowledge, this is the first attempt to use a PSO to MMRAP. The proposed PSO used a totally new, very simple, effective and efficient mechanism to move to the next position without velocity. The result obtained by 2DPSO has been compared with those obtained by genetic algorithm (GA) and binary PSO (BPSO). Computational results show that the proposed 2DPSO is very competitive and performs well in the number of times it finds the best solutions, the average numbers of the earliest finding of the best solutions, and computation times.     

解决零空闲流水线调度问题的离散粒子群算法

研究了以最大完工时间为目标的零空闲流水线调度问题.提出一种复杂度为O(nm)的最大完工时间算法和一种快速插入邻域搜索算法;提出了解决该问题的离散粒子群调度算法,并结合简化邻域搜索算法给出了提高调度算法性能的措施.仿真实验表明了所得算法的有效性.     

基于动态邻域微粒群的Smith预估双控制器设计

针对模型未知时滞系统的预测补偿控制,提出一种基于动态邻域拓扑微粒群算法以优化动态神经网络的参数,并将其作为预估器和辨识器应用于一种新的Smith预估双控制器结构设计.利用微粒群算法空间搜索能力指标,动态建立邻域拓扑结构,优化神经网络参数,并将两者的组合模型应用于新的双控制器结构,将负载扰动和定值控制分开,以提高Smith预测补偿模型的控制精度和鲁棒性,最后通过仿真验证了所提出方法的有效性.     

Application of dynamic neighborhood small population particle swarm optimization for reconfiguration of shipboard power system

In all-electric navy ships, severe damage or faults may occur during different conditions. As a result, critical loads may suffer from power deficiencies, ultimately leading to a complete system collapse. Therefore, a fast reconfiguration of shipboard power system (SPS) is necessary to serve the critical loads. This work proposes a novel swarm intelligent algorithm based on dynamic neighborhood small population particle swarm optimization (PSO) (DNSPPSO). DNSPPSO is a variant of PSO having fewer numbers of particles and regenerating new solutions within the search space every few iterations. This concept of regeneration in DNSPPSO makes the algorithm fast and greatly enhances its capability. Meanwhile, this algorithm can handle multi-objective problem effectively by using dynamic neighborhood strategy. This technique sorts the objectives and evaluates objectives one by one but retaining the global best solution and fitness so far. Therefore, the strategy converts the multi-objective problem into a single objective optimization problem. The strength of the proposed reconfiguration strategy is demonstrated by an 8-bus test example in Matlab environment comparing with discrete PSO (DPSO), small population PSO (SPPSO) and NSGA-II.     

目(2055)基于聚类的多子群粒子群优化算法*

在粒子群优化算法基础上,提出了基于聚类的多子群粒子群优化算法。该算法在每次迭代过程中首先通过聚类方法把粒子群体分成若干个子群体,然后粒子群中的粒子根据其个体极值和“子群”中的最优粒子更新自己的速度和位置值。这种处理增加了粒子之间的信息交换,利用了更多粒子在迭代过程中的信息,使算法的收敛性能更好。仿真结果表明,该算法的性能优于粒子群优化算法。     

基于双重距离的多目标粒子群优化算法

多目标粒子群优化(multi-objective particle swarm optimization,MOPSO)算法在维护收敛性的同时搜索分布良好的最优解集较为费力.为此,提出一种基于双重距离的MOPSO,由种群的平均距离定义粒子的邻域空间,邻域粒子数为粒子的等级,数量越多,粒子的等级越大.当等级相同时,算法结合粒子的拥挤距离选择最优粒子,并更新外部归档集.此外,算法结合粒子的变异行为避免陷入局部最优.在对比实验中,该算法在收敛性和多样性上可取得较优结果.最后,将该算法应用到电力系统的环境/经济调度模型(environmental/economic dispatch,EED),也可获得性能较好的解集.     

基于扩散机制的双种群粒子群优化算法*

为了避免标准粒子群优化算法（PSO）过早收敛的缺点,把热力学中的扩散现象引入到PSO算法的改进当中,提出了基于扩散机制的双种群粒子群优化算法(DPSO)。DPSO算法中定义了粒子的扩散能、种群的温度和粒子的扩散概率三个概念,两个群体中的粒子在进化过程中根据粒子的扩散概率被选入到各自种群的扩散池中,从而实现两个种群之间信息的交换和共享。通过解决典型的多峰、高维函数优化问题来证实DPSO算法的有效性,实验结果表明DPSO比标准PSO具有更高的性能。