截图
简介
这是图像遗传算法ppt，包括了进化计算，进化计算概述——生物学基础，进化计算概述——产生与发展，遗传算法——研究内容，遗传算法——基本结构等内容，欢迎点击下载。
图像遗传算法ppt是由红软PPT免费下载网推荐的一款课件PPT类型的PowerPoint.
人工智能
5.3 进化计算
进化计算（Evolutionary Computation，EC）是在达尔文（Darwin）的进化论和孟德尔（Mendel）的遗传变异理论的基础上产生的一种在基因和种群层次上模拟自然界生物进化过程与机制的问题求解技术。它主要包括
遗传算法（Genetic Algorithm，GA）
进化策略（Evolutionary Strategy，ES）
进化规划（Evolutionary Programming，EP）
遗传规划（Genetic Programming，GP） 四大分支。 其中，第一个分支是进化计算中最初形成的一种具有普遍影响的模拟进化优化算法。因此我们主要讨论遗传算法。
5.3.1 进化计算概述——生物学基础
什么是进化计算 进化计算是一种模拟自然界生物进化过程与机制进行问题求解的自组织、自适应的随机搜索技术。它以达尔文进化论的“物竟天择、适者生存”作为算法的进化规则，并结合孟德尔的遗传变异理论，将生物进化过程中的
繁殖（Reproduction）
变异（Mutation）
竞争（Competition）
选择（Selection） 引入到了算法中。
进化计算的生物学基础 自然界生物进化过程是进化计算的生物学基础，它主要包括遗传(Heredity)、变异(Mutation)和进化(Evolution)理论。
进化论 进化是指在生物延续生存过程中，逐渐适应其生存环境，使得其品质不断得到改良的这种生命现象。遗传和变异是生物进化的两种基本现象，优胜劣汰、适者生存是生物进化的基本规律。
达尔文的自然选择学说认为：在生物进化中，一种基因有可能发生变异而产生出另一种新的生物基因。这种新基因将依据其与生存环境的适应性而决定其增殖能力。一般情况下，适应性强的基因会不断增多，而适应性差的基因则会逐渐减少。通过这种自然选择，物种将逐渐向适应于生存环境的方向进化，甚至会演变成为另一个新的物种，而那些不适应于环境的物种将会逐渐被淘汰。
遗传理论 遗传是指父代（或亲代）利用遗传基因将自身的基因信息传递给下一代（或子代)，使子代能够继承其父代的特征或性状的这种生命现象。正是由于遗传的作用，自然界才能有稳定的物种。
在自然界，构成生物基本结构与功能的单位是细胞（Cell）。细胞中含有一种包含着所有遗传信息的复杂而又微小的丝状化合物，人们称其为染色体（Chromosome）。在染色体中，遗传信息由基因（Gene）所组成，基因决定着生物的性状，是遗传的基本单位。染色体的形状是一种双螺旋结构，构成染色体的主要物质叫做脱氧核糖核酸(DNA)，每个基因都在DNA长链中占有一定的位置。一个细胞中的所有染色体所携带的遗传信息的全体称为一个基因组(Genome)。细胞在分裂过程中，其遗传物质DNA通过复制转移到新生细胞中，从而实现了生物的遗传功能。
变异理论 变异是指子代和父代之间，以及子代的各个不同个体之间产生差异的现象。变异是生物进化过程中发生的一种随机现象，是一种不可逆过程，在生物多样性方面具有不可替代的作用。引起变异的主要原因有以下两种：
杂交 指有性生殖生物在繁殖下一代时两个同源染色体之间的交配重组，即两个染色体在某一相同处的DNA被切断后再进行交配重组，形成两个新的染色体。
复制差错 指在细胞复制过程中因DNA上某些基因结构的随机改变而产生出新的染色体。
5.3.1 进化计算概述——产生与发展
进化计算自20世纪50年代以来，其发展过程大致可分为三个阶段。
萌芽阶段（'50年代后期到'70年代中期）
20世纪50年代后期，一些生物学家在研究如何用计算机模拟生物遗传系统中，产生了遗传算法的基本思想，并于1962年由美国密执安（Michigan）大学霍兰德（Holland）提出。1965年德国数学家雷切伯格（Rechenberg）等人提出了一种只有单个个体参与进化，并且仅有变异这一种进化操作的进化策略。同年，美国学者弗格尔（Fogel）提出了一种具有多个个体和仅有变异一种进化操作的进化规划。1969年美国密执安（Michigan）大学的霍兰德（Holland）提出了系统本身和外部环境相互协调的遗传算法。至此，进化计算的三大分支基本形成。
成长阶段（'年代中期到'80年代后期） 1975年，霍兰德出版专著《自然和人工系统的适应性（Adaptation in Natural and Artificial System）》，全面介绍了遗传算法。同年，德国学者施韦费尔（Schwefel）在其博士论文中提出了一种由多个个体组成的群体参与进化的，并且包括了变异和重组这两种进化操作的进化策略。1989年，霍兰德的学生戈尔德伯格（Goldberg）博士出版专著《遗传算法——搜索、优化及机器学习（Genetic Algorithm——in Search Optimization and Machine Learning）》，使遗传算法得到了普及与推广。
发展阶段（'90年代至今）
1989年，美国斯坦福（Stanford）大学的科扎（Koza）提出了遗传规划的新概念，并于1992年出版了专著《遗传规划----应用自然选择法则的计算机程序设计（Genetic Programming :on the Programming of Computer by Means of Natural Selection）》该书全面介绍了遗传规划的基本原理及应用实例，标志着遗传规划作为计算智能的一个分支已基本形成。
进入20世纪90年代以来，进化计算得到了众多研究机构和学者的高度重视，新的研究成果不断出现、应用领域不断扩大。目前，进化计算已成为人工智能领域的又一个新的研究热点。
5.3.2 遗传算法——研究内容
性能分析。遗传算法的性能分析一直都是遗传算法研究领域中最重要的主题之一。在遗传算法中，群体规模、杂交和变异算子的概率等控制参数的选取是非常困难的，同时它们又是必不可少的实验参数。遗传算法还存在一个过早收敛问题，也就是说遗传算法的最后结果并不总是达到最优解，怎样阻止过早收敛问题是人们感兴趣的问题之一。另外，为了拓广遗传算法的应用范围，人们在不断研究新的遗传染色体表示法和新的遗传算子。
并行遗传算法。遗抟算法在操作上具有高度的并行性，只要通过保持多个群体和恰当地控制群体间的相互作用来模拟并行执行过程，即使不使用并行计算机，我们也能提高算法的执行效率。
分类系统。分类系统属于基于遗传算法的机器学习中的一类型，它包括一个简单的基于串规则的并行生成子系统、规则评价子系统和遗传算法子系统。目前，分类系统是遗传算法研究中的一个非常活跃的领域
5.3.2 遗传算法——基本概念
遗传算法的基本思想是从初始种群出发，采用优胜劣汰、适者生存的自然法则选择个体，并通过杂交、变异来产生新一代种群，如此逐代进化，直到满足目标为止。遗传算法所涉及到的基本概念主要有以下几个：
种群（Population）：种群是指用遗传算法求解问题时，初始给定的多个解的集合。遗传算法的求解过程是从这个子集开始的。
个体（Individual）：个体是指种群中的单个元素，它通常由一个用于描述其基本遗传结构的数据结构来表示。例如，可以用0、1组成的长度为l的串来表示个体。
染色体（Chromos）：染色体是指对个体进行编码后所得到的编码串。染色体中的每1位称为基因，染色体上由若干个基因构成的一个有效信息段称为基因组。
适应度（Fitness）函数：适应度函数是一种用来对种群中各个个体的环境适应性进行度量的函数。其函数值是遗传算法实现优胜劣汰的主要依据
遗传操作（Genetic Operator）：遗传操作是指作用于种群而产生新的种群的操作。标准的遗传操作包括以下三种基本形式：
选择（Selection）
交叉（Crosssover）
变异（Mutation）
遗传算法与自然进化的比较
5.3.2 遗传算法——基本结构
遗传算法主要由染色体编码、初始种群设定、适应度函数设定、遗传操作设计等几大部分所组成，其算法主要内容和基本步骤可描述如下：
(1) 选择编码策略，将问题搜索空间中每个可能的点用相应的编码策略表示出来，即形成染色体；
(2) 定义遗传策略，包括种群规模N，交叉、变异方法，以及选择概率Pr、交叉概率Pc、变异概率Pm等遗传参数；
(3) 令t=0，随机选择N个染色体初始化种群P(0)；
(4) 定义适应度函数f（f>0）；
(5) 计算P(t)中每个染色体的适应值；
(6) t=t+1；
(7) 运用选择算子，从P(t-1)中得到P(t)；
(8) 对P(t)中的每个染色体，按概率Pc参与交叉；
(9) 对染色体中的基因，以概率Pm参与变异运算；
(10) 判断群体性能是否满足预先设定的终止标准，若不满足则返回(5)。
5.3.2 遗传算法——遗传编码
常用的遗传编码算法有二进制码、格雷码（Gray Code）、实数编码和字符编码等。
二进制编码（Binary encoding）
二进制编码是将原问题的结构变换为染色体的位串结构。在二进制编码中，首先要确定二进制字符串的长度l，该长度与变量的定义域和所求问题的计算精度有关。
例 假设变量x的定义域为[5，10]，要求的计算精度为10E-5，则需要将[5，10]至少分为600000个等长小区间，每个小区间用一个二进制串表示。于是，串长至少等于20，原因是：
524288=219<600000<220=1048576
这样，对应于区间[5，10]内满足精度要求的每个值x，都可用一个20位编码的二进制串<b19，b18，…，b0>来表示。
二进制编码存在的主要缺点是汉明（Hamming）悬崖。
例如，7和8的二进制数分别为0111和1000，当算法从7改进到8时，就必须改变所有的位。
格雷编码（Gray encoding）
格雷编码是对二进制编码进行变换后所得到的一种编码方法。这种编码方法要求两个连续整数的编码之间只能有一个码位不同，其余码位都是完全相同的。它有效地解决了汉明悬崖问题，其基本原理如下：
设有二进制串b1，b2，…，bn，对应的格雷串为a1，a2，…，an，则从二进制编码到格雷编码的变换为：
其中，⊕表示模2加法。而从一个格雷串到二进制串的变换为：
例 十进制数7和8的二进制编码分别为0111和1000，而其格雷编码分别为0100和1100。
实数编码（Real encoding）
实数编码是将每个个体的染色体都用某一范围的一个实数（浮点数）来表示，其编码长度等于该问题变量的个数。
这种编码方法是将问题的解空间映射到实数空间上，然后在实数空间上进行遗传操作。由于实数编码使用的是变量的真实值，因此这种编码方法也叫做真值编码方法。
实数编码适应于那种多维、高精度要求的连续函数优化问题。
5.3.2 遗传算法——适应度函数
适应度函数是一个用于对个体的适应性进行度量的函数。通常，一个个体的适应度值越大，它被遗传到下一代种群中的概率也就越大。
常用的适应度函数
在遗传算法中，有许多计算适应度的方法，其中最常用的适应度函数有以下两种：
原始适应度函数
它是直接将待求解问题的目标函数f(x)定义为遗传算法的适应度函数。例如，在求解极值问题
时，f(x)即为x的原始适应度函数。
采用原始适应度函数的优点是能够直接反映出待求解问题的最初求解目标，其缺点是有可能出现适应度值为负的情况。
标准适应度函数
在遗传算法中，一般要求适应度函数非负，并其适应度值越大越好。这就往往需要对原始适应函数进行某种变换，将其转换为标准的度量方式，以满足进化操作的要求，这样所得到的适应度函数被称为标准适应度函数fNormal(x)。
极小化问题
对极小化问题，其标准适应度函数可定义为
其中，fmax (x)是原始适应函数f(x)的一个上界。如果fmax (x) 未知，则可用当前代或到目前为止各演化代中的f(x)的最大值来代替。可见， fmax (x) 是会随着进化代数的增加而不断变化的。
极大化问题
对极大化问题，其标准适应度函数可定义为
其中，fmin(x)是原始适应函数f(x)的一个下界。如果fmin(x) 未知，则可用当前代或到目前为止各演化代中的f(x)的最小值来代替。
适应度函数的加速变换
在某些情况下，适应度函数在极值附近的变化可能会非常小，以至于不同个体的适应值非常接近，使得难以区分出哪个染色体更占优势。对此，最好能定义新的适应度函数，使该适应度函数既与问题的目标函数具有相同的变化趋势，又有更快的变化速度。
适应度函数的加速变换有两种基本方法
线性加速
适应度函数的定义如下：
其中， 是加速转换前的适应度函数； 是加速转换后的适应度函数； α和β是转换系数。
非线性加速
幂函数变换方法
指数变换方法
对于的选择应满足如下条件：
保证夫代中那些适应度接近于平均适应度个体，能够保证有相当数量的个体被遗传到下一代中
M是指将当前的最大适应度放大为其平均值的M倍，这样通过选择适当的M值可以拉开不同染色体间的适应度值的差距
5.3.2 基本遗传操作——选择
遗传算法中的基本遗传操作包括选择、交叉和变异3种，而每种操作又包括多种不同的方法，下面分别对它们进行介绍。
选择操作
选择（Selection）操作是指根据选择概率按某种策略从当前种群中挑选出一定数目的个体，使它们能够有更多的机会被遗传到下一代中。
常用的选择策略可分为比例选择、排序选择和竞技选择三种类型。
比例选择
比例选择方法（Proportional Model）的基本思想是：各个个体被选中的概率与其适应度大小成正比。
常用的比例选择策略包括：轮盘赌选择、繁殖池选择
轮盘赌选择
轮盘赌选择法又被称为转盘赌选择法或轮盘选择法。在这种方法中，个体被选中的概率取决于该个体的相对适应度。而相对适应度的定义为
其中，P(xi)是个体xi的相对适应度，即个体xi被选中的概率；f(xi)是个体xi的原始适应度；是种群的累加适应度。
轮盘赌选择算法的基本思想是：根据每个个体的选择概率P(xi)将一个圆盘分成N个扇区，其中第i个扇区的中心角为：
并再设立一个固定指针。当进行选择时，可以假想转动圆盘，若圆盘静止时指针指向第i个扇区，则选择个体i。
从统计角度看，个体的适应度值越大，其对应的扇区的面积越大，被选中的可能性也越大。这种方法有点类似于发放奖品使用的轮盘，并带有某种赌博的意思，因此亦被称为轮盘赌选择。
5.3.2 基本遗传操作——交叉
交叉操作
交叉（Crossover）操作是指按照某种方式对选择的父代个体的染色体的部分基因进行交配重组，从而形成新的个体。交配重组是自然界中生物遗传进化的一个主要环节，也是遗传算法中产生新的个体的最主要方法。根据个体编码方法的不同，遗传算法中的交叉操作可分为二进制交叉和实值交叉两种类型。
二进制交叉
二进制交叉（Binary Valued Crossover）是指二进制编码情况下所采用的交叉操作，它主要包括单点交叉、两点交叉、多点交叉和均匀交叉等方法。
单点交叉
单点交叉也称简单交叉，它是先在两个父代个体的编码串中随机设定一个交叉点，然后对这两个父代个体交叉点前面或后面部分的基因进行交换，并生成子代中的两个新的个体。假设两个父代的个体串分别是：
X=x1 x2 … xk xk+1 … xn
Y=y1 y2 … yk yk+1 … yn
随机选择第k位为交叉点，若采用对交叉点后面的基因进行交换的方法，但点交叉是将X中的xk+1到xn部分与Y中的yk+1到yn部分进行交叉，交叉后生成的两个新的个体是：
X’= x1 x2 … xk yk+1 … yn
Y’= y1 y2 … yk xk+1 … xn
例 设有两个父代的个体串A=0 0 1 1 0 1 和B=1 1 0 0 1 0 ，若随机交叉点为4，则交叉后生成的两个新的个体是：
A’= 0 0 1 1 1 0
B’= 1 1 0 0 0 1
两点交叉
两点交叉是指先在两个父代个体的编码串中随机设定两个交叉点，然后再按这两个交叉点进行部分基因交换，生成子代中的两个新的个体。
假设两个父代的个体串分别是：
X=x1 x2 … xi … xj … xn
Y=y1 y2 … yi … yj …，yn
随机设定第i、j位为两个交叉点（其中i<j<n），两点交叉是将X中的xi+1到xj部分与Y中的yi+1到yj部分进行交换，交叉后生成的两个新的个体是：
X’= x1 x2 … xi yi+1 … yj xj+1 … xn
Y’= y1 y2 … yi xi+1 … xj yj+1 … yn
例 设有两个父代的个体串A= 0 0 1 1 0 1 和B= 1 1 0 0 1 0 ，若随机交叉点为3和5，则交叉后的两个新的个体是：
A’= 0 0 1 0 1 1
B’= 1 1 0 1 0 0
多点交叉
多点交是指先随机生成多个交叉点，然后再按这些交叉点分段地进行部分基因交换，生成子代中的两个新的个体。
假设交叉点个数为m，则可将个体串划分为m+1个分段，其划分方法是：
当m为偶数时，对全部交叉点依次进行两两配对，构成m/2个交叉段。
当m为奇数时，对前(m-1)个交叉点依次进行两两配对，构成(m-1)/2个交叉段，而第m个交叉点则按单点交叉方法构成一个交叉段。
下面以m=3为例进行讨论。假设两个父代的个体串分别是X=x1 x2 … xi … xj … xk … xn和Y=y1 y2 … yi … yj … yk … yn，随机设定第i、j、k位为三个交叉点（其中i<j<k<n），则将构成两个交叉段。交叉后生成的两个新的个体是：
X’= x1 x2 … xi yi+1 … yj xj+1 … xk yk+1 … yn
Y’= y1 y2 … yi xi+1 … xj yj+1 … yk xk+1 … xn
例 设有两个父代的个体串A= 0 0 1 1 0 1 和B= 1 1 0 0 1 0 ，若随机交叉点为1、3和5，则交叉后的两个新的个体是：
A’= 0 1 0 1 0 0
B’= 1 0 1 0 1 1
均匀交叉
均匀交叉（Uniform Crossover）是先随机生成一个与父串具有相同长度，并被称为交叉模版（或交叉掩码）的二进制串，然后再利用该模版对两个父串进行交叉，即将模版中1对应的位进行交换，而0对应的位不交换，依此生成子代中的两个新的个体。事实上，这种方法对父串中的每一位都是以相同的概率随机进行交叉的。
例 设有两个父代的个体串:
A=0 0 1 1 0 1和B=1 1 0 0 1 0， 若随机生成的模版T=0 1 0 0 1 1，则交叉后的两个新的个体是A’=0 1 1 0 1 0和B’=1 0 0 1 0 1。即
A： 0 0 1 1 0 1
B： 1 1 0 0 1 0
T： 0 1 0 0 1 1
A’：0 1 1 1 1 0
B’：1 0 0 0 0 1
实值交叉
实值交叉是在实数编码情况下所采用的交叉操作，主要包括离散交叉和算术交叉，下面主要讨论离散交叉（部分离散交叉和整体离散交叉） 。
部分离散交叉是先在两个父代个体的编码向量中随机选择一部分分量，然后对这部分分量进行交换，生成子代中的两个新的个体。
整体交叉则是对两个父代个体的编码向量中的所有分量，都以1/2的概率进行交换，从而生成子代中的两个新的个体。
以部分离散交叉为例，假设两个父代个体的n维实向量分别是 X=x1x2… xi…xk…xn和Y=y1y2…yi…yk…yn，若随机选择对第k个分量以后的所有分量进行交换，则生成的两个新的个体向量是：
X’= x1 x2 … xk yk+1 … yn
Y’= y1 y2 … yk xk+1 … xn
例 设有两个父代个体向量A=20 16 19 32 18 26和B=36 25 38 12 21 30，若随机选择对第3个分量以后的所有分量进行交叉，则交叉后两个新的个体向量是：
A’= 20 16 19 12 21 30
B’= 36 25 38 32 18 26
5.3.2 基本遗传操作——变异
变异操作
变异（Mutation）是指对选中个体的染色体中的某些基因进行变动，以形成新的个体。变异也是生物遗传和自然进化中的一种基本现象，它可增强种群的多样性。遗传算法中的变异操作增加了算法的局部随机搜索能力，从而可以维持种群的多样性。根据个体编码方式的不同，变异操作可分为二进制变异和实值变异两种类型。
二进制变异
当个体的染色体采用二进制编码表示时，其变异操作应采用二进制变异方法。该变异方法是先随机地产生一个变异位，然后将该变异位置上的基因值由“0”变为“1”，或由“1”变为“0”，产生一个新的个体。
例 设变异前的个体为A=0 0 1 1 0 1，若随机产生的变异位置是2，则该个体的第2位由“0”变为“1”。
变异后的新的个体是A’= 0 1 1 1 0 1 。
实值变异
当个体的染色体采用实数编码表示时，其变异操作应采用实值变异方法。该方法是用另外一个在规定范围内的随机实数去替换原变异位置上的基因值，产生一个新的个体。最常用的实值变异操作有:
基于位置的变异方法
该方法是先随机地产生两个变异位置，然后将第二个变异位置上的基因移动到第一个变异位置的前面。
例 设选中的个体向量C=20 16 19 12 21 30，若随机产生的两个变异位置分别时2和4，则变异后的新的个体向量是：
C’= 20 12 16 19 21 30
基于次序的变异
该方法是先随机地产生两个变异位置，然后交换这两个变异位置上的基因。
例 设选中的个体向量D=20 12 16 19 21 30，若随机产生的两个变异位置分别时2和4，则变异后的新的个体向量是：
D’= 20 19 16 12 21 30
5.3.2 遗传算法应用简例
用遗传算法求函数 的最大值，其中 为[0，31]间的整数。
解 这个问题本身比较简单，其最大值很显然是在 =31处。但作为一个例子，它有着较好的示范性和可理解性。
按照遗传算法，其求解过程如下：
(1) 编码
由于 的定义域是区间[0，31]上的整数，由5位二进制数即可全部表示。因此，可采用二进制编码方法，其编码串的长度为5。
例如，用二进制串00000来表示 =0，11111来表示 =31等。其中的0和1为基因值。
(2) 生成初始种群
若假设给定的种群规模 =4，则可用4个随机生成的长度为5的二进制串作为初始种群。再假设随机生成的初始种群（即第0代种群）为：
S01=0 1 1 0 1 S02=1 1 0 0 1
S03=0 1 0 0 0 S04=1 0 0 1 0
(3) 计算适应度
要计算个体的适应度，首先应该定义适应度函数。由于本例是求 的最大值，因此可直接用 来作为适应度函数。即：
其中的二进制串S对应着变量 的值。根据此函数，初始种群中各个个体的适应值及其所占比例如表5-5所示。
表1 初始种群情况表
可以看出，在4个个体中S03的适应值最大，是当前最佳个体。
(4) 选择操作
假设采用轮盘赌方式选择个体，且依次生成的4个随机数（相当于轮盘上指针所指的数）为0.85、0.32、0.12和0.46，经选择后得到的新的种群为：
S01=1 0 0 1 0
S02=1 1 0 0 1
S03=0 1 1 0 1
S04=1 1 0 0 1
其中，染色体1 1 0 0 1在种群中出现了2次，而原染色体0 1 0 0 0则因适应值太小而被淘汰。
(5) 交叉
假设交叉概率Pi为50%，则种群中只有1/2的染色体参与交叉。若规定种群中的染色体按顺序两两配对交叉，且有S01与S02交叉，S03与S04不交叉，则交叉情况如表5-6所示。
表2 初始种群的交叉情况表
可见，经交叉后得到的新的种群为：
S01=1 0 0 0 1
S02=1 1 0 1 0
S03=0 1 1 0 1
S04=1 1 0 0 1
(6) 变异
变异概率Pm一般都很小，假设本次循环中没有发生变异，则变异前的种群即为进化后所得到的第1代种群。即：
S11=1 0 0 0 1
S12=1 1 0 1 0
S13=0 1 1 0 1
S14=1 1 0 0 1
然后，对第1代种群重复上述(4)-(6)的操作。
对第1代种群，同样重复上述(4)-(6)的操作。其选择情况如表5-7所示。
表3 第1代种群的选择情况表
其中若假设按轮盘赌选择时依次生成的4个随机数为0.14、0.51、0.24和0.82，经选择后得到的新的种群为：
S11=1 0 0 0 1
S12=1 1 0 1 0
S13=1 1 0 1 0
S14=1 1 0 0 1
可以看出，染色体1 1 0 1 0被选择了2次，而原染色体0 1 1 0 1则因适应值太小而被淘汰。
对第1代种群，其交叉情况如表5-8所示。
表5-8 第1代种群的交叉情况表
可见，经杂交后得到的新的种群为：
S11=1 0 0 1 0
S12=1 1 0 0 1
S13=1 1 0 0 1
S14=1 1 0 1 0
可以看出，第3位基因均为0，已经不可能通过交配达到最优解。这种过早陷入局部最优解的现象称为早熟。为解决这一问题，需要采用变异操作。
对第1代种群，其变异情况如表5-9所示。
表5-9 第1代种群的变异情况表
它是通过对S14的第3位的变异来实现的。变异后所得到的第2代种群为：
S21=1 0 0 1 0
S22=1 1 0 0 1
S23=1 1 0 0 1
S24=1 1 1 1 0
对第2代种群，同样重复上述(4)-(6)的操作。其选择情况如表5-10所示。
表5-10 第2代种群的选择情况表
其中若假设按轮盘赌选择时依次生成的4个随机数为0.42、0.15、0.59和0.91，经选择后得到的新的种群为：
S21=1 1 0 0 1
S22=1 0 0 1 0
S23=1 1 0 0 1
S24=1 1 1 1 0
对第2代种群，其交叉情况如表5-11所示。
这时，函数的最大值已经出现，其对应的染色体为 1 1 1 1 1， 经解码后可知问题的最优解是在点 =31处。
求解过程结束。
谢谢
展开
