阅读材料——遗传算法

《阅读材料——遗传算法》由会员分享，可在线阅读，更多相关《阅读材料——遗传算法（32页珍藏版）》请在装配图网上搜索。

1、阅读材料算法研究与图灵奖图灵奖设立于1966年，是美国计算机协会ACM在计算机科学与技术方面所授予的 最高奖项，被称为计算机界的诺贝尔奖，主要授予在计算机领域做出突出贡献的个人。 表1.2是历届图灵奖获得者的简要介绍。表1.2历届图灵奖获得者的简要介绍年份姓名获奖原因1966 年Alan J. Perlis高级程序设计技巧，编译器构造1967 年Maurice V. Wilkes内部存储程序，程序库1968 年Richard Hamming数值方法，自动编码系统，错误检测和错误纠正码1969 年Marvin Minsky人工智能1970 年James H. Wilkinson数值分析，线性代数

2、，“倒退”错误分析1971 年John McCarthy人工智能1972 年Edsger Dijkstra现代编程语言的主要贡献者之一1973 年Charles W. Bachman数据库技术1974 年Donald E. Knuth算法分析和编程语言的设计1975 年Allen Newell, Herbert A. Simon人工智能，人类认知心理学和列表处理1976 年Michael O. Rabin, Dana S. Scott非确定性自动机1977 年John Backus高级编程系统，程序设计语言规范的形式化定义1978 年Robert W. Floyd设计高效可靠软件的方法学197

3、9 年Kenneth E. Iverson程序设计语言和数学符号，互动系统的设计1980 年Antony R. Hoare程序设计语言的定义与设计1981 年Edgar F. Codd数据库系统，尤其是关系型数据库1982 年Stephen A. Cook计算复杂性1983 年Ken Thompson， Dennis M. Ritchie通用的操作系统理论，UNIX操作系统1984 年Niklaus Wirth计算机语言设计1985 年Richard M. Karp算法理论，尤其是NP完全性理论1986 年John Hopcroft， Robert Tarjan算法和数据结构的设计与分析198

4、7 年John Cocke编译理论，大型系统的体系结构，精简指令集1988 年Ivan Sutherland计算机图形学1989 年William Kahan数值分析1990 年Fernando J. Corbato大型多功能、可实现时间和资源共享的计算系统1991 年Robin Milner可计算的函数逻辑(LCF)、ML和并行理论(CCS)1992 年Butler W. Lampson分布式，个人计算环境1993 年Juris Hartmanis，Richard E. Stearns计算复杂性理论1994 年Edward Feigenbaum, Raj Reddy大规模人工智能系统1995

5、 年Manuel Blum计算复杂性理论，密码学和程序校验1996 年Amir Pnueli时序逻辑，程序与系统验证1997 年Douglas Engelbart互动计算1998 年James Gray数据库与事务处理1999 年Frederick P. Brooks计算机体系结构，操作系统，软件工程2000 年Andrew Chi-Chih Yao伪随机数生成，密码学与通信复杂度2001 年Ole-Johan Dahl, Kristen Nygaard面向对象编程2002 年Ronald L. Rivest， Adi Shamir, Leonard M. Adleman公钥密码学2003 年

6、Alan Kay面向对象编程2004 年Vinton G. Cerf, Robert E. KahnTCP/IP协议2005 年Peter NaurALGOL 60，BNF 范式2006 年Frances Allen优化编译器技术的理论和实践，并行转换2007 年Edmund Clarke， Allen Emerson， Joseph Sifakis模型检测技术2008 年Barbara Liskov让计算机软件更加可靠、安全和更具一致性2009 年Charles Thacker第一台现代个人计算机Alto的先驱性设计与实现2010 年Leslie ValiantPAC学习，代数计算，并行与分

7、布式计算算法在计算机科学领域无处不在，很多图灵奖获得者在算法设计及复杂性分析方面 都有所建树。例如，Hoare在26岁就发明了闻名于世的快速排序算法；Ronald、Shamir 和Adleman发明了国际上最具影响力的公钥密码算法RSA；数据结构与算法领域的主 要内容都是出自Knuth编著的程序设计的艺术；Floyd发明了求解多源点最短路径 的Floyd算法；Karp给出了证明NP完全问题的方法，在网络流和组合优化问题领域都 发明了许多高效算法； Hopcroft 和他的学生 Tarjan 由于在数据结构和算法方面的众多 创造性贡献而共同获此殊荣，在业界传为美谈；姚期智(Chi-ChihYao

8、)发明了伪随机 数的生成算法，在加密/解密方面也发现了许多有价值的算法；Peter Naur创建了语法描 述中广泛使用的BNF范式;Sutherland发明的图形图像算法改善了屏幕刷新的文件显示, 以及对图形对象的递归扫描； Cook 的开创性文章揭开了计算复杂性中 NP 完全性的研 究；Rabin与Scott合作撰写的研究论文提出了非确定性机器的观点；Dijkstra发明了单 源点的最短路径算法 Dijkstra 算法，以及程序并发执行过程中进程同步的解决方法； Wilkinson在数值线性代数方面发现很多有意义的算法；Blum发现了著名的算法设计技 术分支限界法；等等。阅读材料算法的实验分

