清华大学《人工智能导论》课程电子教案(四)

遗传算法达尔文进化论：“物竞天择、适者生存”70年代由美国的密执根大学的Holland教授首先提出近年来，遗传算法作为一种有效的工具，已广泛地应用于最优化问题求解之中。生物进化与遗传算法群体种群子群选择婚配变异遭淘汰的群体生物进化中的概念遗传算法中的作用环境适应函数适应性适应值函数适者生存适应函数值最大的解被保留的概率最大个体问题的一个解染色体解的编码基因编码的元素群体被选定的一组解种群根据适应函数选择的一组解交配以一定的方式由双亲产生后代的过程变异编码的某些分量发生变化的过程生物进化与遗传算法之间的对应关系遗传算法的三个主要操作选择交配变异“轮盘赌”法：设群体的规模为N，F(xi)(i=1,...,N)是其中N个染色体的适应值。则第i个染色体被选中的概率由下式给出：NjjiixFxFxp1)()()(选择x1x2x3x4x5x6模拟“轮盘赌”算法（1）r=random(0,1)，s=0，i=0；（2）如果s≥r，则转（4）；（3）s=s+p(xi)，i=i+1,转（2）（4）xi即为被选中的染色体，输出i（5）结束。“确定性”法对于规模为N的群体，一个选择概率为p(xi)的染色体xi被选择次数的期望值e(xi)：对于群体中的每一个xi，首先选择次。这样共得到个染色体。然后按照从大到小对染色体排序，依次取出个染色体，这样就得到了N个染色体。Nxpxeii)()()(ixeNiixe1)()()(iixexeNiixeN1)(交配交配发生在两个染色体之间，由两个被称之为双亲的父代染色体，经杂交以后，产生两个具有双亲的部分基因的新的染色体。当染色体采用二进制形式编码时，交配过程是以这样一种形式进行的：a1a2...aiai+1...anb1b2...bibi+1...bna1a2...aibi+1...bnb1b2...biai+1...an交配前交配后交配位置变异变异发生在染色体的某一个基因上，当以二进制编码时，变异的基因由0变成1，或者由1变成0。如对于染色体x=11001，如果变异位发生在第三位，则变异后的染色体变成了y=11101。遗传算法（1）给定群体规模N，交配概率pc和变异概率pm，t＝0；（2）随机生成N个染色体作为初始群体；（3）对于群体中的每一个染色体xi分别计算其适应值F(xi)；（4）如果算法满足停止准则，则转（10）；（5）对群体中的每一个染色体xi计算概率；（6）依据计算得到的概率值，从群体中随机的选取N个染色体，得到种群；（7）依据交配概率pc从种群中选择染色体进行交配，其子代进入新的群体，种群中未进行交配的染色体，直接复制到新群体中；（8）依据变异概率pm从新群体中选择染色体进行变异，用变异后的染色体代替新群体中的原染色体；（9）用新群体代替旧群体，t=t+1，转（3）；（10）进化过程中适应值最大的染色体，经解码后作为最优解输出；（11）结束。例：求函数的最大值其中x为[0,31]间的整数编码：采用二进制形式编码由于x的定义域是[0,31]间的整数，刚好可以用5位二进制数表示，因此可以用5位二进制数表示该问题的解，即染色体。如00000表示x＝0，10101表示x＝21，11111表示x＝31等2)(xxf适应函数：直接使用函数f(x)作为适应函数。假设群体的规模N＝4，交配概率pc＝100％，变异概率pm＝1％。设随机生成的初始群体为：01101，11000，01000，10011选择方法：“确定性”法序号群体适应值选择概率（％）期望次数选中次数10110116914.440.58121100057649.231.972301000645.470.22041001136130.851.231第0代情况表序号种群交配对像交配位子代适应值1011012401100144211000141100162531100042110117294100113210000256第0代种群的交配情况序号群体适应值选择概率（％）期望次数选中次数1011001448.210.33021100162535.621.42131101172941.561.66241000025614.600.581第1代情况表序号种群交配对像交配位子代适应值1110012311011729211011131100162531101141100002564100003111011729第1代种群的交配情况序号种群交配对像交配位子代适应值1110112311001625211101131111196131000042100012894110113211010676第2代种群的交配情况0200400600800100012000123最大值平均值最大适应值、平均适应值进化曲线遗传算法的特点（1）遗传算法是一个随机搜索算法，适用于数值求解具有多参数、多变量、多目标等复杂的最优化问题。（2）遗传算法对待求解问题的指标函数没有什么特殊的要求，比如不要求诸如连续性、导数存在、单峰值假设等。甚至于不需要显式的写出指标函数。（3）在经过编码以后，遗传算法几乎不需要任何与问题有关的知识，唯一需要的信息是适应值的计算。也不需要使用者对问题有很深入的了解和求解技巧，通过选择、交配和变异等简单的操作求解复杂的问题，是一个比较通用的优化算法。（4）遗传算法具有天然的并行性，适用于并行求解。收敛性定理：如果在代的进化过程中，遗传算法每次保留到目前为止的最好解，并且算法以交配和变异为其随机化操作，则对于一个全局最优化问题，当进化代数趋于无穷时，遗传算法找到最优解的概率为1。遗传算法的实现问题编码评价适应函数交配规则停止条件编码举例：十杆桁架问题100kg100kg303030A1A2A3A4A5A6A7A8A9A10假设每个杆的截面积在0.1至10之间，在该范围内，有16个可能的取值。这样我们可以用4位二进制向量表示截面积的可能取值，其中0000表示0.1，1111表示10，余下的14位二进制向量表示其他的截面积的可能取值。这样10个杆，共用40位二进制向量表示一个十杆桁架问题的染色体。例：0010111000010011101100111111001100111010编码举例：旅行商问题对于n个城市的旅行商问题，可以用一个矩阵来表示一个可能解。如果按行展开该矩阵，则该可能解可以用一个4×4的二进制向量表示为：010010000001001001001000000100104321DCBA二进制表示存在的问题采用这样的表示方法，对于n城市的旅行商问题，至少需要用n×n位二进制向量表示一个可能的旅行路线。一个n×n位二进制向量，所有可能的编码个数为，而一个对称的n城市旅行商问题的可能解个数为n!/2，只占编码个数非常小的比例。以n＝10为例，编码个数为可能解个数的7.0×1023倍。可能解在整个状态空间中，是非常稀疏的，交配和变异所产生的是大量的非可能解。nn2遗传算法的评价定理4给出了当进化代数趋于无穷时，遗传算法找到最优解的概率为1。即保证了遗传算法的收敛性。但在实际计算时，希望随时了解遗传算法的进展情况，监视算法的变化趋势。当前最好法该方法在每一代进化过程中，记录得到的最好解，通过最好解的变化，了解算法的变化趋势。不同的算法之间，也可以通过该最好解的变化情况进行横向比较。在线比较法该方法用当前代中染色体的平均指标函数值来刻划算法的变化趋势。计算方法如下：其中T为当前代中染色体的个数。TtlineontfTv1_)(1离线比较法该方法与在线比较法有些相似，但是用进化过程中每代最好解的指标函数值的平均值，来评价算法的进化过程。计算方法如下：其中T是到目前为止的进化代数，f*(t)是第t代中，染色体的最好指标函数值。TtlineofftfTv1*_)(1适应函数一般情况下，我们可以直接选取问题的指标函数作为适应函数。如求函数f(x)的最大值，就可以直接采用f(x)为适应函数。但在有些情况下，函数f(x)在最大值附近的变化可能会非常小，以至于他们的适应值非常接近，很难区分出那个染色体占优。在这种情况下，希望定义新的适应函数，要求该适应函数与问题的指标函数具有相同的变化趋势，但变化的速度更快。非线性加速适应函数其中f(x)是问题的指标函数，fmax是当前得到的最优指标函数值，M是一个充分大的数。其他如果,)(,)(1)('maxmaxMfxfxffxf线性加速适应函数上式中的第一个方程表示变换前后的平均值不变，第二个方程表示将当前的最优值放大为平均值的M倍。)()('xfxfmxfMxfmxfmxfmiiimimiimii1111)()}({max)()(二进制编码的交配规则双亲双子法a1a2...aiai+1...anb1b2...bibi+1...bna1a2...aibi+1...bnb1b2...biai+1...an交配前交配后交配位置变化交配法11010011100010由于两个父染色体的前三位完全一致，因此当交配位选择在前三位时，其子染色体将与两个父染色体完全一致。变化交配法就是在随机产生交配位时，排除掉这样的交配位。多交配位法1101001110000011000101101011整数编码的交配规则下面以旅行商问题为例，介绍几种整数编码的交配规则。常规交配法随机选取一个交配位，子代1交配位之前的基因选自父代1交配位之间的基因，交配位之后的基因，从父代2中按顺序选取那些没有出现过的基因。交配位交配位父代1：12345678子代1：12345786父代2：52173846子代2：52173468基于次序的交配法父代1:12345678910父代2:59246110738所选位置:****父代1中与所选位置相对应的数字为：2、3、5、8。从父代2中找出这些数字，并去除它们，其中b表示空位置：父代2:b9b461107bb用2、3、5、8依次填入上述父代2的空位置中，得到子代1：子代1:29346110758基于位置的交配法首先随机产生一组位置。对于这些位置上的基因，子代1从父代2中直接得到，子代1的其他位置的基因，按顺序从父代1中选取那些不相重的基因。子代2也类似处理。如：父代1：123456789父代2：592461738****子代1：192465738基于部分映射的交配法对于两个选定的父代染色体父代1和父代2，随机产生两个位置，两个父代在这两个位置之间的基因产生对应对，然后用这种对应对分别去替换两个父代的基因，从而产生两个子代。父代1：264381579父代2：851762439子代1：184762539对应对：3:78:61:2变异规则二进制编码中的变异整数编码中的变异二进制编码中的变异当问题以二进制编码形式表示时，随机的产生一个变异位，被选中的基因由“0”变为“1”，或者由“1”变为“0”。变异前变异后11011011101001变异位整数编码中的变异基于位置的变异随机的产生两个变异位，然后将第二个变异位上的基因移动到第一变异位之前。21364572413657变异前变异后基于次序的变异随机的产生两个变异位，然后交换这两个变异位上的基因。21364572436157变异前变异后打乱变异随机选取染色体上的一段，然后打乱在该段内的基因次序。21364572436157变异前变异后逆序交换方式可以认为是打乱变异的一个特例。性能评价如何对遗传算法的性能进行评价是一件很困难的事情，为此需要确定性能度量和一些具有代表性的函数。一般可以用达到最优点时性能函数值的平均计算次数和计算所需要的时间来进行度量。一些学者给出了如下的测试函数集，这些函数或者是多峰值的，或者是不连续的，或者是具有一定的噪声的，对于求解他们的最小值具有一定的难度。1010,)()](sin1[)()(sin)(:11221212212111