1关于计算智能（关于计算智能（Computational Intelligence, CI）l1。92年，美国学者James首次提出：计算智能(CI)是依靠生产者提供的数字、数据材料进行加工处理，而不是依赖于知识；人工智能（Artificial Intelligence, AI）则是须用知识进行处理。l2。94年，James在Florida, Orlando, 94IEEEE WCCI会议上又阐述他的观点，智能有三个层次2生物智能（Biological Intelligence, BI）l由人脑的物理化学过程反映出来的，人脑是有机物，它是智能的基础。人工智能（人工智能（Artificial Intelligence, AIArtificial Intelligence, AI） l l是非生物的，人造的，常用符号来表示，AIAI的来源是人类知识的精华。的来源是人类知识的精华。 计算智能（计算智能（Computational Intelligence, CIComputational Intelligence, CI） l l是由数学方法和计算机实现的，是由数学方法和计算机实现的，CICI的来源数的来源数值计算的传感器。值计算的传感器。33 3。关系：。关系：从复杂性来看，从复杂性来看，BI AI CIBI AI CI ； 从所属关从所属关系来看，系来看， BI BI ）AI AI ）CICI； AIAI是是CICI到到BIBI的过渡，的过渡，因为因为AIAI中除计算算法之外，还包括符号表示中除计算算法之外，还包括符号表示及数值信息处理。模糊集合和模糊逻辑是及数值信息处理。模糊集合和模糊逻辑是AIAI到到CICI的过渡。的过渡。l l 也有些人认为也有些人认为CICI不属于不属于AIAI，仅有部分重合。，仅有部分重合。 l l AIAI：符号主义，知识、规则、推理，：符号主义，知识、规则、推理，左脑左脑 l l CICI：连接主义，数据、学习、记忆，：连接主义，数据、学习、记忆，右脑右脑41、神经计算2、模糊计算3、粗糙集理论4、 遗传算法5、进化策略与编程6、人工生命7、粒群优化8、蚁群算法9、自然计算10、免疫计算目前计算智能的研究内容目前计算智能的研究内容5人工神经网络的基本模型人工神经网络的基本模型 l1生物神经元l2人工神经元的形式化模型l3人工神经网络模型l4人工神经网络的学习规则61、生、生 物物 神神 经经 元元l1.1神经元的结构l1.2膜电位与神经元的兴奋71.1 神经元的结构神经元的结构本体：本体：细胞体（细胞膜、质、核），对输入信号进行处理，相当于CPU。树突：树突：本体向外伸出的分支，多根，长1mm左右，本体的输入端。轴突：轴突：本体向外伸出的最长的分支，即神经纤维，一根，长1cm1m左右，通过轴突上的神经末梢将信号传给其它神经元，相当于本体的输出端。 突触：突触：各神经元之间轴突和树突之间的接口，即神经末梢与树突相接触的交界面，每个细胞体大约有103104个突触。突触有兴奋型和抑制型两种。8l神神 经经 元元 结结 构构91.2 膜电位与神经元的兴奋膜电位与神经元的兴奋膜电位：膜电位：细胞膜将细胞分为内外两部分，当外部电位为0时，称内部电位为膜电位。 静止膜电位：静止膜电位：当没有输入信号时的膜电位成为静止膜电位，通常为-70mv左右。兴奋状态：兴奋状态：当外部有输入信号时，将使膜电位发生变化，倘若使膜电位升高，比静止膜电位高15mv以上，即超过-55mv（阈值），神经元被激活，内部电位急剧上升至100mv左右，并维持约1ms，然后急剧下降。相当输出一个100mv高1ms宽的脉冲，并沿轴突以100m/s的速度传至其它的神经元。10抑制状态：抑制状态：当外部输入信号使膜电位下降低于阈值电位时，神经元处于抑制状态，无脉冲输出。“兴奋抑制”状态满足“01”律A/D转换：转换：电脉冲到达各突触接口后，放出某种化学物质，该物质作用于各个和其相连的神经元的细胞膜，并使其膜电位发生变化，完成了将离散的脉冲信号转换为连续变化的电位信号。11时间加算功能：时间加算功能：对于不同时间通过同一突触传入的信号具有时间的加算功能。 空间加算功能：空间加算功能：对于同一时间通过不同突触的输入信号具有空间加算功能。122 人工神经元的形式化模型人工神经元的形式化模型l2.1M-P模型l2.2感知器模型13MP模型属于一种阈值元件模型，它是由美国McCulloch和Pitts提出的最早神经元模型之一。MP模型是大多数神经网络模型的基础。MP模型模型14标准标准MP模型模型 15wij代表神经元i与神经元j之间的连接强度(模拟生物神经元之间突触连接强度)，称之为连接权；ui代表神经元i的活跃值，即神经元状态；vj代表神经元j的输出，即是神经元i的一个输入；i代表神经元i的阈值。函数f表达了神经元的输入输出特性。在MP模型中，f定义为阶跃函数：16如果把阈值i看作为一个特殊的权值，则可改写为:其中，w0i-i，v01为用连续型的函数表达神经元的非线性变换能力，常采用s型函数:该函数的图像如下图所示1718MP模型在发表时并没有给出一个学习算法来调整神经元之间的连接权。但是，我们可以根据需要，采用一些常见的算法来调整神经元连接权，以达到学习目的。下面介绍的Hebb学习规则就是一个常见学习算法。19Hebb学学习习规规则则神经网络具有学习功能。对于人工神经网络而言，这种学习归结为神经元连接权的变化。调整wij的原则为：若第i和第j个神经元同时处于兴奋状态，则它们之间的连接应当加强，即：wijuivj这一规则与“条件反射”学说一致，并已得到神经细胞学说的证实。是表示学习速率的比例常数。202 感知器模型感知器是一种早期的神经网络模型，由美国学者F.Rosenblatt于1957年提出.感知器中第一次引入了学习的概念，使人脑所具备的学习功能在基于符号处理的数学到了一定程度的模拟，所以引起了广泛的关注。简单感知器简单感知器简单感知器模型实际上仍然是MP模型的结构，但是它通过采用监督学习来逐步增强模式划分的能力，达到所谓学习的目的。21其结构如下图所示感知器处理单元对n个输入进行加权和操作v即：其中，Wi为第i个输入到处理单元的连接权值为阈值。f取阶跃函数.22感知器在形式上与MP模型差不多，它们之间的区别在于神经元间连接权的变化。感知器的连接权定义为可变的，这样感知器就被赋予了学习的特性。利用简单感知器可以实现逻辑代数中的一些运算。Y=f(w1x1+w2x2-)(1)“与”运算。当取w1w21，1.5时，上式完成逻辑“与”的运算。23(2)“或”运算，当取wlw21，0.5时，上式完成逻辑“或”的运算。(3)“非”运算，当取wl=-1，w20，-1时完成逻辑“非”的运算。Y=f(w1x1+w2x2-)24与许多代数方程一样，上式具有一定的几何意义。对于一个两输入的简单感知器，每个输入取值为0和1，如上面结出的逻辑运算，所有输入样本有四个，记为(x1，x2)：(0，0)，(0，1)，(1，0)，(1，1)，构成了样本输入空间。例如，在二维平面上，对于“或”运算，各个样本的分布如下图所示。直线1*x1+1*x2-050将二维平面分为两部分，上部为激发区(y，=1，用表示)，下部为抑制区(y0，用表示)。25简单感知器引入的学习算法称之为误差学习算法。该算法是神经网络学习中的一个重要算法，并已被广泛应用。现介绍如下：误差型学习规则：误差型学习规则：(1)选择一组初始权值wi(0)。(2)计算某一输入模式对应的实际输出与期望输出的误差26(3)如果小于给定值，结束，否则继续。(4)更新权值(阈值可视为输入恒为1的一个权值)：wi（t+1）wi（t+1）-wi（t）dy(t)xi。式中为在区间(0，1)上的一个常数，称为学习步长，它的取值与训练速度和w收敛的稳定性有关；d、y为神经元的期望输出和实际输出；xi为神经元的第i个输入。(5)返回(2)，重复，直到对所有训练样本模式，网络输出均能满足要求。2728对于学习步长的取值一般是在(0，1)上的一个常数，但是为了改进收敛速度，也可以采用变步长的方法，这里介绍一个算法如下式：式中，为一个正的常量这里取值为0.1。所以，对应于输入(0，0)，修正权值(注意：=w0,x0=-1)w0（1）dyx00.1(10)(1)0.1，W0(1)=0.1+w0（1）=0.1-0.1=0.0依次进行。29同样的方法，对其他输入样本都进行学习。整个学习过程就是某一超平面在样本空间中几何位置调整的过程。初值w1(7)0225w2(7)00875，(7)01875。这样的一组网络参数满足计算要求。3031感知器对线性不可分问题的局限性决定了它只有较差的归纳性，而且通常需要较长的离线学习才能达到收效。32多层感知器多层感知器 如果在输入和输出层间加上一层或多层的神经元(隐层神经元)，就可构成多层前向网络，这里称为多层感知器。 这里需指出的是：多层感知器只允许调节一层的连接权。这是因为按感知器的概念，无法给出一个有效的多层感知器学习算法。33上述三层感知器中，有两层连接权，输入层与隐层单元间的权值是随机设置的固定值，不被调节；输出层与隐层间的连接权是可调节的。34对于上面述及的异或问题，用一个简单的三层感知器就可得到解决实际上，该三层感知器的输入层和隐层的连接，就是在模式空间中用两个超平面去划分样本，即用两条直线：x1+x2=0.5x1十x21.5。353637可以证明，只要隐层和隐层单元数足够多，多层感知器网络可实现任何模式分类。但是，多层网络的权值如何确定，即网络如何进行学习，在感知器上没有得到解决：当年Minsky等人就是因为对于非线性空间的多层感知器学习算法未能得到解决，使其对神经网络的研究作出悲观的结论。382.4 人工神经网络模型人工神经网络模型 l1神经网络节点的形式化描述l2神经元状态转移函数的类型l3神经网络分类及其拓扑结构l4神经网络的知识表示与处理能力391 神经网络节点的形式化描述神经网络节点的形式化描述l图图 神经元结构模型神经元结构模型40l i =xi wij +si -il ui =f (i )lYi =g (ui )=f (i )h=g f412 神经元状态转移函数的类型神经元状态转移函数的类型l当神经元没有内部状态时，可令yi=ui，h=f 。常用的神经元状态转移函数有：l1、阶跃函数l2、准线形函数423、Sigmoid函数l4、双曲正切函数43 图图 神经元状态转移函数神经元状态转移函数l阶跃函数l准线形函数lSigmoid函数l双曲正切函数443 神经网络分类及其拓扑结构神经网络分类及其拓扑结构l一、神经网络的分类一、神经网络的分类l1、按照对生物神经系统的不同组织层次和抽象层次的模拟，可分为：l（1）神经元层次模型l研究工作主要集中在单个神经元的动态特性和自适应特性，探索神经元对输入信息选择的响应和某些基本存贮功能的机理。l（2）组合式模型l它由数种相互补充、相互协作的神经元组成，用于完成某些特定的任务。如模式识别、机器人控制等。45l（3）网络层次模型l它是由许多相同神经元相互连接而成的网络，从整体上研究网络的集体特性。l（4）神经系统模型l一般由多个不同性质的神经网络构成，以模拟生物神经的更复杂或更抽象的性质。l（5）智能型模型l这是最抽象的层次，多以语言形式模拟人脑信息处理的运行、过程、算法和策略。这些模型试图模拟如感知、思维、问题求解等基本过程且与AI相关。46l2、按照网络的结构与学习方式分：l（1）按照网络的性能分：连续型与离散型网络；确定型与随机型网络。l（2）按照网络的结构分：前馈网络；反馈网络。l（3）按照学习方式分：有教师指导的网络；无教师指导的网络。l（4）按照连接突触的性质分：一阶线性关联网络；高阶线性关联网络。47l二、神经网络的拓扑结构二、神经网络的拓扑结构l1、不含反馈的前向网络(a)l2、从输出层到输入层有反馈的前向网络(b)l3、层内有反馈的前向网络(c)l4、相互结合型网络(d)48l图图 网络结构的各种形态网络结构的各种形态495 人工神经网络的学习规则人工神经网络的学习规则 l1人工神经网络的学习方式l2人工神经网络学习规则501 人工神经网络的学习方式人工神经网络的学习方式l一、死记学习死记学习l联想记忆（自、他），先设计成记忆模式为稳态，给定有关信息时就回忆起来。l二、有教师指导的学习有教师指导的学习l给定输入模式，教师指定期望输出，通过调整权系。前向网络，如BP算法。l三、竞争学习竞争学习l给定一个输入模式，使某些（个）神经元兴奋。如ART网络。512 人工神经网络学习规则人工神经网络学习规则l一、相关规则相关规则l依据连接之间的激活水平改变权系。（死记学习）。l1、学习规则l网络中若第i与第j个神经元同时处于兴奋状态，则它们之间的连接权值Wij应当加强，即：lWij(n+1)=Wij(n)+WijWij=YiYj 0 学习速率系数l要求：Y 0,1或Y -1,+1lHopfield网络使用修正的Hebb规则：l Wij=(2Yi-1)(2Yj-1)l要求：Y 0,1或Y -1,+152l二、纠错规则纠错规则l依据输出节点的外部反馈来改变权系，使实际输出与期望输出相一致。（有教师指导的学习）l2、感知器的学习规则l如果一个节点的输出正确，则连接权值不变。l如果输出本应为0而为1，则相应地减小权值。l如果输出本应为1而为0，则相应地增加权值。53l3、 学习规则l网络中神经元j 与神经元i 的连接权值为Wij，则对权值的修正为：Wij= i Yil 其中：为学习率；i = Ti - Yi 为i的偏差，即i的实际输出和教师信号之差。学习规则仅用于单层网络的学习规则，如单层感知器的学习。54l4、广义学习规则l用于多层网络，对于输出层节点和相邻隐层节点之间的权值修正用 学习规则，对于其它层间的连接权值，则使用广义 学习规则。设i为隐层节点，其偏差的计算为：l i=f (neti ) k Wkil Wij= i Yil其中：k为i的上一层节点k的偏差，Wki为i 与k 间的连接权值。i的下一层节点的偏差可以用递归的方法得到。55l5、Boltzmann机学习规则（模拟退火算法）l模拟退火算法基本上由三部分组成：l(1)以一定的概率密度函数跃迁到新的状态，这个概率密度函数称为生成函数。l(2)以一定的概率密度函数容忍评估函数的偶然上升，这个概率密度函数称为容忍函数。l(3)以一定的冷却方式降低温度，这个等效温度是生成函数和容忍函数的控制参量。56l经典的模拟退火算法中使用了高斯型生成函数，ll其中T(t)是温度，决定了概率密度分布的特征宽度，这种分布函数远处是指数型衰减的，因而代表一种局域型搜索过程，为了能找到全局最小，温度要下降的很慢，Geman兄弟证明只要满足退火率为：ll且T(0)要足够大。57l算法大致如下，从一个随机选取的状态出发，依据生成函数产生一个新的状态，如果这个新的状态的评估函数值比原来的状态低，则令它为系统新的状态；如果它比原先状态的评估函数值高，则它成为新状态的概率由容忍函数确定，若系统不进入这个状态，则它仍保持原先的状态，生成函数与容忍函数按照规定的冷却方式变化。l在学习过程中，随机地改变一权值，确定权值改变后产生的最终能量，并按照下述规则来确定是否保留此权值的变化。58l若随机改变权值后，ANN能量降低，则保留这一改变。l若随机改变权值后，ANN能量没降低，则根据一预选的概率分布来保留这一改变，否则l拒绝权值的改变，使权值恢复到原来的值。l在第步虽然性能有可能变差，但从整体上来看，却能保证ANN能达到能量最小点。在中逐渐减小概率值。59l6、梯度下降算法l将数学上的最优化方法应用于ANN中，权值的修正量正比于误差对加权的一阶导数。ll其中，E是描述误差的误差函数，是学习率。60l三、无教师指导的学习规则三、无教师指导的学习规则 l学习表现为适应于输入空间的检测规则。l7、竞争学习规则l设输入层有n个节点，输出层m个节点，dj为距离接近测度，则：i1,2,n,j1,2,m61l胜者：lj1,2,ml62BP神经网络神经网络lBP神经网络(反向传播网络back-propagationnetwork)是目前应用最广泛的一种神经网络模型，可以用它来作为时间序列的预测模型。网络由输入层、隐层和输出层组成,通常采用BP学习算法进行网络的训练。隐层可以有一层或多层，可以采用含有一层隐层的BP神经网络。63BP神经网络神经网络Kolmogorov定理已经证明,仅有一个隐层的神经元和隐层采用S型传递函数的多层神经网络能以任意精度逼近任意连续函数。64BP神经网络神经网络65BP神经网络神经网络l各个神经元之间的连接并不只是一个单纯的传输信号的通道，而是在每对神经元之间的连接上有一个加权系数，这个加权系数就是权值，它起着生物神经系统中神经元的突触强度的作用，它可以加强或减弱上一个神经元的输出对下一个神经元的刺激。修改权值的规则称为学习算法，它可以根据经验或学习来改变。66BP神经网络神经网络BP算法可以对网络中各层的权系数进行修正，解决了多层网络的学习问题。其学习过程由正向传播和反向传播组成。正向传播是根据输入从第一个隐含层开始逐层地进行计算,并向下一层传递（每一层神经元只影响下一层神经元的状态）,直到传出输出层，求出输入对应的实际输出。然后将实际输出与期望输出进行比较得到误差信号，如果它们的误差不能满足要求，,则沿着原来的连接通路逐层返回，即误差反向逐层传播，用于修改连接权值和阈值,使误差逐步减小,直到满足要求为止。一旦网络经过训练达到稳定，并用于求解现实问题,则就只需正向传播,不需要再进行反向传播。673. 2 数学模型输入层与隐层间权值为：阈值为：隐层与输出层间权值为：阈值为：网络的作用函数称为S型函数： 假定：假定：68，输入层输入层神经元 i ： 输入： 输出： =隐含层隐含层神经元 k ： 输入： 输出： =输出层输出层神经元 j ： 输入： 输出： =69那么：那么：误差 为期望输出70采用梯度法对各层权值进行修正： 非输出层神经元的误差 等于所有与该神经元相连的神经元的输出端误差 乘以对应的权值 并求和。71 BP神经网络数学描述要点神经网络数学描述要点： 输入和输出的样本对的关系是连续非线性的，如： 各层输入与输出的关系 由权值wki和wjk构成的两个权重矩阵、两个偏差矩阵 （列矩阵）的行列关系 网络计算目的与初始条件（输入与输出、样本对、初始 权值与偏差值）72初始化神经网络训练结束吗？给定学习模式（输入/输出对）求隐含层、输出层神经元的输出计算实际输出与期望输出之差误差小于指定值？计算隐含层神经元误差计算误差梯度权值修正给出新的输 入计算神经网络输出是是否否1、计算流程图73BP神经网络神经网络74BP神经网络神经网络75BP神经网络神经网络76BP神经网络神经网络77BP神经网络神经网络l总结以上推导可写为l的计算有两种情况:l(1)当j 是一个输出单元时,为与误差信号之积.l(2)当j 是一个隐单元时,为与后面一层的的加权和之积78BP神经网络神经网络O0=-1O1O2O3O4O5w50w30w32w53w31w41w42w40w5479BP神经网络神经网络80BP神经网络神经网络输出层权值调节隐含层权值调节81BP神经网络神经网络82 从上面的过程可以看出，BP网络的学习和训练分成两个阶段，在第一阶段里对于给定的网络输入，通过现有连接权重将其正向传播，获得各个神经元的实际输出；在第二阶段里，首先计算出输出层各神经元的一般化误差，这些误差逐层向输入层方向逆向传播，以获得调整各连接权重所需的各神经元参考误差。BP神经网络神经网络83学习算法 从本质上说，神经网络的训练问题是一个函数极小化问题，但由于它的数学基础是非线性理论，因系统的高度非线性使最初的BP算法存在效率低、收敛慢、易于陷入局部极小等缺陷，使神经网络在复杂系统中的应用受到限制。大部分新的研究都集中在算法的改进上，如共轭梯度算法、基于信息熵优化的算法、改进的改进的BP法法等。通过这些研究，使神经网络的应用得到进一步的发展。84BP神经网络神经网络lBP神经网络存在一些不足之处：851、神经计算2、模糊计算3、粗糙集理论4、 遗传算法5、进化策略与编程6、人工生命7、粒群优化8、蚁群算法9、自然计算10、免疫计算目前计算智能的研究内容目前计算智能的研究内容86人工生命人工生命l当前构建人工生命的途径主要有三类。第一类是通过软件的形式，即用编程的方法建造人工生命。由于这类人工生命主要在计算机内活动，其行为主要通过计算机屏幕表现出来，所以它们被称为虚拟人工生命或数字人工生命。87人工生命定义定义1 1C.Langton:Artificial Life is the study of man-made system that exhibit behaviors characteristic of natural living system研究具有自然生命系统行为的人造系统。研究具有自然生命系统行为的人造系统。88lArtificiallifecancontributetotheoreticalbiologybylocating“life-as-know-it”withinthelargerpictureof“life-as-it-could-be”89人工鱼涂晓媛涂晓媛获了1996ACMDoctoralDissertationAward.90人工鱼涂晓媛涂晓媛91人工鱼涂晓媛涂晓媛92人工鱼涂晓媛涂晓媛93人工鱼涂晓媛涂晓媛94机器鱼95机器鱼96机器鱼97机器鱼98机器鱼l这些机器鱼是由英国艾克塞斯大学计算机科学系的胡霍生（HuoshengHu）教授和他带领的人类中心机器人小组制作的。99蚁群算法l20世纪90年代初期，意大利学者多里戈、马尼佐和科洛龙等人从生物进化和仿生学角度出发，研究蚂蚁寻找路径的自然行为，提出了蚁群算法，并用该方法求解TSP问题、二次分配问题和作业调度等问题，取得较好的效果。100蚁群算法蚁群算法蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。101蚁群算法为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低.当后来的蚂蚁再次碰到这个路口的时候选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。102简化的蚂蚁寻食过程简化的蚂蚁寻食过程 1/3蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。103简化的蚂蚁寻食过程简化的蚂蚁寻食过程 2/3本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。104简化的蚂蚁寻食过程简化的蚂蚁寻食过程 3/3假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这也就是前面所提到的正反馈效应。105InterruptTheFlow106ThePathThickens!107TheNewShortestPath108AdaptingtoEnvironmentChanges109自然蚁群与人工蚁群算法自然蚁群与人工蚁群算法 基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如TSP问题。 人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。 两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离。110算法步骤（以TSP为例）l初始化l蚂蚁随机分布到各个城市l环游l蚂蚁依次选择路径直到返回出发点l更新路径111算法核心算法核心l转移概率的计算li：蚂蚁当前位置；j：蚂蚁可以到达的位置；A：蚂蚁可以到达位置的集合；ij：启发性信息；ij：i到j的路径的信息素数量112算法核心算法核心(续续)l信息素更新lijk：蚂蚁k由i到j的路径上留下的单位长度轨迹信息素数量l05，15，0.10.99，10Q10000113信息素更新与算法信息素更新与算法l在线更新onlineupdatel完全模拟蚂蚁运动规律l离线更新offlineupdatel人为l在线更新方式已被可获得更佳效果的离线更新方式所取代114信息素更新与算法信息素更新与算法TSP问题的人工蚁群算法中，假设m只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的信息素值决定。信息素的更新方式有2种，一是挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值“好”(有蚂蚁走过)的边增加信息素。115信息素更新与算法（续）信息素更新与算法（续）l三种蚁群算法lantcyclesystem：lantquantitysystem：lantdensitysystem：116 发展现状发展现状l目前研究和应用主要集中在比利时、意大利、英国、法国、德国等欧洲国家，日本和美国开始启动l1998年和2000年在比利时布鲁塞尔大学召开了第一届和第二届蚂蚁优化国际研讨会 l国内开始有少量公开报道和研究成果l严格理论基础尚未奠定，有关研究仍停留在实验探索阶段 117WEB CLUSTERINGWhy?Thesizeoftheinternethasdoublingitssizeeveryyear.Estimated2.1billionasofJuly2001Organizingandcategorizingdocumentisnotscalabletothegrowthofinternet.Document clustering? Istheoperationofgroupingsimilardocumenttoclassesthatcanbeusedtoobtainananalysisofthecontent.Antclusteringalgorithmcategorizewebdocumenttodifferentinterestdomain.118119基于蚁群算法的聚类算法基于蚁群算法的聚类算法主要步骤：l随机分布待聚类模式；l每只蚂蚁计算当前对象在局部环境的群体相似度，并通过概率转换函数得到拾起或放下对象的概率，以这个概率行动；l经过群体大量的相互作用，最终得到若干聚类中心；l最后收集聚类结果。