计算群体智能.ppt

求解TSP算法步骤 ⑴初始化　随机放置蚂蚁，为每只蚂蚁建立禁忌表tabuk，将初始节点置入禁忌表中; ⑵迭代过程 k=1 while k=ItCount do (执行迭代) for i = 1 to m do (对m只蚂蚁循环) for j = 1 to n - 1 do (对n个城市循环) 　　 根据式(1)，采用轮盘赌方法在窗口外选择下一个城市j; 将j置入禁忌表,蚂蚁转移到j; 　 end for end for 计算每只蚂蚁的路径长度; 根据式(2)更新所有蚂蚁路径上的信息量; k = k + 1; end while ⑶输出结果,结束算法. 蚁群的规模和停止规则 一、蚁群大小 一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数。 二、终止条件 1 给定一个外循环的最大数目； 2 当前最优解连续K次相同而停止，其中K是一个给定的整数，表示算法已经收敛，不再需要继续。 蚂蚁算法的缺点 蚂蚁算法的缺点： 1）收敛速度慢 2）易于陷入局部最优 4.5 人工免疫算法 4.5.1免疫算法的生物学基础 ?免疫系统是哺乳动物抵御外来有害物质侵害的防御系统，动物一生始终处于复杂多变的、充满伤害的自然环境中，能够平安无事、进行正常的生命活动，免疫系统在其中起着重要的作用。免疫是生物体的特异性生理反应, 由具有免疫功能的器官、组织、细胞、免疫效应分子及基因等组成。 免疫系统通过分布在全身的不同种类的淋巴细胞识别和清除侵入生物体的抗原性异物。 当生物系统受到外界病毒侵害时, 便激活自身的免疫系统,其目标是尽可能保证整个生物系统的基本生理功能得到正常运转。 4.5.2 免疫算法的起源 ?在生物自然界中，免疫现象普遍存在，并对物种的生存与繁衍 发挥着重要的作用； ?生物的免疫功能主要是由参与免疫反应的细胞或由其构成的器官来完成的； ?生物免疫主要有两种类型： ?特异性免疫反应（Specific Immunity） ?非特异性免疫反应（Nonspecific Immunity）； ?生物免疫系统是通过自我识别、相互刺激与制约而构成了一个 动态平衡的网络结构 。 4.5.3免疫算法的生物免疫机制 4.5.4 免疫算法的基本概念 ? 抗原：在生命科学中，是指能够刺激和诱导机体的免疫系统使其产生免疫应答，并能与相应的免疫应答产物在体内或体外发生特异性反应的物质。在我们的算法中，是指所有可能错误的基因，即非最佳个体的基因。 ?抗体：在生命科学中，是指免疫系统受抗原刺激后，免疫细胞转化为浆细胞并产生能与抗原发生特异性结合的免疫球蛋白，该免疫球蛋白即为抗体。 ?免疫疫苗：根据进化环境或待求问题的先验知识，所得到的对最佳个体基因的估计。 ?免疫调节：在免疫反应过程中，大量的抗体的产生降低了抗原对免疫细胞的刺激，从而抑制抗体的分化和增殖，同时产生的抗体之间也存在着相互刺激和抑制的关系，这种抗原与抗体、抗体与抗体之间的相互制约关系使抗体免疫反应维持一定的强度，保证机体的免疫平衡。 ?免疫记忆：指免疫系统将能与抗原发生反应的抗体作为记忆细胞保存记忆下来，当同类抗原再次侵入时，相应的记忆细胞被激活而产生大量的抗体，缩短免疫反应时间。 ?抗原识别：通过表达在抗原表面的表位和抗体分子表面的对位的化学基进行相互匹配选择完成识别，这种匹配过程也是一个不断对抗原学习的过程，最终能选择产生最适当的抗体与抗原结合而排除抗原。 4.5.5 免疫算法的流程 4.5.6 免疫算法具体步骤 ?(1) 产生初始群体： 对初次应答，初始抗体随机产生;而对再次应答，则借助免疫机制的记忆功能，部分初始抗体由记忆单元获取。由于记忆单元中抗体具有较高的适应度和较好的解群分布，因此可提高收敛速度。 ?(2) 根据先验知识抽取疫苗 ?(3) 计算抗体适应度 ?(4) 收敛判断 若当前种群中包含了最佳个体或达到最大进化代数，则结束算法;否则进行以下步骤。 ?(5) 产生新抗体 每一代新抗体主要通过两条途径产生： (a) 基于遗传操作生成新抗体:采用赌轮盘选择机制，当群体相似度小于阂值A0时，多样性满足要求，则抗体被选中的概率正比于适应度;反之，按下述(b)的方式产生新抗体，交叉和变异操作均采用单点方式。 (b) 随机产生P个新抗体：为保证抗体多样性，模仿免疫系统细胞的新陈代谢功能，随机产生P个新抗体，使抗体总数为N+P，再根据群体更新，产生规模为N的下一代群体。 ?(6) 群体更新： 对种群进行接种疫苗和免疫选择操作，得到新一代规模为N的父代种群，返回步骤3 免疫算法具体步骤之--免疫算子 ?免疫算子有两种类型： 全免疫 非特异