并行遗传算法收敛性分析及优化运算

经典遗传算法（Canonical Genetic Algorihms)利用单一种群对种群个体进行交叉、变异和选择操作，在进行过程中的超级个体易产生过早收敛现象，粗粒度并行遗传算法利用多个子群进行进化计算，各子群体分别独立进行遗传操作，相互交换最优个体后继续进化。文证明了该算法的搜索过程是一个有限时齐遍历马尔柯夫链，给出粗粒度并行遗传算法全局最优收敛性证明。对于旅行商问题TSP（Traveling Salesman Problem)利用粗粒度并行遗传算法进行了求解，以解决经典遗传算法的收敛到局部最优值问题。仿真结果表明，算法的收敛性能优于经典遗传算法。     

基于CGA和ICA的人脸特征提取方法研究

独立分量分析方法是一种有效的人脸特征提取方法。为了提高独立分量分析法表征人脸特征空间的能力，采用遗传算法对特征空间进行选择优化，获得最优的人脸特征子集。针对遗传算法的随机初始化个体分布不均匀性问题，采用混沌种群生成算法，使遗传算法的搜索更具有全局性。仿真实验表明，该方法的识别率明显优于单一独立分量分析方法。     

基于梯度信息指导交叉的遗传算法

针对基本遗传算法在解空间中盲目选取交叉个体,导致算法在后期搜索能力差、收敛速度慢的缺点,提出了一种基于梯度信息指导交叉的遗传算法。该算法通过确定当前种群中目标个体的最速下降方向,选取该方向下的一个有效范围,在该有效范围内选择个体与目标个体进行交叉操作,使交叉后的子代不断向最优解靠近,有效地保证了交叉操作的目的性和可行性。四个典型测试函数的仿真实验表明,该算法显著加快了遗传算法的寻优速度,提高了遗传算法定位最优解的精度。     

一种带融合操作的实数多种群遗传算法

提出了一种带融合操作的实数多种群遗传算法。该算法由多个种群组成,根据各个种群中最优个体的适应值及其成长性优化计算资源分配;引入融合操作,利用各种群中的最优个体产生新个体,取代各种群中的最差个体,改善种群的遗传进程。实例计算表明该算法是有效的。     

一种关系积和遗传算法相结合的属性约简算法

属性约简是粗糙集(rough set,RS)理论进行规则提取中的重要步骤之一.决策表的最小属性约简是NP-hard问题.遗传算法(genetic algorithm,GA)是求解此类问题的有效方法之一,但在利用遗传算法求解属性约简过程中,需要计算各个个体的适应度,每计算一个个体的适应度,需要根据该个体代表的属性组,组织决策表,对组织后的决策表进行扫描,这样,算法就需要多次对决策表进行操作,影响到算法的执行效率.我们基于集合理论,提出了关系积概念,把决策表的属性约简过程转化为关系积的运算,利用关系积计算遗传算法各个体的适应度,不需要扫描决策表,避免了对决策表的操作,提高了遗传算法求解属性约简的效率,通过实例对这一算法进行了详细的描述.     

量子遗传算法在口腔种植定位中的研究与应用

口腔种植体设计方案的制定时间较长、智能程度不高,口腔医学数据信息量较大。为此,对种植体模型进行研究,提出一种改进的量子遗传算法。把种群细分为不同的特征群体,各特征群体实施自适应调整进化步长的量子旋转门操作,以及个体间信息交流的交叉操作。实验结果表明,与经典的遗传算法以及Bloch量子遗传算法相比,该算法能有效地优化种植体定位参数,搜索能力和收敛性能较好。     

一个求解0-1背包问题的遗传算法

遗传算法是一种基于自然选择和遗传机制的搜索算法。本文将其用于解决一个著名的NP完备问题——0- 1背包问题,并对经典遗传算法进行了改进。通过对贪婪算法进行了改进以产生初始种群,并在进行交叉和变异操作过程中引入了对无效个体的校正操作,从而较好地保持了种群的多样性和优良度。数值实验表明该算法具有较好的全局最优性。     

基于混合遗传克隆算法的关联规则挖掘

针对在数据挖掘应用中关联规则挖掘的问题,给出一种基于混合遗传克隆算法的关联规则挖掘方法,该算法将遗传算法和克隆算法优点相结合,通过克隆操作来产生一组新的个体,独立地对所产生的各个体进行变异,交叉操作,同时采用自适应方式动态选取交叉和变异概率,有效地克服了遗传算法容易陷入局部最优的缺点,从而求得问题的最优解。实验结果表明,该方法能高效地解决关联规则挖掘问题。     

基于禁忌搜索遗传混合算法的装配线平衡