9、析渐进分析是一种数学方法，渐进分析技术能够在数量级上对算法进行精确度量。但 是，数学不是万能的，实际上，许多貌似简单的算法很难用数学的精确性和严格性来分 析，尤其分析平均情况。算法的实验分析(experiment analysis)是一种事后计算的方法， 通常需要将算法转换为对应的程序并上机运行。例如，为了测算起泡排序算法在实际运 行过程中的比较次数和移动次数，可以设置两个计数器countl和count2,在比较语句执 行前将计数器countl加1,在交换语句执行后将计数器count2加3 (因为交换操作需要 用三条赋值语句实现)。程序如下：void BubbleSort(int r , in

10、t n)int count1 = 0, count2 = 0; /count1 和 count2 记载比较次数和移动次数 int bound, exchange = n - 1;/第一趟起泡排序的区间是0, n-1while (exchange != 0)/当上一趟排序有记录交换时bound = exchange; exchange = 0;for (int j = 0; j rj+1)/注意不能写作 count1+int temp = rj; rj = rj + 1; rj + 1 = temp;count2 = count2 + 3;/1 次交换是 3 次移动操作exchange = j;

11、/记载每一次记录交换的位置coutvv比较次数是vvcountlvvendl;coutvv移动次数是vvcount2vvendl;下面给出算法实验分析的一般步骤：(1) 明确实验目的。在对算法做实验分析时，可能会有不同的目的，实验的设计 依赖于实验者要寻求什么答案。例如，检验算法效率理论分析的正确性，比较相同问题 的不同算法或相同算法的不同实现间的效率，等等。(2) 决定度量算法效率的方法。一般来说，有以下两种度量方法： 计数法。在算法中的适当位置插入一些计数器，来度量算法中基本语句(或某 些关键语句)的执行次数。 计时法。度量某个特定程序段的运行时间，可以在程序段的开始处和结束处查 询系统时

12、间，然后计算这两个时间的差。需要注意的是，在分时系统中，所记录的时间 很可能包含了 CPU 运行其他程序的时间(例如系统程序)，而实验应该记录的是专门 用于执行特定程序段的时间。例如，在UNIX中将这个时间称为用户时间，time命令可 以完成这个功能。(3) 生成实验数据。对于某些经典算法(例如TSP问题)，研究人员已经制定了 一系列输入实例作为测试的基准，但大多数情况下，需要实验人员自己确定实验的输入 实例。( 4)对输入实例运行算法对应的程序，记录得到的实验数据，通常用表格或者散 点图记录实验数据。以表格呈现实验数据的优点是直观、清晰，可以方便地对数据进行 计算。散点图在笛卡儿坐标系中用点

13、将数据标出，其优点是可以确定算法的效率类型。 表2.1是对某算法采用计数法得到的实验数据，图2.5给出了一个散点图的示例。表2.1表格法记录实验数据规模100020003000400050006000700080009000次数11,96624,30339,99253,01067,27278,69291,274113,063129,799JL问题规模图2.5典型的散点图( 5)分析得到的实验数据。根据实验得到的数据，结合实验目的，对实验结果进 行分析，并根据实验结果不断调整实验的输入实例，经过对比分析，得出具体算法效率 的有关结论。算法的渐进分析和实验分析的基本区别是：渐进分析不依赖于特定输入

14、，缺点是适 用性不强，尤其对算法做平均性能分析时；实验分析能够适用于任何算法，缺点是其结 论依赖于实验中使用的特定输入实例和特定的计算机系统。实际应用中，可以采用渐进 分析和实验分析相结合的方式来分析算法，首先在理论上描述算法的运行效率，然后针 对特定计算机或程序根据实验分析确定其中一些必要的参数。【问题】设模式的长度为m,用蛮力法求解KMP算法中的next值时，T0可直接 给出，一般情况下，计算nextj（lWjWm-l）需要在T0 Tj-1中分别取长度为j-1、 2、1 的真前缀和真后缀并比较是否相等，最坏情况下的时间代价是：算法，使其时间代价【想法】模式 T 示Tj对应的k值（nextj

15、=ma0义如0.T农进蛮力法求解KMP算法中next值的符Tj都对应一个k值，用nextj表j = 0j-k.Tj-1集合非空其它情况因为T0既没有真前缀也没有真后缀，因此next0= -1。假设已经计算出next0,next1，nextj,如何计算 nextj+1呢？设 k=nextj，则 T0.Tk-1 = Tj-k-Tj-1， 这意味着T0.Tk-1是T0.Tj-1的真前缀，同时Tj-k.Tj-1是T0Tj-1的真 后缀。为了计算nextj+1，比较Tk和Tj，可能出现两种情况：(1) Tk=Tj:说明 T0Tk-1Tk=Tj-kTj-1Tj，如图 3.16 所示。由 next 值的定义

16、， nextj+1 = k+1；T0-T j-k-Tk-1TkTj-1TjTj+1T0-T j-k-Tk-1Tk-Tj-1TjTj+1图 3.16 Tk=Tj的情况（2） Tk5Tj：此时要找出T0.Tj-1的真前缀和真后缀相等的第2大子串，由 于T0Tj-1的真前缀和真后缀相等的最大子串是T0.Tk-1,而nextk的值为 T0.Tk-1的真前缀和真后缀相等的最大子串的长度，则T0.Tnextk-1即为T0 Tj-1的真前缀和真后缀相等的第2大子串，如图3.17所示。令k=nextk，再比较Tk 和Tj，此时仍会出现两种情况，当Tk=Tj时，与情况（1）类似，此时,nextj+1=k+1；

