遗传算法及其在生物反应.ppt

《遗传算法及其在生物反应.ppt》由会员分享，可在线阅读，更多相关《遗传算法及其在生物反应.ppt（73页珍藏版）》请在三一办公上搜索。

1、8.遗传算法及其在生物反应过程研究中的应用,8.1 引言8.2 GA的运行过程与特点8.3 GA的基本理论8.4 GA的应用,8.1 引言,遗传算法（Genetic Algorithms，基因算法，简称GA）的产生和发展是生物学、遗传学、系统科学、计算机科学与技术等科技革命的结果。对GA的研究与应用已引起国际上诸多领域的专家和学者的普遍关注，并且在许多领域取得了良好的效果。GA是一种建立在Darwin生物进化论和Mendel群体遗传学基础上的一种算法。自然界中生物体的结构体现了生物对其环境的生存与繁殖能力。自然界总是延续适应性强的物种，淘汰不适应的物种。“适应性”驱使遗传操作，异性结合和变异创

2、造出新的和适应性更强的生物结构。,60年代，美国Michigan大学Holland教授等人认为：只要适当地结合计算机技术，就能产生一种类似自然界以进化方式解决各类问题的技术。把实际问题用二进制数字（0.1）代码串表示，然后把这种二进制代码串视为“染色体”并对其进行变换。用该方法无需知道所要解决问题的类型，所需的唯一信息是它们在搜索过程中所产生的针对每个染色体的评价值，根据这些评价值对染色体进行迭代处理，从中发现并保存好的染色体，从而得到问题的最优解。1975年Holland教授发表了标志GA诞生的代表作，但没有受到足够的重视。80年代后，随着计算机技术的进步和人工神经网络、人工生命及机器学习理

3、论的发展，GA在理论和应用方面都得到了较大的发展。,Bagley、Hollstien、De Jong等人对遗传算法中所涉及到的有关数学方面的问题以及遗传算法在纯数学方面的应用进行了研究。Goldberg成功地将遗传算法应用于管道系统的优化和机器学习问题，他所著的Genetic Algorithms in Search，Optimization and Machine Learning一书全面阐述了GA的发展历程、现状、各种算法和应用实例，有力地促进了GA在工程技术中的广泛应用。自从1985年召开了首届遗传算法国际会议（ICGA：International Conference on Genet

4、ic Algorithms）以来，ICGA以每两年一度的频率汇集了一大批对遗传算法理论与实践感兴趣的人。据统计1983年全世界发表的有关遗传算法的文献为19篇，到1993年已达600篇。,1991年由Davis编著国际上出版了第一本遗传算法手册。由De Jong主编，MIT出版社出版，1993年创刊的杂志Evolutionary Computation为遗传算法理论发表提供了论坛。在全球信息网上也专门开辟了GA的讨论组(GAListRequestAIC.NRL.NAVY.MLL有关网址有：ttp:www.aic.nrl.navy.mil/galist)，每星期发布一次国际上有关GA的学术活动及

5、信息交流等方面的信息。GA的初期应用研究主要围绕组合优化问题求解，近些年来它已迅速地扩展到机器学习、设计规划、系统控制、模式识别、人工生命等众多科学技术领域。,8.2 GA的运行过程与特点,8.2.1 GA的运行过程以函数优化为例，假设其目标函数为：Ff（x,y,z）（x,y,z），FR(8.1)为了不失一般性，假设要求(xo,yo,zo)使得F有最大值，即：,其中：（x,y,z）为自变量，其定义域为;F为实数，是解的优劣程度或适应性的一种度量；f为解空间（x,y,z）到实数域FR的一种映射。GA把该问题中的自变量（x,y,z）当作生物体，将其转化为由基因组成的染色体，相应的函数值F定义为适应

6、度，未知函数为环境，生物体进化的目标是成为具有最佳适应性的基因型。,图8.1 遗传算法的一般运行过程,(1)基因编码：将求解问题中每一个变量看作一个基因，根据各个变量的类型和取值范围，选择合适位数的码分别对其进行编码，简称基因码，如xa1,a2,a3。编码策略有二进制编码和实数编码等，若采用二进制码表达实数，每个二进制位即为一个基因，如果一维参数xa,b，则(8.3)其中，l是串的长度，gi为第i个基因。,(2)建立个体：将各个变量的基因码按一定顺序排列和连接，组合成个体。特定取值的各个变量组成的一个编码串，称为个体的一个基因型。例如，求解问题中包含有两个变量，其基因码分别为：xa1,a2,a

