基于大值堆的自调整粗粒度并行遗传算法模型

一般粗粒度并行遗传算法（CGGA）的性能受诸多因素的影响表现不尽如人意。以降低通信代价为主要目标，受物种金字塔模型的启发，设计了一种双阈值限制下的自调整堆结构，并对其堆调整具体操作进行了改进，以期望改进后算法中种群间的通信代价大幅度降低，优化收敛速度，提高算法效率。通过对遗传算法的几个典型测试函数通信量的分析和实验表明，基于该模型的并行遗传算法在降低通信代价、提高收敛速度、优化最终解方面收效明显。     

基于大值堆的自调整粗粒度并行遗传算法模型

一般粗粒度并行遗传算法(CGGA)的性能受诸多因素的影响表现不尽如人意。以降低通信代价为主要目标,受物种金字塔模型的启发,设计了一种双阈值限制下的自调整堆结构,并对其堆调整具体操作进行了改进,以期望改进后算法中种群间的通信代价大幅度降低,优化收敛速度,提高算法效率。通过对遗传算法的几个典型测试函数通信量的分析和实验表明,基于该模型的并行遗传算法在降低通信代价、提高收敛速度、优化最终解方面收效明显。     

基于模式迁移策略的并行遗传算法

通过分析影响并行遗传算法性能的诸多因素，以降低通信代价为问题的突破口，提出一种基于模式定量的迁移策略SMS．SMS迁移策略借鉴网络信息传输机制，通过模式识别压缩提取出子种群中的优质遗传信息，再将一遗传信息在另一子种群中按比例传播，文中首先依据模式定理对模式迁移策略的算法有效性进行了探讨，然后从理论角度给出了采用模式迁移策略后通信量降低的形式化度量，最后分析了由此带来的算法可扩展性的提高。     

动态拓扑下的可重构服务承载网资源迁移方法

提出了动态网络模型分析承载网资源迁移问题,并引入了迁移效率概念,设计了资源迁移方法。该方法以元请求迁移过程为基础,分别针对拓扑收缩和增长情况提出资源容错迁移和资源均衡迁移两种算法。仿真结果表明,基于迁移效率的资源迁移方法提高了请求接受率和负载均衡度,同时降低了迁移代价。     

基于DSP的分布式并行遗传算法

提出了一种基于多片DSP的单向迁移分布式并行遗传算法.将每一片DSP构成算法的一个子群体,通过DSP本身所具有的高速串行通信接口连接成环状,每个子群体只向一个方向的邻近子群体迁移个体以提高迁移的效率.实验表明,该方法有效地提高了遗传算法的运行效率.     

基于改进的迁移率模型的生物地理学优化算法

生物地理学优化（BBO）算法通过迁移和变异不断更新栖息地,以寻找最优解,其中迁移率模型的优劣会直接影响算法的优化性能。针对原始BBO算法采用线性迁移率模型适应性不足的问题,基于Logistic函数、三次多项式函数以及双曲正切函数提出了三种新的非线性迁移率模型,并应用于原始BBO算法中。对17个典型的基准函数进行优化性能测试,结果表明,基于双曲正切函数的迁移率模型所得解更接近函数的全局最小值,总体表现优于原始线性迁移率模型的BBO算法以及相关改进算法中表现优异的余弦迁移率模型。稳定性测试结果表明,在不同的变异率下,基于双曲正切函数的迁移率模型在多数测试函数上表现优于原始线性迁移率模型。在满足解多样性的基础上,该模型能够较好地适应非线性迁移问题,提高寻优能力。     

一种新并行遗传算法及其应用

基于量子计算的概念和原理,本文提出一种新并行量子遗传算法,即粗粒度并行量子遗传算法(CGPQGA)。该算法的核心是引入层环粗粒度并行计算模型和一种新进化策略。由于CGPQGA只需迁移搜索到的最佳个体到各个子群体,因而算法的通信开销很小。通过用CGPQGA设计控制器的应用实例表明,CGPQGA优于常规并行遗传算法,能加速子群体中最佳个体的迁移,收敛速度快,全局寻优能力强,同时具有勘探和开采的能力。     

基于模糊满意度的软件定义网络交换机迁移策略

