《现代计算方法讲座.ppt》由会员分享，可在线阅读，更多相关《现代计算方法讲座.ppt（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、现代计算方法讲座现在学习的是第1页，共34页提纲提纲进化计算方法（遗传算法）进化计算方法（遗传算法）人工神经网络人工神经网络蚁群智能计算蚁群智能计算数据挖掘技术与方法（支持向量机）数据挖掘技术与方法（支持向量机）现在学习的是第2页，共34页背景介绍背景介绍 2121世纪，系统生物学的诞生进一步提升世纪，系统生物学的诞生进一步提升了后基因组时代的生命科学研究能力。正了后基因组时代的生命科学研究能力。正如胡德所说：如胡德所说：“系统生物学将是系统生物学将是2121世纪医世纪医学和生物学的核心驱动力。学和生物学的核心驱动力。”现在学习的是第3页，共34页生物学世纪的两桩令人瞩目的科学事件生物学世纪的
2、两桩令人瞩目的科学事件 19941994年年,美国科学家美国科学家AdelmanAdelman在在ScienceScience上发表了第一篇用上发表了第一篇用DNADNA分子的生化反应进行计算并解决人类数学问题的开创性分子的生化反应进行计算并解决人类数学问题的开创性文章。这个事件则向人们揭示，生命体也是计算的主体，不文章。这个事件则向人们揭示，生命体也是计算的主体，不仅人、动物甚至更简单的生命物质也会进行计算，例如细胞仅人、动物甚至更简单的生命物质也会进行计算，例如细胞核核DNADNA份子也可以是计算的主体。份子也可以是计算的主体。20032003年年,人类染色体的人类染色体的DNADNA全序
3、列测序完成，从此人类有全序列测序完成，从此人类有了自己的遗传密码。这件事告诉人们生命体是计算的产物，了自己的遗传密码。这件事告诉人们生命体是计算的产物，这种计算依赖的数据和计算程序的编码隐藏在人类已测定这种计算依赖的数据和计算程序的编码隐藏在人类已测定的的3030亿个碱基对中。亿个碱基对中。现在学习的是第4页，共34页 进入进入2121世纪短短的世纪短短的1010年，年，向生命世界学习计算的思想悄向生命世界学习计算的思想悄然在科学界传播开来，形成新然在科学界传播开来，形成新的计算主义。的计算主义。现在学习的是第5页，共34页一、进化计算方法（遗传算法）一、进化计算方法（遗传算法）两种力量导致了
4、生物进化的产生，构成进化两种力量导致了生物进化的产生，构成进化的基本要素：变异与选择。的基本要素：变异与选择。根据现代生物进化理论，所有的生物体的特根据现代生物进化理论，所有的生物体的特征及其变化都受到基因的控制，并将自己征及其变化都受到基因的控制，并将自己的基因拷贝给子女，这就是遗传密码。的基因拷贝给子女，这就是遗传密码。自然选择是对生物的表现型的选择遗传变异自然选择是对生物的表现型的选择遗传变异是基因型中某个遗传密码形成突变，或者是基因型中某个遗传密码形成突变，或者遗传密码进行重新组合。遗传密码进行重新组合。现在学习的是第6页，共34页在模仿进化原理而形成的仿生计算中最基础与典型的在模仿进
5、化原理而形成的仿生计算中最基础与典型的算法就是算法就是遗传算法遗传算法(Genetic Algorithm)Genetic Algorithm)遗传算法是遗传算法是John HollandJohn Holland开发的一种进化算法开发的一种进化算法 遗传算法的基本操作：遗传算法的基本操作：Step 1Step 1 将问题求解的对象编码成由基因组成的染色体；将问题求解的对象编码成由基因组成的染色体；Step 2Step 2 设计杂交和变异规则；设计杂交和变异规则；Step 3Step 3 设计适应值函数并进行遗传操作。设计适应值函数并进行遗传操作。现在学习的是第7页，共34页GAGA的形式化定义
6、的形式化定义记记 为抽象的个体，为抽象的个体，为所有字符长度为为所有字符长度为 的二进的二进制串的集合。种群制串的集合。种群 表示为表示为 个个体的一个组，记为个个体的一个组，记为 ，定义适应值函数，定义适应值函数 (实数实数)，称为个体的适应值。选择操作的算子定义为称为个体的适应值。选择操作的算子定义为 ；杂交操作的算子；杂交操作的算子 ；变异操作的算子；变异操作的算子 。定义。定义 为杂交概率，为杂交概率，为变异概率，则一下七元组就定义了一个遗传运为变异概率，则一下七元组就定义了一个遗传运算（即为一个特定的算（即为一个特定的GAGA）现在学习的是第8页，共34页案例案例实例目标函数作图，实
7、例目标函数作图，MatlabMatlab程序程序 x=-1:0.01:2;y=x.*sin(10*pi*x)+2.0;plot(x,y);grid on;现在学习的是第9页，共34页现在学习的是第10页，共34页现在学习的是第11页，共34页二、人工神经网络二、人工神经网络早在早在2020世纪上半叶开始了这个领域的研究，在多半个世纪世纪上半叶开始了这个领域的研究，在多半个世纪的发展中成为无论在理论还是应用方面都日趋成熟的仿生的发展中成为无论在理论还是应用方面都日趋成熟的仿生计算分支。计算分支。神经网络具有学习功能，其学习也称训练。神经网络神经网络具有学习功能，其学习也称训练。神经网络能够从环境
8、中学习，从而以新的方式对环境的变化作能够从环境中学习，从而以新的方式对环境的变化作出反应时神经网络最有意义的性质。出反应时神经网络最有意义的性质。19491949年年HebbHebb提出了最著名的经典学习规则，称为提出了最著名的经典学习规则，称为HebbHebb学习学习规则，用于调整神经网络的突触权值。规则，用于调整神经网络的突触权值。现在学习的是第12页，共34页 人工神经网络是大量模拟神经元互连而成的网络，人工神经网络是大量模拟神经元互连而成的网络，是人脑的抽象、简化、模拟，反映人脑的基本特征。是人脑的抽象、简化、模拟，反映人脑的基本特征。ANNANN模型模型具有下面三个要素：具有下面三个
9、要素：具有一组突触连接，用表示神经元与的联结强度，或具有一组突触连接，用表示神经元与的联结强度，或称为权值，但称为权值，但ANNANN的权值可取正与负值。的权值可取正与负值。具有反映生物神经元时空整合功能的输入信号累加具有反映生物神经元时空整合功能的输入信号累加器。器。具有一个激励函数，勇于转换神经元的输出。激具有一个激励函数，勇于转换神经元的输出。激励函数将输出信号压缩励函数将输出信号压缩(限制限制)形成一个范围的有形成一个范围的有限值。限值。现在学习的是第13页，共34页人工神经网络的基本方法人工神经网络的基本方法Step 1 Step 1 设计神经网络结构，特别是学习方法；设计神经网络结
10、构，特别是学习方法；Step 2 Step 2 利用训练集求解神经网络参数；利用训练集求解神经网络参数；Step 3 Step 3 对已有参数进行计算并学习修正网络参数。对已有参数进行计算并学习修正网络参数。现在学习的是第14页，共34页案例案例人工神经网络模型中激励函数人工神经网络模型中激励函数SigmoidSigmoid图像图像 ，MatlabMatlab程序如下程序如下：v=-10:0.1:10;a=.5;f=1./(1+exp(-a*v);plot(v,f,red);hold on;%another a:a=.8;f=1./(1+exp(-a*v);plot(v,f,blue);%on
11、ce more:a=2;f=1./(1+exp(-a*v);plot(v,f,green);现在学习的是第15页，共34页现在学习的是第16页，共34页 19431943年，神经生物学家年，神经生物学家W.McCullchW.McCullch和数学家和数学家W.PittsW.Pitts在著名的论文神经活动内容概念的逻辑演算中总结在著名的论文神经活动内容概念的逻辑演算中总结生物神经元的基本生理特征，提出了第一个神经计算模生物神经元的基本生理特征，提出了第一个神经计算模型，即神经元的阈值元件模型，简称型，即神经元的阈值元件模型，简称MPMP模型。模型。19491949年，加拿大心理学家年，加拿大心
12、理学家Douald HebbDouald Hebb在他的论著在他的论著行为的组织一文中，对大脑神经元的学习与条件行为的组织一文中，对大脑神经元的学习与条件反射做了大胆假设：如果两个神经元都处于兴奋激活反射做了大胆假设：如果两个神经元都处于兴奋激活状态，那么彼此的突出联结权机会得到加强。这就是状态，那么彼此的突出联结权机会得到加强。这就是著名的著名的HebbHebb学习规则。学习规则。Rochester,John HollandRochester,John Holland与与IBMIBM公司的研究人员合作公司的研究人员合作以网络吸收经验来调节强度模拟了以网络吸收经验来调节强度模拟了HebbHeb
13、b的学习规则，并的学习规则，并在计算机上实现了学习，产生了许多涌现现象，使计算在计算机上实现了学习，产生了许多涌现现象，使计算机有了类似人脑的学习功能。机有了类似人脑的学习功能。现在学习的是第17页，共34页三、蚁群智能计算三、蚁群智能计算 生物群体的行为反应了生物的集群智能，生物群体的行为反应了生物的集群智能，例如鸟群飞行的自动队列、鱼群在游动中例如鸟群飞行的自动队列、鱼群在游动中交换位置、细胞群有序地传播信息等，表交换位置、细胞群有序地传播信息等，表现出十分有效的群体决策能力。各种不同现出十分有效的群体决策能力。各种不同的集群智能现象启发人们产生不同的模仿的集群智能现象启发人们产生不同的模
14、仿集群智能的算法，例如蚁群算法、粒子群集群智能的算法，例如蚁群算法、粒子群算法、元胞自动机算法等。算法、元胞自动机算法等。现在学习的是第18页，共34页蚁群算法的基本假设蚁群算法的基本假设 蚂蚁之间通过信息素和环境进行通信，每只蚂蚁只根据其蚂蚁之间通过信息素和环境进行通信，每只蚂蚁只根据其邻近的局部环境做出反应，并发生影响。邻近的局部环境做出反应，并发生影响。蚂蚁对环境的反应由其自身原因决定。由于生物的蚂蚁对环境的反应由其自身原因决定。由于生物的基因学说，可以认为实际上是其基因的适应性表现，基因学说，可以认为实际上是其基因的适应性表现，即蚂蚁是对环境反应的表现型主体。即蚂蚁是对环境反应的表现型
15、主体。在个体水平上每只蚂蚁仅根据环境作独立选择，而在群在个体水平上每只蚂蚁仅根据环境作独立选择，而在群体水平上单只蚂蚁的行为是随机的，但是蚂蚁可通过关体水平上单只蚂蚁的行为是随机的，但是蚂蚁可通过关联性，自组织地形成高度有序的群体行为。联性，自组织地形成高度有序的群体行为。现在学习的是第19页，共34页蚁群算法的基本模型设计蚁群算法的基本模型设计Step 1 Step 1 将问题求解的目标编译成空间将问题求解的目标编译成空间路径的图问题；路径的图问题；Step 2 Step 2 设计抽象蚂蚁的行为规则、状设计抽象蚂蚁的行为规则、状态转移规则、信息更新规则；态转移规则、信息更新规则；Step 3
16、 Step 3 迭代终止条件设定。迭代终止条件设定。现在学习的是第20页，共34页案例案例 问题描述：设有问题描述：设有n n个城市，坐标已知，个城市，坐标已知，n n个个城市构成一个完全图，利用蚁群算法找出城市构成一个完全图，利用蚁群算法找出从一个城市出发走遍每个城市，并且不重从一个城市出发走遍每个城市，并且不重复到达任一个城市的最短路径。复到达任一个城市的最短路径。现在学习的是第21页，共34页实现该问题的程序实现该问题的程序function R_best,L_best,L_ave,Shortest_Route,Shortest_Length=.ACATSP(C,NC_max,m,Alph
17、a,Beta,Rho,Q)%=%ACATSP.m%Ant Colony Algorithm for Traveling Salesman Problem%-%主要符号说明：主要符号说明：%Cn个城市的坐标，个城市的坐标，n2的矩阵的矩阵%NC_max最大迭代次数最大迭代次数%m蚂蚁个数蚂蚁个数%Alpha表征信息素重要程度的参数表征信息素重要程度的参数%Beta表征启发式因子重要程度的参数表征启发式因子重要程度的参数%Rho信息素蒸发系数信息素蒸发系数%Q信息素增加强度系数信息素增加强度系数%R_best各代最佳路线各代最佳路线%L_best各代最佳路线的长度各代最佳路线的长度%=现在学习的是
18、第22页，共34页%第一步：参数初始化：第一步：参数初始化：n=size(C,1);%n表示问题的规模（城市个数）表示问题的规模（城市个数）D=zeros(n,n);%D表示完全图的赋权邻接矩阵表示完全图的赋权邻接矩阵for i=1:n for j=1:n if i=j%计算距离计算距离 D(i,j)=(C(i,1)-C(j,1)2+(C(i,2)-C(j,2)2)0.5;else D(i,j)=eps;end D(j,i)=D(i,j);end%jend%uEta=1./D;%Eta为启发因子，这里设为距离的倒数为启发因子，这里设为距离的倒数Tau=ones(n,n);%Tau为信息素矩阵为
19、信息素矩阵Tabu=zeros(m,n);%存储并记录路径的生成存储并记录路径的生成R_best=zeros(NC_max,n);%各代最佳路线各代最佳路线L_best=inf.*ones(NC_max,1);%各代最佳路线的长度各代最佳路线的长度L_ave=zeros(NC_max,1);%各代路线的平均长度各代路线的平均长度现在学习的是第23页，共34页for NC=1:NC_max%第二步：循环变量迭代。停止条件之一：达到最大迭代第二步：循环变量迭代。停止条件之一：达到最大迭代次数次数%将将m只蚂蚁放到只蚂蚁放到n个城市上个城市上 Randpos=;for i=1:(ceil(m/n)R
20、andpos=Randpos,randperm(n);end Tabu(:,1)=(Randpos(1,1:m);for j=2:n for i=1:m%第三、四步：蚂蚁标号迭代第三、四步：蚂蚁标号迭代 visited=Tabu(i,1:(j-1);%已访问的城市已访问的城市 J=zeros(1,(n-j+1);%待访问的城市待访问的城市 P=J;%待访问城市的选择概率分布待访问城市的选择概率分布 Jc=1;for k=1:n if length(find(visited=k)=0 J(Jc)=k;Jc=Jc+1;end end 现在学习的是第24页，共34页%第五步：计算可选节点的选择概率第
21、五步：计算可选节点的选择概率 for k=1:length(J)P(k)=(Tau(visited(end),J(k)Alpha).*(Eta(visited(end),J(k)Beta);end P=P/(sum(P);%第五步续：按最大概率选取节点第五步续：按最大概率选取节点 Pcum=cumsum(P);Select=find(Pcum=rand);to_visit=J(Select(1);%第六步：更新禁忌表第六步：更新禁忌表 Tabu(i,j)=to_visit;end%i end%j 现在学习的是第25页，共34页%第七步：第七步：i,j循环循环 if NC=2 Tabu(1,:)
22、=R_best(NC-1,:);end%记录本次迭代最佳路线记录本次迭代最佳路线 L=zeros(m,1);for i=1:m R=Tabu(i,:);for j=1:(n-1)L(i)=L(i)+D(R(j),R(j+1);end L(i)=L(i)+D(R(1),R(n);end L_best(NC)=min(L);pos=find(L=L_best(NC);R_best(NC,:)=Tabu(pos(1),:);L_ave(NC)=mean(L);现在学习的是第26页，共34页%第八步：更新信息素第八步：更新信息素 Delta_Tau=zeros(n,n);for i=1:m for j
23、=1:(n-1)Delta_Tau(Tabu(i,j),Tabu(i,j+1).=Delta_Tau(Tabu(i,j),Tabu(i,j+1)+Q/L(i);end Delta_Tau(Tabu(i,n),Tabu(i,1).=Delta_Tau(Tabu(i,n),Tabu(i,1)+Q/L(i);end Tau=(1-Rho).*Tau+Delta_Tau;%第九步：禁忌表清零第九步：禁忌表清零 Tabu=zeros(m,n);end现在学习的是第27页，共34页%第九步续：完成，输出结果第九步续：完成，输出结果Pos=find(L_best=min(L_best);Shortest_R
24、oute=R_best(Pos(1),:);Shortest_Length=L_best(Pos(1);subplot(1,2,1);DrawRoute(C,Shortest_Route);subplot(1,2,2);plot(L_best);hold on;plot(L_ave);现在学习的是第28页，共34页说明：图中左图是找出的最短路径，其中圆点表示城市，横纵轴表示坐标。图中右图横坐标说明：图中左图是找出的最短路径，其中圆点表示城市，横纵轴表示坐标。图中右图横坐标表示迭代次数表示迭代次数(算法一共执行的次数算法一共执行的次数)，纵轴表示路径长度。其中图中下面线是表示在蚁群算，纵轴表示路
25、径长度。其中图中下面线是表示在蚁群算法中，分别迭代法中，分别迭代k k次，在次，在m m条路径中最短的一条路径长度，上面线是表示在条路径中最短的一条路径长度，上面线是表示在m m调路径中平均路径调路径中平均路径的长度。的长度。现在学习的是第29页，共34页四、数据挖掘技术（支持向量机算法）四、数据挖掘技术（支持向量机算法）数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据集中识别新颖的、潜在有用的以及最终可理解的非平的数据集中识别新颖的、潜在有用的以及最终可理解的非平凡模式和知识的过程。它是一门涉及面很广的交叉学科，包凡模式和知识的过
26、程。它是一门涉及面很广的交叉学科，包括机器学习、数理统计、神经网络、数据库、模式识别、粗括机器学习、数理统计、神经网络、数据库、模式识别、粗糙集、模糊数学等相关技术。糙集、模糊数学等相关技术。V.VapnikV.Vapnik等人从二十世纪六、七十年代开始致力于统计学习理等人从二十世纪六、七十年代开始致力于统计学习理论方面的研究，到九十年代中期，随着该理论的不断发展和成熟，论方面的研究，到九十年代中期，随着该理论的不断发展和成熟，也由于神经网络等学习方法在理论上缺乏实质性进展，统计学习也由于神经网络等学习方法在理论上缺乏实质性进展，统计学习理论开始受到越来越广泛的重视。同时，在这一理论的基础上发
27、理论开始受到越来越广泛的重视。同时，在这一理论的基础上发展了一种新的通用学习方法，即为支持向量机展了一种新的通用学习方法，即为支持向量机(Support Vector(Support Vector MachineMachine或或SVM)SVM)。现在学习的是第30页，共34页支持向量机的训练算法的基本模型支持向量机的训练算法的基本模型 现在学习的是第31页，共34页用于分类问题的支持向量机算法用于分类问题的支持向量机算法Step1 设已知训练样本集设已知训练样本集 ,期望输出期望输出 ,;Step2 选择核函数和惩罚参数选择核函数和惩罚参数C,构造并求解最优化构造并求解最优化问题问题 的最优解的最优解 ;现在学习的是第32页，共34页Step3 选择选择 ，一个小于，一个小于C的正分量的正分量 ,并据此计算并据此计算 ;Step4 求决策函数求决策函数 现在学习的是第33页，共34页概括地说概括地说,支持向量机就是首先通过内积函支持向量机就是首先通过内积函数定义的非线性变换将输入空间变换到一数定义的非线性变换将输入空间变换到一个高维空间个高维空间,在这个空间中在这个空间中(广义广义)最优分最优分类面类面.最后根据最后根据f(x)f(x)的符号来确定输入样本的符号来确定输入样本的归属。的归属。现在学习的是第34页，共34页