7、3和yb1,b2，如果按x到y的顺序连接，则一个个体为：Ax,ya1,a2,a3,b1,b2。(3)建立种群：生物在自然界是以种群的形式生存的。在t时刻，随机产生n个个体组成一个群体：P(t)A1,A2,.,An，该群体代表优化问题的一些可能解的集合。作为进化起点的初始种群P(0)可以用随机方式或其它方式产生。,(4)评价：根据求解问题的函数关系和编码规则，将群体P(t)中的每一个体的基因码所对应的自变量取值(xi,yi,zi)代入式(8.2)，算出其函数值Fi，i1,2.n。Fi 越大，表示该个体有较高的适应性，更适应于f的定义的生存环境。适应度Fi 为群体进化时的选择提供了依据。(5)繁殖

8、（或复制）：按一定的繁殖概率Ps 从群体P(t)中选取M对个体，作为双亲用于繁殖后代，产生新的个体加入下一代群体P(t+1)中。Ps 的大小取决于每个个体的适应度函数Fi。适应度越高，则复制概率越大。也就是说，适应于生存环境的优良个体将有更多的繁殖后代的机会，从而使优良特性得以遗传。繁殖是遗传算法的关键，它体现了自然界中适者生存的思想。,(6)杂交（或交叉）：对于选中的用于繁殖的每一对个体，按某一概率Pc从某一位置相互交叉，如个体A1 和A2交叉产生新一代的个体B1和B2，它们组合了父辈个体A1 和A2 的特征，即 A1=1010101001 B1=1011110010 A2=01111100

9、10 B2=0110101001 其作用是集父代之优，产生新的一代，以实现高效搜索。可见，杂交体现了自然界中信息交换的思想。,(7)突变（或变异）：以一定概率Pm从群体P(t1）中随机选取若干个体，对于选中的个体，随机选取某些基因进行变异运算，如1变成0或0变成1，以保证群体中基因的多样性，避免过早收敛，陷入局部解。与自然界一样，每一个基因发生变异的概率是很小的。变异模拟了生物进化过程中的偶然基因突变现象。P(t1)种群的繁殖、杂交、突变完成后，即以P(t1)种群取代P(t)种群完成一代繁殖。GA的搜索能力主要是由繁殖和杂交赋予的，突变算子则保证了算法能搜索到问题解空间的每一点，从而使算法具有

10、全局最优，它进一步增强了GA的搜索能力。,(8)检测：对P(t1)种群进行评价，检测进化速度和收敛性，判断进化是否成熟，如果不成熟，则继续进行逐代繁殖和进化，使种群中个体的品质不断得到优化。如成熟，则结束求解过程，这时所获得的种群及其中的个体就是求解问题的优化解。以上所述是GA的最基本操作。Goldberg称之为简单遗传算法（Simple GA，简称SGA）。在运用SGA的过程中，各国学者在SGA的基础上提出了许多改进方法及应注意的一些问题：1)控制参数的选择及编码；2)遗传算子的改进及后代的产生；3)种群评价和最优个体的选择；4)中止条件的选择及收敛性。,1）控制参数的选择及编码控制参数：编

11、码串长、种群数、繁殖、杂交及突变概率等。GA对种群数的设定和维持十分敏感，从维持群体中个体的多样性及防止陷入局部解的角度考虑，种群数越多越好。但是，这除了会明显增加计算量外还可能影响个体间的竞争。遗传操作概率的选择和设定目前尚无统一的理论指导，多数视具体问题而定。Grefenstett利用原级GA来优化选取GA控制参数，但其存在的问题是须保证一定的种群规模和遗传代数，多次（一般至少在1000次以上）调用待优化的GA程序。丁承民等提出了利用正交试验法来优化GA控制参数的选取。,GA的作用对象是优化变量的染色体编码。编码一般遵循De Jong提出的两条编码规则：(1)有意义建筑块（building

12、 block）编码规则：要求所采用的编码方式应当易于生成建筑块，这里的建筑块指的是具有低阶、短定义长度及高适应度的模式；(2)最小字符集编码规则：所使用的编码应采用最少数量的符号来实现对问题的表述。,一般而言，符号越少的编码方法所提供的模式数越多，越有利于算法的寻优。例，一个L位的二进制码串可代表2L 个整数，而一个l位的K进制码串则代表Kl 个整数。由于两种编码所对应的解数目相同，所以2LKl。因为K2，所以Ll，又因为二进制和K进制编码的模式数分别为(21)L 和(K1)l，而(8.4)(8.5)2L Kl，(112)(11K)，Ll(8.6)(8.7)可见，二进制编码能产生更多的模式数。

13、,采用编码方式（特别是二进制编码）有以下优点：(1)可很好地指导搜索，使得有某种结构的个体容易生存，以产生适应性更强的后代；(2)使算法具有隐含并行性，使在相对少量的种群上进行的操作实质上隐含着大范围搜索。为了克服普通二进制编码所带来的GA早熟问题，Schraudolph等提出了动态变量编码：当由某种方法得知种群已经收敛，则缩小变量定义域一个范围，从而使得在全局最优点附近可以进行更精确的搜索。对于单一实变量如XUmin,Umax进行编码，设二进制长度为L，则存在从0,2L-1到Umin,Umax 的映射。编码精度为Umin-Umax（2L-1）。对于多参数优化问题，一般先对每个参数进行二进制编

