智能多媒体实验报告基于遗传算法的函数优化

1、智能多媒体实验报告实验六：基于遗传算法的函数优化姓名：班级：学号：同做者： 一、实验目的利用遗传算法求解函数极值。二、算法概要1遗传算法概要遗传算法是具有“生成+检测”的迭代过程的搜索算法。它的基本处理流程如图6.1所示。由此流程图可见，遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。选择（selection）、交叉（crossover）和变异（mutation）是遗传算法的3个主要操作算子，它们构成了所谓的遗传操作（genetic operation），使遗传算法具有了其它传统方法所没有的特性。遗传算子包含如下6个基本因素：（1） 参数编码：由于遗传算法不能直接处理解空间的解数据，

2、因此必须通过编码将它们表示成遗传空间的基因型串结构数据。（2） 生成初始群体：由于遗传算法的群体型操作需要，所以必须为遗传操作准备一个由若干初始解组成的初始群体。初始群体的每个个体都是通过随机方法产生。（3） 适应度评估检测：遗传算法在搜索进化过程中一般不需要其他外部信息，仅用适应度（fitness）值来评估个体或解的优劣，并作为以后遗传操作的依据。（4） 选择（selection）：选择或复制操作是为了从当前群体中选出优良的个体， 使它们有机会作为父代为下一代繁殖子孙。个体适应度越高，其被选择的机会就越多。此处采用与适用度成比例的概率方法进行选择。具体地说，就是首先计算群体中所有个体适应度的

3、总和（），再计算每个个体的适应度所占的比例（），并以此作为相应的选择概率。（5） 交叉操作：交叉操作是遗传算法中最主要的遗传操作。简单的交叉（即一点交叉）可分两步进行：首先对种群中个体进行随机配对;其次，在配对个体中随机设定交叉处，配对个体彼此交换部分信息。（6） 变异：变异操作是按位（bit）进行的，即把某一位的内容进行变异。变异操作同样也是随机进行的。一般而言，变异概率都取得较小。变异操作是十分微妙的遗传操作，它需要和交叉操作配合使用，目的是挖掘群体中个体的多样性，克服有可能限于局部解的弊病。这6个要素构成了遗传算法的核心内容，其流程如图6.1所示。图6.1 遗传算法的基本流程2二进制编码

4、及解码方法二进制编码是遗传算法中最主要的一种编码方法，它使用的编码符号集是由二进制符号0和1所组成的二进制符号集0，1，它所构成的个体基因型是一个二进制编码符号串。二进制编码符号串的长度与问题所要求的求解精度有关。假设某一参数的取值范围是umin，umax，我们用长度为l的二进制编码符号串来表示该参数，则它总共能够产生种不同的编码，若使参数编码时的对应关系如下：0000000000000000=0 umin 0000000000000001=1 umin+ 11111111111111111=2l1 umax则二进制编码的编码精度为： （6-1）假设某一个个体的编码是：x blbl1bl，则对

5、应的解码公式为： （6-2）例如，对于，若用十位长的二进制编码来表示该参数的话，则下述符号串：x：0010101111就可表示一个个体，它所对应的参数值是。此时的编码精度为。其中：f 个体适应度umin，umax 某变量的取值范围 编码精度三、算法步骤及流程图step1：参数设置及种群初始化；step2：适应度评价；step3：轮盘赌选择；step4：交叉；step5：变异；step6：适应度评价；step7：终止条件判断，若未达到终止条件，则转到step3；step8：输出结果。四、实验程序主程序clc;clear;close all;v = 2*rand(50,22)-1;v=hardli

