人工智能第五章109

人工智能原理ArtificialIntelligencePrinciple信息工程学院张永梅第5章计算智能(2)进化计算人工生命第五章计算智能(2)5.1遗传算法5.2进化策略5.3进化编程5.4人工生命第五章计算智能(2)作业：5-2，5-7，5-9答疑时间及地点•答疑时间：每周四5、6节•答疑地点：三教2604•电子邮件：[e-mail]•联系方式：13810842037第四章计算智能(1)4.1概述4.2神经计算4.3模糊计算计算智能涉及神经网络、模糊逻辑、进化计算和人工生命等领域，它的研究和发展反映了当代科学技术多学科交叉与集成的重要发展趋势。计算智能是借鉴仿生学的思想，基于人们对生物体智能机理的认识，采用数值计算的方法去模拟和实现人类的智能。计算智能是一种以模型（计算模型、数学模型）为基础，以分布、并行计算为特征的自然智能模拟方法。进化计算（EvolutionaryComputation,EC）包括：遗传算法(geneticalgorithms，GA)进化策略(evolutionstrategies)进化编程(evolutionaryprogramming)遗传编程(geneticprogramming)人类不满足于模仿生物进化行为，希望能够建立具有自然生命特征的人造生命和人造生命系统。人工生命是人工智能和计算智能的一个新的研究热点。进化计算是一种对人类智能的演化模拟方法，它是通过对生物遗传和演化过程的认识，用进化算法去模拟人类智能的进化规律的。人工生命(Artificiallife，AL)是通过人工模拟生命系统，来研究生命的领域。人工生命的概念，包括两个方面内容：（1）属于计算机科学领域的虚拟生命系统，涉及计算机软件工程与人工智能技术；（2）基因工程技术人工改造生物的工程生物系统，涉及合成生物学技术。AL是首先由计算机科学家ChristopherLangton于1987年在LosAlamosNationalLaboratory召开的生成以及模拟生命系统的国际会议上提出。世界首个人工生命结构诞生中新网2010年5月22日电综合媒体报道，美国克莱格.文特尔研究所一个有华人参与的研究团队宣布，在实验中制造出世界首个完全由人造基因指令控制的人造生命，使人类的能力拓展到可以操纵自然世界，将来可制造有特殊功能的生物，在生产疫苗及洁净能源等领域大派用场。由美国生物学家文特尔领导的研究团队，重塑“丝状支原体丝状亚种”(Mycoplasmamycoides)这种微生物的DNA，并将新DNA片段“黏”在一起，植入另一种山羊支原体中。新生命于2010年4月诞生，昵称“Synthia”(合成体)，这种微生物由蓝色细胞组成，能够生长、繁殖，细胞分裂了逾10亿次，产生一代又一代的人造生命。植入的DNA片段包含约850个基因，而人类DNA图谱上共有约2万个基因。进化计算（EvolutionaryComputation,EC）包括：遗传算法(geneticalgorithms，GA)进化策略(evolutionstrategies)进化编程(evolutionaryprogramming)遗传编程(geneticprogramming)其中，遗传算法是进化计算中最初形成的一种具有普遍影响的模拟进化优化算法。因此我们主要讨论遗传算法。进化计算是一种模拟自然界生物进化过程与机制进行问题求解的自组织、自适应的随机搜索技术。它将生物进化过程中的繁殖（Reproduction）变异（Mutation）竞争（Competition）选择（Selection）引入到了算法中。什么是进化计算进化计算的生物学基础自然界生物进化过程是进化计算的生物学基础，它主要包括:遗传(Heredity)变异(Mutation)进化(Evolution)理论生物进化与遗传算法群体种群子群选择婚配变异遭淘汰的群体遗传算法(GeneticAlgorithm)达尔文进化论：“物竞天择、适者生存”。70年代由美国的密执根大学的Holland在他的著作《AdaptationinNaturalandArtificialSystems》首次提出遗传算法，并主要由他和他的学生发展起来。近年来，遗传算法作为一种有效的工具，已广泛地应用于最优化问题求解之中。第五章计算智能(2)5.1遗传算法5.2进化策略5.3进化编程5.4人工生命5.1遗传算法遗传算法是模仿生物遗传学和自然选择机理，通过人工方式所构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的最重要的形式。遗传算法为那些难以找到传统数学模型的难题指出了一个解决方法。进化计算和遗传算法借鉴了生物科学中的某些知识，这也体现了人工智能这一交叉学科的特点。5.1遗传算法遗传算法的起源自然界所提供的答案是经过漫长的自适应——遗传过程获得的结果。我们也可以利用这一过程本身去解决一些复杂的问题。遗传算法的研究主要集中在以下几个方面：函数优化、组合优化生产调度、自动控制、机器人学、图像处理、人工生命、演化编程和机器学习。5.1.1遗传算法的基本机理霍兰德的遗传算法通常称为简单遗传算法（SimpleGeneticAlgorithm,SGA）。现以此作为讨论主要对象，加上适应的改进，来分析遗传算法的结构和机理。5.1遗传算法编码与解码适应度函数遗传操作5.1.1遗传算法的基本机理5.1遗传算法基本思想是从初始种群出发，采用优胜劣汰、适者生存的自然法则选择个体，并通过杂交、变异来产生新一代种群，如此逐代进化，直到满足目标为止。遗传算法的基本概念遗传算法（GeneticAlgorithm）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。5.1.1遗传算法的基本机理5.1遗传算法遗传算法的基本概念遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体（individual）组成。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小挑选（selection）个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。5.1.1遗传算法的基本机理5.1遗传算法遗传算法的基本概念遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主要有以下特点：1、遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际值本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便地应用遗传操作算子。2、遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。3、遗传算法使用多个点的搜索信息，具有隐含并行性。4、遗传算法使用概率搜索技术，而非确定性规则。5.1.1遗传算法的基本机理5.1遗传算法基本思想是从初始种群出发，采用优胜劣汰、适者生存的自然法则选择个体，并通过杂交、变异来产生新一代种群，如此逐代进化，直到满足目标为止。遗传算法的基本概念种群（Population）：种群是初始给定的多个解的集合。它一般是整个搜索空间的一个很小的子集。个体（Individual）：个体是指种群中的单个元素。一个个体也就是搜索空间中的一个点。染色体（Chromos）：由多个基因组成，表示一个个体。染色体是指对个体进行编码后所得到的编码串。染色体中的每1位称为基因，染色体上由若干个基因构成的一个有效信息段称为基因组。适应度（Fitness）函数：适应度函数是一种用来对种群中各个个体的环境适应性进行度量的函数。其函数值是遗传算法实现优胜劣汰的主要依据。5.1.1遗传算法的基本机理5.1遗传算法遗传算法的基本概念适应度(fitness)借鉴生物个体对环境的适应程度，而对问题中的个体对象所设计的表征其优劣的一种测度适应度函数(fitnessfunction)问题中的全体个体与其适应度之间的一个对应关系一般是一个实值函数该函数就是遗传算法中指导搜索的评价函数5.1.1遗传算法的基本机理5.1遗传算法遗传算法的基本概念染色体(chromosome)染色体是由若干基因组成的位串（生物学）个体对象由若干字符串组成来表示（遗传算法）个体染色体9----1001（2，5，6）----010101110遗传算法(geneticalgorithm)染色体就是问题中个体的某种字符串形式的编码表示染色体以字符串来表示基因是字符串中的一个个字符5.1.1遗传算法的基本机理5.1遗传算法遗传算法的基本概念编码与解码将问题结构变换为位串形式编码表示的过程叫编码；将位串形式编码表示变换为原问题结构的过程叫解码或译码。Huffman编码方法是一种效率高、方法简单的编码。信源中符号出现的概率相差越大，Huffman编码效果越好。哈夫曼（Huffman）编码Huffman编码一般可将数据压缩20%至90%，其压缩效率取决于被压缩数据的特征。（1）把信源符号xi(i=1,2,…,N)按出现概率的值由小到大的顺序排列；Huffman编码步骤（2）对两个概率最小的符号分别分配以“0”和“1”，然后把这两个概率相加作为一个新的辅助符号的概率；（3）将这个新的辅助符号与其他符号一起重新按概率大小顺序排列；（4）跳到第2步，直到出现概率相加为1为止；Huffman编码步骤（5）用线将符号连接起来，从而得到一个码树，树的N个端点对应N个信源符号；（6）从最后一个概率为1的节点开始，沿着到达信源的每个符号，将一路遇到的二进制码“0”或“1”顺序排列起来，就是端点所对应的信源符号的码字。Huffman编码方法例如：信源符号分布为：a:4/22b:3/22c:2/22d:1/22e:5/22f:7/22排序为：d,c,b,a,e,f1/222/223/224/225/227/22Huffman编码方法cbafe7/225/224/222/2210f=11e=01a=00b=101c=1001d=1000d1/223/226/2222/2213/229/223/2210101010哈夫曼解码在通信中，若将字符用哈夫曼编码形式发送出去，对方接收到编码后，将编码还原成字符的过程，称为哈夫曼解（译）码。解码:从根结点起，每输入一个数码即沿二叉树下移一层，数码为0时移向左分支，数码为1时移向右分支，待达到叶子结点时即译出一个字符，再输入的数码又从根结点开始重新做起。反复由根出发，直到译码完成。5.1.1遗传算法的基本机理5.1遗传算法遗传算法的基本概念遗传操作（GeneticOperator）：遗传操作是指作用于种群而产生新的种群的操作。包括以下3种基本形式：选择（Selection）交叉（Crosssover）变异（Mutation）5.1.1遗传算法的基本机理5.1遗传算法遗传算法的基本概念遗传操作选择操作也叫复制（reproduction）操作，根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。交叉操作的简单方式是将被选择出的两个个体P1和P2作为父母个体，将两者的部分码值进行交换。变异操作的简单方式是改变数码串的某个位置上的数码。二进制编码表示的简单变异操作是将0与1互换：0变异为1，1变异为0。选择算子模拟生物界优胜劣汰的自然选择法则的一种染色体运算从种群中选择适应度较高的染色体进行复制，以生成下一代种群算法：个体适应度计算在被选集中每个个体具有一个选择概率