14、码得到子串，再把这些子串连成一个染色体。每一个子串可以有不同的长度、Umin和Umax。,2）遗传算子的改进及后代的产生 遗传算子的改进 多点杂交：SGA对于染色体只采用单点杂交，采用多点杂交有利于对一个承载多个变量问题的染色体提高遗传搜索效率。但应注意的问题是多点杂交可能导致过多破坏GA的基本遗传模式，使得收敛速度反而下降，常用的多点杂交有两点杂交和均匀杂交。两点杂交就是在染色体中随机选取两点，然后交换两点中的一段基因链。均匀杂交是从父母染色体中以一定概率（0.5）随机选取等位基因而构成两个子代染色体。目前可以肯定的是这两种杂交都优于单点杂交。但均匀杂交与两点杂交孰优孰劣尚无定论。,自适应选

15、择杂交和突变概率（Adaptive GA简称AGA）：Srinvivas等人提出一种使杂交概率Pc和突变概率Pm随适应度自动改变的改进方法。当种群各个体适应度趋于一致或趋于局部最优时，使Pc和Pm增加，反之亦然。其中Pc、Pm的表达式如下：(8.8)(8.9)0k1,k2,k3,k4 1(8.10)max为当前种群最大适应度，f为待杂交父母个体中较大的适应度，为某个体适应度。经测试，该方法效果显著。,杂交位置的非等概率选取一般而言，对染色体各位置进行等概率杂交会导致优化变量在等优化空间中产生不等概率的变化量，因此为了使得杂交子代个体对应的优化变量在寻优空间中均匀分布，章柯和刘贵忠提出杂交位置非

16、等概率选取的交叉操作方法。在产生后代的过程中选用不同方法 稳态GA（Steady State GA,简称SSGA）SGA在换代时总是由子代个体全部代替父代个体，而子代个体适应度不可能总是超过父代，这样父代中有较高适应度的个体无法保留下来，从而进化时会产生振荡。SSGA 是通过父代和子代适应度排序，固定种群大小，保留适应度最高的部分个体组成新的子代，从而使整个种群表现出稳态进化的趋势。,最优保存SGA（Optimum Maintaining SGA简称OMSGA）：与SSGA相类似的OMSGA，它是Grefenstette提出的最优个体保存策略（Elitist strategy）。它的基本思想是

17、把所发现的父代最优解保存下来。为了保持种群规模不变，父代最优个体将取代子代中的最差个体，这样以前的最优解不至于丧失。逼近因子模型（Crowding Factor Model）：这是由De Jong提出的，他规定当一个新个体产生时，必须有一个老个体死亡。这个老个体是从整个随机产生的含有逼近因子（CF）个体的子集中产生。它是这个子集中与新个体逐位相比最相似的个体。这种相似性常用Hamming距离表示。一般取CF2或3，这种CF模型有利于种群避免早熟，对多极值函数优化和机器学习很有用。,3）种群评价和最优个体的选择 在运用SGA处理群体时，对于某些不利于优化的现象，有必要调整个体间的竞争水平，以期得

18、到最好的运算结果。在运行GA的初期，个体差异较大，在大部分适应度较差的个体中，可能遇到少数特别好的个体。当采用经典的比例选择规则时，即“适应度大的多复制，适应度小的被淘汰，适应度中等的保持不变”的原则，容易使个别好的个体的后代充斥整个种群，导致运算过早收敛（即早熟）。而在SGA运行的后期，虽然存在着个体的多样性，但群体的平均适应度接近最佳适应度，优秀的个体在产生后代时，优势不明显从而使整个种群进化停滞不前，因此适当地调整适应度是必要的。,模拟退火规则：Stoffa借鉴模拟退火思想提出了如下式所示的计算适应度的公式：(8.11)TTo（0.99g-1）(8.12)式中fi是第i个个体适应度，M为

19、种群个体总数，g为遗传代数序号，T为温度，To为初始温度。这样在高温时（即GA前期），适应度相近的个体产生后代的概率相近，而当温度不断下降后，适应度相近的个体适应度差异放大，从而使优秀的个体优势更明显。,线性变换规则设f为原适应度，f为变换后适应度，则线性变换的关系式为：(8.13)式中a、b为系数。式(8.13)必须满足以下两个条件：（8.14)（8.15)式(8.14)表示变换后的平均适应度须等于原平均适应度，以保证每一个具有平均适应度个体，在下一代中得以等量复制；式(8.15)表示变换后的最大适应度等于原平均适应度的c倍，c为群体中最佳个体预期得到的复制数。一般对于不太大的群体（5010

