遗传算法翻译

第一章基本思路和概念1.1导言日益专业化和多样化带来了大量的专著和教科书，对越来越多的专门话题。然而，“树”的数学知识及相关领域没有成长，只有提出了新的分支。也刚好，往往在事实上，那些被认为是完全不相干的分支，突然被发现有关系了。应用数学对于现实世界中的问题，大部分的手段，在开始，用数学建模，也许用严格的限制，理想化，或简化，然后解决数学问题，最后基于数学问题的解答得出结论。由于约60年来，转移范式已经发生了-从某种意义上说，相反的方式来进入流行。重点是世界已经做得很好，即使在数学建模不被大家知道的时代。更具体地说，有一个庞大的数目，高度精密的程序和机制，在我们的世界里，其中有总能吸引到有兴趣的研究人员，由于它们的令人钦佩的完美。模仿这些原则在数学上，并使用它们来解决更广泛层次的问题，变得极有帮助，在各个学科上。只是简单地说，让我们提以下三个例子：人工神经网（ANNs）：简单模型的神经细胞（神经元）以及他们相互作用；可用于函数逼近，机器学习，模式识别等。模糊控制：人类往往能够控制流程这方面还没有解析模型是可用。这种知识可以仿照数学上的手段语言控制规则和模糊集。模拟退火：鲁棒概率优化方法模拟凝固的晶体下慢慢降低温度;适用于广泛的一类问题。第四类这种方法将成为这次报告主要的研究对象-遗传算法（GAs）。这个世界，正向我们今天看到它的样子，其各种不同的动物，其独有的高度适应自己的环境，再加上其生态平衡（根据乐观的估计，仍然只有一个），是一个被我们称之为进化，一个基于性和无性繁殖，自然选择，突变等的三十亿年实验的产品。如果我们看一看其内部，今天生物的复杂性和适应性已达到在相当长的一段时间精炼并结合遗传物质。一般来说，遗传算法是模拟任何进化的。不过，在多数情况下，遗传算法不外乎基于进化原则的概率优化方法。这个概念首先出现在1967年，在J.D.bagley的论文“采用遗传及相关算法的适应系统的行为”。理论性和适用性之后是那么地被，可视为遗传算法先驱的J.H.Holland所强烈影响。从那时起，这一领域出现了巨大的发展。这项报告的目的是给予这类方法和他们的应用优化，程序归纳，和机器学习一个全面的概述。1.2定义和术语作为第一次近似，让我们限制，以认为基因算法是最优化算法。一般来说，最优化问题是以以下形式给出：Findan匚Xsuchthatfismaximalin忑山 f—]R”isanarbitraryr^al-valuedfunction..l.£. 仃"“在实践中，有时几乎是不可能的，取得全球性的解决办法，在严格意义上的（1.1）。视乎实际问题，它可以有资格去有一个局部最大或将至少靠近到一个局部或全球最大。所以，让我们假设我们对目标函数f是“尽可能高的”x值感兴趣。搜索区间X可以看出，在直接类推到一套竞争的个体在现实世界里，其中f是分配一个“适应度”给每个个体的一个函数（这是，当然，一个严重的简化）。在现实世界中，繁殖和适应是在遗传信息的水平上实现的。因此，遗传算法不是发生在值在区间x上的搜索，而是在一些他们的被编码的事物上（简言之串）。1.1定义。假设s是一组串（非平凡的情况下，有一些下面的基本原理）。设X是上述最佳化问题的一个搜索区间，然后一个函数就是所谓的编码函数。相反，函数C:.S一-Y.£ I——' ）就是所谓的译码函数。在实践中，编码和解码函数都必须指定依赖于实际问题的需要，但并不一定是双射。不过，在大多数情况下用映射解码函数是有用的。（我们将很快看到一些例子）。此外，以下的等式，往往是假定被满足了的：(co可三ids最后，我们可以写下编码最大化问题的一般形式：Findan列匚Ssuchthatf=fa?isaslargt?aspossible下表列出不同的表达方式，这些都是在遗传学里常见的，并附上与之等价的在遗传算法框架下的用词：自然进化遗传算法基因型编码串表现型未编码点染色体串基因串位置等位基因在某位置的值适应性目标函数值经过这一准备工作，我们可以写下遗传算法的基本结构。1.2算法。t:=0;计算初始种群B0;WHILE停止条件尚未履行DOBEGIN选择个体进行繁殖;营造子代越过个体;最终变种一些个体;计算出新的一代END从上述算法中可以明显地看出，从一个世代到下一个包括四个基本组成部分：选择：为了选拔个体（串），并根据他们的适应度进行繁殖（目标函数值）。交叉：交换两个个体遗传信息的一种方法；如果编码选择适当的话，两个好的父母产生良好的孩子。突变：在现实的进化，遗传物质是可以随机改变的，由错误复制或其他基因的畸形，如：用伽马射线辐射。遗传算法中，突变是可以实现的，靠串的以一定的概率的随机改变。积极的效应是遗传多样性的保存，并且，作为一种效果，就是局部的最大值可以被避免。抽样调查：一个程序，能从前一代和他的子代计算出新的一代。相对于传统的连续优化方法，如牛顿或梯度下降方法，我们可以列举以下显著差异：遗传算法处理问题参数的编码而不是参数本身，即搜索区间是S而不是X本身。在几乎所有的常规方法从一个单一的角度搜索时，遗传算法一直运作于整个种群的点上（串）。这给遗传算法的健壮性做了很多贡献。它改进了达到全局最佳的机会，并且，反之亦然，降低被困在一个局部固定点的风险。普通的遗传算法不使用任何辅助的关于目标函数值例如导数的信息。因此，他们可以适用于任何类型的连续或离散优化问题。唯一必须做的，是指定一个有意义的解码函数。遗传算法使用不确定的变换运算，而传统方法为连续优化，应用确定的变换运算。更具体地说，新的一代是由有随机组件的实际的一代计算得出。我们将在以后，在这些随机组件是什么样的，这样一些例子的帮助下了解。第二章一类简单的遗传算法曾经有一次在一间酒店里发生火灾，那里在那时正好在举行一次科学会议。当时正是深夜并且所有的客人都在熟睡。火灾发生时，与会人员来自不同学科。首先被烟雾弄醒的是数学家。他的第一反应是立即跑向浴室，在那里他看到仍然有水从水龙头流出，他惊叹道：“有一个办法！”。在同一时间，然而，物理学家去了解火灾情况，仔细看了一下火势然后回到自己屋子取了能正好扑灭火焰的水。电子工程师就没有那么挑剔，并开始一桶一桶地向火上浇水。最后，当生物学家醒来时，他对他自己说：“适者生存”然后继续睡觉。轶闻原引C.L.Liu在这一章中，我们将提出一个非常简单但极其重要的子类遗传算法用的是固定数量固定长度的二进制字符串。为此，让我们假设我们所考虑的串都来自集合s={0,1}n，其中n明显是串的长度。种群大小以下将被用m标注。因此，在t时间的一代是m串的一个名单，我们将把它表示为=八'1 • - 1。所有遗传算法，在这一章将顺从以下结构：t:=0:Computeinitialpopulatioti =（帕山’...f亦打）；VVHILEstoppitigcatidiiiottnotfu（filledDOBEGIN 、FOR::=ITO哦DOselect；ihimif-viditiil 上％;FOR::=1TO哦-1STEP2DOIFRandom[Ci.1]<PcTHEN旳阳汕+iwith切+M+i；FOR::=ITO哦DOf:=f斗1END2.1算法。显然，选择，交叉（只是以pC的概率来进行），及突变仍然有自由度，当取样作业已经被指定时。很容易地看到，每一个被选定的个体是在交叉和变异后被它的一个孩子取代；未经选择的个体马上死去。这是一个比较常见的取样作业，既使其他变种是已知的和合理的。在下面，我们将研究其余三项作业选择，交叉和突变。遗传操作上的二进制字符串选择选择是以偏重个体高适应度超过低适应度的解的指导算法的元件。它可以是一种确定性的操作，但在大部分实现中他有随机的元件。一种变异，当今非常流行（以后我们会给予它的优点一个理论解释），是以下结构，选择某一个体的可能性是正比于他的适应度。它可以被视为一个随机实验P[加訂注沖诃词=初E與如）（2.1）当然，这个公式仅仅当所有的适应度值是积极的时成立。如果情况并非如此，一个非递减的变换专：底一此十必须适用（在最简单的情况下的一种转变）。那么概率可以表示为P[&/>tissdected\=了（『如））（2.2）E曲如））（2.2）七=1我们可以迫使式（2.1）被满足，以适应一个，在某些意义上说，广义轮盘游戏一样的随机实验。在这轮盘游戏中，插槽不是同样宽的，即不同的结果，可出现不同概率。图2.1给出了一个图形暗示，这个轮盘游戏怎样进行。选择结构（2.1）的算法形成可写如下，（2.2）与此类似：1.2算法。x■-Random[Os1]；Z：=1WHILE,＜『讥越VEj=1施如j./龙驚朮如jDOi：=i-I-1;select汕；由于显而易见的原因，这种方法通常被称为按比例选拔。2.1.2交叉在有性繁殖中，因为它出现在现实世界中，双亲的遗传物质在双亲的配子合并时混合。一般情况下，染色体是随机地分裂和合并，其后果是孩子的一些基因来自一个父代而其他的来自另外的父代。