针对装配线平衡问题（ALBP）,文中提出了一种禁忌搜索遗传混合算法。在混合算法中,遗传算法部分采用特殊的遗传变异操作算子（双点交叉和移位插入变异）,使算法只在可行作业序列子空间中进行搜索,有效减小了搜索范围,提高了算法运行效率;禁忌搜索部分是在每代遗传操作完成以后,随机选择一些个体进行禁忌搜索操作,来增强算法的搜索能力。最后以经典问题的求解验证了禁忌搜索遗传算法在收敛性能和计算效率上较使用单纯的遗传算法高。     

基于禁忌搜索遗传混合算法的装配线平衡

针对装配线平衡问题(ALBP),文中提出了一种禁忌搜索遗传混合算法.在混合算法中,遗传算法部分采用特殊的遗传变异操作算子(双点交叉和移位插入变异),使算法只在可行作业序列子空间中进行搜索,有效减小了搜索范围,提高了算法运行效率;禁忌搜索部分是在每代遗传操作完成以后,随机选择一些个体进行禁忌搜索操作,来增强算法的搜索能力.最后以经典问题的求解验证了禁忌搜索遗传算法在收敛性能和计算效率上较使用单纯的遗传算法高.     

参数可变自适应遗传算法在军事地形图矢量化中的应用

针对纸制军事地图矢量化问题进行研究,提出一种基于自适应遗传算法的军事地形图矢量化方法,并在生成新的个体后,增加个体修正操作,提高个体的适应度。在该算法中,提出一种即考虑进化代数对算法的影响,又考虑到每代不同个体适应度作用的自适应交叉概率和变异概率。通过与传统方法的实验比较,证明该方法的可用性和有效性。     

一种协调勘探和开采的遗传算法：收敛性及性能分析

提出了一种新的遗传算法结构。在该结构中,每一代的新种群由保留种 群、繁殖种群的随机种群三部分组成,而它们的相对数量则由不同的参数进行控制,这体现了该算法在运行过程中对搜索空间勘探和开采操作的协调和权衡。通过把该算法建模为齐次的有限Markov链,该文证明了该算法具有全局收敛性。对试验数据的分析表明,该算法能够有效协调算法对问题解空间的勘探和开采操作,因而在处理复杂问题时表现出较高的性能。     

基于疫苗自动获取与更新的免疫遗传算法

收敛速度缓慢已成为遗传算法研究中亟待解决的主要问题之一．为了提高遗传算法的收敛速度,提出了一种基于疫苗自动获取与更新的免疫遗传算法．从各代种群中选出优良个体,然后从这些优良个体中提取免疫疫苗,概率地对后代种群的个体接种疫苗．接种疫苗是利用疫苗确定位上的等位基因替代个体相应位上等位基因的操作．接种疫苗加速了优良模式的繁殖,修复了被交叉、变异破坏的优良模式．种群与疫苗库相互作用、协同进化,极大地提高了算法的收敛速度．基于模式定理分析了算法的计算效率．最后,几个典型函数优化问题的仿真结果表明了算法的可行性和有效性．     

相对主元分析及其在数据压缩和故障诊断中的应用研究

传统主元分析(Principal component analysis, PCA)方法因忽视量纲对系统的影响, 从而使选取的主元难以具有代表性; 而在进行量纲标准化后, 又因得到的特征值常常是近似相等的而无法进行有效的主元提取. 针对这一主要问题, 本文通过引入相对化变换(Relative transform, RT)、相对主元(Relative principal components, RPCs) 和分布"均匀"等概念, 建立起一种相对主元分析(Relative principal component analysis, RPCA)的新方法. 该方法首先对系统各分量进行量纲标准化; 其次再根据系统的先验信息分析和确定各分量的重要程度; 然后在系统能量守恒的准则下, 赋以系统各分量相应的权值; 最后利用已建立起的相对主元模型, 对系统实施RPCA. 同时运用数值例子, 开展了RPCA在数据压缩和系统故障诊断中的应用研究. 理论分析和仿真实验均表明, 采用RPCA方法选取出的主元更具代表性和显著几何意义, 加之选取主元的灵活性, 将使新方法具有更广泛的应用前景.     

遗传算法在建筑概念设计中的应用

介绍了一种可以应用于建筑概念设计的遗传算法.该算法采用基于数学表示二叉树结构的编码方法,以及相应的交叉、变异操作,目标函数及人机交互相结合的适应度值确定方法,生成简单的曲线.选定的曲线经过三维可视化处理形成实体.这些生成的三维实体与人工设计的构件一起被分类,然后统一保存到构件库中.通过采用二进制编码的遗传算法,生成组合方案,组合构件库的构件,形成比较复杂的外观造型.以一个建筑外观设计为例,介绍了算法的执行过程.     

On minimizing coding operations in network coding based multicast: an evolutionary algorithm