20、0），c1.22.0，它控制着原适应度最大的个体的复制数目。,根据式（8.1315）可写出：(8.16)(8.17)解得：(8.18)(8.19),图8.2 适应度缩小的线性转换,图8.3 适应度放大的线性转换,由图8.2和8.3可见，经线性转换后，在GA运行初期，优秀个体的适应度被缩小；而在GA运行的后期优秀个体的适应度被放大。但是当一些个体的适应度远小于fav和fmax，而fav和fmax又比较接近时，用线性转换法把fav和fmax拉开会导致原适应度低的转换后为负值。为了保证适应度非负，需由下式求解a和b，即由：(8.20)得：(8.21),4）中止条件的选择及收敛性目标函数：许多实际问题

21、中，所期望的是非负。因此，需要把目标函数转换成求最大值问题且函数值非负的适应度函数。对于GA，把目标函数乘以-1的做法不能保证适应度非负，一般采用下式进行转换：(8.22)式中Cmax可以是进化过程中所得到的最大值，也可以是当前密码串集中的最大值，或者是一个输入常数；g(X)为进化过程中某串的适应度。中止条件：1）固定遗传代数；2）前后几代个体平均适应度的差或方差小于某个极小阈值。,GA全局收敛性Rudolph用齐次有限马尔科夫链证明了SGA收敛不到全局最优解；Eiben等人用马尔科夫链证明了OMSGA（Optimum Maintaining SGA）的概率性全局收敛；Fogel通过马尔科夫链

22、证明无论如何初始化、选取何种遗传算子和目标函数，SGA都不可能收敛到解空间中的某一点，只要采用SSGA(Steady State GA)或OMSGA便可达到全局收敛；恽为民等人应用齐次有限马尔科夫链也证明了SGA不是全局收敛，指出OMSGA是全局收敛的。,传统的优化算法大致可分为以下几类：解析法、数值计算法、枚举法、随机搜索法。(1)解析法：根据目标函数与约束函数的变化规律，藉助于数学分析求出一组含有导数的方程或不等式最优解的必要条件，最后利用充分条件或其它方法从中确定最优解。要求有明确且连续可微的目标函数，这对于现实的优化领域中大量的不连续体系不适用。即使导数存在，当问题中诸函数为复杂的非线

23、性函数时，求解导数为零的方程组十分困难。对于多峰函数，根据梯度信息求取优化解的的解析法很可能陷入局部最优解。,8.2.2 遗传算法的特点,(2)数值计算法：从某个事先给定的初始估计值出发，按照某种规则，以适当的步长沿着目标函数所改进的方向前进，逐步向目标函数的最优化点逼近，直至满足所需精度为止。它不需要优化问题的解析表达式，只需要计算函数值，或者实验过程中逐步产生的函数值。但当变量数较大时，因解空间大，该法计算量大，以致难以收敛或无法胜任。(3)穷举法：在一个连续的离散搜索空间内，计算每一个点的目标函数，再加以比较。该方法简单易行，但效率太低，许多实际问题所对应的搜索空间都很大，难以逐一比较。

24、(4)随机搜索法：比数值计算法和穷举法有所改进，但盲目性大，效率仍然不高。只有在搜索空间形成紧密分布时，才可能具有高的搜索效率。,GA具有如下几个方面的优越性：1.全局最优性。GA是从一群初始解点开始搜索，所用的初始点是在解空间中随机选取。它不是从单一的初始点开始，然后进行点对点（由当前解点移到另一个解点）搜索，而是同时对搜索空间中多个点进行搜索。此外，GA采用的是概率转换规则，而不是确定性转换规则，这种不确定的随机转换规则使其朝着搜索空间更优化的区域移动，从而大大提高了搜索效率及找到全局最优解的可能性。2.并行性。GA的群体、随机搜索特征使得GA具有并行搜索的能力，非常适合于大规模并行分布处

25、理系统。,3.很强的鲁棒性。GA在搜索过程中只使用适应度函数值作为搜索的依据，不需要梯度信息及其它辅助信息。它摆脱了对数学模型的依赖，不受函数连续可微与否的约束，因而，它能够解决任何形式的非线性问题。4.可扩展性。GA易于和别的技术如神经网络、模糊推理、混沌行为和人工生命等相结合，形成性能更优的问题求解方法。5.GA使用简单，适应性强。易于被写成一个通用的算法去求解许多不同的优化问题。,8.3 GA的基本理论,8.3.1 模式（schema）理论J.H.Holland等人提出。模式：编码空间（即所使用染色体的全体）中具有相同构型（configuration）编码的子集。相同构型：该子集中各编码