图2.1：以图形表示的轮盘赌选择，而备选方案的数量m是6。弧线内的数字是

任意一个被选弧形所对应的概率。这个机制是所谓的交叉。这是一个非常强大的为了引入新的遗传物质，并保持遗传多样性的工具，但具有优秀特性，良好的父代也产生表现良好的甚至更好的子代。几项调查都得出了这样的结论，交叉是为什么有性繁殖物种适应速度比无性繁殖快的原因。基本上，交叉是双亲的染色体之间的基因交换。在最简单的情况下，我们能够用切开两个串在一个随机选择的点，并交换两个尾巴的方法实现这个过程。这个过程，以下我们会称之为一点交叉，是可视化图2.2。图2.2：二进制字符串的一点交叉。2.3算法。P陽：=Random{1 化一1}；FORz1TO呷DOBEGINChild^i]:=PfmHif]:Child^:=ENDFORi■=p陽-4-1TO>!DOBEGINChildi[i]:=PmmDF]:CM"』』：=Parenti[：]END一点交叉是一个简单而常常使用的方法，为了在二进制上操作的遗传算法。对于其他问题或不同的编码，其他的交叉方法会非常有用，甚至是必要的。我们提到的只是他们中的一小部分，为了获取更多详细资料见[20.22]:N点交叉：取代仅有一点，N个断开点是随机选择。每个第二部分都被互换。此类中两点交叉尤为重要。分段交叉：相似于N点交叉，不同的是断点的数量可以改变。均匀交叉：对每个位置，它是否被互换是随机地决定。shuffle交叉：首先随机选择置换被应用于双亲，然后N点交叉被应用于打乱的父代，最后打乱的子代以相反的置换被变回来。突变我们简单遗传算法的最后一个要素是突变-一个个体被放射性物质或其他环境影响后的遗传信息的随机畸形。在现实的繁殖中，某一基因的变化概率相对于其他基因是相等的。因此，用以下诱变技术为某一特定的二进制字符串s,是很自然的，其中pM是单个基因被修改的概率。2.4算法。FOR：匸1TO江DOIFRandom[0?l]THENinverts国;当然,pM应该相当低目的是避免这个遗传算法的行为混乱得像个随机搜索。再次，类似交叉的情况，选择适当的诱变技术依赖于编码和问题本身。我们提几个选择，更多的细节可见于[20]和[22]：倒置每一个位：以概率pM,其中一个随机选择位不是。以比特为单位反转：整个字符串一位一位地以pM为概率反转。随机选择：以概率pM,字符串被随机选择的所代替。摘要如果我们把以上描述填写到方法里，我们能为在区间s={0,1}n里解决最佳化方法写出一个普遍的遗传方法。2.5算法。t1=0.C™rL=-inifia? 帀ridii灵=(切』-..一，対•：,□；■：WHILEsti、冲“唸widiH汕iwt押肿注DOBEGIN(hproportLCTLjJseLeetLoni■FOR>:=1TO+r^DOBEGINI：=Randam|0,1|：k：=1.while E>1f込初匸二1/|：Mooi?1=i?+1.h』+l:=瓦JEND(hone-pointcrossover时FORf:=1TO-1STEP2DOBEGINIFRandom|0.1|<pcTHENBEGINfKi-:=Random{1,...,n—1}:FORt:=^es+1TOmDOBEGINaux：=如j+i|虬hj+iRI：=H+ij+il罰傀+ir+il^l■=曲工ENDENDEND0jmihtLonhiFORf:=1TODOFORJI:=1TQnDO[FF?andom[0,1]<阿THEN"Etg+iZI；'£=t+1END2.2例子2.2.1一个非常简单的例子考虑以下函数找到全局最大的问题：fi: 11'1 31｝—RXI—- x2,当然，解决的办法是显而易见的，但这个问题的单纯，使我们能够用手计算出一些步骤，以获得一些遗传算法背后的原则。对于事情清单的第一步，需要做是为了使遗传算法工作，是，当然，指定适当的串空间遵循一个适当的编码和解码方案。在这个例子中，考虑s二｛0,1｝5,其中值从｛0,...,31｝是由它的二进制代表编码。相应地，一个字符串解码后为三⑸=丫屮-4•加t=0像在[22]中，让我们假定我们使用算法2.5，因为这是与种群数量大小为4,

