《现代计算方法专题讲座培训教材》由会员分享，可在线阅读，更多相关《现代计算方法专题讲座培训教材（34页珍藏版）》请在金锄头文库上搜索。
1、现代计算方法专题讲座,提纲,进化计算方法（遗传算法） 人工神经网络 蚁群智能计算 数据挖掘技术与方法（支持向量机）,背景介绍,21世纪，系统生物学的诞生进一步提升了后基因组时代的生命科学研究能力。正如胡德所说：“系统生物学将是21世纪医学和生物学的核心驱动力。”,进入21世纪短短的10年，向生命世界学习计算的思想悄然在科学界传播开来，形成新的计算主义。,一、进化计算方法（遗传算法）,两种力量导致了生物进化的产生，构成进化的基本要素：变异与选择。 根据现代生物进化理论，所有的生物体的特征及其变化都受到基因的控制，并将自己的基因拷贝给子女，这就是遗传密码。 自然选择是对生物的表现型的选择遗传变异是
2、基因型中某个遗传密码形成突变，或者遗传密码进行重新组合。,在模仿进化原理而形成的仿生计算中最基础与典型的算法就是遗传算法(Genetic Algorithm) 遗传算法是John Holland开发的一种进化算法 遗传算法的基本操作： Step 1 将问题求解的对象编码成由基因组成的染色体； Step 2 设计杂交和变异规则； Step 3 设计适应值函数并进行遗传操作。,GA的形式化定义,记 为抽象的个体， 为所有字符长度为 的二进制串的集合。种群 表示为 个个体的一个组，记为 ，定义适应值函数 (实数)， 称为个体的适应值。选择操作的算子定义为 ；杂交操作的算子 ；变异操作的算子 。定义
3、为杂交概率， 为变异概率，则一下七元组就定义了一个遗传运算（即为一个特定的GA）,案例,实例目标函数作图，Matlab程序 x = -1: 0.01: 2; y = x .* sin(10*pi * x) + 2.0; plot(x, y); grid on;,二、人工神经网络,早在20世纪上半叶开始了这个领域的研究，在多半个世纪的发展中成为无论在理论还是应用方面都日趋成熟的仿生计算分支。 神经网络具有学习功能，其学习也称训练。神经网络能够从环境中学习，从而以新的方式对环境的变化作出反应时神经网络最有意义的性质。 1949年Hebb提出了最著名的经典学习规则，称为Hebb学习规则，用于调整神经
4、网络的突触权值。,人工神经网络是大量模拟神经元互连而成的网络， 是人脑的抽象、简化、模拟，反映人脑的基本特征。ANN模型具有下面三个要素：,具有一组突触连接，用表示神经元与的联结强度，或称为权值，但ANN的权值可取正与负值。 具有反映生物神经元时空整合功能的输入信号累加器。 具有一个激励函数，勇于转换神经元的输出。激励函数将输出信号压缩(限制)形成一个范围的有限值。,人工神经网络的基本方法,Step 1 设计神经网络结构，特别是学习方法； Step 2 利用训练集求解神经网络参数； Step 3 对已有参数进行计算并学习修正网络参数。,案例,人工神经网络模型中激励函数Sigmoid图像 ，Ma
5、tlab程序如下 ： 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); % once more: a = 2; f = 1./(1 + exp(-a * v); plot(v, f, green);,1943年，神经生物学家W.McCullch和数学家W.Pitts在著名的论文神经活动内容概念的逻辑演算中总结生物神经元的基本生理特征，提出了第一个神经计算模型，即神经
6、元的阈值元件模型，简称MP模型。 1949年，加拿大心理学家Douald Hebb在他的论著行为的组织一文中，对大脑神经元的学习与条件反射做了大胆假设：如果两个神经元都处于兴奋激活状态，那么彼此的突出联结权机会得到加强。这就是著名的Hebb学习规则。 Rochester, John Holland与IBM公司的研究人员合作以网络吸收经验来调节强度模拟了Hebb的学习规则，并在计算机上实现了学习，产生了许多涌现现象，使计算机有了类似人脑的学习功能。,三、蚁群智能计算,生物群体的行为反应了生物的集群智能，例如鸟群飞行的自动队列、鱼群在游动中交换位置、细胞群有序地传播信息等，表现出十分有效的群体决策
7、能力。各种不同的集群智能现象启发人们产生不同的模仿集群智能的算法，例如蚁群算法、粒子群算法、元胞自动机算法等。,蚁群算法的基本假设, 蚂蚁之间通过信息素和环境进行通信，每只蚂蚁只根据其邻近的局部环境做出反应，并发生影响。 蚂蚁对环境的反应由其自身原因决定。由于生物的基因学说，可以认为实际上是其基因的适应性表现，即蚂蚁是对环境反应的表现型主体。 在个体水平上每只蚂蚁仅根据环境作独立选择，而在群体水平上单只蚂蚁的行为是随机的，但是蚂蚁可通过关联性，自组织地形成高度有序的群体行为。,蚁群算法的基本模型设计,Step 1 将问题求解的目标编译成空间路径的图问题； Step 2 设计抽象蚂蚁的行为规则、
8、状态转移规则、信息更新规则； Step 3 迭代终止条件设定。,案例,问题描述：设有n个城市，坐标已知，n个城市构成一个完全图，利用蚁群算法找出从一个城市出发走遍每个城市，并且不重复到达任一个城市的最短路径。,实现该问题的程序,function R_best, L_best, L_ave, Shortest_Route, Shortest_Length =. ACATSP(C, NC_max, m, Alpha, Beta, Rho,Q) %= % ACATSP.m % Ant Colony Algorithm for Traveling Salesman Problem %- % 主要符号说
9、明： % Cn个城市的坐标，n2的矩阵 % NC_max最大迭代次数 % m蚂蚁个数 % Alpha表征信息素重要程度的参数 % Beta表征启发式因子重要程度的参数 % Rho信息素蒸发系数 % Q信息素增加强度系数 % R_best各代最佳路线 % L_best各代最佳路线的长度 %=,% 第一步：参数初始化： 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(
10、i,2)-C(j,2)2 )0.5; else D(i, j) = eps; end D(j, i) = D(i, j); end % j end % u Eta = 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); % 各代路线的平均长度,for N
11、C = 1: NC_max %第二步：循环变量迭代。停止条件之一：达到最大迭代次数 % 将m只蚂蚁放到n个城市上 Randpos = ; for i = 1: ( ceil(m/n) ) Randpos = 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;
12、 for k = 1: n if length( find(visited = k) ) = 0 J(Jc) = k; Jc = Jc + 1; end end,% 第五步：计算可选节点的选择概率 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)
13、 ); % 第六步：更新禁忌表 Tabu(i, j) = to_visit; end % i end % j,% 第七步：i, j循环 if NC = 2 Tabu(1, :) = 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)
14、; R_best(NC, :) = Tabu(pos(1), :); L_ave(NC) = mean(L);,% 第八步：更新信息素 Delta_Tau = zeros(n, n); for i = 1: m for j = 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-
15、Rho) .* Tau + Delta_Tau; % 第九步：禁忌表清零 Tabu = zeros(m, n); end,% 第九步续：完成，输出结果 Pos = find(L_best = min(L_best); Shortest_Route = 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);,说明：图中左图是找出的最短路径，其中圆点表示城市，横纵轴表示坐标。图中右图横坐标表示迭代次数(算法一共执行的次数)，纵轴表示路径长度。其中图中下面线是表示在蚁群算法中，分别迭代k次，在m条路径中最短的一条路径长度，上面线是表示在m