In telecommunications networks, to enable a valid data transmission based on network coding, any intermediate node within a given network is allowed, if necessary, to perform coding operations. The more coding operations needed, the more coding resources consumed and thus the more computational overhead and transmission delay incurred. This paper investigates an efficient evolutionary algorithm to minimize the amount of coding operations required in network coding based multicast. Based on genetic algorithms, we adapt two extensions in the proposed evolutionary algorithm, namely a new crossover operator and a neighbourhood search operator, to effectively solve the highly complex problem being concerned. The new crossover is based on logic OR operations to each pair of selected parent individuals, and the resulting offspring are more likely to become feasible. The aim of this operator is to intensify the search in regions with plenty of feasible individuals. The neighbourhood search consists of two moves which are based on greedy link removal and path reconstruction, respectively. Due to the specific problem feature, it is possible that each feasible individual corresponds to a number of, rather than a single, valid network coding based routing subgraphs. The neighbourhood search is applied to each feasible individual to find a better routing subgraph that consumes less coding resource. This operator not only improves solution quality but also accelerates the convergence. Experiments have been carried out on a number of fixed and randomly generated benchmark networks. The results demonstrate that with the two extensions, our evolutionary algorithm is effective and outperforms a number of state-of-the-art algorithms in terms of the ability of finding optimal solutions.     

改进的自适应遗传算法在人体行为识别中的应用

为提高传统自适应遗传算法优化的BP神经网络对人体行为的识别率,提出了一种改进的自适应遗传算法优化的BP神经网络预测方法.该算法使用新的动态变化的交叉和变异分布指数计算公式来优化传统的二进制交叉和多项式变异操作,根据种群集中和分散的剧烈程度自适应地增大或减小交叉和变异的概率,极大地弥补了传统的交叉和变异操作所造成的破坏优...     

Optimization of electronics component placement design on PCB using self organizing genetic algorithm (SOGA)

The optimal placement of electronic components on a printed circuit board (PCB) requires satisfying multiple conflicting design objectives as most of the components have different power dissipation, operating temperature, types of material and dimension. In addition, most electronic companies are currently emphasizing on designing a smaller package electronic system in order to increase the system performance. This paper presents a new self organizing genetic algorithm (SOGA) method for solving this multi-objective optimization problem. The SOGA can be viewed as a cascade of two GAs which consists of two steps fitness evaluation process to ensure that the fitness of selected chromosomes for each iteration process is optimally selected. The algorithm is developed based on weighted sum approach genetic algorithm (WSGA) where an inner loop GA is used to optimize the selection of weights of the WSGA. Experiments are conducted to evaluate the performance of SOGA. Four objective functions are formulated in the experiments which are temperature of components, area of PCB, high power component placement and high potential critical components distance. Comparisons of the performance of SOGA are made with two well known methods namely fixed weight GA (FWGA) and random weighted GA (RWGA). The results show that the SOGA gives a better optimal solution as compared to the other methods.     

A novel hybrid genetic algorithm using local optimizer based on heuristic pattern move

A new hybrid genetic algorithm with the significant improvement of convergence performance is proposed in this study. This algorithm comes from the incorporation of a modified microgenetic algorithm with a local optimizer based on the heuristic pattern move. The hybridization process is implemented by replacing the two worst individuals in the offspring obtained from the conventional genetic operations with two new individuals generated from the local optimizer in each generation. Some implementation-related problems such as the selection of control parameters in the local optimizer are addressed in detail. This new algorithm has been examined using six benchmarking functions, and is compared with the conventional genetic algorithms without the local optimizer incorporated, as well as the hybrid algorithms incorporated with the hill-climbing method in terms of convergence performance. The results show that the proposed hybrid algorithm is more effective and efficient to obtain the global optimum. It takes about 6.4%-74.4% of the number of generations normally required by the conventional genetic algorithms to obtain the global optimum, while the computation cost for reproducing each new generation has hardly increased compared to the conventional genetic algorithms. Another advantage of this new algorithm is the implementation process is very simple and straightforward. There are no extra function evaluations and other complex calculations involved in the added local optimizer as well as in the hybridization process. This makes the new algorithm easy to be incorporated with the existing software packages of genetic algorithms so as to further improve their performance. As an engineering example, this new algorithm is applied for the detection of a crack in a composite plate, which demonstrates its effectiveness in solving engineering practical problems.     

利用条件概率和Gibbs抽样技术为分布估计算法构造通用概率模型

本文针对传统分布估计算法在建立概率模型时面临的各种困难,提出一种基于条件概率和Gibbs抽样的概率模型,能有效改进分布估计算法的通用性.使用该模型的分布估计算法利用进化过程中有前途的优秀个体构造出多个监督学习样本集,并对每个样本集估计出对应分量的条件概率,再使用这一组条件概率进行Gibbs抽样产生新的个体替代种群中的劣等个体.通过仿真实验表明,改进后的算法能够求解出可加性降解函数的全局最优解,表现出较强的全局优化能力.