【作者】 朱灿；

【导师】 梁昔明；

【作者基本信息】 中南大学 ， 计算机应用技术， 2009， 博士

【摘要】 工程和科学计算中的很多优化问题从最初的低维优化发展为高维、大规模复杂优化,或常常带有比较复杂的约束条件,因而比较难以求解。以遗传算法为代表的各类进化算法在求解该类复杂问题时越来越受到重视。然而有关实数编码遗传算法(RCGA)的工作机理的研究比较少,不能有效地指导算法的改进。本文研究了RCGA的工作机理,分析了RCGA种群漂移的规律,提出了一些改进算法,用高维优化和约束测试函数进行了数值实验,验证了本文算法的有效性。具体创新性成果如下:1、本文指出适应度函数设计存在不合理性,提出一个种子的适应度值理论上应该和该种子到全局最优点的欧氏距离成负相关性;提出了基本交叉算子实质上就是基于差分法的一维搜索。在进化后阶段,当两父体种子在同一邻域内时,该搜索在整个进化过程中成为有效搜索的可能性比较大,当两父体种子距离比较远时,成为有效搜索的可能性逐渐减小。单重均匀或非均匀变异算子在种群空间里其变异都不是均匀的;2、本文提出优势种群(块)的概念,通过研究优势块在种群中种子个数的期望值增长规律提出了标准RCGA种群漂移块式定理:遗传算法的进化过程中,新的优势块不断出现排挤了原来的优势块,直到最后一个优势块出现不再被排挤为止。如果RCGA各参数设置合理,RCGA中的新的优势块规模期望值具有近似按指数级增长的趋势。在此基础上阐述了RCGA的参数设置规则,分析了RCGA提前收敛的原因,解释了一些改进算法之所以有效的原因,结合算子作用机制提出了RCGA工作机理。从微观上来说,遗传算法是一种基于差分法的邻域搜索、局部搜索和全局搜索自适应结合的算法;邻域搜索、局部搜索和全局搜索所占比例受种群中优势块的个数以及各个优势块种子个数的变化而变化。从宏观上来说,遗传算法是一种以一定概率选择多个区域(面向搜索块)的迭代算法。优势种子邻域内种子浓度增大有利于加快优势块收敛速度。3、本文提出了一种多精英保存策略遗传算法(GAEP),通过求解三个经典的连续函数优化问题与当前一些改进进化算法数值结果对比,验证了GAEP算法的有效性。分析了该算法的局限性并改进提出了基于物种选择的遗传算法(GASS)。通过模拟生物进化的阶段性对GASS算法进行了改进,得到了改进算法(IGASS)。三个算法都通过最优种群的隔离来保持选择压力,最优种群边界的自适应收缩和最优种群规模的不定期减小至1保持了种群的多样性,比较好地平衡选择压力和种群多样性,算法IGASS既对种群划分(横向划分),又对进化代数自适应的划分(纵向划分),消除了参数(最大进化代数)对均匀变异算子的步长在整个进化过程不均匀的影响,从而性能更稳定。通过标准的高维和超高维数值实验分析了IGASS算法的动态性能,并对算法IGASS与CEC2008国际会议技术报告里提供的十个参照算法进行比较,结果表明,IGASS算法适应度函数计算次数、求解精度以及算法稳定性基本上都优越于参照算法。算法IGASS尤其适合于求解变量可分离的超高维问题。4、本文指出以往的约束处理策略都没有很好地与精英保存策略结合起来。通过对惩罚因子的局部分析,提出了一种与精英保存策略相结合的惩罚函数法约束处理策略,结合IGASS算法提出了一种混合算法(MGASS),算法MGASS将种群划分为三个子种群,此三子种群按不同策略进化。标准的约束测试函数数值实验表明该算法性能比较好。更多还原

【Abstract】 Genetic algorithms, usually adoptting real-coded, as one of the important branch of evolutionary algorithms, have been used to solve complicated optimization problems more and more widely. However the theoretical results on mechanism research of real-code genetic algorithms (RCGA) was relatively few, which was studied and several improved GAs were proposed in this dissertation. The main contributions are as followes:1、Action mechanism of genetic operators was analysed.There was negative correlation between fitnees value and the distance between global optimal solution and individuals. One pass of simple cross operator is a one-dimensional search based on differential method in essence. One generation of simple cross operation can be regarded as a combination of effective neighborhood search and local random search. The proportion of neighborhood search will change with the number of advantage block and the size of advantage block in population. New individuals generated by single- (or multi-) uniform (or nonuniform) mutation operator occupied problem space with non-uniform distribution. Enhancing seeds number of neighborhood of advantage individuals will improve the local convergence rate.2、A new analytical method of genetic drift of genetic algorithm with real-code was proposed by studying the expectation size growth of advantage subpopulation. The effect of genetic operator on the expectation size of advantage subpopulation was estimated concerned local characteristics of problems. Block Theory of RCGA was deduced that the processing of RCGA is expressed. After random searching of the first phase, the size of advantage blocks increase at the exponent growth but only optimal subpopulation was survived with the creasing of average fitness value and whose size tended to a steady value. The difference between Block Theory and Schema Theory was contrasted. The appropriate parameter setting was analyzed and the prematurity reason was explained. From the macroscopic point of view, RCGA is a iteration method to select multiple blocks at a diverse probability to the next generation.3、Based on the analysis of advanced convergence by block theory, The dissertation proposed a novel genetic algorithm with several elitists preserved method(GAEP). After analysing on the limitations of GAEP, Genetic algorithms with speices selection (GASS) come into being. Improved GASS(IGASS) was proposed by using stage characteristic of biological evolution for reference. Local searching was enhanced by boundary auto-contraction of optimal subpopulation. Gene segregation was carried out by the size of optimal subpopulation decreasing aperiodically and cross operation between optimal subpopulation and rest subpopulation. Optimization problems with separable variables were defined whose properties were studied. It’s analyzed that the three algorithms are effective and especially appropriate for solving high-dimension optimization problems whose variables are separable, which is approved by numerical experiments.4、Common constraint-handling techniques are surveyed, which were not combined with elitist preservation strategies. A new constraint-handling techniques was proposed combined elitist preservation strategies and penalty function method, whose penalty factor was designed by local analysis. A new memetic algorithms to slove constraint optimization problems come into being from IGASS. Some numerical tests were made. The results show that the algorithm is effective and robust.更多还原