基于种群规模可变的粗粒度并行遗传算法

在科学计算领域，并行计算越来越成熟，并行遗传算法开始受到关注。本文分析了遗传算法并行化的动机和实现模型，提出了一种新算法－基于种群规模可变的粗粒度并行遗传算法,仿真结果验证了这种新算法的有效性和合理性。     

一种基于粗粒度-主从式的混合并行遗传算法

为了解决串行遗传算法的收敛速度和早熟问题．人们开始研究遗传算法的并行执行，并取得了很好的结果。本文提出了一种基于分布式集群环境的层次结构(粗粒度一主从式)的并行遗传算法一混合并行遗传算法。仿真表明，采用混合并行遗传算法可以有效的提高优化的速度和解的精度。     

大规模问题数据并行性能的分析

从应用的角度建立了评价大规模问题数据并行处理性能的模型,分析了区域的不同划分对解整个问题算法的收敛速度有影响时的并行性能,进而就操作重叠、数据规模以及算法选取等几个方面的问题对大规模数据并行性能所产生的影响进行了分析.最后,给出的例子证明了模型的有效性.     

网格平台下并行遗传算法的设计

并行遗传算法是遗传算法研究中的一个重要课题,提出了一种在网格平台下实现遗传算法的设计和一些关于遗传算法本身的改进,以及需要进一步研究的课题。     

一种粗粒度并行遗传算法的设计与实现

遗传算法(Genetic Algorithms,GA)作为搜索最优解的方法,有很广泛的应用,但随着问题的规模扩大,复杂度增加,GA的求解速度大大降低。并行遗传算法(Paralle Genetic Algorithms,PGA)成为解决遗传算法速度瓶颈的有效方法。本文提出了并行遗传算法新的应用平台-Internet,讨论了并行遗传算法应用于Internet的具体实现中的关键问题,并给出单向环拓扑的具体实现和仿真验证。     

改进粗粒度并行遗传算法在网格任务调度中的应用

现有并行遗传算法采用随机方法划分子种群,算法收敛性能不高,并且不可避免的破坏种群的较优模式;为了改进这些缺陷,设计了一种新的多点交叉算子,提出了一种改进的粗粒度并行遗传算法;取资源数为6,任务数为50,种群的规模为60,遗传代数为600;采用相同的控制参数进行仿真实验;仿真实验表明,与传统并行遗传算法相比较,提出的改进算法在收敛速度和寻优空间方面有很大的提升。     

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

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

基于并行遗传算法的智能公交排班研究

智能公交排班问题是公交车辆智能调度的一个典型问题之一。它可以描述为：利用某种智能化算法,在有限的步骤内,找出所有满足约束条件的最优或者接近最优的排班方案。由于排班问题搜索规模巨大,传统算法在短时间内难以获得高质量可行解。文章引入并行遗传算法,对三种主流并行模型进行评价分析,并设计了求解车辆排班问题的粗粒度并行遗传算法,编制了算法实现程序。     

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

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

并行遗传算法分析

在科学计算机领域,并行遗传算法开始受到关注。分析了遗传算法并行化的同和实现模型,讨论了遗传算法隐含的并行性,对于灵活应用并行遗传算法有指导意义。     

Efficient External Memory Algorithms by Simulating Coarse-Grained Parallel Algorithms

Abstract. External memory (EM) algorithms are designed for large-scale computational problems in which the size of the internal memory of the computer is only a small fraction of the problem size. Typical EM algorithms are specially crafted for the EM situation. In the past, several attempts have been made to relate the large body of work on parallel algorithms to EM, but with limited success. The combination of EM computing, on multiple disks, with multiprocessor parallelism has been posted as a challenge by the ACM Working Group on Storage I/ O for Large-Scale Computing. In this paper we provide a simulation technique which produces efficient parallel EM algorithms from efficient BSP-like parallel algorithms. The techniques obtained can accommodate one or multiple processors on the EM target machine, each with one or more disks, and they also adapt to the disk blocking factor of the target machine. When applied to existing BSP-like algorithms, our simulation technique produces improved parallel EM algorithms for a large number of problems.     

遗传算法的性能分析

以几个典型的函数优化问题为例,比较,分析几种不同策略下遗传算法的全局收敛性及收敛速度,发现了以往理论分析与实际问题之间的不一致,提出以寻找最优解或最优解组的角度衡量算法收敛性能的观点及标准,定义了一个更为直观地反映算法收敛过程的测度函数及部分在线特性。     

Scalable Parallel Genetic Algorithms

