论文部分内容阅读
摘要：该文介绍了遗传算法的基本概念、基本遗传算法的特点和基本遗传算法的求解步骤，同时也介绍了遗传算法在机器学习、并行处理、人工生命以及遗传算法与进化规则及进化策略的结合的发展动向，最后讨论了基于遗传算法的人工神经网络学习中的应用研究，具体论述了遗传算法在学习神经网络权重和学习神经网络拓扑结构的应用方法。
关键字：遗传算法；机器学习；人工生命；人工神经网络；神经网络拓扑结构
中图分类号：TP183文献标识码：A文章编号：1009-3044(2008)27-2040-03
The Application of Genetic Algorithm to the Artificial Intelligence
WANG Hui
(Xinjiang Petroleum Institute, Urumqi 830000, China)
Abstract: In this paper the author introduces the basic conception of genetic algorithm(GA for short),the feature of GA and the calculation steps. We can also get a general idea of the development in the machine learning, Parallel Processing, artificial Life, and the integration of evolutionary rules and strategies. At last, the application of GA to artificial neural networks is discussed, especially the application of GA to the study of neural networks weight and the neural network topology.
Key words: genetic algorithm; machine learning; artificial life;artificial neural networks; neural network topology
1 遗传算法简介
遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，与传统数学模型截然不同，它为那些难以找到传统数学模型的难题找出了一个解决方法。遗传算法借鉴了生物科学中达尔文的物竞天择、适者生存的进化准则，1975年，Michigan大学Holland教授根据这一规律首次提出了遗传算法（genetic algorithm，简称GA），其基本思想是力求充分模仿这一自然寻优过程的随机性、鲁棒性和全局性。这是一种新型的全局优化搜索算法，因为其直接对结构对象进行操作，不存在求导和函数连续性的限定等数学问题，鲁棒性强、随机性、全局性以及适于并行处理，已广泛应用于神经网络、计算机科学、优化调度、运输问题、组合优化、机器学习、信号处理、自适应控制和人工生命等领域，并且遗传算法在实际应用中也取得了巨大成功。
2 基本遗传算法
遗传算法的工作过程本质上就是模拟生物的进化过程。首先，要规定一种编码方法，使得你的问题的任何一个潜在可行解都能表示成为一个“数字”染色体。然后，创建一个由随机的染色体组成的初始群体（每个染色体代表了一个不同的候选解），并在一段时期中，以培育适应性最强的个体的办法，让它们进化，在此期间，染色体的某些位置上要加入少量的变异。
遗传算法是一种基于空间搜索的算法，它的求解可以看成是最优化过程。遗传算法的最大优点就是，你不需要知道怎么去解决一个问题，你需要知道的仅仅是用什么样的方式对可行解进行编码，使得它能被遗传算法机制所利用。遗传算法并不能保证所得到的解是最优解，但可以将误差控制在容许的范围内。遗传算法具有以下特点：
1） 遗传算法是对参数集合的编码而非针对参数本身进行优化；
2） 遗传算法是从问题解的编码组开始而非从单个解开始搜索；
3） 遗传算法利用目标函数的适应度这一信息而非利用导数或其他辅助信息来指导搜索；
4） 遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。
那么下面对基本遗传算法给出一个求解步骤：
1） 定义一个目标函数；
2） 将可行解群体在一定的约束条件下初始化，每一个可行解用一个向量x来编码，称为一条染色体，向量的分量代表基因，它对应可行解的某一决策变量；
3） 计算群体中每条染色体xi(i＝1，2，…，n)所对应的目标函数值，并以此计算适应值Fi，按Fi的大小来评价该可行解的好坏；
4） 以优胜劣汰的机制，将适应值差的染色体淘汰掉，对幸存的染色体根据其适应值的好坏，按概率随机选择，进行繁殖，形成新的群体；
5） 通过杂交和变异的操作，产生子代。杂交是随机选择两条染色体（双亲），将某一点或多点的基因互换而产生两个新个体，变异是基因中的某一点或多点发生突变；
6） 对子代群体重复步骤(3)～(5)的操作，进行新一轮遗传进化过程，直到迭代收敛（适应值趋稳定）即找到了最优解或准最优解。
3 遗传算法的发展动向
GA在应用方面的取得了较丰硕的成果，其主要应用领域在于函数优化，机器人学，设计，组合优化，信号处理，人工生命等，此外遗传算法还有几个引人注目的新动向。
3.1 基于GA的机器学习
这一新的研究方向把GA从历史离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法，这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望，GA作为一种搜索算法从一开始就与机器学习有密切联系。分类器系统是第一个基于GA的机器学习系统。基于GA的概念学习是近几年机器学习领域的一个较为引人注目的研究方向。还有一些嵌入领域知识的基于GA的机器学习的研究。
3.2 并行处理的GA
并行处理的GA的研究不仅是GA本身的发展，而且对于新一代智能计算机体现结构的研究都是十分重要的，GA在操作上具有高度的并行性，许多研究人员都正在搜索在并行机上高效执行GA的策略。近几年也发表了不少这方面的论文，研究表明，只要通过保持多个群体和恰当地控制群体间的相互作用来模拟并执行过程，即使不使用并行计算机，我们也能提高算法的执行效率。在并行GA的研究方面，一些并行GA可以分为两类：一是粗粒度并行GA，它主要开发群体间的并行性，如Coboon分析了在并行计算机上解图划分问题的多群体GA的性能；另一类是细粒度并行GA，它主要开始一个群体中的并行性，如Kosak将群体中的每个个体映射到一个连接机的处理单元上，并指出了这种方法对网络图设计问题的有效性。
3.3 GA与人工生命的渗透
人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。人工生命与GA有密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础，虽然人工生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人工生命的研究提供了一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展。
3.4 GA与进化规则及进化策略的结合
GA，进化规则及进化策略是进化计算的三个主要分支，这三种典型的进化算法都以自然界中生物的进化过程为自适应全局优化搜索过程的借鉴对象，所以三者之间有较大的相似性，但三种算法又是从不完全相同的角度出发来模拟生物的进化过程，分别是依据不同的生物进化背景，不同的生物进化机制而开发出来的，所以又有差异。但在进化计算领域内更重要的工作是生物的进化机制，构造性能更加优良且适应性更加广泛的进化算法。
4 基于遗传算法优化神经网络的应用研究
神经网络和遗传算法目标相近而方法各异。因此，将这两种方法相互结合，必能达到取长补短的作用。近年来,在这方面已经取得了不少研究成果，形成了以遗传算法与神经网络相结合的进化神经网络(ENN)。遗传算法在神经网络中的应用主要是用遗传算法学习神经网络的权重和学习神经网络的拓扑结构两个部分。
4.1 遗传算法学习神经网络的权重
而最主要的是学习神经网络的权重，也就是用遗传算法来取代一些传统的学习算法 。目前广泛研究的前馈网络中采用的是Rumel hart等人推广的误差反向传播（BP）算法，BP算法具有简单和可塑的优点，但是BP算法是基于梯度的方法，这种方法的收敛速度慢，且常受局部极小点的困扰，采用遗传算法则可把神经网络的结构优化和权值学习合并起来一起求解，克服了BP算法的缺陷，是神经网络权值学习的有效方法。
遗传算法学习神经网络权值的算法步骤如下：
1） 随机产生一组分布，采用某种编码方案对该组中的每个权值（或阈值）进行编码，进而构造出一个个码链（每个码链代表网络的一种权值分布），在网络结构和学习算法已定的前提下，该码链就对应一个权值和阈值取特定值的一个神经网络；
2） 对所产生的神经网络计算它的误差函数，从而确定其适应度函数值，误差与适应度成反比关系；
3） 选择若干适应度函数值最大的个体，直接遗传给下一代（精英保护策略）；
4） 利用交叉和变异等遗传操作算子对当前一代群体进行处理，产生下一代（新一代）群体；
5） 重复步骤2～4，使初始确定的一组权值分布得到不断的进化，直到训练目标得到满足或者迭代次数达到预设目标为止。
4.2 遗传算法学习神经网络的拓扑结构
神经网络结构包括网络的拓扑结构（连接方式）和接点转移函数两方面。利用遗传算法设计神经网络可根据某些性能评价准则如学习速度，泛化能力或结构复杂程度等搜索结构空间中满足问题要求的最佳结构。利用遗传算法设计神经网络的关键问题之一仍然是如何选取编码方案。
遗传算法学习神经网络结构的算法步骤如下:
1） 随机产生若干个不同结构的神经网络，对每个结构编码，每个码链对应一个网络结构，N个码链构成种群。
2） 利用多种不同的初始连接权值分别对每个网络进行训练。
3） 计算在每个对应码链下神经网络的误差函数，利用误差函数或其他策略（如网络的泛化能力或结构复杂度）确定每个个体的适应度函数。
4） 选择若干适应度函数值最大的个体构成父本。
5） 利用交叉，变异等遗传操作算子对当前一代群体进行处理，产生新一代群体。
6） 重复上述2）-5）步骤，直到群体中的某个个体（对应一个网络结构）能满足要求为止。
5 结束语
遗传算法作为一种新型的全局优化搜索算法，由于其直接对结构对象进行操作，不存在求导和函数连续性的限定，又具有鲁棒性强、随机性、全局性以及适于并行处理的优点，在人工神经网络的应用上展现了它的独特魅力与优势，但同时，它在理论和应用技术上也存在着许多不足和缺陷，比如相对鲜明的生物基础，其数学基础显得极为薄弱，尤其是缺乏深刻且具有普遍意义的理论分析。随着理论研究的深入，可以肯定，作为一种高效并行的全局搜索方法，遗传算法以其特有的算法特点使其在许多实际问题中的应用会越来越广；同时，广泛的数学方法和强大的计算机模拟工具的出现，必将使遗传算法的研究取得长足的进展。
参考文献：
[1] 蔡自兴. 人工智能及其应用[M]. 3版.北京：清华大学出版社，2003.
[2] 王风琴. 基于遗传算法的神经网络优化[J].燕山大学学报，2001，25（3）：234-239.
[3] 陈国良. 遗传算法及其应用[M].北京：人民邮电出版社，1999.
[4] 陈颖琪. 进化计算与神经网络的结合[J].红外与激光工程，1999，（4）：8-11，35.
[5] Kretnovich v.Qmtana C and Puentes O.Genetnc Algorithms-What Fitness Scaling is Optimal. Ctberm and System 1993.24.
[6] S W Mathfoud.Genetic drift in sharing methods. 0-7803-I899-4/94.1994 IEEE
[7] V Petrochs.S Kazarns. Varying quality function Gengentic algorithms and the cutting problem. 0-7803-I899-4/94.1994 IEEE
[8] 杨旭东，张彤. 遗传算法应用于系统在线识别研究[J].哈尔滨工业大学学报， 2000，32（1）：102-104.
[9] Pham D T，Jin G. Genetic algorithms using gradient-like ren reduction operator. Electronics Letters. 1995 .31.
[10] Nover D，Baskaran S，Scbuster P. Understanding genetic algorithms dynamics using harvesting strategies. Physics D 79, 1994.
[11] Kao T, Hwang S Y. A genetic algorithm with sruptive selection[J]. IEEE Transcations on System, Man. And Cybernetris-Part B: Cybernetics 1996,26.
[12] Arabas J. Michalewicz Z and Mulawka J. GAVaPS-a Genetic Algorithms with Varying Population Size[C].Proc O the 1st IEEE on Evolutonary Computation IEEE，1994.
[13] Liu Li, Chen Xueyun. Reconfiguration of distribution networks based on fuzzy genetic algorithms[J]. proceedings of Chinese Society of the CSEE, 2000,20(9):44-49.
关键字：遗传算法；机器学习；人工生命；人工神经网络；神经网络拓扑结构
中图分类号：TP183文献标识码：A文章编号：1009-3044(2008)27-2040-03
The Application of Genetic Algorithm to the Artificial Intelligence
WANG Hui
(Xinjiang Petroleum Institute, Urumqi 830000, China)
Abstract: In this paper the author introduces the basic conception of genetic algorithm(GA for short),the feature of GA and the calculation steps. We can also get a general idea of the development in the machine learning, Parallel Processing, artificial Life, and the integration of evolutionary rules and strategies. At last, the application of GA to artificial neural networks is discussed, especially the application of GA to the study of neural networks weight and the neural network topology.
Key words: genetic algorithm; machine learning; artificial life;artificial neural networks; neural network topology
1 遗传算法简介
遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，与传统数学模型截然不同，它为那些难以找到传统数学模型的难题找出了一个解决方法。遗传算法借鉴了生物科学中达尔文的物竞天择、适者生存的进化准则，1975年，Michigan大学Holland教授根据这一规律首次提出了遗传算法（genetic algorithm，简称GA），其基本思想是力求充分模仿这一自然寻优过程的随机性、鲁棒性和全局性。这是一种新型的全局优化搜索算法，因为其直接对结构对象进行操作，不存在求导和函数连续性的限定等数学问题，鲁棒性强、随机性、全局性以及适于并行处理，已广泛应用于神经网络、计算机科学、优化调度、运输问题、组合优化、机器学习、信号处理、自适应控制和人工生命等领域，并且遗传算法在实际应用中也取得了巨大成功。
2 基本遗传算法
遗传算法的工作过程本质上就是模拟生物的进化过程。首先，要规定一种编码方法，使得你的问题的任何一个潜在可行解都能表示成为一个“数字”染色体。然后，创建一个由随机的染色体组成的初始群体（每个染色体代表了一个不同的候选解），并在一段时期中，以培育适应性最强的个体的办法，让它们进化，在此期间，染色体的某些位置上要加入少量的变异。
遗传算法是一种基于空间搜索的算法，它的求解可以看成是最优化过程。遗传算法的最大优点就是，你不需要知道怎么去解决一个问题，你需要知道的仅仅是用什么样的方式对可行解进行编码，使得它能被遗传算法机制所利用。遗传算法并不能保证所得到的解是最优解，但可以将误差控制在容许的范围内。遗传算法具有以下特点：
1） 遗传算法是对参数集合的编码而非针对参数本身进行优化；
2） 遗传算法是从问题解的编码组开始而非从单个解开始搜索；
3） 遗传算法利用目标函数的适应度这一信息而非利用导数或其他辅助信息来指导搜索；
4） 遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。
那么下面对基本遗传算法给出一个求解步骤：
1） 定义一个目标函数；
2） 将可行解群体在一定的约束条件下初始化，每一个可行解用一个向量x来编码，称为一条染色体，向量的分量代表基因，它对应可行解的某一决策变量；
3） 计算群体中每条染色体xi(i＝1，2，…，n)所对应的目标函数值，并以此计算适应值Fi，按Fi的大小来评价该可行解的好坏；
4） 以优胜劣汰的机制，将适应值差的染色体淘汰掉，对幸存的染色体根据其适应值的好坏，按概率随机选择，进行繁殖，形成新的群体；
5） 通过杂交和变异的操作，产生子代。杂交是随机选择两条染色体（双亲），将某一点或多点的基因互换而产生两个新个体，变异是基因中的某一点或多点发生突变；
6） 对子代群体重复步骤(3)～(5)的操作，进行新一轮遗传进化过程，直到迭代收敛（适应值趋稳定）即找到了最优解或准最优解。
3 遗传算法的发展动向
GA在应用方面的取得了较丰硕的成果，其主要应用领域在于函数优化，机器人学，设计，组合优化，信号处理，人工生命等，此外遗传算法还有几个引人注目的新动向。
3.1 基于GA的机器学习
这一新的研究方向把GA从历史离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法，这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望，GA作为一种搜索算法从一开始就与机器学习有密切联系。分类器系统是第一个基于GA的机器学习系统。基于GA的概念学习是近几年机器学习领域的一个较为引人注目的研究方向。还有一些嵌入领域知识的基于GA的机器学习的研究。
3.2 并行处理的GA
并行处理的GA的研究不仅是GA本身的发展，而且对于新一代智能计算机体现结构的研究都是十分重要的，GA在操作上具有高度的并行性，许多研究人员都正在搜索在并行机上高效执行GA的策略。近几年也发表了不少这方面的论文，研究表明，只要通过保持多个群体和恰当地控制群体间的相互作用来模拟并执行过程，即使不使用并行计算机，我们也能提高算法的执行效率。在并行GA的研究方面，一些并行GA可以分为两类：一是粗粒度并行GA，它主要开发群体间的并行性，如Coboon分析了在并行计算机上解图划分问题的多群体GA的性能；另一类是细粒度并行GA，它主要开始一个群体中的并行性，如Kosak将群体中的每个个体映射到一个连接机的处理单元上，并指出了这种方法对网络图设计问题的有效性。
3.3 GA与人工生命的渗透
人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。人工生命与GA有密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础，虽然人工生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人工生命的研究提供了一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展。
3.4 GA与进化规则及进化策略的结合
GA，进化规则及进化策略是进化计算的三个主要分支，这三种典型的进化算法都以自然界中生物的进化过程为自适应全局优化搜索过程的借鉴对象，所以三者之间有较大的相似性，但三种算法又是从不完全相同的角度出发来模拟生物的进化过程，分别是依据不同的生物进化背景，不同的生物进化机制而开发出来的，所以又有差异。但在进化计算领域内更重要的工作是生物的进化机制，构造性能更加优良且适应性更加广泛的进化算法。
4 基于遗传算法优化神经网络的应用研究
神经网络和遗传算法目标相近而方法各异。因此，将这两种方法相互结合，必能达到取长补短的作用。近年来,在这方面已经取得了不少研究成果，形成了以遗传算法与神经网络相结合的进化神经网络(ENN)。遗传算法在神经网络中的应用主要是用遗传算法学习神经网络的权重和学习神经网络的拓扑结构两个部分。
4.1 遗传算法学习神经网络的权重
而最主要的是学习神经网络的权重，也就是用遗传算法来取代一些传统的学习算法 。目前广泛研究的前馈网络中采用的是Rumel hart等人推广的误差反向传播（BP）算法，BP算法具有简单和可塑的优点，但是BP算法是基于梯度的方法，这种方法的收敛速度慢，且常受局部极小点的困扰，采用遗传算法则可把神经网络的结构优化和权值学习合并起来一起求解，克服了BP算法的缺陷，是神经网络权值学习的有效方法。
遗传算法学习神经网络权值的算法步骤如下：
1） 随机产生一组分布，采用某种编码方案对该组中的每个权值（或阈值）进行编码，进而构造出一个个码链（每个码链代表网络的一种权值分布），在网络结构和学习算法已定的前提下，该码链就对应一个权值和阈值取特定值的一个神经网络；
2） 对所产生的神经网络计算它的误差函数，从而确定其适应度函数值，误差与适应度成反比关系；
3） 选择若干适应度函数值最大的个体，直接遗传给下一代（精英保护策略）；
4） 利用交叉和变异等遗传操作算子对当前一代群体进行处理，产生下一代（新一代）群体；
5） 重复步骤2～4，使初始确定的一组权值分布得到不断的进化，直到训练目标得到满足或者迭代次数达到预设目标为止。
4.2 遗传算法学习神经网络的拓扑结构
神经网络结构包括网络的拓扑结构（连接方式）和接点转移函数两方面。利用遗传算法设计神经网络可根据某些性能评价准则如学习速度，泛化能力或结构复杂程度等搜索结构空间中满足问题要求的最佳结构。利用遗传算法设计神经网络的关键问题之一仍然是如何选取编码方案。
遗传算法学习神经网络结构的算法步骤如下:
1） 随机产生若干个不同结构的神经网络，对每个结构编码，每个码链对应一个网络结构，N个码链构成种群。
2） 利用多种不同的初始连接权值分别对每个网络进行训练。
3） 计算在每个对应码链下神经网络的误差函数，利用误差函数或其他策略（如网络的泛化能力或结构复杂度）确定每个个体的适应度函数。
4） 选择若干适应度函数值最大的个体构成父本。
5） 利用交叉，变异等遗传操作算子对当前一代群体进行处理，产生新一代群体。
6） 重复上述2）-5）步骤，直到群体中的某个个体（对应一个网络结构）能满足要求为止。
5 结束语
遗传算法作为一种新型的全局优化搜索算法，由于其直接对结构对象进行操作，不存在求导和函数连续性的限定，又具有鲁棒性强、随机性、全局性以及适于并行处理的优点，在人工神经网络的应用上展现了它的独特魅力与优势，但同时，它在理论和应用技术上也存在着许多不足和缺陷，比如相对鲜明的生物基础，其数学基础显得极为薄弱，尤其是缺乏深刻且具有普遍意义的理论分析。随着理论研究的深入，可以肯定，作为一种高效并行的全局搜索方法，遗传算法以其特有的算法特点使其在许多实际问题中的应用会越来越广；同时，广泛的数学方法和强大的计算机模拟工具的出现，必将使遗传算法的研究取得长足的进展。
参考文献：
[1] 蔡自兴. 人工智能及其应用[M]. 3版.北京：清华大学出版社，2003.
[2] 王风琴. 基于遗传算法的神经网络优化[J].燕山大学学报，2001，25（3）：234-239.
[3] 陈国良. 遗传算法及其应用[M].北京：人民邮电出版社，1999.
[4] 陈颖琪. 进化计算与神经网络的结合[J].红外与激光工程，1999，（4）：8-11，35.
[5] Kretnovich v.Qmtana C and Puentes O.Genetnc Algorithms-What Fitness Scaling is Optimal. Ctberm and System 1993.24.
[6] S W Mathfoud.Genetic drift in sharing methods. 0-7803-I899-4/94.1994 IEEE
[7] V Petrochs.S Kazarns. Varying quality function Gengentic algorithms and the cutting problem. 0-7803-I899-4/94.1994 IEEE
[8] 杨旭东，张彤. 遗传算法应用于系统在线识别研究[J].哈尔滨工业大学学报， 2000，32（1）：102-104.
[9] Pham D T，Jin G. Genetic algorithms using gradient-like ren reduction operator. Electronics Letters. 1995 .31.
[10] Nover D，Baskaran S，Scbuster P. Understanding genetic algorithms dynamics using harvesting strategies. Physics D 79, 1994.
[11] Kao T, Hwang S Y. A genetic algorithm with sruptive selection[J]. IEEE Transcations on System, Man. And Cybernetris-Part B: Cybernetics 1996,26.
[12] Arabas J. Michalewicz Z and Mulawka J. GAVaPS-a Genetic Algorithms with Varying Population Size[C].Proc O the 1st IEEE on Evolutonary Computation IEEE，1994.
[13] Liu Li, Chen Xueyun. Reconfiguration of distribution networks based on fuzzy genetic algorithms[J]. proceedings of Chinese Society of the CSEE, 2000,20(9):44-49.