什么是遗传算法

什么是遗传算法 什么是“遗传算法” 遗传算法是模拟自然界中按“优胜劣汰”法则进行进化过程而的算法。Bagley和Rosengerg于1967年在他们的博士论文中首先提出了遗传算法的概念。1975年Holland出版的专著奠定了遗传算法的理论基础。如今遗传算法不但给出了清晰的算法描述，而且也建立了一些定量分析的结果，在众多领域得到了广泛的应用，如用于控制(煤气管道的控制)、规划(生产任务规划)、设计(通信网络设计)、组合优化(TSP问、背包问题)以及图像处理和信号处理等。 那么什么是遗传算法呢, 遗传算法是如此简单，任何人只要用高中时学过的生物术语就可以理解。以一群个体为例，它们都有自己的DNA。然后衡量每一个个体的适应性(把它看作是适用于个体的DNA的官能来衡量)，并且使那些更适应的个体更有可能繁衍。而最不适应的个体将会被灭绝。每个幸存者都会有机会繁衍(重要的是任何幸存者都可能会繁衍，如果不太适应的话，仅仅是降低了可能性)。合并双亲的DNA，对合并后的DNA应用随机变异以模拟繁衍。理论上说来，新的个体是和双亲一样适应的，由于变异或增或减会有些微小的变化。然后循环会周而复始。 虽然，有许多变化的因素在影响遗传算法，包括人群大小、代(算法的迭代)、合并方法、适应性函数，适应性将如何影响繁衍的可能性，以及发生了多少变异。 该算法也存在一些缺陷。如果把应用于DNA的适应性官能看成是一系列的二进制位，效果最好。换句话说，如果DNA是一系列二进制的选项，是还是不是。蓝眼睛,黑眼睛,红头发,黑头发,合并双亲的DNA和随后的变异应当不允许特定的一些位组合出现，因为得出的DNA可能不再是最初的问题的有效解答。请记住，所谓“DNA”仅仅是适应性公式纯数学的一种解答。该公式中用到的一些值可能是无效的—例如，除数为零。 另外，遗传算法不受时间限制。由您来挑选代的数目。您可以确定某个目标 — 比方说，“找一个适应性为0.99999 的个体”，找到后停止。但是，结果是算法永远也不会结束，因为它没找到那个个体。如果您制定了不切实际的目标，或者代的数目太小，就会出现问题。尝试、出错，以及深入的思考是解决这个问题的最佳途径。 遗传算法 Genetic algorithms缩写为AGS 模拟自然界大量生物体的生长，能为传统方法难以解的问题较快地求出好的近似解，用于工程化问题的设计,可能获得全局最优解。1975年美国密执大学Holland教授在《自然和人工系统的适配》的文中提出了这种算法的理论基础。同年，该校Deong在博士论文中，将AGS成功地用于解决优化题，从而进入实践开发阶段。现在广泛应用于许工程和研究领域，如控制参数、运输调度、管道线选择以及电磁器件优化设计等问题。 全域优化所选用的搜索方法的不同可分为三类: (1)解析算法 (2)枚举算法 (3)随机搜索算法 解析算法主要运用目标函数的解析性质(如一阶、二阶导数等)来求全优值,这一方法又可以分为直接法与间接法。直接法根据目标函数的梯度来确定下一步搜索的方向,采用的是一种“爬山”策略,即根据最陡的方向爬上一个局部最优点,但很难找到全优值;间接法则从极值的必要条件出发导出一组方程,然后求解方程组,并通过比较求得全优值。然而导出的方程组一般是非线性的,它的求解也是非常困难的,所以间接法只对一些很简单的问题才适用。 枚举算法主要应用于动态规划。随机搜索算法包括盲目随机搜索法和导向随机搜索法。盲目随机搜索法包括覆盖法和随机方向搜索法,该方法的计算量很大,一般只适合于简单的优化问题;导向随机法又可称为智能搜索算法,这是近年来研究最多的一类全域优化方法。它包括模拟退火(SA)、演化算法(包括遗传算法(GA)、演化规划(EP)、演化策略(ES)和遗传程序设计(GP))、混沌优化(CS)和蚁群算法(ACA)、基于均匀设计优化算法和混合启发式搜索算法等。 目前混合启发式搜索算法的研究相对较少,主要是针对上面单个智能搜索算法的不足所提出的混合优化算法,经实验测试,其结果和效率明显优于单个智能搜索算法,是目前的研究热点。