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.     

LPNet: A DNN based latency prediction technique for application mapping in Network-on-Chip design

Analytical models used for latency estimation of Network-on-Chip (NoC) are not producing reliable accuracy. This makes these analytical models difficult to use in optimization of design space exploration. In this paper, we propose a learning based model using deep neural network (DNN) for latency predictions. Input features for DNN model are collected from analytical model as well as from Booksim simulator. Then this DNN model has been adopted in mapping optimization loop for predicting the best mapping of given application and NoC parameters combination. Our simulations show that using the proposed DNN model, prediction error is less than 12% for both synthetic and application specific traffic. More than 108 times speedup could be achieved using DPSO with DNN model compared to DPSO using Booksim simulator.     

基于离散微粒群算法求解背包问题研究

微粒群算法(PSO)是一种新的演化算法,主要用于求解数值优化问题.基于离散微粒群算法(DPSO)分别与处理约束问题的罚函数法和贪心变换方法相结合,提出了求解背包问题的两个算法:基于罚函数策略的离散微粒群算法(PFDPSO)和基于贪心变换策略的离散微粒群算法(GDPSO).通过将这两个算法与文献[7]中的混合微粒群算法(Hybrid_PSO)进行数值计算比较发现:对于求解大规模的背包问题,GDPSO非常优秀,其求解能力优于Hybrid_PSO和PFDPSO,是求解背包问题的一种非常有效的方法.     

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

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

求解TSP问题的自逃逸混合离散粒子群算法研究

通过对旅行商问题（TSP）局部最优解与个体最优解、群体最优解之间的关系分析,针对DPSO算法易早熟和收敛慢的缺点,重新定义了离散粒子群DPSO的速度、位置公式,结合生物界中物种在生存密度过大时个体会自动分散迁徙的特性和局部搜索算法（SEC）后,提出了一种新的自逃逸混合离散粒子群算法（SEHDPSO）.自逃逸思想是一种确定性变异操作,能使算法中陷入局部极小区域的粒子通过自逃逸行为进行全局寻优,从而克服算法易早熟的缺陷.仿真结果表明,SEHDPSO算法比混合蚁群算法（ACS＋2-OPT）具有更好的收敛性和搜索效率.     

基于异质交互式文化混合算法的机器人探测任务规划

针对机器人任务规划的混合算法缺乏通用结构框架的问题,借鉴文化进化的双重结构思想,提出一种交互式仿生群协进化混合算法体系框架．它包括基于佳点集遗传算法的上层知识空间、基于离散粒子群优化的底层主群空间、自上而下的影响机制和自下而上的接受机制,以实现异质种群交互;通过预留用户评价接口,实现了算法的人机交互．为提高粒子群优化性能,运用佳点集初始化主群空间,使初始粒子均匀分布于可行解内;提出新的粒子进化模型并定义粒子进化力指标,提高了种群的多样性和算法稳定性;通过引入邻域局部搜索策略增强算法的搜索能力．最后,采用TSPLIB标准数据对异质交互式文化混合算法（HICHA）进行测试,实验结果表明,该算法无论是在收敛速度或稳定性方面,还是在求解质量方面,均优于其它算法．HICHA为机器人探测任务规划问题的解决提供了新思路．     

Discrete particle swarm optimization method for the large-scale discrete time–cost trade-off problem

Despite many research studies have concentrated on designing heuristic and meta-heuristic methods for the discrete time–cost trade-off problem (DTCTP), very little success has been achieved in solving large-scale instances. This paper presents a discrete particle swarm optimization (DPSO) to achieve an effective method for the large-scale DTCTP. The proposed DPSO is based on the novel principles for representation, initialization and position-updating of the particles, and brings several benefits for solving the DTCTP, such as an adequate representation of the discrete search space, and enhanced optimization capabilities due to improved quality of the initial swarm. The computational experiment results reveal that the new method outperforms the state-of-the-art methods, both in terms of the solution quality and computation time, especially for medium and large-scale problems. High quality solutions with minor deviations from the global optima are achieved within seconds, for the first time for instances including up to 630 activities. The main contribution of the proposed particle swarm optimization method is that it provides high quality solutions for the time–cost optimization of large size projects within seconds, and enables optimal planning of real-life-size projects.     

基于蚁群优化算法的NoC映射

功耗问题正逐渐成为NoC领域的研究热点,很多研究人员都在研究NoC功耗最小化的设计技术。文章采用一种有效的蚁群优化算法实现了NoC映射：在自动映射处理单元的同时,尽可能地减少了系统的通讯功耗。实验结果表明采用蚁群优化算法可以很快地收敛;针对不同的应用,可以减少25％-70％通讯功耗。     

一种具有混合编码的二进制差分演化算法

