1、概述人工神经网络(Artificial Neural Network)遗传算法禁忌搜索算法模拟退火算法蚁路算法精品资料 你怎么称呼老师？如果老师最后没有总结一节课的重点的难点，你是否会认为老师的教学方法需要改进？你所经历的课堂，是讲座式还是讨论式？教师的教鞭“不怕太阳晒，也不怕那风雨狂，只怕先生骂我笨，没有学问无颜见爹娘”“太阳当空照，花儿对我笑，小鸟说早早早”现代优化方法包括人工神经网络、遗传算法、禁忌搜索算法、模拟退火算法、蚁路算法等；这些算法是根据一些直观基础而构建的，我们把它称之为启发式算法，有人称现代优化算法主要指仿生算法；牵涉到的学科广泛 生物进化、人工智能、数学和物理、神经系统和
2、统计力学等。这些算法和人工智能、计算机科学和运筹学相融合。计算复杂性与传统算法的局限旅行商问题：一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为dij，如何选择一条道路使得商人每个城市走一遍后回到起点且所走路径最短。对称距离 非对称距离采用枚举法来解决非对称旅行商问题假定有n个城市，共需要(n-1)!次枚举，假定完成25个城市的总距离的计算及比较需要1秒，则当城市增加时，需要的时间如下表所示：城市数城市数24242525262627272828292930303131时间1s24s10m4.3h4.9d136.5d10.8y325y人类对人工智能的研究可以分成两种方式对应着两种不同的
3、技术：传统的人工智能技术心理的角度模拟 基于人工神经网络的技术生理的角度模拟人工神经网络的定义 是由人工神经元互联组成的网络，从微观结构和功能上对人脑的抽象、简化，是模拟人类智能的一条重要途径。反映了人脑功能的若干基本特征，如，并行信息处理、学习、联想、模式分类、记忆等。简单地讲，它是一个数学模型，可以用电子线路来实现，也可以用计算机程序来模拟，是人工智能研究的一种方法。智能的含义 智能是个体有目的的行为，合理的思维，以及有效的、适应环境的综合能力。智能是个体认识客观事物和运用知识解决问题的能力。人类个体的智能是一种综合能力。智能的概念的八个方面人工智能：研究如何使类似计算机这样的设备去模拟人
4、类的这些能力。研究人工智能的目的 增加人类探索世界，推动社会前进的能力 进一步认识自己联接主义观点 核心：智能的本质是联接机制。神经网络是一个由大量简单的处理单元组成的高度复杂的大规模非线性自适应系统ANN力求从四个方面去模拟人脑的智能行为 物理结构 计算模拟 存储与操作 训练物理符号系统和人工神经网络系统的差别物理符号系统物理符号系统人工神经网络人工神经网络处理方式 逻辑运算模拟运算执行方式 串行并行动作离散连续存储局部集中全局分布两种人工智能技术的比较传统的传统的AIAI技术技术ANNANN技术技术基本实现方式串行处理；由程序实现控制并行处理；对样本数据进行多目标学习；通过人工神经元之间的
5、相互作用实现控制基本开发方法设计规则、框架、程序；用样本数据进行调试（由人根据已知的环境去构造一个模型）定义人工神经网络的结构原型，通过样本数据，依据基本的学习算法完成学习自动从样本数据中抽取内涵（自动适应应用环境）设计规则、框架、程序；用样本数据进行调试（由人根据已知的环境去构造一个模型）适应领域符号处理，数值计算模拟处理，感觉，大规模数据并行处理模拟对象左脑（逻辑思维）右脑（形象思维）信息的分布表示运算的全局并行和局部操作处理的非线性人工神经网络可以根据所在的环境去改变它的行为自相联的网络异相联的网络：它在接受样本集合A时，可以抽取集合A中输入数据与输出数据之间的映射关系。“抽象”功能。不
6、同的人工神经网络模型，有不同的学习/训练算法基本特征的自动提取由于其运算的不精确性，表现成“去噪音、容残缺”的能力，利用这种不精确性，比较自然地实现模式的自动分类。泛化（Generalization）能力与抽象能力信息的分布存提供容错功能 由于信息被分布存放在几乎整个网络中，所以，当其中的某一个点或者某几个点被破坏时，信息仍然可以被存取。系统在受到局部损伤时还可以正常工作。并不是说可以任意地对完成学习的网络进行修改。也正是由于信息的分布存放，对一类网来说，当它完成学习后，如果再让它学习新的东西，这时就会破坏原来已学会的东西。擅长两个方面：对大量的数据进行分类，并且只有较少的几种情况；必须学习一
7、个复杂的非线性映射。目前应用：人们主要将其用于语音、视觉、知识处理、辅助决策等方面。在数据压缩、模式匹配、系统建模、模糊控制、求组合优化问题的最佳解的近似解（不是最佳近似解）等方面也有较好的应用。萌芽期（20世纪40年代）人工神经网络的研究最早可以追溯到人类开始研究自己的智能的时期，到1949年止。1943年，心理学家McCulloch和数学家Pitts建立起了著名的阈值加权和模型，简称为M-P模型。发表于数学生物物理学会刊Bulletin of Mathematical Biophysics1949年，心理学家D.O.Hebb提出神经元之间突触联系是可变的假说Hebb学习律。第一高潮期（19
8、501968）以Marvin Minsky，Frank Rosenblatt，BernardWidrow等为代表人物，代表作是单级感知器（Perceptron）。可用电子线路模拟。人们乐观地认为几乎已经找到了智能的关键。许多部门都开始大批地投入此项研究，希望尽快占领制高点。反思期（19691982）M.L.Minsky和S.Papert，Perceptron，MIT Press，1969年异或”运算不可表示二十世纪70年代和80年代早期的研究结果认识规律：认识实践再认识第二高潮期（19831990）1982年，J.Hopfield提出循环网络 用Lyapunov函数作为网络性能判定的能量函数，
9、建立ANN稳定性的判别依据 阐明了ANN与动力学的关系 用非线性动力学的方法来研究ANN的特性 指出信息被存放在网络中神经元的联接上1984年，J.Hopfield设计研制了后来被人们称为Hopfield网的电路。较好地解决了著名的TSP问题，找到了最佳解的近似解，引起了较大的轰动。第二高潮期（19831990）1985年，UCSD的Hinton、Sejnowsky、Rumelhart等人所在的并行分布处理（PDP）小组的研究者在Hopfield网络中引入了随机机制，提出所谓的Boltzmann机。1986年，并行分布处理小组的Rumelhart等研究者重新独立地提出多层网络的学习算法BP算法
10、，较好地解决了多层网络的学习问题。再认识与应用研究期（1991）问题：应用面还不够宽 结果不够精确 存在可信度的问题。人的思维由脑完成 人脑约由10111012个神经元组成，每个神经元约与104105个神经元联接，能接受并处理信息。因此，人脑是复杂的信息并行加工处理巨系统。人脑可通过自组织、自学习，不断适应外界环境的变化。其自组织、自学习性来源于神经网络结构的可塑性，主要反映在神经元之间联接强度的可变性上。人(或其它生物)的神经网络示意图一个神经元通过晶枝(dendrite)接收到信息后，它对这些信息进行处理，并通过它所控制的触突(synapse)传给其它神经元。神经元的六个基本特征：神经元及
11、其联接；神经元之间的联接强度决定信号传递的强弱；神经元之间的联接强度是可以随训练改变的；信号可以是起刺激作用的，也可以是起抑制作用的；一个神经元接受的信号的累积效果决定该神经元的状态；每个神经元可以有一个“阈值”。人工神经元神经元是构成神经网络的最基本单元（构件）。人工神经元模型应该具有生物神经元的六个基本特性。单层神经网络的结构(转自Matlab帮助文件)有些教材把它称为两层结构多层神经网络的结构(转自Matlab帮助文件)Hopfield网络(反馈型结构)其它网络结构人工神经网络计算过程示意图神经网络在目前已有几十种不同的模型。通常可按5个原则进行神经网络的归类。按照网络的结构区分，则有前
12、向网络和反馈网络。按照学习方式区分，则有有教师学习和无教师学习网络。按照网络性能区分，则有连续型和离散性网络，随机型和确定型网络。按照突触性质区分，则有一阶线性关联网络和高阶非线性关联网络。按对生物神经系统的层次模拟区分，则有神经元层次模型，组合式模型，网络层次模型，神经系统层次模型和智能型模型。常见的神经网络类型及应用名称名称典应用型典应用型Perception感知器文字识别、分类问题、声音识别Back Propagation反向传播网络评估、预测、识别等包含有各种优化算法来实现它。自组织网络分类问题Hopfield网络TSP问题生物进化的规律：选择、遗传和变异。借鉴了生物进化的特征，其主要
13、特征为：进化发生在解的编码上(染色体)人为地构造函数使好的染色体的后代数超过平均数 染色体保持父母的特征 染色体会产生变异生物遗传概念遗传算法中的作用适者生存算法终止时，有可能得到最优解个体解染色体解的编码基因解中每一分量的特征(如各分量的值)适应性适应函数值群体选定的一组解种群根据适应函数选定一组解交配通过交叉原则产生的一组新的解变异编码的某个分量发生变化的过程生物遗传概念和遗传算法中的概念比较例：用遗传算法求f(x)=x2，0 x31，x为整数的最大值用五位二进制编码00000，1000016，1111131五位字符串称为染色体，每位称为基因，每个基因有两种状态0,1首先产生一个随机群体，
14、如4个(通常取偶数个)x1=00000,x2=11001,x3=01111,x4=01000适应函数fitness(xi)=f(x)=x2fitness(x1)=0,fitness(x2)=252,fitness(x3)=152,fitness(x4)=82定义第i个个体入选种群的概率为适应值大的染色体生存的概率较大()()()iijjfitness xp xfitness x假若要产生四个个体，则根据各个体的概率，有可能是如下结构：2个11001,1个01111,1个10000采用如下方式交配21322344(11001)(11111)(01111)(01001)(11001)(11000)
15、(01000)(01001)xyxyxyxy若y4的第一个基因发生变异，则y4=11001如满足停止规则，则结束，否则重新计算适应度函数，继续上述过程。应用：各种NP-Hard优化问题为了找到“全局最优解”，就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索，导致一叶障目，不见泰山。禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它（但不是完全隔绝），从而获得更多的搜索区间。兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。当兔子们再寻找的时候，一般地会有意识地避开泰山
16、，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表（tabu list）”的含义。那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度（tabu length）”；如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个有兔子留守的地方优越性太突出，超过了“best to far”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，
17、这就叫“特赦准则（aspiration criterion）”。这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里。应用：TSP问题温度、能量、概率分布间的关系由统计力学表明，在温度T，分子停留在状态r满足Boltzmann概率分布：在同一温度，分子停留在能量小状态的概率比停留在能量大状态的概率要大。在最小能量状态下，概率关于温度T是单调下降的。温度趋向0时，分子停留在最低能量状态的概率趋向1。()1PrBE rk TEE reZ T1982年,KirkPatrick将退火思想引入组合优化领域，提出一种解大规模组合优化问题的算法，对NP完全组合优化问题尤其有效。这源于固体的
18、退火过程，即先将温度加到很高,再缓慢降温(即退火)，使达到能量最低点。如果急速降温(即为淬火)则不能达到最低点。组合优化问题与退火进行比较组合优化问题组合优化问题退火问题退火问题解状态最优解能量最低的状态费用函数能量模拟退火算法可以分解为解空间、目标函数和初始解三部分。模拟退火的基本思想:初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L对k=1，L做第(3)至第6步：产生新解S计算增量t=C(S)-C(S)，其中C(S)为评价函数若t0，然后转第2步。模拟退火算法的应用很广泛，可以较高的效率求解最大截问题(Max Cut Problem)、0-1背包问题(Z
19、ero One Knapsack Problem)、图着色问题(Graph Colouring Problem)、调度问题(Scheduling Problem)等等。蚂蚁在觅食过程中，会分泌一种化学物质，称为信息素(pheromone)。某种特殊的信息素被用于标记路径信息。某些蚂蚁通过其他蚂蚁释放的路径信息素来寻找到食物。双桥实验由于正反馈机制，所有的蚂蚁最终会选择某一条路径对两条桥路径长度相同的情况，选择两条路径的概率相同对两条路径长度不同的情况，较短路径有较大的概率。路径探索尽管由于正反馈存在，不是所有的蚂蚁都选择同一条路径，这种行为称为“路径探索”。学习和忘记尽管增加了较短的路径，但蚂蚁仍然选择较长路径应用：车间作业调度TSP问题布局优化故障诊断聚类分析、数据挖掘
