搜索
2智能智能ABCABCNNNN——神经网络，神经网络，PRPR——模式识别，模式识别，II——智能智能zzAA－－ArtificialArtificial，，表示人工的（非生物的），即人造的表示人工的（非生物的），即人造的zzBB－－BiologicalBiological，，表示物理的＋化学的＋（？？）＝生物的表示物理的＋化学的＋（？？）＝生物的zzCC－－ComputationalComputational，，表示数学＋计算机表示数学＋计算机ABC的关系图37.17.1进化计算概述进化计算概述¾¾生物进化生物进化生物在变异、遗传与自然选择作用下的演变发展，物种淘汰和物种产生过程。地球上原来无生命，大约在30多亿年前，在一定的条件下，形成了原始生命，其后，生物不断的进化，直至今天世界上存在着170多万个物种。生物进化论昀早由查尔斯·罗伯特·达尔文提出，在其名著《物种起源》有详细的论述。4zz低级、简单低级、简单ÎÎ高级、复杂高级、复杂¾¾生物进化生物进化5zz生物进化过程生物进化过程((从简单到复杂，从低级向高级从简单到复杂，从低级向高级))本身是一个本身是一个自然的、并行发生的、稳健的优自然的、并行发生的、稳健的优化化过程。过程。zzDarwinDarwin的经典进化理论、的经典进化理论、WeismannWeismann的自然的自然选择理论及选择理论及MendelMendel的遗传学理论一起构成了的遗传学理论一起构成了新达尔文进化理论新达尔文进化理论，这一理论认为，进化是，这一理论认为，进化是指生物通过指生物通过繁殖、变异、竞争和自然选择繁殖、变异、竞争和自然选择这这44个基本演变过程实现生物种群的个基本演变过程实现生物种群的““优胜劣汰优胜劣汰””。。67.17.1进化计算概述进化计算概述¾¾进化计算进化计算ECEC进化计算(EvolutionaryComputation,EC)的相关研究始于20世纪50年代后期，它基于生物的自然进化与自然选择的生存遗传机制，针对一类复杂难解的优化问题，研究通用的智能化的问题求解方法，属于迭代法。22()2cos2()0.222020xyxyzeeeπ++−=+−−2xz=]40,40[],30,30[,min−∈−∈yxz7zz进化计算进化计算主要包括主要包括::遗传算法遗传算法(GeneticAlgorithm,GA)(GeneticAlgorithm,GA)遗传编程遗传编程(GeneticProgramming,GP)(GeneticProgramming,GP)进化编程进化编程(EvolutionaryProgramming,EP)(EvolutionaryProgramming,EP)进化策略进化策略(EvolutionaryStrategies,ES)(EvolutionaryStrategies,ES)89z采用简单的编码技术表示各种复杂的问题解结构，每个解称为一个染色体，染色体的特征称为基因，因此染色体又可称基因型个体，每一组解就构成一个种群，对于由若干个体构成的初始种群，将每个个体看成是问题解空间中的一点，通过迭代，简单、高效、并行地随机搜索问题的解，末代种群中的最优个体经过解码即是问题的最优解或近似最优解。z在迭代过程中，根据个体对问题的适应度以一定的概率通过杂交和变异等遗传操作和优胜劣汰的自然选择机制指导学习、确定搜索方向，以便搜索能够朝着产生更好的解的方向进行。10进化计算的设计进化计算的设计主要涉及四个环主要涉及四个环节，即节，即编码方案、编码方案、选择策略、遗传选择策略、遗传操作、进化参数操作、进化参数。。不同的设计策略不同的设计策略构成了不同类型构成了不同类型的进化算法。的进化算法。11¾¾遗传算法遗传算法(GeneticAlgorithm,GA)(GeneticAlgorithm,GA)zz是进化计算的最重要形式，它是建立在新达尔文进是进化计算的最重要形式，它是建立在新达尔文进化论的基础上的一种计算模型，是一种通过模拟自化论的基础上的一种计算模型，是一种通过模拟自然进化过程搜索最优解的迭代自适应概率搜索方然进化过程搜索最优解的迭代自适应概率搜索方法，法，美国美国MichiganMichigan大学的大学的HollandHolland及其研究团队于及其研究团队于19751975年首次提出了遗传算法年首次提出了遗传算法，并出版了里程碑式的，并出版了里程碑式的专著专著““AdaptationinNaturalandArtificialAdaptationinNaturalandArtificialSystemsSystems””(Holland(Holland,1975),1975)，随后算法被扩展推广并，随后算法被扩展推广并正式定名为遗传算法正式定名为遗传算法(Holland,1992)(Holland,1992)，与此同时，，与此同时，GAGA开始被国内外研究者广泛关注。开始被国内外研究者广泛关注。12¾¾遗传编程遗传编程(GeneticProgramming,GP)(GeneticProgramming,GP)zz遗传编程也称遗传规划或遗传程序设计，是一种模遗传编程也称遗传规划或遗传程序设计，是一种模仿人类智能进行自动程序设计的方法，是进化计算仿人类智能进行自动程序设计的方法，是进化计算中最年轻的分支，由中最年轻的分支，由HollandHolland的学生的学生KozaKoza首次提出首次提出((KozaKoza,2008),2008)。。zz它采用遗传算法的基本思想，但编码方式更灵活，它采用遗传算法的基本思想，但编码方式更灵活，使用一种长度、大小都可变的树形分层结构来表示使用一种长度、大小都可变的树形分层结构来表示解空间。这些分层结构的叶结点是问题的原始变解空间。这些分层结构的叶结点是问题的原始变量，中间结点则是组合这些原始变量的函数。于量，中间结点则是组合这些原始变量的函数。于是，每个分层结构对应问题的一个可能解，也可以是，每个分层结构对应问题的一个可能解，也可以理解为求解该问题的一个计算机程序。理解为求解该问题的一个计算机程序。13¾¾进化编程进化编程(EvolutionaryProgramming,EP)(EvolutionaryProgramming,EP)zz进化编程也称进化规划，进化编程也称进化规划，2020世纪世纪6060年代初由年代初由FogelFogel等等在美国首次提出在美国首次提出((FogelFogeletaletal,1966),1966)。。zz他们在人工智能的研究中发现，智能行为具有预测他们在人工智能的研究中发现，智能行为具有预测其所处环境的状态、并按给定目标作出适当响应的其所处环境的状态、并按给定目标作出适当响应的能力。在研究中，他们将模拟环境描述成由有限字能力。在研究中，他们将模拟环境描述成由有限字符集中的符号组成的序列。于是问题转化为怎样根符集中的符号组成的序列。于是问题转化为怎样根据当前观察到的符号序列做出响应，以获得最大收据当前观察到的符号序列做出响应，以获得最大收益。这里，收益按环境中将要出现的下一个符号及益。这里，收益按环境中将要出现的下一个符号及预先定义好的效益目标来确定。进化编程中常用有预先定义好的效益目标来确定。进化编程中常用有限态自动机限态自动机(FiniteStateMachine,FSM)(FiniteStateMachine,FSM)来表示这样来表示这样的策略。的策略。14¾¾进化策略进化策略(EvolutionaryStrategies,ES)(EvolutionaryStrategies,ES)zz一般只适合求解数值优化问题，一般只适合求解数值优化问题，2020世纪世纪6060年代初，年代初，由由RechenbergRechenberg，，SchwefelSchwefel及及BienertBienert等在德国共同创等在德国共同创立立(Thomas(ThomasBaeckBaecketal,2000)etal,2000)。。zz早期进化策略的种群中只包含一个个体，即单父代早期进化策略的种群中只包含一个个体，即单父代单子代；而且遗传操作只有变异。在每一进化代，单子代；而且遗传操作只有变异。在每一进化代，变异后的个体与其父体进行比较，选择两者之优。变异后的个体与其父体进行比较，选择两者之优。这种进化策略称为这种进化策略称为(1+1)(1+1)进化策略。这种策略存在有进化策略。这种策略存在有时收敛不到全局最优解、效率较低等弊端。时收敛不到全局最优解、效率较低等弊端。15¾¾进化计算的特点进化计算的特点––智能性智能性适者生存、不适应者淘汰；自组织、自学习适者生存、不适应者淘汰；自组织、自学习––本质并行性本质并行性内在并行、内含并行内在并行、内含并行––全局性与多解性全局性与多解性以种群为单位搜索以种群为单位搜索––稳健性稳健性通用、鲁棒通用、鲁棒––随机性随机性在概率意义上朝昀优解方向靠近在概率意义上朝昀优解方向靠近167.27.2遗传算法及空间信息处理遗传算法及空间信息处理¾¾遗传算法的基本框架与设计遗传算法的基本框架与设计Holland所提出的GA通常为简单遗传算法(Simplegeneticalgorithm,SGA)，其基本数学模型为：0(,,,,,,)SGACEPMTΦ,ΓΨ=，其中C表示编码方案，E表示适应度评价函数，P0表示初始种群，M表示种群规模，,Φ,ΓΨ分别表示选择算子、杂交算子、变异算子等遗传操作，T表示终止条件。17z遗传算法的一般步骤：¾确定问题解空间的表示方式，即编码方案，形成问题解空间与染色体基因串空间的映射关系，每个个体用一个基因串表达。¾随机产生满足一定约束条件的初始种群。¾根据所设计的适应度函数，计算种群中每个个体的适应度。¾根据个体的适应度值大小，选择优者以一定概率执行杂交、变异操作，产生下一代种群。¾迭代执行步骤3和步骤4，直至满足算法的停止条件。¾输出末代最优个体基因串，并解码，即是问题的最优解或最优近似解，算法结束。18用遗传算法求解一元函数2()23fxxx=−++的昀大值，其中[0,3]x∈。19（（11））编码方案编码方案早期的遗传算法主要使用二进制编码。即用一个固定长度的二进制基因串来表示一个个体，代替变量的实数值，串长就决定了解的精度。对于axb≤≤要求精度为小数点后k位，区间被划分为至少()10kba−区段，于是基因串长gl应该满足2gl-1≥(b-a)×10t。即2log(()101)tglba⎡⎤≥−+⎢⎥,log((21)/())gltba⎢⎥≤−−⎣⎦设个体的二进制串为gk-1…g2g1g0，，则对应的解码方式为10()(2)21kiikibaxag−•=−=+•−∑。对于本例，初始种群中的每个个体用10位二进制来表示，由上式计算得到精度为小数点后2位，(1001001011)转换成实数为：96310(30)0(22221)1.7221−+•++++=−。20z除了二进制编码外，常用的编码方式还有实数编码和格雷码。z二进制编码在求解本问题时存在以下缺点：¾不能直观反映所求问题本身的结构特征；¾相邻整数的二进制编码可能具有较大的Hamming距离，降低遗传算子的搜索效率；¾由精度确定串长，从而导致精度固定不能微调(串长太短则影响精度，串长太大则降低算法效率)。¾而实数编码则是该问题的直观描述，不存在编码和解码过程，从而提高了解的精度和运算速度。21zz（（22）适应度函数）适应度函数在遗传算法中，适应值的度量是群体演化的依据，因此，对于种群中的一系列个体基因串，设计出的适应度函数要有能力识别出潜在的优秀个体，即优秀个体的适应度函数值也高。在一般优化问题中，经常是问题本身，有时也对其进行一些比例变换，如线性比例变换、δ截断、幂变换等。对于本例，适应度函数E(v)=f(x)，其中v是x对应的基因串表示，如E(1001001011)=f(1.72)=—(1.72)2+2×1.72+3=3.4816。22zz（（33）遗传操作