【作者】 岳嵚；

【导师】 冯珊；

【作者基本信息】 华中科技大学 ， 系统工程， 2008， 博士

【摘要】 遗传算法是一种随机性的全局优化算法。粗粒度并行遗传算法作为遗传算法的一个重要改进型,具有比经典遗传算法更好的计算性能,可以比较有效地平衡未成熟收敛和局部收敛速度过慢这对矛盾。本文主要讨论粗粒度并行遗传算法。作为一种启发式搜索算法,遗传算法的计算结果具有不稳定性和不可重现性。现在学术界对遗传算法中的某些遗传操作的作用机制还不十分清楚,遗传算法的许多性能特点无法在数学上严格证明。遗传算法的计算过程也会受到各种随机因素的影响。但是大量的实际计算表明,遗传算法的计算结果具有一定的规律性,在统计意义上具有一定的可靠性。本文采用了对同一参数组合进行多次重复计算的方法,提高实证分析的准确性和可信度。多次重复计算所得的最优解的均方差和产生这些最优解的代数的平均值来评价计算结果的稳定性和收敛性。通过遗传算法和随机遍历搜索算法的对比分析,评价遗传算法的计算效率。通过对多个具有不同典型数学特性的经典测试函数进行实际计算以及计算结果的对比分析,得到了遗传算法计算性能的特点和最佳参数设置的相关结论;通过从统计学角度对多次重复计算的结果进行分析,得到了遗传算法的稳定性和可信度方面的相关结论,这说明可以利用分析遗传算法及其改进型求解解析问题的计算效果所得到的结论,使遗传算法在求解复杂的大型实际工程优化问题时获得更好的计算效果。为了改善变异操作的性能,本文提出了三种不同的思路共六种具体实施方法对遗传算法的变异操作进行改进。实证分析表明这六种改进方法的计算结果都明显优于不采用任何改进措施的经典遗传算法,其中每隔一定进化代数再随机产生新个体的方法为最优。对粗粒度并行遗传算法的子种群个数、种群规模和进化代数进行了实证分析,总结出这三个参数对算法的计算效果和计算效率的实际影响的结论。并通过与经典遗传算法的计算结果的比较和分析,论证了粗粒度并行遗传算法拥有较为理想的计算结果和运行过程,具有较高的种群多样性和计算稳定性。对同步迁移和异步迁移这两种迁移方式进行了统一描述,并对同步迁移和不同参数设置的异步迁移的具体计算性能进行了实证分析。计算结果表明:同步迁移作为异步迁移的一种特例,既不是异步迁移中最优的形式,也不是最差的形式;想要使算法达到最佳的计算效果,关键在于基础迁移间隔和迁移概率这两个参数的设置;单峰问题比多峰问题更适合采取同步迁移方式。本文对各子种群使用不同参数设置的改进型粗粒度并行遗传算法进行了讨论和实证分析,这种经过改进的新方法通过提高各个子种群之间进化行为的差别来提高整个种群的多样性,使粗粒度并行遗传算法能真正达到不同子种群搜索不同的局部最优解的目的,提高了粗粒度并行遗传算法的种群多样性和计算性能。实算显示这种改进具有实际效果,对多峰问题效果尤为明显。以往为了提高应用遗传算法求解实际工程优化问题的计算性能所采取的措施都必须了解待求解问题的具体特性后,才能找到合适的进化策略设定方法,这种改进的新型粗粒度并行遗传算法可以避免这种缺陷,为求解实际工程优化问题带来了方便,提高了遗传算法的实用性和可行性。用粗粒度并行遗传算法对澜沧江上的梯级水电站的短期调度问题这一实际案例进行求解计算。本文首先对问题建模,根据遗传算法的特点对模型进行变换,然后利用已得到的进化策略设定方法用粗粒度并行遗传算法对模型进行优化求解,并对计算结果进行分析讨论。通过对工程实际问题的求解,说明粗粒度并行遗传算法可以很好地解决工程实际问题,特别是对于需要对不同初始数据进行多次求解的模型,遗传算法是具有优势的。通过本文中的实证分析研究,为使用遗传算法对大型复杂的工程实际问题进行计算提供了进化策略设定方法的参照依据,对遗传算法的推广和更有效地应用具有实际价值;理论上,本文对遗传算法的实证分析和参数设置研究为遗传算法的机理研究提供了可信实算数据支持。更多还原