Genetic algorithms, search algorithms based on the genetic processes observed in natural evolution, have been used to solve difficult problems in many different disciplines. When applied to very large-scale problems, genetic algorithms exhibit high computational cost and degradation of the quality of the solutions because of the increased complexity. One of the most relevant research trends in genetic algorithms is the implementation of parallel genetic algorithms with the goal of obtaining quality of solutions efficiently. This paper first reviews the state-of-the-art in parallel genetic algorithms. Parallelization strategies and emerging implementations are reviewed and relevant results are discussed. Second, this paper discusses important issues regarding scalability of parallel genetic algorithms.     

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

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

Efficient Parallel Graph Algorithms for Coarse-Grained Multicomputers and BSP

In this paper we present deterministic parallel algorithms for the coarse-grained multicomputer (CGM) and bulk synchronous parallel (BSP) models for solving the following well-known graph problems: (1) list ranking, (2) Euler tour construction in a tree, (3) computing the connected components and spanning forest, (4) lowest common ancestor preprocessing, (5) tree contraction and expression tree evaluation, (6) computing an ear decomposition or open ear decomposition, and (7) 2-edge connectivity and biconnectivity (testing and component computation). The algorithms require O(log p) communication rounds with linear sequential work per round (p = no. processors, N = total input size). Each processor creates, during the entire algorithm, messages of total size O(log (p) (N/p)) . The algorithms assume that the local memory per processor (i.e., N/p ) is larger than p ^ε , for some fixed ε > 0 . Our results imply BSP algorithms with O(log p) supersteps, O(g log (p) (N/p)) communication time, and O(log (p) (N/p)) local computation time. It is important to observe that the number of communication rounds/ supersteps obtained in this paper is independent of the problem size, and grows only logarithmically with respect to p . With growing problem size, only the sizes of the messages grow but the total number of messages remains unchanged. Due to the considerable protocol overhead associated with each message transmission, this is an important property. The result for Problem (1) is a considerable improvement over those previously reported. The algorithms for Problems (2)—(7) are the first practically relevant parallel algorithms for these standard graph problems. Received July 5, 2000; revised April 16, 2001.     

遗传算法的性能分析研究

回顾了遗传算法的理论研究状况,介绍了NoFreeLunch定理,描述了遗传算法的通用框架,构造了遗传算法的性能分析矩阵,并通过模拟实验分析了一系列遗传算法的性能.实验表明,这种评价算法性能的方法切实可行,可操作性好,具有一定的通用性.     

Improving Parallel Ordering of Sparse Matrices Using Genetic Algorithms

In the direct solution of sparse symmetric and positive definite linear systems, finding an ordering of the matrix to minimize the height of the elimination tree (an indication of the number of parallel elimination steps) is crucial for effectively computing the Cholesky factor in parallel. This problem is known to be NP-hard. Though many effective heuristics have been proposed, the problems of how good these heuristics are near optimal and how to further reduce the height of the elimination tree remain unanswered. This paper is an effort for this investigation. We introduce a genetic algorithm tailored to this parallel ordering problem, which is characterized by two novel genetic operators, adaptive merge crossover and tree rotate mutation. Experiments showed that our approach is cost effective in the number of generations evolved to reach a better solution in reducing the height of the elimination tree.     

归一化实数编码的多维并行遗传算法

给出了归一化多维实数编码的基本定义,并在此基础上提出了基于归一化实数编码的多维并行遗传算法;对归一化实数编码多维并行交叉算子、多维并行变异算子进行了详细的研究;提出了多维优化问题归一化实数编码长度计算公式;对遗传算法的控制参数确定进行了阐述;对归一化实数编码的多维并行遗传算法适应度函数的确定方法进行了研究.实验表明,归一化实数编码多维并行遗传算法可以大大提高多维优化问题的收敛速度,从而进一步提高算法的性能,这些特点对于计算复杂的非线性多维优化问题具有重要的意义.     

一种主从式并行遗传算法设计

该文对串行遗传算法进行了并行设计,加入对当前通用消息传递接口MPI的支持,形成了一个主从式并行遗传算法。针对该算法用经典的测遗传算法效率的OliverTSP问题进行测试,得出并行遗传算法可以更好的提高遗传算法的收敛性。     

一种主从式并行遗传算法设计

该文对串行遗传算法进行了并行设计,加入对当前通用消息传递接口MPI的支持,形成了一个主从式并行遗传算法。针对该算法用经典的测遗传算法效率的OliverTSP问题进行测试,得出并行遗传算法可以更好的提高遗传算法的收敛性。