26、（串）在某些特征位具有相同的码值。例如，用L位二进制串编码的模式形式如下：(a1,a2,ai,al),ai 0,1,*(8.23)其中“*”表示0或1。给定一个模式，如果在模式的特征位上，一个编码的值与模式的值相同，则该编码称为与该模式相匹配。因此，模式中“*”越多，则与该模式相匹配的编码越多。例如一个长度为4的模式是*1*1，与其相匹配的编码有四个，即（1111），（1101），（0111），（0101）(8.24),一个模式H包含四个参数：模式长度L即为编码串长度 模式阶O(H)是模式中位置确定的个数 定义长度(H)是第一个确定位置与最后一个确定位置之间的距离。例如，O（*1*1）2,（*

27、1*1）422模式的维数D(H)表示模式中包含编码串的个数：D(H)2L-O（H）(8.25),1.繁殖操作对模式的影响假设第t代遗传时，群体P(t)中模式H有m个样本，记作m(H,t)，在繁殖过程中，一个编码串能否被繁殖取决于其对环境的适应度，适应度大者被繁殖的概率就大。假设含H的串的适应度为F(H)，则含H的串按PrF(H)F的概率繁殖，每个样本繁殖的数目为nPr。如果 为所有含H的串的平均适应度，则第t1代含模式H的模式数为：(8.26)或(8.27)其中 为群体的平均适应度。,由此可见，如果平均适应度 超过群体平均适应度 的模式H，其群体数在下一代中增加，否则，则减少。假设模式H的平均

28、适应度比群体平均适应度多C，C为常数，则(8.28)如果从t0开始，可得(8.29)由上式可知，繁殖操作的作用是使平均适应度高于（或低于）群体平均适应度的模式按指数形式增加（或减少）。,2.杂交操作对模式的影响 如果交叉点落在模式的定义长度范围之外，该模式不因杂交操作而被破坏。反之，如果交叉点落在模式的定义长度之内，杂交之后，该模式将被破坏。则当编码串长为L时，随机产生的交叉点有L-1位。交叉点落在模式定义长度(H)范围内的概率，即为该模式遭破坏的概率Pd(H)(L-1)。由于杂交本身也是以一定的概率Pc发生的，所以模式H因杂交操作而破坏的概率为：(8.30)由于在模式H及其配对的串中有一相同

29、的确定位时，既使交叉点落在定义长度内，模式H仍将被保留，因此，式(8.30)给出的破坏概率为上界，即(8.31),3.突变操作对模式的影响 令随机改变编码串中某一位的突变概率为Pm，所以确定位置个数为O(H)的模式被破坏的概率为：PdO(H)Pm(8.32)综合上述三种操作，模式定理可表示如下：(8.33)它表明：在GA的繁殖、杂交和突变的作用下，定义长度(H)短、模式阶O(H)低及适应度F(H)高于平均适应度的 模式，其样本数在遗传过程中将以指数形式增加。,8.3.2 遗传算法的隐含并行性,遗传算法的隐含并行性研究的是能被有效处理的模式数的下限，即样本数以指数级增长的模式数的最低限。对于一个

30、具有n个L位码串的串集，假定只考虑那些生存概率大于Ps的模式，即在单点交叉和低概率变异情况下，那些定义长度(H)(L-1)的模式。,以(H)=5串长L=10（模式为1 0 1 1 1 0 0 0 1 0）为例，首先可考虑其前五位（下划线）的模式数，即1 0 1 1 1 0 0 0 1 0由于下划线中最后一位是固定的，这意味着它具有如下形式的模式%1*其中“*”为无关符，“%”既可以是确定值(0或1),也可以是“*”。显然其模式数为ms=2(H)-1=25-1=24=16个。同样，每次把下划线向右移动一个位置，即1 0 1 1 1 0 0 0 1 0共可以移动L-(H)-1次，定义长度小于(H)

31、的模式数为。则，一个具有n个位码串的串集，其模式总数为2(H)-1n（L-(H)+1）。,由于在一个规模较大的群体中肯定会有完全相同的低阶模式，为了进一步修正，我们选择规模为n=2(H)/2的群体，由于模式数是按二项式分布的，因而模式阶高于和低于(H)/2的模式各占一半。如果只考虑那些阶高于(H)/2的模式，则模式数的下界为：（8.34）由于n=2(H)/2，则有（8.35）其中c为常数。由此可见，遗传算法有效处理的模式个数与群体规模n的立方成比例。结论：尽管GA只对n个串体进行运算，而且具有高阶长定义长度的模式在交叉和变异算子作用下遭到破坏，GA仍隐含地处理了大量的模式O（n3），这一性质即