针对软件定义网络中多控制器间负载均衡的迁移代价和迁移效率问题,提出一种基于模糊满意度的交换机迁移策略。首先,构建均衡判断矩阵,监测控制器负载状态,且提出交换机组选择度,划分交换机组以选取迁移交换机;其次,考虑迁移代价和负载均衡率,构建模糊满意度迁移竞争模型,且提出改进蚁群算法优化求解,选择最佳迁入控制器;最后,将迁移交换机迁往迁入控制器,实现交换机的快速迁移。实验结果表明,与现有交换机迁移策略相比,所提方法在保证较高负载均衡率的同时,进一步优化了网络性能,迁移代价平均减少约26.8%,控制器平均响应时间缩短约0.41 s,改善了交换机迁移过程。     

云数据中心基于贪心算法的虚拟机迁移策略

为了节省云数据中心的能量消耗,提出了几种基于贪心算法的虚拟机（VM）迁移策略。这些策略将虚拟机迁移过程划分为物理主机状态检测、虚拟机选择和虚拟机放置三个步骤,并分别在虚拟机选择和虚拟机放置步骤中采用贪心算法予以优化。提出的三种迁移策略分别为：最小主机使用效率选择且最大主机使用效率放置算法MinMax_Host_Utilization、最大主机能量使用选择且最小主机能量使用放置算法MaxMin_Host_Power_Usage、最小主机计算能力选择且最大主机计算能力放置算法MinMax_Host_MIPS。针对物理主机处理器使用效率、物理主机能量消耗、物理主机处理器计算能力等指标设置最高或者最低的阈值,参考贪心算法的原理,在指标上超过或者低于这些阈值范围的虚拟机都将进行迁移。利用CloudSim作为云数据中心仿真环境的测试结果表明,基于贪心算法的迁移策略与CloudSim中已存在的静态阈值迁移策略和绝对中位差迁移策略比较起来,总体能量消耗少15%,虚拟机迁移次数少60%,平均SLA违规率低5%。     

基于动态迁移的光传送网SDN低时延调度研究

光传送网SDN调度较传统网络具有更好的动态性,为了使SDN网络性能与大数据和云计算需求匹配,提出了一种低时延动态迁移策略.先以SDN网络结构、流表耗时、以及时延调整系数等变量构建通信代价模型,得到通信代价的目标与约束.基于通信代价模型对SDN网络架构采取动态迁移,根据路径请求量计算控制器的平均时延与累计效用,再利用控制与数据信道负载对流表采取动态调整.通过仿真,确定了光传送网SDN调度过程中,当控制器个数改变时,时延几乎不受影响;当数据量增加时,时延及其增速也能得到有效控制;在动态迁移后,负载差异度降低至迁移前的71.92％.实验结果表明所提方法能够有效降低光传送网SDN调度时延,并保证良好的网络负载均衡.     

并行混合免疫遗传算法及其应用

以并行遗传算法(PGA)为基础,对其早熟、收敛慢等缺陷加以改进,提出一种并行混合免疫遗传算法(PHIGA)。该算法将免疫原理引入到遗传算法中,提高了算法的整体性能。这主要表现在一方面免疫选择可有效地防止早熟,另一方面基于免疫记忆的子群体信息交换策略可加速收敛。算法采用混沌初始化和基于自适应交叉、变异的多种群搜索,与单纯形法的混合可更好地改善其局部搜索性能。文中布局问题的算例验证了该算法的可行性和有效性。     

Markov chain models of parallel genetic algorithms

Implementations of parallel genetic algorithms (GA) with multiple populations are common, but they introduce several parameters whose effect on the quality of the search is not well understood. Parameters such as the number of populations, their size, the topology of communications, and the migration rate have to be set carefully to reach adequate solutions. This paper presents models that predict the effects of the parallel GA parameters on its search quality. The paper reviews some recent results on the case where each population is connected to all the others and the migration rate is set to the maximum value possible. This bounding case is the simplest to analyze, and it introduces the methodology that is used in the remainder of the paper to analyze parallel GA with arbitrary migration rates and communication topologies. This investigation considers that migration occurs only after each population converges; then, incoming individuals are incorporated into the populations and the algorithm restarts. The models find the probability that each population converges to the correct solution after each restart, and also calculate the long-run chance of success. The accuracy of the models is verified with experiments using one additively decomposable function     

Parallel physical optimization algorithms for allocating data to multicomputer nodes

