现代计算方法概论

现代计算方法专题提纲进化计算方法（遗传算法）人工神经网络蚁群智能计算数据挖掘技术与方法（支持向量机）背景介绍

21世纪，系统生物学的诞生进一步提升了后基因组时代的生命科学研究能力。正如胡德所说：“系统生物学将是21世纪医学和生物学的核心驱动力。”

生物学世纪的两桩令人瞩目的科学事件◆1994年,美国科学家Adelman在Science上发表了第一篇用DNA分子的生化反应进行计算并解决人类数学问题的开创性文章。这个事件则向人们揭示，生命体也是计算的主体，不仅人、动物甚至更简单的生命物质也会进行计算，例如细胞核DNA份子也可以是计算的主体。◆

2003年,人类染色体的DNA全序列测序完成，从此人类有了自己的遗传密码。这件事告诉人们生命体是计算的产物，这种计算依赖的数据和计算程序的编码隐藏在人类已测定的30亿个碱基对中。

进入21世纪短短的10年，向生命世界学习计算的思想悄然在科学界传播开来，形成新的计算主义。一、进化计算方法（遗传算法）两种力量导致了生物进化的产生，构成进化的基本要素：变异与选择。根据现代生物进化理论，所有的生物体的特征及其变化都受到基因的控制，并将自己的基因拷贝给子女，这就是遗传密码。自然选择是对生物的表现型的选择遗传变异是基因型中某个遗传密码形成突变，或者遗传密码进行重新组合。

在模仿进化原理而形成的仿生计算中最基础与典型的算法就是遗传算法(GeneticAlgorithm)遗传算法是JohnHolland开发的一种进化算法遗传算法的基本操作：

Step1将问题求解的对象编码成由基因组成的染色体；

Step2设计杂交和变异规则；

Step3设计适应值函数并进行遗传操作。

GA的形式化定义记为抽象的个体，为所有字符长度为的二进制串的集合。种群表示为个个体的一个组，记为，定义适应值函数(实数)，称为个体的适应值。选择操作的算子定义为；杂交操作的算子；变异操作的算子。定义为杂交概率，为变异概率，则一下七元组就定义了一个遗传运算（即为一个特定的GA）

案例实例目标函数作图，Matlab程序

x=-1:0.01:2;y=x.*sin(10*pi*x)+2.0;plot(x,y);gridon;二、人工神经网络早在20世纪上半叶开始了这个领域的研究，在多半个世纪的发展中成为无论在理论还是应用方面都日趋成熟的仿生计算分支。神经网络具有学习功能，其学习也称训练。神经网络能够从环境中学习，从而以新的方式对环境的变化作出反应时神经网络最有意义的性质。1949年Hebb提出了最著名的经典学习规则，称为Hebb学习规则，用于调整神经网络的突触权值。

人工神经网络是大量模拟神经元互连而成的网络，

是人脑的抽象、简化、模拟，反映人脑的基本特征。ANN模型具有下面三个要素：◆具有一组突触连接，用表示神经元与的联结强度，或称为权值，但ANN的权值可取正与负值。◆具有反映生物神经元时空整合功能的输入信号累加器。◆具有一个激励函数，勇于转换神经元的输出。激励函数将输出信号压缩(限制)形成一个范围的有限值。

人工神经网络的基本方法Step1设计神经网络结构，特别是学习方法；Step2利用训练集求解神经网络参数；Step3对已有参数进行计算并学习修正网络参数。案例人工神经网络模型中激励函数Sigmoid图像，Matlab程序如下：v=-10:0.1:10;a=.5;f=1./(1+exp(-a*v));plot(v,f,'red');holdon;%another'a':a=.8;f=1./(1+exp(-a*v));plot(v,f,'blue');%oncemore:a=2;f=1./(1+exp(-a*v));plot(v,f,'green');

◆1943年，神经生物学家W.McCullch和数学家W.Pitts在著名的论文《神经活动内容概念的逻辑演算》中总结生物神经元的基本生理特征，提出了第一个神经计算模型，即神经元的阈值元件模型，简称MP模型。

◆1949年，加拿大心理学家DoualdHebb在他的论著《行为的组织》一文中，对大脑神经元的学习与条件反射做了大胆假设：如果两个神经元都处于兴奋激活状态，那么彼此的突出联结权机会得到加强。这就是著名的Hebb学习规则。

◆Rochester,JohnHolland与IBM公司的研究人员合作以网络吸收经验来调节强度模拟了Hebb的学习规则，并在计算机上实现了学习，产生了许多涌现现象，使计算机有了类似人脑的学习功能。

三、蚁群智能计算

生物群体的行为反应了生物的集群智能，例如鸟群飞行的自动队列、鱼群在游动中交换位置、细胞群有序地传播信息等，表现出十分有效的群体决策能力。各种不同的集群智能现象启发人们产生不同的模仿集群智能的算法，例如蚁群算法、粒子群算法、元胞自动机算法等。蚁群算法的基本假设◆蚂蚁之间通过信息素和环境进行通信，每只蚂蚁只根据其邻近的局部环境做出反应，并发生影响。◆蚂蚁对环境的反应由其自身原因决定。由于生物的基因学说，可以认为实际上是其基因的适应性表现，即蚂蚁是对环境反应的表现型主体。◆

在个体水平上每只蚂蚁仅根据环境作独立选择，而在群体水平上单只蚂蚁的行为是随机的，但是蚂蚁可通过关联性，自组织地形成高度有序的群体行为。蚁群算法的基本模型设计Step1将问题求解的目标编译成空间路径的图问题；Step2设计抽象蚂蚁的行为规则、状态转移规则、信息更新规则；Step3迭代终止条件设定。案例

问题描述：设有n个城市，坐标已知，n个城市构成一个完全图，利用蚁群算法找出从一个城市出发走遍每个城市，并且不重复到达任一个城市的最短路径。

实现该问题的程序function[R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=...ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)%%=====================================================================%ACATSP.m%AntColonyAlgorithmforTravelingSalesmanProblem%%---------------------------------------------------------------------%主要符号说明：%C n个城市的坐标，n×2的矩阵%NC_max 最大迭代次数%m 蚂蚁个数%Alpha 表征信息素重要程度的参数%Beta 表征启发式因子重要程度的参数%Rho 信息素蒸发系数%Q 信息素增加强度系数%R_best 各代最佳路线%L_best 各代最佳路线的长度%%=================================================%第一步：参数初始化：n=size(C,1);%n表示问题的规模（城市个数）D=zeros(n,n);%D表示完全图的赋权邻接矩阵fori=1:nforj=1:nifi~=j%计算距离D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;elseD(i,j)=eps;endD(j,i)=D(i,j);end%jend%uEta=1./D;%Eta为启发因子，这里设为距离的倒数Tau=ones(n,n);%Tau为信息素矩阵Tabu=zeros(m,n);%存储并记录路径的生成R_best=zeros(NC_max,n);%各代最佳路线L_best=inf.*ones(NC_max,1);%各代最佳路线的长度L_ave=zeros(NC_max,1);%各代路线的平均长度forNC=1:NC_max%第二步：循环变量迭代。停止条件之一：达到最大迭代次数%将m只蚂蚁放到n个城市上Randpos=[];fori=1:(ceil(m/n))Randpos=[Randpos,randperm(n)];endTabu(:,1)=(Randpos(1,1:m))';forj=2:nfori=1:m%第三、四步：蚂蚁标号迭代

visited=Tabu(i,1:(j-1));%已访问的城市J=zeros(1,(n-j+1));%待访问的城市P=J;%待访问