智能算法初步课件

智能算法初步2014年数学建模培训一、MATLAB软件入门二、数学建模与Matlab软件应用三、智能算法初步入门四、遗传算法及其应用一、MATLAB软件入门MATLAB软件广泛的应用：（1）数值分析。（2）数值和符号计算。（3）工程与科学绘图。（4）控制系统的设计与方针。（5）数字图像处理。（6）数字信号处理。（7）通讯系统设计与仿真。（8）财务与金融工程。（9）等等一、MATLAB软件入门计算的逼近过程。x=1; %x值得输入sin(x) %输出sinxa1=x^(2*1-1)/factorial(2*1-1) %一次部分和a2=a1-x^(2*2-1)/factorial(2*2-1) %二次部分和a3=a2+x^(2*3-1)/factorial(2*3-1) %三次部分和a4=a3-x^(2*4-1)/factorial(2*4-1)a5=a4+x^(2*5-1)/factorial(2*5-1)a6=a5-x^(2*6-1)/factorial(2*6-1)MATLAB求解程序思考：利用求解piEXAMP1_1一、MATLAB软件入门2.矩阵、数组运算初步1）

基本表示：[]括起来，;分割开每一行，每行使用空格或,进行分割！基本要求：矩阵要求每行输入元素个数一样。如a1=[1,2,3;4,5,6;7,8,9];a2=[1,2,3,4,5,6,7,8,9];a3=[1;2;3;4;5;6;7;8;9];不正确：a4=[1,2,3,4,5;6,7,8,9];2）

等差元素向量的生成。两种方法 i.vec1=10:5:61;%10为起点，5为步长（可以为负数，缺省 %时默认为1），61为终止点 ii.Vec2=lenspace(10,60,11)%10为起点，60为终点，11为生 %成向量长度。一、MATLAB软件入门3.矩阵向量四则运算+，-，*，/运算时要符合矩阵四则运算的基本要求！要注意*/和.*./的区别！例：运算如下程序，并讨论区别。A=[1,2;3,4];B=[4,3;2,1];A+BA-BA*BB*AA/BB/AA.*BA./BA^2A.^2思考：是否可以做如上相应的运算？为什么？EXAMP1_2一、MATLAB软件入门4.向量矩阵的寻址、添加A=[1:5;6:10;11:15;16:20;21:25;26:30];B=[A,ones(size(A,1),1)];C=[A;31:35];D=A(1:2,:);%这里两处冒号的使用有什么不同？E=A(:,1:2);F=A(2,3);思考：如何利用矩阵的添加、寻址方法，给出系统对应位置的主子式的计算？常用的矩阵命令，根据help来对以下命令进行学习！length,size,ones,zeros,eig,diag,max,min,rank,inv等等！EXAMP1_3一、MATLAB软件入门例：绘制一个正方形。Matlab绘图为描点连线！正方形的顶点分别为(0,0),(0,1),(1,1),(1,0),则做如下程序即可！x=[00110];y=[01100];plot(x,y)axis([-.5,1.5,-.5,1.5])EXAMP1_5思考：1.利用圆和椭圆的参数方程绘制相应的图形。 2.在同一个图中绘制如下两个函数的图形。