6、m(v);n,l = size(v); ger = 200; pc = 0.5; pm = 0.01; updatef=0;c=0;disp(sprintf(number of generations: %d,ger);disp(sprintf(population size: %d,n);disp(sprintf(crossover probability: %.3f,pc);disp(sprintf(mutation probability: %.3f,pm);f=-1*(x.2+y.2);% general parameters & initial operationssol1=1; v

7、mfit = ; it = 1; vx = ; c = ;updatef=-10;x = decod(v(:,1:11),11); y = decod(v(:,12:end),11); fit = eval(f);% generationst0 = clock;while it sp(sindex) sindex=sindex+1; %寻找要选择个体的位置 end newv(i,:)=v(sindex,:); endfor i=1:n v(i,:)=newv(i,:);%用选择出的个体构成的种群替代旧的种群end% crossverfor i=1:n cindex(i)=i;endfor i=

8、1:n %产生要配对的父代的序号；经过n次顺序调换，将原有顺序打乱，使相邻两个个体作为交叉的父代 point=unidrnd(n-i+1); temp=cindex(i); cindex(i)=cindex(i+point-1); cindex(i+point-1)=temp;endfor i=1:2:n p=rand(1); if(ppc) point=unidrnd(l-1)+1;%1pointl 产生交叉点 for j=point:(l-1) %交叉 ch=v(cindex(i),j); v(cindex(i),j)=v(cindex(i+1),j); %cindex中相邻的两个为两个父

9、代的序号 v(cindex(i+1),j)=ch; end endend% mutationm=rand(n,l)=sol1 sol1=updatef; v(indb1,:)=updatec;endupdatef=sol1;updatec=v(indb1,:);sol2,indb2 = min(fit);v(indb2,:) = v(indb1,:);x = decod(v(:,1:11),11); y = decod(v(:,12:end),11); fit = eval(f);media = mean(fit);vx = vx sol1; vmfit = vmfit media; if r

10、em(it,1) = 0 | it = 10, if c=1 disp(sprintf(gen.: %d x: %2.5f y: %2.5f av: %2.2f f(x,y): %2.40f,it,x(indb1),y(indb1),media,sol1); else disp(sprintf(gen.: %d av: %2.2f f(x,y): %2.5f,it,media,sol1); endend;it = it + 1;end;t = etime(clock,t0); %f = flops - f0;x=x;y=y;x = x(indb1); y = y(indb1); fx = so

11、l1; p = v;disp(sprintf(the total time is %2.4f,t); disp(sprintf(maximum found f(x,y): %.2f,fx);% xx=vx;yy=vmfit; figure(2); plot(vx,k); title(f(x,y) x mean); xlabel(generations); ylabel(f(x,y); hold on; plot(vmfit,k:); legend(best,mean,0);hold off;decod.m子程序function code = decod(w_code, len)w_size =

12、 size(w_code);code = ones(w_size(1), 1);%n*1的矩阵%编写解码表code_arry = ones(1, len);for i = 0:len-1 code_arry(i+1) = 2.i;end%针对每一个样本进行解码for i = 1:w_size(1) w = w_code(i, :); m = w.*code_arry; code(i) = sum(m);end%转换到给定区间rate = 2./(2.len-1);code = -1 +rate.*code;return ;程序流程图：五、实验结果number of generations: 2

13、00population size: 50crossover probability: 0.500mutation probability: 0.010gen.: 1 x: 0.05227 y: 0.17440 av: -0.55 f(x,y): -0.0331482272125327780000000000000000000000gen.: 2 x: 0.04934 y: 0.17440 av: -0.53 f(x,y): -0.0328503900402103420000000000000000000000gen.: 3 x: -0.09331 y: -0.12066 av: -0.48

14、f(x,y): -0.0232661425718860420000000000000000000000gen.: 4 x: 0.05227 y: 0.10992 av: -0.42 f(x,y): -0.0148140582009155010000000000000000000000gen.: 5 x: 0.05227 y: 0.10992 av: -0.37 f(x,y): -0.0148140582009155010000000000000000000000gen.: 6 x: 0.05227 y: 0.10992 av: -0.34 f(x,y): -0.0148140582009155

15、010000000000000000000000gen.: 7 x: 0.05227 y: 0.07865 av: -0.31 f(x,y): -0.0089184095590458482000000000000000000000gen.: 8 x: 0.05227 y: 0.01612 av: -0.33 f(x,y): -0.0029922135148867180000000000000000000000gen.: 9 x: 0.05227 y: 0.01612 av: -0.38 f(x,y): -0.0029922135148867180000000000000000000000gen

16、.: 10 x: 0.05227 y: 0.01612 av: -0.32 f(x,y): -0.0029922135148867180000000000000000000000gen.: 11 x: 0.05227 y: 0.01612 av: -0.24 f(x,y): -0.0029922135148867180000000000000000000000gen.: 12 x: 0.04836 y: 0.01612 av: -0.25 f(x,y): -0.0025989157104096623000000000000000000000gen.: 13 x: 0.04836 y: 0.01

17、612 av: -0.24 f(x,y): -0.0025989157104096623000000000000000000000gen.: 14 x: 0.04836 y: 0.01612 av: -0.22 f(x,y): -0.0025989157104096623000000000000000000000gen.: 15 x: 0.04836 y: 0.01612 av: -0.24 f(x,y): -0.0025989157104096623000000000000000000000gen.: 16 x: 0.04836 y: 0.00049 av: -0.25 f(x,y): -0

18、.0023392627909490826000000000000000000000gen.: 17 x: 0.04836 y: 0.00049 av: -0.30 f(x,y): -0.0023392627909490826000000000000000000000gen.: 18 x: 0.04836 y: 0.00049 av: -0.31 f(x,y): -0.0023392627909490826000000000000000000000gen.: 19 x: 0.04836 y: 0.00049 av: -0.34 f(x,y): -0.00233926279094908260000

19、00000000000000000gen.: 20 x: 0.04836 y: 0.00049 av: -0.37 f(x,y): -0.0023392627909490826000000000000000000000gen.: 21 x: 0.03273 y: 0.03175 av: -0.41 f(x,y): -0.0020796098714885034000000000000000000000gen.: 22 x: 0.03273 y: 0.03175 av: -0.33 f(x,y): -0.0020796098714885034000000000000000000000gen.: 2

20、3 x: 0.03273 y: 0.03175 av: -0.30 f(x,y): -0.0020796098714885034000000000000000000000gen.: 24 x: 0.03273 y: 0.03175 av: -0.28 f(x,y): -0.0020796098714885034000000000000000000000gen.: 25 x: 0.03273 y: 0.03175 av: -0.26 f(x,y): -0.0020796098714885034000000000000000000000gen.: 26 x: 0.03273 y: 0.03175

21、av: -0.21 f(x,y): -0.0020796098714885034000000000000000000000gen.: 27 x: 0.03273 y: 0.03175 av: -0.13 f(x,y): -0.0020796098714885034000000000000000000000gen.: 28 x: 0.03273 y: 0.03175 av: -0.13 f(x,y): -0.0020796098714885034000000000000000000000gen.: 29 x: 0.03273 y: 0.03175 av: -0.11 f(x,y): -0.002

22、0796098714885034000000000000000000000gen.: 30 x: 0.03273 y: 0.03175 av: -0.10 f(x,y): -0.0020796098714885034000000000000000000000gen.: 31 x: 0.03273 y: 0.03175 av: -0.10 f(x,y): -0.0020796098714885034000000000000000000000gen.: 32 x: 0.03273 y: 0.03175 av: -0.10 f(x,y): -0.002079609871488503400000000

23、0000000000000gen.: 33 x: 0.03273 y: 0.03175 av: -0.19 f(x,y): -0.0020796098714885034000000000000000000000gen.: 34 x: 0.02101 y: 0.03175 av: -0.23 f(x,y): -0.0014495696992679788000000000000000000000gen.: 35 x: 0.02101 y: 0.03175 av: -0.21 f(x,y): -0.0014495696992679788000000000000000000000gen.: 36 x:

24、 0.02101 y: 0.03175 av: -0.22 f(x,y): -0.0014495696992679788000000000000000000000gen.: 37 x: 0.02101 y: 0.03175 av: -0.23 f(x,y): -0.0014495696992679788000000000000000000000gen.: 38 x: 0.02101 y: 0.03175 av: -0.17 f(x,y): -0.0014495696992679788000000000000000000000gen.: 39 x: 0.02003 y: 0.03175 av:

25、-0.17 f(x,y): -0.0014094762337630387000000000000000000000gen.: 40 x: 0.02003 y: 0.03175 av: -0.18 f(x,y): -0.0014094762337630387000000000000000000000gen.: 41 x: 0.01710 y: 0.00440 av: -0.15 f(x,y): -0.0003116789639848482400000000000000000000gen.: 42 x: 0.01710 y: 0.00440 av: -0.19 f(x,y): -0.0003116

26、789639848482400000000000000000000gen.: 43 x: 0.01710 y: 0.00440 av: -0.19 f(x,y): -0.0003116789639848482400000000000000000000gen.: 44 x: 0.01710 y: 0.00440 av: -0.21 f(x,y): -0.0003116789639848482400000000000000000000gen.: 45 x: 0.01710 y: 0.00440 av: -0.20 f(x,y): -0.0003116789639848482400000000000

27、000000000gen.: 46 x: 0.01710 y: 0.00440 av: -0.15 f(x,y): -0.0003116789639848482400000000000000000000gen.: 47 x: 0.01710 y: 0.00440 av: -0.15 f(x,y): -0.0003116789639848482400000000000000000000gen.: 48 x: 0.00537 y: 0.00440 av: -0.19 f(x,y): -0.0000482076192380845980000000000000000000gen.: 49 x: 0.0

28、0537 y: 0.00440 av: -0.25 f(x,y): -0.0000482076192380845980000000000000000000gen.: 50 x: 0.00537 y: 0.00440 av: -0.20 f(x,y): -0.0000482076192380845980000000000000000000gen.: 51 x: 0.00537 y: 0.00244 av: -0.15 f(x,y): -0.0000348431307364366280000000000000000000gen.: 52 x: 0.00537 y: 0.00049 av: -0.1

29、3 f(x,y): -0.0000291154928071597700000000000000000000gen.: 53 x: 0.00537 y: 0.00049 av: -0.13 f(x,y): -0.0000291154928071597700000000000000000000gen.: 54 x: 0.00147 y: 0.00440 av: -0.11 f(x,y): -0.0000214786422347901870000000000000000000gen.: 55 x: 0.00147 y: 0.00440 av: -0.09 f(x,y): -0.00002147864

30、22347901870000000000000000000gen.: 56 x: 0.00147 y: 0.00440 av: -0.07 f(x,y): -0.0000214786422347901870000000000000000000gen.: 57 x: 0.00147 y: 0.00440 av: -0.04 f(x,y): -0.0000214786422347901870000000000000000000gen.: 58 x: 0.00049 y: 0.00440 av: -0.03 f(x,y): -0.00001956942959169790000000000000000

31、00000gen.: 59 x: 0.00049 y: 0.00440 av: -0.03 f(x,y): -0.0000195694295916979000000000000000000000gen.: 60 x: 0.00049 y: 0.00440 av: -0.05 f(x,y): -0.0000195694295916979000000000000000000000gen.: 61 x: 0.00049 y: 0.00440 av: -0.05 f(x,y): -0.0000195694295916979000000000000000000000gen.: 62 x: 0.00049

32、 y: 0.00440 av: -0.03 f(x,y): -0.0000195694295916979000000000000000000000gen.: 63 x: 0.00049 y: 0.00440 av: -0.05 f(x,y): -0.0000195694295916979000000000000000000000gen.: 64 x: 0.00049 y: 0.00440 av: -0.06 f(x,y): -0.0000195694295916979000000000000000000000gen.: 65 x: 0.00049 y: 0.00440 av: -0.09 f(

33、x,y): -0.0000195694295916979000000000000000000000gen.: 66 x: 0.00049 y: 0.00440 av: -0.07 f(x,y): -0.0000195694295916979000000000000000000000gen.: 67 x: 0.00049 y: 0.00049 av: -0.06 f(x,y): -0.0000004773031607730718200000000000000000gen.: 68 x: 0.00049 y: 0.00049 av: -0.05 f(x,y): -0.000000477303160

34、7730718200000000000000000gen.: 69 x: 0.00049 y: 0.00049 av: -0.06 f(x,y): -0.0000004773031607730718200000000000000000gen.: 70 x: 0.00049 y: 0.00049 av: -0.08 f(x,y): -0.0000004773031607730718200000000000000000gen.: 71 x: 0.00049 y: 0.00049 av: -0.13 f(x,y): -0.000000477303160773071820000000000000000

35、0gen.: 72 x: 0.00049 y: 0.00049 av: -0.16 f(x,y): -0.0000004773031607730718200000000000000000gen.: 73 x: 0.00049 y: 0.00049 av: -0.13 f(x,y): -0.0000004773031607730718200000000000000000gen.: 74 x: 0.00049 y: 0.00049 av: -0.12 f(x,y): -0.0000004773031607730718200000000000000000gen.: 75 x: 0.00049 y:

36、0.00049 av: -0.10 f(x,y): -0.0000004773031607730718200000000000000000gen.: 76 x: 0.00049 y: 0.00049 av: -0.04 f(x,y): -0.0000004773031607730718200000000000000000gen.: 77 x: 0.00049 y: 0.00049 av: -0.05 f(x,y): -0.0000004773031607730718200000000000000000gen.: 78 x: 0.00049 y: 0.00049 av: -0.05 f(x,y)

37、: -0.0000004773031607730718200000000000000000gen.: 79 x: 0.00049 y: 0.00049 av: -0.08 f(x,y): -0.0000004773031607730718200000000000000000gen.: 80 x: 0.00049 y: 0.00049 av: -0.09 f(x,y): -0.0000004773031607730718200000000000000000gen.: 81 x: 0.00049 y: 0.00049 av: -0.13 f(x,y): -0.0000004773031607730

38、718200000000000000000gen.: 82 x: 0.00049 y: 0.00049 av: -0.16 f(x,y): -0.0000004773031607730718200000000000000000gen.: 83 x: 0.00049 y: 0.00049 av: -0.14 f(x,y): -0.0000004773031607730718200000000000000000gen.: 84 x: 0.00049 y: 0.00049 av: -0.11 f(x,y): -0.0000004773031607730718200000000000000000gen

39、.: 85 x: 0.00049 y: 0.00049 av: -0.15 f(x,y): -0.0000004773031607730718200000000000000000gen.: 86 x: 0.00049 y: 0.00049 av: -0.13 f(x,y): -0.0000004773031607730718200000000000000000gen.: 87 x: 0.00049 y: 0.00049 av: -0.11 f(x,y): -0.0000004773031607730718200000000000000000gen.: 88 x: 0.00049 y: 0.00

40、049 av: -0.10 f(x,y): -0.0000004773031607730718200000000000000000gen.: 89 x: 0.00049 y: 0.00049 av: -0.09 f(x,y): -0.0000004773031607730718200000000000000000gen.: 90 x: 0.00049 y: 0.00049 av: -0.09 f(x,y): -0.0000004773031607730718200000000000000000gen.: 91 x: 0.00049 y: 0.00049 av: -0.09 f(x,y): -0

41、.0000004773031607730718200000000000000000gen.: 92 x: 0.00049 y: 0.00049 av: -0.08 f(x,y): -0.0000004773031607730718200000000000000000gen.: 93 x: 0.00049 y: 0.00049 av: -0.08 f(x,y): -0.0000004773031607730718200000000000000000gen.: 94 x: 0.00049 y: 0.00049 av: -0.09 f(x,y): -0.00000047730316077307182

42、00000000000000000gen.: 95 x: 0.00049 y: 0.00049 av: -0.12 f(x,y): -0.0000004773031607730718200000000000000000gen.: 96 x: 0.00049 y: 0.00049 av: -0.17 f(x,y): -0.0000004773031607730718200000000000000000gen.: 97 x: 0.00049 y: 0.00049 av: -0.15 f(x,y): -0.0000004773031607730718200000000000000000gen.: 9

43、8 x: 0.00049 y: 0.00049 av: -0.13 f(x,y): -0.0000004773031607730718200000000000000000gen.: 99 x: 0.00049 y: 0.00049 av: -0.11 f(x,y): -0.0000004773031607730718200000000000000000gen.: 100 x: 0.00049 y: 0.00049 av: -0.18 f(x,y): -0.0000004773031607730718200000000000000000gen.: 101 x: 0.00049 y: 0.0004

44、9 av: -0.16 f(x,y): -0.0000004773031607730718200000000000000000gen.: 102 x: 0.00049 y: 0.00049 av: -0.13 f(x,y): -0.0000004773031607730718200000000000000000gen.: 103 x: 0.00049 y: 0.00049 av: -0.11 f(x,y): -0.0000004773031607730718200000000000000000gen.: 104 x: 0.00049 y: 0.00049 av: -0.08 f(x,y): -

45、0.0000004773031607730718200000000000000000gen.: 105 x: 0.00049 y: 0.00049 av: -0.07 f(x,y): -0.0000004773031607730718200000000000000000gen.: 106 x: 0.00049 y: 0.00049 av: -0.06 f(x,y): -0.0000004773031607730718200000000000000000gen.: 107 x: 0.00049 y: 0.00049 av: -0.07 f(x,y): -0.0000004773031607730

46、718200000000000000000gen.: 108 x: 0.00049 y: 0.00049 av: -0.08 f(x,y): -0.0000004773031607730718200000000000000000gen.: 109 x: 0.00049 y: 0.00049 av: -0.08 f(x,y): -0.0000004773031607730718200000000000000000gen.: 110 x: 0.00049 y: 0.00049 av: -0.12 f(x,y): -0.0000004773031607730718200000000000000000

47、gen.: 111 x: 0.00049 y: 0.00049 av: -0.13 f(x,y): -0.0000004773031607730718200000000000000000gen.: 112 x: 0.00049 y: 0.00049 av: -0.14 f(x,y): -0.0000004773031607730718200000000000000000gen.: 113 x: 0.00049 y: 0.00049 av: -0.12 f(x,y): -0.0000004773031607730718200000000000000000gen.: 114 x: 0.00049

48、y: 0.00049 av: -0.11 f(x,y): -0.0000004773031607730718200000000000000000gen.: 115 x: 0.00049 y: 0.00049 av: -0.10 f(x,y): -0.0000004773031607730718200000000000000000gen.: 116 x: 0.00049 y: 0.00049 av: -0.07 f(x,y): -0.0000004773031607730718200000000000000000gen.: 117 x: 0.00049 y: 0.00049 av: -0.07

49、f(x,y): -0.0000004773031607730718200000000000000000gen.: 118 x: 0.00049 y: 0.00049 av: -0.10 f(x,y): -0.0000004773031607730718200000000000000000gen.: 119 x: 0.00049 y: 0.00049 av: -0.11 f(x,y): -0.0000004773031607730718200000000000000000gen.: 120 x: 0.00049 y: 0.00049 av: -0.07 f(x,y): -0.0000004773

50、031607730718200000000000000000gen.: 121 x: 0.00049 y: 0.00049 av: -0.12 f(x,y): -0.0000004773031607730718200000000000000000gen.: 122 x: 0.00049 y: 0.00049 av: -0.08 f(x,y): -0.0000004773031607730718200000000000000000gen.: 123 x: 0.00049 y: 0.00049 av: -0.07 f(x,y): -0.0000004773031607730718200000000

51、000000000gen.: 124 x: 0.00049 y: 0.00049 av: -0.07 f(x,y): -0.0000004773031607730718200000000000000000gen.: 125 x: 0.00049 y: 0.00049 av: -0.09 f(x,y): -0.0000004773031607730718200000000000000000gen.: 126 x: 0.00049 y: 0.00049 av: -0.06 f(x,y): -0.0000004773031607730718200000000000000000gen.: 127 x:

52、 0.00049 y: 0.00049 av: -0.04 f(x,y): -0.0000004773031607730718200000000000000000gen.: 128 x: 0.00049 y: 0.00049 av: -0.03 f(x,y): -0.0000004773031607730718200000000000000000gen.: 129 x: 0.00049 y: 0.00049 av: -0.05 f(x,y): -0.0000004773031607730718200000000000000000gen.: 130 x: 0.00049 y: 0.00049 a

53、v: -0.05 f(x,y): -0.0000004773031607730718200000000000000000gen.: 131 x: 0.00049 y: 0.00049 av: -0.05 f(x,y): -0.0000004773031607730718200000000000000000gen.: 132 x: 0.00049 y: 0.00049 av: -0.10 f(x,y): -0.0000004773031607730718200000000000000000gen.: 133 x: 0.00049 y: 0.00049 av: -0.11 f(x,y): -0.0

54、000004773031607730718200000000000000000gen.: 134 x: 0.00049 y: 0.00049 av: -0.13 f(x,y): -0.0000004773031607730718200000000000000000gen.: 135 x: 0.00049 y: 0.00049 av: -0.11 f(x,y): -0.0000004773031607730718200000000000000000gen.: 136 x: 0.00049 y: 0.00049 av: -0.10 f(x,y): -0.0000004773031607730718200000000000000000gen.: 137