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

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

基于动态邻域的QPSO算法

为了保证种群的多样性,提高算法的全局搜索能力,在具有量子行为的粒子群优化算法（QPSO）中引入邻域拓扑结构的概念,采用邻域结构中的轮形结构,提出一种基于动态邻域的具有量子行为的粒子群优化算法（NQPSO）。并用若干个标准函数进行测试,比较了NQPSO算法与标准PSO（SPSO）和传统QPSO算法的性能。实验结果表明,NQPSO算法具有强的全局搜索能力,其性能优于其它两个算法,尤其体现在解决高维的优化问题上。     

种群拓扑结构对人工鱼群算法性能的影响

基本人工鱼群算法采用基于距离的邻域拓扑结构,存在计算量大、运行速度慢等问题。为此,引入粒子群优化算法中的4种典型种群拓扑结构:星形,轮形,环形和冯·诺依曼结构,代替基于距离的邻域拓扑结构,并分析不同构对算法性能的影响。在5个准测试函数上的实验结果表明,对于单峰函数,星形结构算法的优化效果较好;对于局部最优点较多的函数,轮形和环形结构算法的优化效果较好。根据优化问题的复杂度选用不同的拓扑结构,可以提高人工鱼群算法的优化性能。     

基于环形邻域拓扑的自适应速度PSO算法

为克服全局粒子群优化算法易陷入局部最优的缺点,基于全局自适应速度粒子群优化（SAVPSO）算法,给出一种基于环形邻域拓扑的局部SAVPSO算法来求解约束优化问题,同时采用动态目标方法（DOM）来有效处理约束条件,并以13个经典的测试函数为例对算法的性能进行仿真实验研究。测试结果表明,与全局SAVPSO算法相比,该算法具有较强的全局寻优能力,可以较好地避免陷入局部最优;另外,粒子的邻域大小及实现形式对算法的性能均有一定的影响。     

层次环形拓扑结构的动态粒子群算法

粒子群算法（PSO）的拓扑结构决定粒子之间的信息交互方式,是影响算法性能的关键因素。为提高算法性能,提出了一种层次环形拓扑结构的动态粒子群算法（HRPSO）,粒子组成的环被分配在规则树中,算法运行时,环在层次中动态移动。通过6个标准测试函数优化,比较了HRPSO与几种基准算法的性能,实验结果证明HRPSO在精确性和稳定性上具有优势。     

基于冯诺依曼拓扑结构的骨干粒子群优化算法

为了改善骨干粒子群优化BBPSO算法的易早熟、易陷入局部最优解等缺点,提出了一种基于冯诺依曼拓扑结构的改进骨干粒子群优化VBBPSO算法。新算法提出"兼顾落后粒子"概念,通过应用冯诺依曼拓扑结构构造邻域,用邻域最优解取代全局最优解,引入中心项调节系数,在邻域范围内调整BBPSO算法的进化中心项与离散控制项,提高了算法全局探索能力与局部开发能力。实验结果表明,较几种经典的BBPSO算法,VBBPSO算法的综合性能有明显提升。     

基于网络邻域拓扑的粒子群优化算法

探讨类无标度网、全局耦合网、环形网、随机网、星形网等邻域拓扑结构对粒子群优化算法寻优效果的影响。理论分析与实验结果显示,以类无标度网作为邻域拓扑结构的粒子群优化算法在误差范围内的寻优效果最好,收敛速度最快,可以较好地避免陷入局部最优,且网络平均度对粒子群优化算法的寻优效果有一定的影响。     

一种具有动态拓扑结构的粒子群算法研究

受小世界网络模型的启发,提出了一种具有动态拓扑结构的新颖粒子群算法。该算法通过对每个粒子邻域的记忆和更新,模拟小世界网络模型中的信息传播方式。在大量基准问题上的实验结果显示,提出的算法能有效保持优秀粒子与非优粒子所占比例的均衡性,维持了种群的多样性,避免了经典粒子群算法在高维、多峰问题上的早熟收敛现象。     

一种改进的自适应邻域粒子群优化算法

在对粒子群优化(PSO)算法进行深入分析的基础上,建立了自适应邻域更新机制,再对惯性权重更新机制进行自适应化,分别从拓扑邻域结构和惯性权重两个角度对局部版PSO算法进行了改进,提出了一种实用、高效的自适应邻域粒子群优化算法,经7个标准测试函数验证,该算法具有较高效率和精度。     

动态邻域混合粒子群优化算法