Three parallel physical optimization algorithms for allocating irregular data to multicomputer nodes are presented. They are based on simulated annealing, neural networks and genetic algorithms. All three algorithms deviate from the sequential versions in order to achieve acceptable speedups. The parallel simulated annealing (PSA) and neural network (PNN) algorithms include communication schemes that are adapted to the properties of the allocation problem and of the algorithms themselves for maintaining both good solutions and reasonable execution times. The parallel genetic algorithm (PGA) is based on a natural model of evolution. The performances of these algorithms are evaluated and compared. The three parallel algorithms maintain the good solution qualities of their sequential counterparts. Their comparison shows their suitability for different applications. For example, PGA yields the best solutions, but it is the slowest of the three. PNN is the fastest, but it yields lower quality solutions. PSA's performance lies in the middle.     

机器人轨线跟踪的视觉与控制集成方法

针对视觉引导的机器人轨线跟踪控制问题,结合视觉传感器的测量特点提出了视觉 与控制集成的控制方案,在跟踪轨线切向实现等速度控制,而在法向实现位置控制,这一法向 位置误差容易由采样图象直接获得,采用一并行控制器可实现伺服级上的视觉引导,使系统 跟踪性能得到明显提高,在小视场条件下(26.4mm×26.4mm)跟踪速度达到250mm/s.     

模拟跨导滤波器多目标并行进化的设计

以往模拟滤波器的设计,需要经过人工多次修改、计算和调试。提出一种模拟跨导滤波器的硬件进化结构及多目标并行进化的设计方法。应用一种基于渗透原理迁移策略的多目标并行遗传算法,实现跨导滤波器的参数优化。对多目标并行遗传算法的遗传操作进行了改进,构造了适合滤波器参数进化的多目标适应度函数。在高[Q]值的跨导滤波器的设计中,采用级联法构成的四阶带通跨导滤波器能够满足其在阻带、通带以及过渡带方面的性能要求,对其实效性进行了仿真和验证,进化的参数数值与理论结果符合得非常好。     

粗粒度并行遗传算法性能分析

依据实验来分析影响并行遗传算法性能的因素得到的结论缺乏理论上的说服力．通过对粗粒度并行遗传算法加速比公式的分析，提出了影响并行遗传算法性能的关键因素，同时否定了以迁移率作为评价并行遗传算法性能指标的合理性，并通过实难进一步验证结论的正确性．得到的结论为提高遗传算法的并行化效率提供了可靠的依据。     

A generalized scheme for mapping parallel algorithms

A generalized mapping strategy that uses a combination of graph theory, mathematical programming, and heuristics is proposed. The authors use the knowledge from the given algorithm and the architecture to guide the mapping. The approach begins with a graphical representation of the parallel algorithm (problem graph) and the parallel computer (host graph). Using these representations, the authors generate a new graphical representation (extended host graph) on which the problem graph is mapped. An accurate characterization of the communication overhead is used in the objective functions to evaluate the optimality of the mapping. An efficient mapping scheme is developed which uses two levels of optimization procedures. The objective functions include minimizing the communication overhead and minimizing the total execution time which includes both computation and communication times. The mapping scheme is tested by simulation and further confirmed by mapping a real world application onto actual distributed environments     

Dynamic control and prototyping of parallel algorithms forintermediate- and high-level vision

Developing parallel algorithms for intermediate and high levels of computer vision systems is addressed. Because the algorithms are complex and the nature and size of the input and output data sets vary for each application, the authors have directly developed parallel algorithms for dynamic control of both processing and communication complexity during execution. They have also examined the merits of functional prototyping and transforming programs into imperative execution code for final implementation. To evaluate and give direction to their work, they have implemented algorithms for plane detection and object recognition on a flexible transputer network     

Asynchronous migration for parallel genetic programming on a computer cluster with multi-core processors

An island model is a typical implementation of genetic programming on parallel computers with distributed memory. The island model has a migration facility that sends/receives some individuals in an island to/from another island to maintain diversity. The island model requires synchronization to migrate same-generation individuals between islands, and this synchronization causes an increase in computation time. This article proposes a new parallel genetic programming implementation based on the island model with asynchronous migration. Most recent computers are equipped with one or more multi-core processors, and are suitable for multi-threading. Therefore we employ a communication thread for migration between islands. The communication thread on a processor communicates with the communication thread on another processor to migrate individuals at appropriate intervals. Since the migration and other genetic operations can be independently processed on each core, and since we allow the exchange of individuals of different generations, no synchronization is needed in our implementation. In addition, a fitness calculation is also executed in parallel by the remaining cores. Experimental results show that the proposed method can reduce the computation time to about 17% in serial GP by using 40 threads.