差分演化(DE)是Storn和Price于1997年提出的一种基于个体差异重组思想的演化算法,非常适用于求解连续域上的最优化问题.首先引入"差异算子"等概念,给出DE的一种简洁算法描述,并分析了它所具有的特性.然后,为了使DE能够求解离散域上的最优化问题,基于数学变换思想引入"辅助搜索空间"和"个体混合编码"等概念,通过定义一个特殊的满射变换,在辅助搜索空间的作用下将连续域上的高效差分演化搜索变换为离散域上的同步演化搜索,由此提出了第1个二进制差分演化算法:具有混合编码的二进制差分演化算法(HBDE).接着,给出了HBDE的依概率收敛和完全收敛的定义,并利用离散Markov随机理论证明了HBDE是完全收敛的. HBDE不仅完全具有DE的各种特性和所有优点,而且非常适用于求解离散域上的最优化问题,对随机生成的大规模3-SAT问题实例和典型0/1背包问题实例的数值计算表明:该算法具有很好的全局收敛性和稳定性,其性能远远超过二进制粒子群优化算法和遗传算法.     

PSOSA混合优化策略

本文提出了一种微粒群算法与模拟退火算法相结合的混合优化方法，该方法在群体进化的每一代中，首先通过微粒群算法的进化方法来控制微粒的飞行方向，然后利用模拟退火算法来拓展其搜索领域。这样既可以利用微粒群算法的收敛快速性，又可以利用模拟退火算法的全局收敛性。本文还证明了该混合优化方法依概率1收敛于全局最优解。仿
真结果表明，在搜索空间维数增大时，该方法的全局收敛性明显优于基本微粒群算法。     

基于克隆多尺度协同开采的离散微粒群算法

提出一种克隆多尺度协同开采的离散微粒群算法.多尺度变异概率根据粒子适应值大小进行动态调节,在算法初期通过大尺度概率变异增加算法多样性,后期通过逐渐减小的小尺度变异提高算法在最优解附近的局部精确解搜索性能,对当前最优解进行克隆选择,可进一步增强算法逃出局部极小解的能力以及所求解的精度.将算法应用于5个benchmark函数优化问题并与其他算法比较,结果表明该算法不仅能增强全局解搜索性能,同时最优解的精度也有所提高.     

并行定向扰动的混合粒子群优化算法

针对全向变异易使粒子失去已有的有利搜索信息的问题, 提出了一种并行定向变异的混合粒子群优化算法。该算法以当前群体最优位置为基准, 用变异信息矩阵和混沌位置变异矩阵对群体进行并行定向扰动, 有效利用了现有的有利搜索信息。该算法将并行定向变异与序列二次规划法融为一体, 实现了全局搜索和局部寻优的统一。仿真实验和比较分析结果表明并行定向变异混合粒子群优化算法具有良好的、稳定的优化效果。     

Energy efficient heuristic application mapping for 2-D mesh-based network-on-chip

Application mapping in 2-D mesh-based Network-on-Chip (NoC) architecture is an optimization problem in which each application task (e.g., processor or memory units) should be mapped one-to-one onto a network element (switch or router) to optimize performance requirements (e.g., communication energy or communication latency) under certain platform constraints (e.g., bandwidth and/or latency). Network-on-Chip is a scheme that establishes links between limited application-specific components within Multi-Processor System-on-Chip (MPSoC), but it has a vital role to ensure the maximum data transfer rate and reduce total number of physical interconnections. Most of the works on heuristic application mapping for mesh-based NoC design aim to minimize both total communication energy and run-time, however they experience the following issues: (i) relatively high CPU time due to linear search for the task and tile mapping combinations, (ii) consumption of relatively high communication energy due to random tile selection when two or more tiles are equivalent in terms of average weighted distance by their adjacent mapped tasks, and (iii) even after constructive application mapping, some of the tasks consume higher communication energy due to their inappropriate placements. In this paper we present a low time-complexity heuristic mapping algorithm of weighted application graph under permissible bandwidth constraint to minimize communication energy of 2-D mesh-based NoC architecture. The experimental results of multimedia benchmarks, as well as randomly generated samples show the low communication energy as well as time-complexity under bandwidth constraints in comparison to the recent heuristic application mapping approaches. In our approach, the communication energy is also close to the optimal solution obtained by Integer Linear Programming (ILP).     

A hybrid swarm intelligence algorithm for the travelling salesman problem

Abstract: We present a hybrid model named HRKPG that combines the random‐key search method and an individual enhancement scheme to thoroughly exploit the global search ability of particle swarm optimization. With a genetic algorithm, we can expand the area of exploration of individuals in the solution space. With the individual enhancement scheme, we can enhance the particle swarm optimization and the genetic algorithm for the travelling salesman problem. The objective of the travelling salesman problem is to find the shortest route that starts from a city, visits every city once, and finally comes back to the start city. With the random‐key search method, we can search the ability of the particle and chromosome. On the basis of the proposed hybrid scheme of HRKPG, we can improve solution quality quite a lot. Our experimental results show that the HRKPG model outperforms the particle swarm optimization and genetic algorithm in solution quality.     

Improving solution characteristics of particle swarm optimization using digital pheromones

