人工智能-马少平_清华大学出版社_chp774遗传算法

《人工智能-马少平_清华大学出版社_chp774遗传算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、7.4遗传算法达尔文进化论：“物竞天择、适者生存”70年代由美国的密执根大学的Holland教授首先提出近年来，遗传算法作为一种有效的工具，已广泛地应用于最优化问题求解之中。生物进化与遗传算法群体种群子群选择婚配变异遭淘汰的群体生物进化中的概念遗传算法中的作用环境适应函数适应性适应值函数适者生存适应函数值最大的解被保留的概率最大个体问题的一个解染色体解的编码基因编码的元素群体被选定的一组解种群根据适应函数选择的一组解交配以一定的方式由双亲产生后代的过程变异编码的某些分量发生变化的过程生物进化与遗传算法之间的对应关系遗

2、传算法的三个主要操作选择交配变异“轮盘赌”法：设群体的规模为N，F(xi)(i=1,...,N)是其中N个染色体的适应值。则第i个染色体被选中的概率由下式给出：选择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，首先选择次。这样共得

3、到个染色体。然后按照从大到小对染色体排序，依次取出个染色体，这样就得到了N个染色体。交配交配发生在两个染色体之间，由两个被称之为双亲的父代染色体，经杂交以后，产生两个具有双亲的部分基因的新的染色体。当染色体采用二进制形式编码时，交配过程是以这样一种形式进行的：a1a2...aiai+1...anb1b2...bibi+1...bna1a2...aibi+1...bnb1b2...biai+1...an交配前交配后交配位置变异变异发生在染色体的某一个基因上，当以二进制编码时，变异的基因由0变成1，或者由1变成0。如对于

4、染色体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

5、）依据变异概率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等适应函数：直接使用函数f(x)作为适应函数。假设群体的

6、规模N＝4，交配概率pc＝100％，变异概率pm＝1％。设随机生成的初始群体为：01101，11000，01000，10011选择方法：“确定性”法序号群体适应值选择概率（％）期望次数选中次数10110116914.440.58121100057649.231.972301000645.470.22041001136130.851.231第0代情况表序号种群交配对像交配位子代适应值1011012401100144211000141100162531100042110117294100113210000256第0代种群

7、的交配情况序号群体适应值选择概率（％）期望次数选中次数1011001448.210.33021100162535.621.42131101172941.561.66241000025614.600.581第1代情况表序号种群交配对像交配位子代适应值1110012311011729211011131100162531101141100002564100003111011729第1代种群的交配情况序号种群交配对像交配位子代适应值11101123110016252111011311111961310000421000128

8、94110113211010676第2代种群的交配情况最大适应值、平均适应值进化曲线遗传算法的特点（1）遗传算法是一个随机搜索算法，适用于数值求解具有多参数、多变量、多目标等复杂的最优化问题。（2）遗传算法对待求解问题的指标函数没有什么特殊的要求，比如不要求诸如连续性、导数存在、单峰值假设等。甚至于不需要显式的写出指标函数。（3）在经过编码以后