32、为隐并行性，这表明GA具有比传统的优化方法更强的处理能力。,8.4 GA的应用,应用遗传算法于生物反应过程研究主要在三个方面：发酵动力学模型参数估算、发酵培养基优化和发酵工艺条件优化。8.4.1 发酵动力学模型参数估算Park等人于1997年应用GA于生物过程参数估算，其结果与梯度法或非线性回归相比，用GA能够产生一组更合适的动力学参数。我们应用GA于常见发酵动力学模型的参数估算，与POWELL法相比，拟合精度更高。,1.数学模型与目标函数基于常见的分批发酵动力学模型，我们可以得到如下所示的解析解：(8.36)(8.37)(8.38)为了由分批发酵过程中所测得的S（t）、P（t)和X（t）数据

33、来确定max、Ks、YG、YP 和m这七个动力学参数，我们确定的目标函数g（x）如下所示：min g(x)=(yij)2(8.39)其中，yij 表示X、P、t在不同S浓度下的实验值与计算值的离差平方和。,2.应用GA估算参数（1）编码根据已有的知识和经验确定7个估算参数的寻优范围：YG0.01,1、YP0.01,1、ma0.001,1、Ks2,200、m 0.001,10、0.1,100、0.01,1。采用二进对每个参数进行编码，得到子串。设每个子串长度均为11，则每个个体长度L为117=77。每个参数实数值x（x Umin，Umax）与其二进制解码整数值x（x 0，2-1）的对应关系为：x

34、=Umin+x(8.40),（2）初始化种群：种群规模应保持适当，若过小，则所含的信息太少，不能发挥GA 的效力；若过大，计算量随之增加，延长收敛时间。针对本问题，我们随机产生40个个体，该群体代表优化问题的一些可能解的集合。（3）适值计算：由于本问题是目标函数的最小化问题，故我们设适合度函数为：,其中，Cmax为进化过程中的临界目标函数值。取Cmax=10000，则f(x)的变化范围在010000之间。,（4）繁殖：采用转轮法，即适合度越高的个体，从父代中被选中的概率越大。采用期望值判断方法，即设每个个体在下一代生存的期望数M为：(8.43)若C0.5，M-C0且符合转轮法选择判断，则该个体