17、当TkMTj时，与情况（2）类似，再找出T0.Tk-1的真前缀和真后缀相等的最大 子串，重复（2）的过程，直到Tk=Tj,或nextk=-1,说明T0Tj-1不存在真前 缀和真后缀相等的子串，此时， nextj+1=0。t亠ftT0Tj-kTk-1TkTj-1TjTj+1T0 -Tk-nextk Tnextk-1 Tk-1TkfTj-k-Tj-nextk.TOTk-l = Tj-kTj-l .Tk-nextkTk-l= Tj-nextkTj-1 又.T0Tnextk-1=Tk-nextkTk-1 .T0Tnextk-1= Tj-nextkTj-1Tj-1Tj图 3.17 TkHTj的情况例如，

18、模式T=abaababc的next值计算如下:j=0 时j=1 时,j=2 时,j=3 时,j=4 时j=5 时,j=6 时j=7 时,next0=-1k=next0=-1 ， next1=0k=next1=0, TOT1；k=next2=0， T0=T2k=next3=1, T1#T3；k=next4=1， T1=T4k=next5=2， T2=T5 k=next6=3, T3#T6；k=nextk=next0=-1， next2=0 next3=k+1=0+1=1 k=nextk=next1=0, T0=T3, next4=k+1=1next5=k+1=1+1=2next6=k+1=2+1

19、=3k=nextk=next3=1,T1=T6, next7=k+1=2/直到字符串末尾/无相同子串确定nextj+1的值/相等子串长度加1【算法实现】基于以上想法的求next值的算法用C+语言描述如下:void GetNext(char T , int next )int j = 0, k = -1;next0 = -1;while (Tj != 0)if (k = -1) next+j = 0; k = 0;else if (Tj = Tk) k+;next+j = k;else k = nextk;取T0-Tj的下一个相等子串的长度【算法分析】算法GetNext只需将模式扫描一遍，设模式

20、的长度为m,则算法的时 间复杂性为 O(m)。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方 便。反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使 子问题缩小到很容易直接求解，这自然导致递归过程的产生。分治与递归就像一对孪生 兄弟，经常同时应用在算法设计之中，并由此产生许多高效的算法。递归n)就是子程序(或函数)直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。递归必须具备以下两个基本要素， 才能在有限次计算后得出结果。( 1 )边界条件：确定递归到何时终止，也称为递归出口；( 2)递归模式：大问题是如何分解为小问

21、题的，也称为递归体。由于递归程序比较简洁，而且调用函数和被调用函数是同一个函数，很多人费解甚 至怀疑这样简洁的语句是如何实现问题求解的。只有深刻理解了递归函数的运行过程， 才能真正理解递归技术，从而设计递归程序。采用图示方法描述递归函数的执行过程， 从中可较直观地了解到递归函数的执行情况，具体方法如下：(1) 顺序写出函数执行的各语句，并用有向弧表示语句的执行次序；(2) 对函数的每个递归调用，写出对应的函数调用，从调用处画一条有向弧指向 被调用函数入口，表示调用路线，从被调用函数末尾处画一条有向弧指向调用语句的 下面，表示返回路线；(3) 在返回路线上标出本次调用所得的函数值。例1 Fibo

22、nacci序列(Fibonaccisequence)。把一对兔子(雌、雄各一只)放到围 栏中，每个月这对兔子都生出一对新兔子，其中雌、雄各一只，从第二个月开始。每对 新兔子每个月也生出一对新兔子，也是雌、雄各一只，一年后围栏中有多少对兔子？令f(n)表示第n个月开始时围栏中的兔子对数，显然有f (1) = 1, f=1,在第n 个月的开始，那些第n-1个月初在围栏中的兔子仍然存在，而每对在第n-2个月就已经 在围栏中的兔子会生均出一对新兔子，所以满足以下递推关系式：J1n=1, 2f (n) = f (n-1) + f (n-2)n2求解Fibonacci序列的递归算法用C+语言描述如下：in

23、t Fib(int n)if (n = 1 | n = 2) return 1;else return Fib(n-1) + Fib(n-2);当n=5时Fibonacci序列的递归算法的执行轨迹如图4.17所示，实线表示深一层递 归，虚线表示调用返回，虚线上的数字表示返回值，有向弧上的数字序号表示递归调用 和返回的执行顺序。图4.17 Fib函数的递归执行过程例2汉诺塔问题(Tower of Hanoi)。在塔A上有n个金碟，所有碟子按从大到 小的次序从塔底堆放至塔顶，紧挨着这座塔有另外两座塔(塔B和塔C),请将塔A 上的碟子移动到塔 C 上去，其间可以借助于塔 B 的帮助。每次只能移动一个