一、MATLAB软件入门5.三维图形作图三维曲面作图。依然是描点划线，但请大家思考，这么描点？命令：meshgrid；mesh例：试绘制出如下二元函数：x=-2:0.1:2;y=-2:0.1:2;[X,Y]=meshgrid(x,y);Z=X.^2+Y.^2;%为什么是.^而不是^？mesh(X,Y,Z)其他三维图形作图命令:surf,waterfall,contour3等等，将上面程序命令中的mesh替换为相应的命令，看会产生什么样的效果？思考：分段函数如何绘制？绘制下分段函数的图形。一、MATLAB软件入门5.循环结构while语句结构(x循环判断)例子：一勤奋的diaos有1万元，每天赚手中钱的1%，一堕落的HRH有500万元，每天花手中钱的1%，问多少天后，diaos成功击败HRH？diaos=1;hrh=500;n=0;whilediaos<hrh %判断，只要条件满足，则循环继续！diaos=diaos*1.01; %每天diaos辛苦赚钱hrh=hrh*0.99; %每天HRH快乐花钱n=n+1; %天数增加endndiaoshrh %分别输出逆袭天数以及逆袭时各自的钱数EXAMP1_9一、MATLAB软件入门6.判断分支结构if…elseif…else…end语句例：模拟抛骰子的过程，抛10000次，记录正面次数和反面次数。使用rand随机生成0-1中均匀分布的随机变量，若落在0~1/6,则筛子点数为1，1/6~2/6之间，点数为2，依次类推。使用循环语句模拟抛掷10000次，记录每次点数即可。有如下程序：N=10000;num=ones(1,6);fori=1:Nr=rand;ifr<1/6num(1)=num(1)+1;elseifr>=1/6&r<2/6num(2)=num(2)+1;elseifr<3/6num(3)=num(3)+1;elseifr<4/6num(4)=num(4)+1;elseifr<5/6num(5)=num(5)+1;elsenum(6)=num(6)+1;endendnumnum/NEXAMP1_10一、MATLAB软件入门6.判断分支结构以上方法运用了判断语句，但是显然非常的复杂，是否有好的方法可以将之改造？学习ceil，floor，round的使用方法！分别为取上整数，取下整数，以及四舍五入。N=10000;num=ones(1,6);fori=1:Nr=rand;gz=ceil(r*6);num(gz)=num(gz)+1;endnumnum/N此程序极大的简化了程序的书写，可读性等也得到了极大的提高！EXAMP1_11二、数学建模与MATLAB软件应用初步1.万花规的计算机模拟如何抽象为数学问题？xy0二、数学建模与MATLAB软件应用初步1.万花规的计算机模拟根据万花规基本特点，大圆和小圆行进的路径是相同的！因此有：小圆圆心位置：笔触点相对于小圆圆心的位置：故笔触点的位置：即为万花规的数学模型！！xy0二、数学建模与MATLAB软件应用初步1.万花规的计算机模拟EXAMP2_1思考：一、关于万花尺绘图是否有一定的周期性规律？这样的周期性规律决定于模型中的那些参数？二、万花尺中小齿轮的初始位置是否影响绘图的最终结果？三、如果外面图形不是圆形，而是椭圆形，模型又该如何来建立？二、数学建模与MATLAB软件应用初步1.万花规的计算机模拟二、数学建模与MATLAB软件应用初步2.身份证号码的识别思考：1.继续完善身份证判定信息，如果用户为河南省，能否继续输出城市信息？能否继续输出县城信息？2.上面程序中并没有考虑输入的出生日期的问题，如会出现出生日期为3215.31.45的情况，如何避免这种情况的发生？3.身份证能否反应其他的信息，进一步的完善程序。1.神经网络算法适用于灰色模型或者黑色模型。即:已知其输入输出，但其系统内部状况（输入输出的函数关系）部分未知或完全未知的情况。如：人口数量，机动车数量，公路面积

和公路客运量，公路货运量

之间的关系！三、智能算法初步入门主要介绍遗传算法的基本理论，然后通过求解几个简单的函数最值问题，来说明如何利用遗传算法进行初步的优化计算。遗传算法

遗传算法（GeneticAlgorithm，简称GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算机算法，它由美国Holland教授1975年提出。遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适合并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位。三、智能算法初步入门

基本思想：遗传算法基本原理基于模仿生物界遗传学的遗传过程，把问题的参数用基因来表示，把问题的解用染色体来表示代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体。这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代，后代随机化地继承父代的最好特征，并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优解。三、智能算法初步入门遗传学相关概念遗传学遗传算法数学1个体要处理的基本对象、结构也就是可行解2群体个体的集合被选定的一组可行解3染色体个体的表现形式可行解的编码4基因染色体中的元素编码中的元素5基因位某一基因在染色体中的位置元素在编码中的位置6适应值个体对于环境的适应程度，或在环境压力下的生存能力可行解所对应的适应函数值7种群被选定的一组染色体或个体根据入选概率定出的一组可行解8选择从群体中选择优胜的个体，淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解三、智能算法初步入门遗传算法计算优化的过程就如同生物学上生物遗传进化的过程，主要有三个基本操作（或算子）：选择（Selection）交叉（Crossover）变异（Mutation）遗传算法步骤三、智能算法初步入门遗传算法基本步骤：把这些可行解置于问题的“环境”中，按适者生存的原则，选取较适应环境的“染色体”进行复制，并通过交叉、变异过程产生更适应环境的新一代“染色体”群把问题的解表示成“染色体”，在算法中就是以二进制编码的串，给出一群“染色体”，也就是假设的可行解经过这样的一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解遗传算法有很多种具体的不同实现过程，这里仅介绍标准遗传算法的主要步骤。遗传算法步骤三、智能算法初步入门选择编码策略，把参数集合（可行解集合）转换染色体结构空间；定义适应函数，便于计算适应值；确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数；随机产生初始化群体；计算群体中的个体或染色体解码后的适应值；按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体；判断群体性能是否满足某一指标，或者已完成预定的迭代次数，不满足则返回第五步，或者修改遗传策略再返回第六步．遗传算法具体步骤三、智能算法初步入门遗传算法具体步骤产生初始群体是否满足终止条件得到结果是结束程序否计算每个个体的适应值以适应度选择个体交叉变异得到新群体例1.设f(x)=-x2+2x+0.5，求max