In this paper, a new approach to particle swarm optimization (PSO) using digital pheromones to coordinate swarms within an n-dimensional design space is presented. In a basic PSO, an initial randomly generated population swarm propagates toward the global optimum over a series of iterations. The direction of the swarm movement in the design space is based on an individual particle’s best position in its history trail (pBest), and the best particle in the entire swarm (gBest). This information is used to generate a velocity vector indicating a search direction toward a promising location in the design space. The premise of the research presented in this paper is based on the fact that the search direction for each swarm member is dictated by only two candidates—pBest and gBest, which are not efficient to locate the global optimum, particularly in multi-modal optimization problems. In addition, poor move sets specified by pBest in the initial stages of optimization can trap the swarm in a local minimum or cause slow convergence. This paper presents the use of digital pheromones for aiding communication within the swarm to improve the search efficiency and reliability, resulting in improved solution quality, accuracy, and efficiency. With empirical proximity analysis, the pheromone strength in a region of the design space is determined. The swarm then reacts accordingly based on the probability that this region may contain an optimum. The additional information from pheromones causes the particles within the swarm to explore the design space thoroughly and locate the solution more efficiently and accurately than a basic PSO. This paper presents the development of this method and results from several multi-modal test cases.     

求解异构并行系统任务分配的混合离散粒子群算法

针对异构并行任务分配的最小完成时间和负载均衡组合优化问题,提出一种混合离散微粒群算法,将启发式Sufferage算法引入离散微粒群算法（DPSO）中,改进DPSO算法中的位置速度关系模型,提高DPSO算法的搜索效率和精度．通过实验验证,从算法效率和收敛速度上均优于DPSO算法和GA算法,且负载均衡度较好．     

Discrete cooperative particle swarm optimization for FPGA placement

Particle swarm optimization (PSO) is a stochastic optimization technique that has been inspired by the movement of birds. On the other hand, the placement problem in field programmable gate arrays (FPGAs) is crucial to achieve the best performance. Simulated annealing algorithms have been widely used to solve the FPGA placement problem. In this paper, a discrete PSO (DPSO) version is applied to the FPGA placement problem to find the optimum logic blocks and IO pins locations in order to minimize the total wire-length. Moreover, a co-operative version of the DPSO (DCPSO) is also proposed for the FPGA placement problem. The problem is entirely solved in the discrete search space and the proposed implementation is applied to several well-known FPGA benchmarks with different dimensionalities. The results are compared to those obtained by the academic versatile place and route (VPR) placement tool, which is based on simulated annealing. Results show that both the DPSO and DCPSO outperform the VPR tool for small and medium-sized problems, with DCPSO having a slight edge over the DPSO technique. For higher-dimensionality problems, the algorithms proposed provide very close results to those achieved by VPR.     

可靠电压频率岛感知的异步片上网络能耗优化

针对采用2D-Torus拓扑结构且支持电压频率岛（VFI）的异步片上网络能耗优化问题,提出了具有可靠性的、基于电压频率岛的划分和分配及片上网络任务映射的能耗优化方法．该方法采用递进优化的方式,根据IP核的动态处理能耗,不同电压频率岛之间的转换能耗和可靠性带来的能耗开销定义了IP核在电压频率岛之间移动的阈值函数,并通过对阈值函数进行判断完成电压频率岛的划分和分配,应用基于三元相关性量子粒子群优化算法完成处理单元到资源节点的映射,在映射中考虑保证系统可靠性的通信开销,对异步片上网络系统的可靠性进行优化．实验结果表明,该算法可以在不过多消耗能耗的情况下显著的改善片上网络系统的可靠性,且可有效降低NOC系统的能耗.     

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.     

Evolution of heterogeneous ensembles through dynamic particle swarm optimization for video-based face recognition

In many real-world applications, pattern recognition systems are designed a priori using limited and imbalanced data acquired from complex changing environments. Since new reference data often becomes available during operations, performance could be maintained or improved by adapting these systems through supervised incremental learning. To avoid knowledge corruption and sustain a high level of accuracy over time, an adaptive multiclassifier system (AMCS) may integrate information from diverse classifiers that are guided by a population-based evolutionary optimization algorithm. In this paper, an incremental learning strategy based on dynamic particle swarm optimization (DPSO) is proposed to evolve heterogeneous ensembles of classifiers (where each classifier corresponds to a particle) in response to new reference samples. This new strategy is applied to video-based face recognition, using an AMCS that consists of a pool of fuzzy ARTMAP (FAM) neural networks for classification of facial regions, and a niching version of DPSO that optimizes all FAM parameters such that the classification rate is maximized. Given that diversity within a dynamic particle swarm is correlated with diversity within a corresponding pool of base classifiers, DPSO properties are exploited to generate and evolve diversified pools of FAM classifiers, and to efficiently select ensembles among the pools based on accuracy and particle swarm diversity. Performance of the proposed strategy is assessed in terms of classification rate and resource requirements under different incremental learning scenarios, where new reference data is extracted from real-world video streams. Simulation results indicate the DPSO strategy provides an efficient way to evolve ensembles of FAM networks in an AMCS. Maintaining particle diversity in the optimization space yields a level of accuracy that is comparable to AMCS using reference ensemble-based and batch learning techniques, but requires significantly lower computational complexity than assessing diversity among classifiers in the feature or decision spaces.