交叉概率pC=l并且突变的概率pM=0.001。如果我们计算出初始代随机均匀分布在{0,1}5之内，第一步我们得到以下例子：IndividualString xvalu^ f(x)No. (geiu>t\rpt)(phtiiotvrpt)x2101101131690.14211000245760.493010008640.06410011193610.31适应度值的和是1170能简单地计算出来，其中平均值是293最大值是576。我们可以从最后一栏看出，按比例的选择比起低适应个体（如3号）更倾向于高适应个体（如2号）。一个随机实验能，例如，给出结果个体1号和个体4号为了新的一代被选出来，而3号死亡并且3号被选择了两次，然后我们获得的第二代如下：所以，我们得到了一个适应度值的和为1754，平均为439，最大为729的新的一代.从这个很基本的例子中我们可以看出，选择更倾向于高适应度的个体，并且双亲的交叉是如何能够繁殖出一个比他双亲都好的子代。继续这个例子，作为一个练习留给读者的。第三章分析虽然一个器官如此完美，如肉眼由自然选择形成，这样的信仰足以使任何人吃惊；但是在任何器官的情况下，如果我们知道在复杂性上的很长的一系列分级，每一个优点为他的拥有者，然后，根据不断变化的生活条件，这儿没有逻辑上不可能的事在获取任何可以想象的完善程度，通过自然选择。查尔斯•达尔文在这句话中，达尔文，在一定意义上，试图用目前并无证据显示反对为他的理论扭转举证责任。这一章的用意是为，为什么遗传算法会以一个在哲学上比达尔文更正确的方式进行，这样一个问题一个答案。不过，我们会看到，在达尔文的进化论，结构的复杂性使得数学分析困难而且繁琐。常规确定性的优化方法，如梯度法，牛顿或拟牛顿方法等，得到保证该序列的迭代以一定的速度或顺序收敛到一个局部最佳的方法是很普遍的。对于任何概率优化方法，这种定理不能被制定，因为算法的行为在一般情况下不是可决定的。声明关于概率优化方法的收敛，只能给出有关期望或平均行为的信息。在遗传算法的情况下，有少数情况使它更难以调查其收敛行为：自从一个单一的从一代到下一代的变换成为了通常的3个概率操作(选择，交叉和突变)的一个组合后，遗传算法的内部结构就相当复杂了。对于每一个涉及概率操作的行为，有很多不同的变种已提出，因此它不可能提供一般的收敛结果，由于操作的选择从根本上影响收敛这一实际情况。在以下，我们将无法给出“严格的”收敛定理，而是结果的一个大概，即为什么遗传算法可以运用在很多问题，但不是所有的问题都必须用它的线索。为了简洁明了，我们将会限制例2.1的算法，即给遗传算法的二进制字符串一个适合数量m和一个合适的长度n。除非另有说明，不然的话没有特定的假设关于选择，交叉，或突变将会被修改。让我们简单地重新考虑在2.2.1里的例子。我们看到，从第一次到第二代的转变在以下给出：Gt?n.#1f(K) #2 /(as)011011690110014411000576 -一，110016250100064110117291001136110000256人们很容易看到，有一个1在第一的位置是有益的。事实上，串的数量有了这个属性后在第一的位置上从2增加到了3到了第二代。由此产生的问题是，这是否是一种巧合，还是为什么遗传算法工作基本原则的一条简单线索。答案将是后者的情况正是这样。为了正式地考察这些方面，让我们作如下定义。3.2定义。一个在字母表｛0,1｝上的字符串S=(S],...,s)满足模式H=(h「...,h)，当且仅当它符合H是所有非匹配位置： " "Vi£｛』|打壬町：理=入根据以上讨论，我们记为 。一个模式H的规范的数量被称之为有序并记为=|｛d£｛1 江｝|忙丰*｝|-第一个和最后一个格式6\H'\=max)i\ht^*}—min{i|^j被称为模式H的界定长度。图3.2：一个维度为n=3的超平面解释。3.1维度定理在本节中，我们将制订并证明在遗传算法即维度定理上的最基本结果。虽然