f(x),x[-1,2]。我们将通过这个简单的求最值问题来详细给出遗传算法的整个过程。（1）编码和产生初始群体首先需要确定编码的策略，也就是说如何把[-1,2]

区间内的数用计算机语言表示出来。编码就是从表现型到基因型的映射，编码时要注意以下三个原则：完备性：问题空间中所有点（潜在解）都能成为GA编码空间中的点（染色体位串）的表现型；健全性：GA编码空间中的染色体位串必须对应问题空间中的某一潜在解；非冗余性：染色体和潜在解必须一一对应．遗传算法应用三、智能算法初步入门编码我们采用二进制形式来解决编码问题，即将某个变量值代表的个体表示为一个{0,1}二进制串。串的长度取决于求解的精度，例如假设求解精度为保留六位小数，由于区间[-1,2]的长度为3，则必须将该区间分为3106

等分。因为221<3106<222，所以编码所用的二进制串至少需要22位。二进制串（b21b20b19…b1b0）与[a,b]

内实数的一一映射：二进制串十进制数[a,b]

内实数b21b20b19…b1b0三、智能算法初步入门转化到[-1,2]

内的实数为：例.二进制串a=<10101000111>

其对应的十进制数为：编码三、智能算法初步入门随机的产生一个初始群体。pop1={<11100011110>，%a1<10001000010>，%a2<10110000000>，%a3<>}%a4这里假设初始群体的个体数为4。转化成[-1,2]

之间的十进制数即为：下面就需要解决每个染色体个体的适应值pop1={

1.523032,0.574022,-0.697235,0.247238}产生初始种群三、智能算法初步入门（2）定义适应函数和适应值由于目标函数f(x)

在[-1,2]

内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率打下基础。定义适应函数：为了便于计算，这里的Fmin

采用了一个特定的输入值例：如果取Fmin=-1，则f(x)=1对应的适应值为g(x)=2适应函数三、智能算法初步入门上述随机产生的初始群体，取Fmin=-1，则它们的目标函数值和适应值分别为：f(pop1)={

1.226437,1.318543,-1.380607,0.933350}g(pop1)={

2.226437,2.318543,0,1.933350}适应函数和适应值三、智能算法初步入门（3）确定选择标准用适应值比例来作为入选概率。设给定的规模为n

的群体pop={a1,a2,...,an

}，个体ai

的适应值为g(ai)，则其入选概率为上述随机产生的初始群体，它们的入选概率分别为：p(pop1)=g(pop1)/sum(g(pop1))={0.343675,0.357892,0,0.298433}三、智能算法初步入门（4）产生种群将入选概率大的个体选入种群，淘汰概率小的个体，并用概率最大的个体补入种群，得到与原群体大小同样的种群。newpop1={<11100011110>，%a1<10001000010>，%a2<10001000010>，%a2<>}%a4Matlab程序参见附录11在上述随机产生的初始群体中，淘汰掉a3，再加入a2，得到新的种群：三、智能算法初步入门（5）交叉

交叉也就是将一组染色体上对应基因段的交换得到新的染色体，然后得到新的染色体组，组成新的群体。将前面得到的newpop1

的四个个体两两配对，重复的不配对，进行交叉（可以在任一位进行交叉）：<11010111010>

<11001000010>

<10000110010>

<11100011110><10001000010>

<10010010101><01110010101>

<>新的群体jchpop1三、智能算法初步入门（6）变异

变异就是通过一个小概率改变染色体位串上的某个基因。现把jchpop1

中第3个个体中的第9位改变，就产生了变异，得到了新的群体pop2

：pop2={

<11001000010>,<11100011110>,<10000110111>,<>}然后重复上述的选择、交叉、变异，直到满足终止条件为止三、智能算法初步入门（7）终止条件

遗传算法的终止条件有两类常见条件：

采用设定最大（遗传）代数的方法，一般可设定为

50代，此时就可能得出最优解．此种方法简单易行，但可能不是很精确

根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因位相似程度来进行控制三、智能算法初步入门算法举例例1.设f(x)=-x2+2x+0.5，求max

f(x),x[-1,2]。

b21b20b19…b1b0b21b20b19…b1b0

三、智能算法初步入门

三、智能算法初步入门算法举例算法举例例