粒子群优化(PSO)算法对于多峰搜索问题一直存在早熟收敛问题。为在增强PSO算法全局搜索能力的同时提高收敛速度,提出一种动态邻域混合粒子群优化算法DNH_PSO,采用PSO局部模型,将随机拓扑和冯诺依曼拓扑相结合形成动态邻域,提高算法的全局搜索能力,为增强算法的局部搜索能力并加快收敛速度,使用粒子邻域全面学习策略,将拟牛顿法引入算法中。与其他PSO实验对比分析表明,该算法对于多峰搜索问题具有较好的全局收敛性。     

Task Scheduling in Distributed Systems Using Heap Intelligent Discrete Particle Swarm Optimization

The optimal mapping of tasks to the processors is one of the challenging issues in heterogeneous computing systems. This article presents a task scheduling problem in distributed systems using discrete particle swarm optimization (DPSO) algorithm with various neighborhood topologies. The DPSO is a recent metaheuristic population‐based algorithm. In DPSO, the set of particles in a swarm flies through the N‐dimensional search space by learning from both the personal best position and a neighborhood best position. Each particle inside the swarm belongs to a specific topology for communicating with neighboring particles in the swarm. The neighborhood topology affects the performance of DPSO significantly, because it determines the rate at which information transmits through the swarm. The proposed DPSO algorithm works on dynamic topology that is binary heap tree for communication between the particles in the swarm. The performance of the proposed topology is compared with other topologies such as star, ring, fully connected, binary tree, and Von Neumann. The three well‐known performance measures such as Makespan, mean flow time, and reliability cost are used for the comparison of the proposed topology with other neighborhood topologies. Computational simulation results indicate that the performance of DPSO algorithm has shown significant improvement with binary heap tree topology used for communication among the particles in the swarm.     

基于共同邻居邻域拓扑稠密性加权的链路预测方法

链路预测旨在利用已知的网络节点和拓扑结构信息,预测网络中未连接的两个节点之间存在连边的可能性。基于网络拓扑相似性的链路预测方法计算复杂度低且预测效果好,但现有的相似性指标对共同邻居的邻域拓扑信息考虑较少。针对此问题,提出一种基于共同邻居邻域拓扑稠密性加权的链路预测方法。首先,基于邻域拓扑相对稠密指数量化节点的邻域拓扑结构;然后,利用共同邻居的节点度和邻域拓扑相对稠密指数刻画共同邻居及其邻域拓扑的相似性贡献;最后,提出基于共同邻居邻域拓扑稠密性加权的节点相似性指标。在多个实际网络数据上的实验结果表明,与现有相似性指标相比,该方法能够取得更高的预测精度。     

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

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

基于冯诺依曼邻居的粒子群多阈值分割算法*

针对多阈值分割问题,提出了一种新的多阈值分割算法。该算法对传统的Otsu进行修改,使其能够更准确地找到直方图中谷的位置;并利用冯诺依曼拓扑邻居粒子群作为阈值优化算法,提高了优化性能。提出了构造冯诺依曼拓扑结构的方法,并分析和比较了它与全互连结构的差别。实验结果显示此算法具有较好的性能。     

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.     

Neighborhood-adaptive differential evolution for global numerical optimization

In this study, we consider the scenario that differential evolution (DE) is applied for global numerical optimization and the index-based neighborhood information of population is used for enhancing the performance of DE. Although many methods are developed under this scenario, neighborhood information of current population has not been systematically exploited in the DE algorithm design. Furthermore, previous studies have shown the effect of neighborhood topology interacted with the function being solved. However, there are few investigations of DE that consider different topologies for different functions during the evolutionary process. Motivated by these observations, a new DE framework, named neighborhood-adaptive DE (NaDE), is presented. In NaDE, a pool of index-based neighborhood topologies is firstly used to define multiple neighborhood relationships for each individual and then the neighborhood relationships are adaptively selected for the specific functions during the evolutionary process. In this way, a more appropriate neighborhood relationship for each individual can be determined adaptively to match different phases of the search process for the function being solved. After that, a neighborhood-dependent directional mutation operator is introduced into NaDE to generate a new solution with the selected neighborhood topology. Being a general framework, NaDE is easy to implement and can be realized with most existing DE algorithms. In order to test the effectiveness of the proposed framework, we have evaluated NaDE via investigating several instantiations of it. Experimental results have shown that NaDE generally outperforms its corresponding DE algorithm on different kinds of optimization problems. Moreover, the synergy among different neighborhood topologies in NaDE is also revealed when compared with the DE variants with single neighborhood topology.