现代计算方法讲座

现代计算方法专题 提纲 进化计算方法 遗传算法 人工神经网络蚁群智能计算数据挖掘技术与方法 支持向量机 背景介绍 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 主要符号说明 Cn个城市的坐标 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 待访问城市的选择概率分布Jc 1 fork 1 niflength find visited k 0J Jc k Jc Jc 1 endend 第五步 计算可选节点的选择概率fork 1 length J P k Tau visited end J k Alpha Eta visited end J k Beta endP P sum P 第五步续 按最大概率选取节点Pcum cumsum P Select find Pcum rand to visit J Select 1 第六步 更新禁忌表Tabu i j to visit end iend j 第七步 i j循环ifNC 2Tabu 1 R best NC 1 end 记录本次迭代最佳路线L zeros m 1 fori 1 mR Tabu i forj 1 n 1 L i L i D R j R j 1 endL i L i D R 1 R n endL best NC min L pos find L L best NC R best NC Tabu pos 1 L ave NC mean L 第八步 更新信息素Delta Tau zeros n n fori 1 mforj 1 n 1 Delta Tau Tabu i j Tabu i j 1 Delta Tau Tabu i j Tabu i j 1 Q L i endDelta Tau Tabu i n Tabu i 1 Delta Tau Tabu i n Tabu i 1 Q L i endTau 1 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 holdon plot L ave 说明 图中左图是找出的最短路径 其中圆点表示城市 横纵轴表示坐标 图中右图横坐标表示迭代次数 算法一共执行的次数 纵轴表示路径长度 其中图中下面线是表示在蚁群算法中 分别迭代k次 在m条路径中最短的一条路径长度 上面线是表示在m调路径中平均路径的长度 四 数据挖掘技术 支持向量机算法 数据挖掘是从大量的 不完全的 有噪声的 模糊的 随机的数据集中识别新颖的 潜在有用的以及最终可理解的非平凡模式和知识的过程 它是一门涉及面很广的交叉学科 包括机器学习 数理统计 神经网络 数据库 模式识别 粗糙集 模糊数学等相关技术 V Vapnik等人从二十世纪六 七十年代开始致力于统计学习理论方面的研究 到九十年代中期 随着该理论的不断发展和成熟 也由于神经网络等学习方法在理论上缺乏实质性进展 统计学习理论开始受到越来越广泛的重视 同时 在这一理论的基础上发展了一种新的通用学习方法