35、被选中，否则被淘汰。这样可避免适合度很低的个体被选中，进一步增加高适合度个体被选中的机会，加快了进化过程。显然，C的取值不能太大，否则容易陷入局部极值。（5）杂交：采用单点交叉，杂交概率Pc=0.60。（6）突变：单点突变，概率Pm=0.05。（7）收敛判断：以前后两代的串集适合度平均值之比趋于1为准。,3.估算结果和讨论以Lorynebacterium glutanlicum分批发酵生产赖氨酸的数据(Nakangama 1972）为例。当gen=0时，初始串集的适合度平均值favg=667.8，当gen=37时，favg上升到9758.2，前后两代的串集适合度平均值之比为1.007。,表8.

36、3 利用GA 和Powell算法得到的参数估算值,从以上结果可见GA 可用于分批发酵动力学模型参数估算，而且与Powe11算法相比较得到了更好的结果，基于GA的数学模型的计算值与实验值的吻合度也有所提高。尽管每一次的运算，只有40个个体，但GA的隐并行性处理方式，使得每一次的运算隐含地处理了大量的模式（403）。我们无法证明本问题收敛的全局最优解，但通过对不同组初始串集多次实验，各动力学参数收敛趋势与上述结果基本一致，可以认为所得到的最好结果接近全局最优解的可能性很大。,8.4.2 发酵培养基优化,由于培养基组成复杂，至今培养基的筛选还是停留在简单的实验设计水平上。一般的过程是先大致确定培养基

37、的组分，将每种组分划分成几个水平，然后进行多因素多水平的正交、均匀设计或响应面法实验，经正交分析或逐步回归后确定培养基配方。缺点：实验点距大、精度不够。倘若组分多，则实验次数呈几何级数增长，为此不是增加实验量就是降低所选组分数，使实验在一个不完整的基础上进行。Freyer等人于1992年首次将GA用于培养基优化；Weuster-Botz等人应用GA优化了由14种组分组成的培养基，甲酸脱氢酶生产能力和活性分别提高50%和100%；Zuzek等人用GA优化由10组分组成的曲霉发酵培养基配方，经过4代的发酵实验，产物产量提高了近3倍；我们也就木糖醇发酵培养基配方优化的遗传算法进行探讨，并且提出了利用

38、遗传算法优化培养基配方的结果建立神经网络模型，结合遗传算法进行仿真优化，取得更好的结果后再进行优化实验的新方法。,1.木糖醇发酵培养基配方以优化前的培养基各成份含量作为各参数的上限，各参数所确定的取值范围如表8.4所示（CaCl2因含量较少及影响不大固定为0.1g/l）：,为了提高寻优概率、保证一定的精度及便于实验操作,把每个组分划分为50等分，即成为6因素50水平的培养基优化问题。,2应用遗传算法于培养基优化（1）编码：采用多参数二进制编码，每个参数的子串长度为6(26=6450)。6个参数组合成长度为36的染色体。（2）选择：随机产生初始种群10个，即10种实验方案。每种实验方案平行做两次

39、，测得的木糖醇含量平均值作为适应度函数值。引入适应度函数线性转换，用转轮选择法从种群中挑选出优良个体作为父代。（3）交叉和变异：随机配对后，每代个体之间通过单点交叉(概率为Pc=0.6)、单点变异(概率为Pm=0.05)产生新的基因型和基因组合。（4）解码：把所产生的用二进制编码的新子代码串还原成自然码，得到一组新的实验方案。,图8.4 每代(NH4)2SO4的浓度分布情况,图8.5 每代 PEP的浓分布情况度,图8.6 每代(NH4)2HPO4的 浓度分布情况,gen=0,gen=1,gen=2,gen=3,gen=0,gen=1,gen=2,gen=3,图8.7 每代YE的浓度分布情况,图

40、8.8 每代MgSO4的浓度分布情况,图8.9 每代 KH2PO4的浓度分布情况,讨论：随着进化的进行，各个参数逐渐收敛到一个或几个区域里，每个区域里个体数目的多少与该区域上一代的适应度函数值大小有关。以(NH4)2SO4浓度的优化为例(图8.4)，在第0代随机产生的实验方案中，(NH4)2SO4的取值几乎覆盖整个浓度范围，经三代进化，(NH4)2SO4的取值90%集中到4.505.0 g/l的范围内。这意味着该参数与其它参数没有交互作用。同样有(NH4)2HPO4(图8.6)、蛋白胨、酵母浸膏(图8.5，8.7)。MgSO4、KH2PO4(图8.8，8.9)则分别收敛到三个和两个有间隔的浓度

41、区域，如40%的KH2PO4浓度值在0.10.90g/l范围内，而60%在5.05.9 g/l范围之内；50%的MgSO4浓度值分布在0.250.295g/l范围内，40%则在0.350.395g/l，说明这些参数与其它参数有交互作用。,表8.5 优化前后培养基组成,表明：用GA能够以较少的实验样本(40个)对培养基配方进行较大规模的搜索，若采用正交设计需要502次实验，响应面实验需506次，即使用均匀设计也得50次。取得了降低培养基成本，提高发酵水平的好结果。,3.神经网络模型构建 输入值：YE、PEP、(NH4)2SO4、(NH4)2HPO4、KH2PO4、MgSO4 的初始浓度 输出值：

42、发酵终止时的木糖醇浓度 学习样本：从用GA优化时所得到的40组实验数据中取20组 神经网络：神经网络法与均匀设计相结合，BP算法，神经元活化函数为Sigmoid。,4木糖醇发酵状态估计用所构建的神经网络模型估计不同培养基配方下木糖醇浓度Pnns，结果表明：除个别点外，大部分木糖醇浓度的计算值Pnns与其实验值Pexp拟合较好（相对误差绝对值低于9%）。5仿真优化GA与ANNs的藕联,编码、选择、交叉、变异等遗传操作如上所述，所不同的是在编码时把每个组分划分为64等分(26=64)，即构成一个6因素64水平的培养基优化系统，以提高寻优密度。,表8.6 各参数等分值,表8.7优化前后的培养基各组分

43、浓度的比较,6.优化实验从遗传算法和人工神经网络模型所产生的四代共40组培养基配方中，挑选具有代表性的培养基配方十组，用摇瓶（每组做两瓶）进行发酵实验。,与单独使用GA优化培养基的前、后相比，木糖醇最高得率分别提高了15.0%和8.8%，培养基中各组分浓度也有较大幅度减低。,8.4.3 生物反应过程优化,由于生物反应过程是一个非常复杂的非线性过程，因而有关该过程操作条件优化方面的报导不多，实际操作时多为恒定过程的操作条件或凭经验予以调控。见于期刊有关生物反应过程操作条件优化方面的文章多为补料分批培养过程补料策略优化方面的问题，而涉及分批发酵过程操作条件优化的论文很少。事实上，大部分发酵产品的生

44、产采用的是分批发酵过程，而过程中最佳操作曲线的确定对发酵产品的生产至关重要，因而开展分批发酵过程操作条件优化非常必要。,虽然业已报导应用最小值原理能够找到分批发酵过程操作变量的最佳操作曲线，然而，其成功与否很大程度上取决于所用的发酵动力学模型的精度。对于集复杂性和显著非线性等特点于一体的生物反应过程而言，要建立其合适的发酵动力学模型往往是很困难的，特别是对于工业规模的生产来说，因受各种因素的干扰困难更大。运用Box等人所提出的调优操作方法也可优化工业规模的发酵操作条件，但并非所有的分批发酵过程都能够用简单的逐步回归方法获得所需的数学模型。有必要寻找一种既通用又实用的分批发酵过程操作条件优化方法

45、。,Rivera等人于1993年在国际自动控制联合会（IFAC）上发表了GA在生物过程优化中的应用一文，开创了应用GA于生物反应过程优化的先河。Moriyama等人应用GA于乙醇发酵培养温度的在线优化。Angelov等人应用GA优化由模糊规则描写的工业规模抗生素发酵过程，取得了提高产物浓度5%的结果。虽然应用遗传算法于生物反应过程优化方面的论文不多，但现已发表的论文已不同程度地表明遗传算法在生物反应过程优化方面的应用价值。本节以我们研究木糖醇发酵过程操作条件优化为例介绍应用GA于发酵过程优化的新方法。,对于一定的发酵装置、菌体及其相应的发酵培养基而言，影响发酵过程的操作条件是pH，温度及溶解氧

46、三要素。而对于像木糖醇发酵这一大类依靠氧化还原酶实现生物转化的过程来说pH和溶解氧尤为重要。因此，应该尽可能地把主要因素综合起来研究。为了通过有限的实验，尽可能地把主要的操作条件进行综合优化，我们提出了基于均匀设计安排操作条件优化实验，用神经网络关联操作条件与目标函数之间的关系，耦联遗传算法进行仿真优化、过程预测和实验优化等一系列发酵过程操作条件优化新方法，整个研究过程如图8.12所示。,图8.12 发酵过程操作条件优化示意图,1实验方案设计基于木糖醇发酵机理及所研究的结果，考虑到细胞生长过程主要经历了延迟期、对数生长期和稳定期三个阶段，我们仅考察发酵过程中搅拌转速和发酵液pH值在不同时刻两次

47、阶跃变化对木糖醇发酵水平的影响，并且与恒定搅拌转速和发酵液pH值的发酵结果进行比较。为了既综合考虑这三种因素的影响，又尽量减少实验次数，我们引入了均匀设计法。具体操作如下：将发酵过程分为三个阶段：0-20小时为第一阶段，20-38小时为第二阶段（t1的范围），38小时到结束为第三阶段（t2的范围），初始pH值设为5.0，在t1、t2点发生阶跃式变化；搅拌转速在第一阶段恒为400rpm，在t1、t2点发生阶跃式变化，共安排十组实验，其中一组为对照实验。,2过程辩识 在上述实验中，不仅过程中的发酵罐搅拌转速和发酵液pH值随时间发生阶跃性变化，而且各批发酵的初始木糖和菌体浓度也难于控制一致，因此用传

48、统的动力学模型更难予以描述，运用神经网络就能够实现过程辩识。学习样本：以所得的十批实验数据。输入变量：发酵时间t、t时刻的木糖浓度S、木糖醇浓度P、菌体浓度X、发酵液pH值、搅拌转速n、发酵时间t+等七个参数 输出变量：t+时刻的S、P、X等三个参数。网络结构：双隐含层，选择常用的sigmoid 函数和BP算法，经训练建立相应的过程辩识模型。,3模型预测性能检验为了检验上述建立的神经网络模型的预测能力，分别从十组数据中任取九组在上述模型基础上进一步训练，余下一组用于预测。经考察发现：无论取何组做预测组，其拟合效果都较好，其中第十组的训练平均误差和预测平均误差分别为5.51和2.88%。除第十组

49、之外的其它九组（即样本组）数据的网络模型计算值与其回归值的拟合效果如图8.13所示。由此可见，以第十组为测试组所建立的网络模型（简记为M10）无论是训练还是测试都有良好的性能。,图8.13 S、P、X的模型计算值与回归值的比较,图8.14 木糖醇发酵过程仿真（符号为实验值，曲线为网络模型计算值）,4过程仿真运用网络模型M10于上述给定的十组初始值（即S0、P0、X0）和控制参数（t1，pH1，n1，t2，pH2，n2）进行过程仿真，结果表明网络模型M10能够较好地用于发酵过程仿真（参见图8.14）。,5.状态估计模型构建 在发酵的初始条件及其过程的操作条件与发酵过程性能指标之间建立神经网络模型

50、。输入变量：S和X的初始状态（即S0、X0）、控制点的时间（t1，t2）及其所对应的控制变量（pH1，n1，pH2，n2）；输出变量：以初糖浓度为基准的最大转化率与生产能力的乘积（YpmaxQp）；学习样本：上述的九组数据(除对照组外)用单隐含层结构和均匀设计法，考察隐层结点个数、学习速率、动量因子对建模的影响，获得了一个测试误差最小（2.76%）的状态估计模型（简记为模型9-1）。以该模型的输出作为GA的适应值用于发酵过程操作条件寻优。,表8.8 各参数的上、下限及精度,6操作条件优化采用多参数二进制编码方式，每个参数的子串长度设为5，则将每个参数分成32（25）个水平，各参数的上、下限及精