【Abstract】 Genetic algorithms(GAs) are optimization algorithms developed by integrating genetic evolution rules and stochastic optimization theory.The CPGA is an important improved form of GAs.It has better performance than the classic GA.It can solve the contradiction of premature convergence and slowness of local convergence.The paper mainly discusses CPGA.As a kind of heuristic searching algorithms,the computation results are unstable and unrepetitive.In the present,few works are available for the process mechanisms of genetic operations,thus many assumptions cannot be proved mathematically.The computation process of GAs will be affected by kinds of stochastic perturbations.On the other hand, many examples show that the results of GAs have certain reliability in statistical sense.The paper improves the reliability of GAs by the method of taking average value of reiteratively computation.The variance of multi-computations results and the average value of these results are taken to be two criterions to estimate the stability and convergence of the computations,and analysis on the computation processes are proceded basic on the criterions.The paper valuates the computation efficiency of GAs by comparing the computing times of GAs and globle stochastic searching algorithm.The main devotion of this work is the computations on the classic test functions that have different mathematical characteristics.According to the comparison analysis,the computational characteristics and the optimal parameter setting results are obtained.The paper has some conclusions on the stability and reliability of GAs by analyzing the results of repeating computing statistically.We also get to know that better computation performence can be gotten by using GAs and their improvement when we solve practical large-scale engineering optimization problems.The paper makes some improvements to mutation operation.The improved methods basic on three considerations,and the paper can realize each one with different ways. There are six kinds of improved methods.The paper analyses their computation characteristics,and get the results that stochastic generating new individuals in every certain evolution generations is optimal way,and the computation results of the six improved methods are better than the ones obtained by classic GA without any improvements.In the paper implement,classic GA is influenced by the problems of premature convergence and convergent speed.CPGA is an important improvement of classic GA, and can solve the problems mentioned here.In the paper,CPGA are used to do examples analysis corresponding to the different parameters of the number of subpopulations,the size of the population and the evolution generations,the results on computation efficiency and practical influences are obtained.And by comparing the results of classic GA,the paper demonstrates that better results and function process can be obtained by using CPGA,which has higher population diversity and better computation stability.The paper systematically describes the synchronous migratory and asynchronous migratory modes,and does example analysis to the performance of synchronous migratory and asynchronous migratory with different parameter setting.The results show that: synchronous migratory as a special case of asynchronous migratory,it is neither the best nor the worst form of asynchronous migratory.In order to get the best computation results, the parameters of the basic migratory space and migratory probability must be well set; compared with multi-modality problems,it is better to take synchronous migratory mode for unimodality problems.The paper also demonstrates a kind of improved CPGA of which each subpopulation uses different parameter settings.The improved methods take use of the frameworks of coarse-grained parallel evolutions,and make the results that CPGA can be find different local optimization solutions for different subpopulations searching.This method improves the subpopulations diversity and computation performance of CPGA.The paper does computation tests to find that the method is effective,especial for the multi-modality problems.And the paper can avoid the computational limitations in solving practical engineering optimization problems,which provides convenience in solving the problems.The paper solves the problem of short-term plan of the step power plants on the LanCangJiang by CPGA.In this article,we build models,transform the models to adjust the characteristics of GAs,and then get optimization solutions by CPGA,which is set by known evolution strategies,and analyze the computation results.By solving the practical engineering problems,it can be concluded that CPGA can be well applied in practical problems.The practices indicate that GAs have advantages especially for the models that will be computed many times by different initialization data.Using the results mentioned above,better computation results can be obtained,when the paper solves the practical engineering optimization problems.In the paper,the improvements to the classic GA provide theory of strategy setting methods for the practical large-scale engineering computations,which is a fine application of GAs.In theoretic aspect,the researches to the example analysis and parameter setting provide great supports to the principle studies of GAs.更多还原