24、碟子，任 何时候都不能把一个碟子放在比它小的碟子上面。汉诺塔问题的求解是一个典型的递归求解过程，具体算法如下：void Hanoi(int n, char A, char B, char C) if (n = 1) cout A C; else Hanoi(n-1, A, C, B);coutA C;Hanoi(n-1, B, A, C);/将碟子从 A 移到 C 上，递归结束将n-1个碟子从A借助C移到B上将碟子从A移到C上将n-1个碟子从B借助A移到C上Hanio(2,A,C,B)Hanio(3,A,B,C)XHanio(3,A,B,C)Hanio(1,A,B,C)Hanio(2,A,C,

25、B)Hanio(1,ABQ _ _ 一 _ MoveA，C)Move (A,B) Hanio(1,C,A,B)-Hanio(1,C，A，B _(6 _ Move)(C,B)Move (A,C)Hanio(2,B,A,C)Hanio(1,B,C,A)Hanio(1,B,A)一(迎MoveJ(B,A)当 n=3 时汉诺塔算法的执行过程如图 4.18 所示，实线表示深一层递归，虚线表示 调用返回，有向弧上的数字表示递归调用和返回的执行顺序。J* def（2）a+b+c=d+e+f（ 3） abcd+e+f,可以肯定这六枚硬币中必有一枚为假币，同时也说明g, h为 真币。这时可将天平两端各去掉一枚硬币

26、，假设去掉c和f同时将天平两端的硬币各 换一枚，假设硬币b, e作了互换，然后进行第二次比较，比较的结果同样可能有三种： a+ed+b：这种情况表明天平两端去掉硬币c, f且硬币b, e互换后，天平两 端的轻重关系保持不变，从而说明了假币必然是a, d中的一个，这时我们只要用一枚 真币（例如h）和a进行比较，就能找出假币。若ah，则a是较重的假币；若a=h, 则d为较轻的假币；不可能出现ah,则c是较重的假币；若 c=h,则f为较轻的假币；不可能出现ch, 则b是较重的假币；若b=h,则e为较轻的假币；不可能出现bvh的情况。对于结果（2）和（3）的情况,可按照上述方法作类似的分析。由于问题的

27、解决是 经过一系列比较和判断,可以用判定树来描述这个判定过程。图5.14给出了八枚硬币的 判定过程，图中大写字母H和L分别表示假币较真币重或轻，边线旁边给出的是天平 的状态。八枚硬币中,每一枚硬币都可能是或轻或重的假币,因此共有16 种结果,则 判定树中有16个叶子结点,从图中可看出,每种结果都需要经过三次比较才能得到。人工神经网络 (artificial neural networks,简称ANN)是一个以有向图为拓扑结构 的动态系统，由许多人工神经元按一定规则连接构成。根据连接的拓扑结构不同，人工 神经网络可以分为四类：分层前向网络、反馈前向网络、互连前向网络、广泛互连网络 等，其中，最常

28、用、最成熟的人工神经网络是分层前向网络。人工神经网络技术与计算 机技术相结合，为人类进一步研究模拟人类智能以及了解人脑思维的奥秘开辟了一条新 途径。人类对人工神经网络的研究可以追溯到1943年，心理学家W.S.McCuloch和数理逻 辑学家W.Pitts最早提出了人工神经网络模型，开创了神经科学理论研究的新纪元。1969 年，M.Minsky和S.Papert出版了有较大影响的感知器一书，指出感知器功能上的 局限性，人工神经网络进入了长达10年的低潮期。20世纪80年代，随着计算机技术、 生物技术和光电技术等学科领域的迅速发展，人工神经网络的研究进入到了一个新的大 发展阶段。1982 年，美

29、国生物学家 J.Hopfield 提出了 Hopfield 网络模型。1985 年， D.E.Rumelhart 和 J. LMcclelland 提出 了误差反向传播算法(back-propagation algorithm， 简称 BP 算法)，是至今为止影响较大的一种网络学习方法。1988 年， Rumelhart、Hinton 和Williams等提出了基于BP算法的分层前向神经网络，成功地解决了多层神经网络中 隐含层神经元连接权值的学习问题。1995年，Mitra把人工神经网络与模糊逻辑理论、 生物细胞学说以及概率论相结合，提出了模糊神经网络，使得神经网络的研究取得了突 破性进展。下

30、面以分层前向网络为例介绍人工神经网络，该模型具有很强的非逻辑归纳特性， 一经问世便受到众多学者的关注，并取得了很大发展。一、拓扑结构图理论研究表明，一个三层的前向神经网络能够模拟任何复杂的非线性系统，它通过 对连续或断续的输入作状态响应而进行信息处理。图 6.25所示是三层前向神经网络拓扑 结构图。jk输入层隐含层输出层图6.25三层前向神经网络拓扑结构图说明：Y1为输入层结点i的输入，Y,3为输出层结点k的输出，Y2为隐含层结点jikj的输出，为结点i和结点j间的连接权值，W.k为结点j和结点k间的连接权值，9k为输出层结点k的阈值，j为隐含层结点j的阈值。二、基本原理分层前向网络的主要思想

31、是，学习过程由信号的正向传播与误差的逆向传播两个过 程组成，正向传播时，模式作用于输入层，经隐含层处理后，传向输出层。若输出层未 能得到期望的输出，则转入误差的逆向传播阶段，将输出误差按某种形式，通过隐含层 向输入层逐层返回，并分摊给各层的所有单元，从而获得各层单元的参考误差（称误差 信号），以此作为依据修改各单元间权值。这种信号正向传播与误差逆向传播的各层权 值的修改过程，是周而复始地进行的，权值不断修改的过程也就是网络的学习（或称训 练）过程。这个过程一直进行到网络输出的总误差逐渐减小到可接受的程度或达到设定 的学习次数为止。算法的一般框架如下：1. 初始化网络权值、阈值、学习次数和其他有

32、关参数；2. 输入一个学习样本；3. 计算隐含层各结点的输出值，计算输出层结点的输出值；4. 计算输出层结点和隐含层结点之间权值的修正量；5. 计算隐含层结点和输入层结点之间权值的修正量；6. 基于步骤4的修正量来修正输出层和隐含层的连接权值和阈值；7. 基于步骤5的修正量来修正隐含层和输入层的连接权值和阈值；8. 若总误差小于规定的误差上限或达到学习次数，则算法结束；否则转步骤2 取下一个学习样本；网络学习过程中用到的主要计算公式如下：1. 神经元的特性函数为Sigmoid型（S型）函数，一般取为2. 总误差为其中，为样本个数，为输出层节点j对第k个样本的输入对应的期望输出）， 为 节点j的

33、实际输出。3. 各层节点的输出为其中，a.是节点j的输入加权和；i为j的信号源方向的相邻层节点；O,为节点i的 输出，同时也是节点j的输入；o0=-i，w0j=e（阈值）。4. 从输出层节点到输入层节点以反向顺序，对各连接权值w.,进行修正ij其中，t为样本个数，l为与节点j在输出侧有连接的节点个数。w三、应用举例设计一个人工神经网络，对表6.1 所示的样本数据进行学习，使学成的网络能解决 类似的模式分类问题。表6.1网络学习样本数据输入输出XXcy,y2y31231230.30.80.11 0 00.70.10.30 1 00.6 0.6 0.60 0 1可以采用图6.25 所示三层前向神经

34、网络，用样本数据对该网络进行学习，学习结束 后，网络可以作为一种模式分类器使用，其输出(1, 0, 0)、(0, 1, 0)、(0, 0, 1)可以表示多 种模式或状态，例如可以分别表示凸、凹和直三种曲线，也可以表示某公司的销售情况： 高峰、低谷和持平等。需要强调的是，要使网络具有很好的模式分类能力，必须给出足 够多的学习样本让其学习，本例仅是一个简单的示例。人工神经网络具有以分布方式存储、并行方式处理、较强的容错能力，并且可以逼 近任意的非线性函数以及有很强的自学习、自适应及联想记忆功能等特征，吸引了众多 研究人员的兴趣，并在相关领域取得了显著的进展。例如：自动化领域中的系统识别和 神经控制

35、器以及智能检测，经济领域中的市场预测和信贷分析，工程领域中的汽车工程、 军事工程、水利工程、化学工程，信息领域中的信号处理、模式识别、数据压缩，医学 领域中的生物活动分析、医学专家系统等。由于贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最 优，这种局部最优选择有时不能得到整体最优解。对于一个具体的问题，怎么知道是否 可以用贪心法求解，以及能否得到问题的最优解呢？这个问题很难给予肯定的回答。但 是，从许多可以用贪心法求解的问题中看到，这类问题一般具有两个重要的性质：最优 子结构性质（optimal sub-structure property）和贪心选择性质（greedy c

36、hoice property）。（ 1 ）最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也 称此问题满足最优性原理。问题的最优子结构性质是该问题可以用动态规划法或贪心法 求解的关键特征。在分析问题是否具有最优子结构性质时，通常先假设由问题的最优解导出的子问题 的解不是最优的，然后证明在这个假设下可以构造出比原问题的最优解更好的解，从而 导致矛盾。（ 2 ）贪心选择性质 所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即贪心 选择来得到，这是贪心法和动态规划法的主要区别。在动态规划法中，每步所做出的选 择（决策）往往依赖于相关子问题的解，因

37、而只有在求出相关子问题的解后，才能做出 选择。而贪心法仅在当前状态下做出最好选择，即局部最优选择，然后再去求解做出这 个选择后产生的相应子问题的解。正是由于这种差别，动态规划法通常以自底向上的方 式求解各个子问题，而贪心法则通常以自顶向下的方式做出一系列的贪心选择，每作一 次贪心选择就将问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心 选择最终导致问题的整体最优解。通常先考察问题的一个整体最优解，并证明可修改这 个最优解，使其从贪心选择开始。做出贪心选择后，原问题简化为规模较小的类似子问 题，然后，用数学归纳法证明，通过每一步的贪心选择，最终

38、可得到问题的整体最优解。例 1 证明贪心法求解背包问题获得的解是整体最优解。 证明：不失一般性，假设物品按其单位重量价值降序排列，即：vi他上屮2上已他设背包问题的贪心策略是选择单位重量价值最大的物品，且X=（ xx2,：x）是找12n到的解，如果所有的xi等于1,则解X显然是最优的。否则，设j是满足x1的最小下 标，根据贪心策略，当ij时，x.=0,即解（X, x2，,x ）为（1, 1,，1, x.,ii12nj0, 0, , 0）的形式，并且满足 w x = C（式 7.3）ii此时背包获得的价值为V(X) = vxiii=1设 Y=（ y1, y2, , yn） 是某个最优解，显然工

39、w y = C（式 7.4）ii则一定有=乙 如果XHY,则一定存在k （lWkWn），对于lWiVk,有x=y.,ii 但xyk。此时，有以下两种情况：Swyiiw y ii(1)若 xyk，因为 yk1,必有 xk1,但是 xk+1 工 w x = S w x = C yk，有 Swx =Swx =Ci i i ii=lS w yiii=l由式7.4可知，yk+，yn不全为0,i=l同时减少 ykl, , y-中的不为n增大yk的值，0的某些值，得到Z=（%勺,），对于Uik,有z，=y.，对于kyk，且 S w z = C。i = 1 由于v/wv2/w2三三v/w，所以，在解Z中，单位

40、重量价值大的物品增多，单1122n n位重量价值小的物品减少，从而解Z优于解Y与Y是最优解矛盾；由（1）和（2）可知，X=Y因此，解X是最优的。例 2 证明贪心法求解活动安排问题得到的解是整体最优解。证明：设E=1, 2,n为n个活动的集合，且E中的活动按结束时间非减序排列， 所以，活动1 具有最早的结束时间。首先证明活动安排问题有一个最优解以贪心选择开 始，即该最优解中包含活动1。设A u E是活动安排问题的一个最优解，且A中的活动 也按结束时间非减序排列，A中的第一个活动是活动k。若k=1,则A就是以贪心选择 开始的最优解；若k1,则设B=A-k+1，即在最优解A中用活动1取代活动k。由

41、于f1Wfk，所以，B中的活动也是相容的，且B中活动个数与A中活动个数相同，故B 也是最优解。由此可见，总存在以贪心选择开始的最优活动安排方案。进一步，在做出了贪心选择，即选择了活动1后，原问题简化为对E中所有与活动 1相容的活动安排子问题。也就是说，若A是原问题的最优解，则A是活动安排子问题 E=s.f1，s戶E的最优解。如若不然，假设B是E的最优解，则B比A包含更多的活 动，将活动1加入B中将产生E的一个解B,且B比A包含更多的活动，这与A是原 问题的最优解相矛盾。因此每一步贪心选择都将问题简化为一个规模较小的与原问题具 有相同形式的子问题。对贪心选择次数应用数学归纳法可证，贪心法求解活动

42、安排问题 最终产生原问题的最优解。阅读材料遗传算法在人类历史上，通过学习与模拟来增强自适应能力的例子不胜枚举。模拟飞禽，人 类可以翱游天空；模拟游鱼，人类可以横渡海洋；模拟昆虫，人类可以纵观千里；模拟 大脑，人类创造了影响世界发展的计算机。人类的模拟能力并不仅仅局限于自然现象和 其他生命体。自 20 世纪后半叶以来，人类正在将其模拟的范围延伸向人自身，除了向 自身结构的学习以外，更向其自身的演化这一宏观的过程学习，来增强解决问题的能力， 其代表性的就是遗传算法(genetic algorithm，简称GA)。1975 年，美国 Michigan 大学的 John Holland 教授模拟达尔文

43、的进化论和孟德尔的 遗传变异理论，提出了遗传算法，其本意是在人工适应系统中设计一种基于自然的演化 机制。一、遗传算法的基本思想遗传算法建立在自然选择和群体遗传学的基础上，从任意初始种群(多个可能解的 集合)出发，通过繁殖(使种群中的优秀个体有更多的机会传给下一代)、杂交(体现自 然界中种群内个体之间的信息交换 )和变异(在种群中引入新的变种确保种群中信息的 多样性)等遗传操作，使种群一代一代进化到搜索空间中越来越好的区域，直至达到最 优解。设p、p和p分别表示繁殖、杂交和变异三种操作的概率，遗传算法的一般过 r c m程如下：卢i.iiiiiiiiiiiiiiiiiiiiiiiiiiiiiii

44、r1. 设置种群个数N,随机初始化种群P(0), t=0；2. 计算种群P(0)中个体的适应值；3. 重复执行下述操作，直到满足终止条件3.1根据个体适应值及选择策略确定P(t)内每个个体的选择概率p.；II3.2对种群P(t)中的个体执行下述操作，直到取完种群中的所有个体；3.2.1根据选择概率在P(t)中选择两个父体；:|3.2.2在0, 1区间随机确定一个随机数r；3.2.3若rWp,则执行繁殖操作，将两个父体直接插到种群P(t+1)中；:-rI；若rWpr+pc，贝y执行杂交操作，并将两后代插到种群P(t+1沖；I否则，对两父体分别执行变异操作，并将两后代插到种群P(t+1)中；3.3

45、计算种群P(t+1)中个体的适应值，t=t+1；:4. 返回种群中适应值最大的个体；二、遗传算法的关键问题理论上，遗传算法可以收敛到全局最优解，但在实际应用中也存在一些问题，比如 种群早熟、收敛速度较慢、收敛于局部最优解等。遗传算法需要解决以下关键问题：1. 编码方式。遗传算法的求解过程通常不是直接作用在问题的解空间上，因此，需 要采用某种编码方式将解空间映射到编码空间(可以是位串、实数等)，每个编码对应 问题的一个解，称为染色体或个体。例如，假设数字9 是某问题中的个体对象，则可以 用二进制位串 1001 作为其编码。遗传算法从原理上要求使用者采用最简单的代码组合 来表示问题的解，这样可以使

46、低阶、长度短、适应度高的基因能够产生更多的后代，从 而加快收敛。选择何种编码表示有时将对算法的性能、效率等产生很大的影响。2. 初始种群。所谓种群就是在编码空间中根据适应值(就是解的满意程度)或某种 竞争机制选择若干个个体组成的群体。遗传算法通常采用随机方法产生初始种群，这样 原理上可以使初始种群均匀分布于整个解空间，使遗传算法从全局范围内搜索最优解。 但对于某些实际问题，往往事先可以获得一些关于最优解的信息。3. 适应度函数。遗传算法使用适应度这个概念来度量种群中的各个个体在优化过程 中有可能达到最优解的优良程度，度量个体适应度的函数称为适应度函数。研究表明， 对同一问题采用不同的适应度函数

47、，遗传算法将导致不同的收敛速度及精度。针对如何 构造合适的适应度函数展开了许多研究，可以由外部显式适应度函数计算，也可以由系 统本身产生，如由个体在种群中的存活量和繁殖量确定。4. 遗传算子。遗传算法主要使用三个算子：繁殖、交叉、变异，其实现方法通常有 轮盘赌法选择、单点交叉和定概率变异。近年来，相继有竞争选择、排序选择、稳态选 择，多点交叉、均匀交叉以及变概率变异、预测变异等提出。5. 终止条件。由于遗传算法没有利用目标函数等信息，所以在计算过程中无法确定 个体在解空间的位置，从而无法用传统的方法来判定算法的是否收敛以终止算法。常用 的方法是预先设定一个最大的演化代数，或算法在连续多少代以后

48、解的适应值没有明显 改进时，可以终止算法。5. 控制参数。遗传算法必须精心选择以下参数：种群规模、染色体长度、杂交概率、 变异概率、最大代数等，这些参数的选择对问题的最终结果影响很大。三、应用举例例 1 利用遗传算法求解区间0, 31上的二次函数 y = x2 的最大值。解：首先定义适应度函数，进行编码。可以设函数(x)= x2作为适应度函数。由于5 位二进制数正好能表示区间0, 31中的全部整数，可以用5位二进制数作个体x的编码。其次，确定种群规模，初始化种群。将种群规模设定为 4，取个体 s1=01101(13)， s2=11000(24), s3=01000(8)，s4=10011(19

49、)组成初始种群 P(0)。再次，确定选择概率的计算函数、交叉概率和变异概率。本例中，设定交叉概率为100% ，变异概率为 1%，选择概率的计算公式为其中，f为适应度函数，f(s)为个体s.的适应值。显然，适应值越高的个体被随机选定的 概率就越大，被选中的次数也就越多，从而被繁殖的次数也就越多。接下来计算各代种群中各个体的适应值，并进行遗传操作，直到适应值最高的个体 出现，具体过程如下：计算P(0)中各个体的适应值和选择概率，如表8.1所示。执行选择操作，设从0, 1 区间中产生4个随机数如下：r1=0.450126， r2=0.110346， r3=0.572647， r4=0.985312根

50、据轮盘赌法选择的结果为：s1=11000(24)，s2=01101(13)，s3=11000(24)，s4=10011(19)可以看出，在第一轮选择中适应值最高的个体s2被选中两次，适应值最低的个体s4 一次也没有被选中而被淘汰。将选择的个体进行杂交操作，将s1与s2配对，s3与s4配 对，分别交换后两位基因，得到新的个体：s1=11001(25)， s2=01100(12)， s3=11011(27)， s4=10000(16)由于变异概率为1%，种群中共有5X4X0.01=0.2位基因可以变异，不足1位，本 轮操作不发生变异。于是，得到第二代种群P(1)：s1=11001(25)， s2=

51、01100(12)， s3=11011(27)， s4=10000(16)计算P(1)中各个体的适应值和选择概率，如表8.1所示。执行选择操作，假设4个 个体均被选中，然后进行杂交操作，将s1与s2配对，s3与s4配对，分别交换后三位基 因，得到新的个体：s1=11100(28)， s2=01001(9)， s3=11000(24)， s4=10011(19)这一轮仍然没有发生变异，得到第三代种群P(2)：s1=11100(28)， s2=01001(9)， s3=11000(24)， s4=10011(19)计算P(2)中各个体的适应值和选择概率，如表8.1所示。执行选择操作，假设被选 中的

52、个体为：s1=11100(28)， s2=10011(19)， s3=11000(24)， s4=11100(28)进行杂交操作，将s1与s2配对，s3与s4配对，分别交换后两位基因，得到新的个 体：s1=11111(31)， s2=10000(16)， s3=11000(24)， s4=11100(28)这一轮仍然没有发生变异，得到第四代种群P(3)，显然，这一代种群中出现了适应 值最高的个体11111(31)，遗传操作终止，将该个体作为最终结果输出。表8.1遗传算法的执行过程第1代种群中各个体情况第2代种群中各个体情况第3代种群中各个体情况个体适应值选择概率个体适应值选择概率个体适应值选择

53、概率s,=011011690.14s,=110016250.36s,=111007840.44s2=110005760.49s2=011001440.08s2=01001810.04s3=01000640.06s3=110117290.41s3=110005760.32s,=1001143610.31s=1000042560.15s,=1001143610.20遗传算法是一种随机的优化与搜索方法，具有并行性、通用性、全局优化性、健壮 性、可操作性与简单性等特点，遗传算法不论是在应用上、算法设计上，还是基础理论 上，都得到了长足的发展，已成为信息科学、计算机科学、运筹学和应用数学等诸多学 科共同

54、关注的热点研究领域。但是到目前为止，它始终未能对自身演化本身的研究发生 作用，而且就其实质来讲，目前，遗传算法学习人类演化的过程还只是形式的，尚未能 刻画人类自身的演化过程，更未能刻画神经元思维的学习过程。因此，就其模型本身来 讲需要更加深入的探讨。阅读材料蚁群算法众所周知，蚂蚁是一种群居类动物，常常成群结队地出现于人类的日常生活环境中。 科学工作者发现，蚂蚁的个体行为极其简单，群体却表现出极其复杂的行为特征，能够 完成复杂的任务。蚂蚁还能够适应环境的变化，例如，在蚁群运动路线上突然出现障碍 物时，蚂蚁能够很快地重新找到最优路径。通过观察，人类发现蚂蚁个体之间通过信息素(pheromone)进

55、行信息传递，从而 能够相互协作，表现出复杂有序的行为。蚁群的这种生活习性引起了一些学者的注意， 1991年，意大利学者M.Dorigo基于自然界蚁群觅食原理，提出了第一个蚁群算法并应 用在 TSP 问题中。蚁群算法被提出之后，其应用范围逐渐广泛，算法本身也不断被完善 和改进，形成了一系列的蚁群算法(ant colony optimization,简称ACO)。一、蚁群算法的基本原理 蚂蚁在寻找食物或者寻找回巢的路径中，会在经过的地方留下一些信息素，而信息 素能被同一蚁群中后来的蚂蚁感受到，并作为一种信号影响后到者的行动，具体表现在 后到的蚂蚁选择有信息素的路径的可能性，比选择没有信息素的路径的

56、可能性大得多， 而后到者留下的信息素会加强原有的信息素，并如此循环下去。这样，经过蚂蚁越多的 路径，被后到蚂蚁选中的可能性就越大(因为残留的信息素浓度较大)。由于在一定的 时间内，越短的路径会被越多的蚂蚁访问，因而积累的信息素也就越多，在下一个时间 内被其他的蚂蚁选中的可能性也就越大。这个过程会一直持续到所有的蚂蚁都走最短的 那一条路径为止。这种行为表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多， 则后到者选择该路径的概率就越大，信息素浓度的增长速度就会越快，通过这种信息的 交流，蚂蚁也就寻找到食物与蚁穴之间的最短路径了。下面举一个非常简单的生物原型来理解蚁群算法的原理，如图 9.15所示

57、。设一群蚂 蚁随机地向四面八方去觅食，当某只蚂蚁觅到食物时就沿原路回巢，同时在归途上留下 信息素，信息素随着向四周散发其浓度会不断下降。若有两只蚂蚁都找到食物，且沿原 路返回，从蚁穴到食物源可沿ABC，也可沿AC两条路径行走，ABC路径长，AC路径 短。甲乙丙三个蚂蚁去搬食物，甲乙先出发，这时选择ABC、AC两条路径的几率是一 样的，不妨设蚂蚁甲走AC这条路径，蚂蚁乙走由ABC这条路径。每只蚂蚁在其经过 的路径上都会释放一定浓度的信息素，而蚂蚁的生物特性会循信息素浓度大的路径前 进。这样当甲已经开始返回的时候，乙还在路上，这时由于AC路径上已经存在信息素， 而ABC路径上在食物源这一端还没有信

58、息素，甲仍循AC返回。当甲抵达巢穴时，丙 出发，丙会循AC前进，因为AC路径上有两次信息素的遗留物(去一次、回来一次)， 而在ABC路径上只有一次信息素的遗留物，故AC路径上的信息素浓度比ABC路径上 的信息素大，因此，蚂蚁会沿信息素浓度大的路径上前行。在大量个体的情况下，最终 所有蚂蚁都会循AC前进，后面的蚂蚁会渐渐地沿着由A到C的最短路程到达食物源。图9.15蚁群觅食过程二、蚁群算法的基本过程蚁群算法根据信息正反馈原理，与某种启发式算法有机结合，其优化过程主要包括 选择、更新和协调三个过程。在选择过程中，信息素浓度越高的路径被选择的概率越大； 在更新过程中，路径上的信息素随蚂蚁的经过而增长，同时也随时间的推移而挥发；在 协调过程中，蚂蚁之间通过信息素进行信息交流相互协作。在选择和更新过程中，较好 的解通过路径上的信息素得到加强，从而引导下一代蚂蚁向较优解邻域搜索使算法收 敛，同时更新过程的信息素挥发又使得算法具有探