几种智能算法的原理及应用介绍.pptx

几种智能算法的原理几种智能算法的原理及应用介绍及应用介绍学学 院：院：数学与统计学院指导教师：指导教师：阮小娥汇汇 报报 人：人：王 彭讨论班报告讨论班报告主要内容：主要内容：1.1.遗传算法遗传算法2.2.蚁群算法蚁群算法3.3.模拟退火算法模拟退火算法4.4.粒子群算法粒子群算法5.5.总结与体会总结与体会1.遗传算法遗传算法1.1 1.1 遗传算法简介遗传算法简介1.2 1.2 遗传算法的基本思想遗传算法的基本思想1.3 1.3 遗传算法的基本操作遗传算法的基本操作1.4 1.4 遗传算法的构成要素遗传算法的构成要素1.5 1.5 遗传算法的操作步骤遗传算法的操作步骤1.6 1.6 遗传算法的特点遗传算法的特点1.7 1.7 遗传算法的应用领域遗传算法的应用领域1.8 1.8 遗传算法的应用举例遗传算法的应用举例1.1 遗传算法简介遗传算法简介 遗传算法简称遗传算法简称GAGA（Genetic AlgorithmsGenetic Algorithms）是）是19621962年由美国年由美国MichiganMichigan大学的大学的HollandHolland教授提出的模拟自然界遗传机制和生物进教授提出的模拟自然界遗传机制和生物进化论而成的一种并行随机搜索最优化方法。化论而成的一种并行随机搜索最优化方法。遗传算法是以达尔文的遗传算法是以达尔文的自然选择学说自然选择学说为基础发展起来的。为基础发展起来的。自然选择学说自然选择学说包括以下三个方面：包括以下三个方面：（1 1）遗遗传传：这这是是生生物物的的普普遍遍特特征征，亲亲代代把把生生物物信信息息交交给给子子代代，子子代代总总是是和和亲亲代代具具有有相相同同或或相相似似的的性性状状。生生物物有有了了这这个个特特征征，物物种种才才能能稳稳定定存在。存在。（2 2）变变异异：亲亲代代和和子子代代之之间间以以及及子子代代的的不不同同个个体体之之间间的的差差异异，称称为为变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。（3 3）生生存存斗斗争争和和适适者者生生存存：具具有有适适应应性性变变异异的的个个体体被被保保留留下下来来，不不具具有有适适应应性性变变异异的的个个体体被被淘淘汰汰，通通过过一一代代代代的的生生存存环环境境的的选选择择作作用用，性性状逐渐逐渐与祖先有所不同，演变为新的物种。状逐渐逐渐与祖先有所不同，演变为新的物种。1.2 遗传算法的基本思想遗传算法的基本思想 遗传算法将遗传算法将“优胜劣汰，适者生存优胜劣汰，适者生存”的生物进化原理引入优的生物进化原理引入优化参数形成的编码串联群体中，按所选择的适应度函数并通过遗化参数形成的编码串联群体中，按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，使适适应度高的个体传中的复制、交叉及变异对个体进行筛选，使适适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。遗传算法的算法简单，可并行处理，并能到到满足一定的条件。遗传算法的算法简单，可并行处理，并能到全局最优解。全局最优解。1.3 遗传算法的基本操作遗传算法的基本操作 遗传算法的基本操作主要有：遗传算法的基本操作主要有：复制复制、交叉交叉、变异变异。（1 1）复制（复制（Reproduction OperatorReproduction Operator）复制是从一个旧种群中选择生命力强的个体位串产生新种群的过程。复制是从一个旧种群中选择生命力强的个体位串产生新种群的过程。具有高适应度的位串更有可能在下一代中产生一个或多个子孙。具有高适应度的位串更有可能在下一代中产生一个或多个子孙。复制操作可以通过随机方法来实现。首先产生复制操作可以通过随机方法来实现。首先产生0101之间均匀分布的随之间均匀分布的随机数，若某串的复制概率为机数，若某串的复制概率为40%40%，则当产生的随机数在，则当产生的随机数在0.401.00.401.0之间时，之间时，该串被复制，否则被淘汰。该串被复制，否则被淘汰。1.3 遗传算法的基本操作遗传算法的基本操作（2 2）交叉（交叉（Crossover OperatorCrossover Operator）复制操作能从旧种群中选择出优秀者，但不能创造新的染色体。而复制操作能从旧种群中选择出优秀者，但不能创造新的染色体。而交叉模拟了生物进化过程中的繁殖现象，通过两个染色体的交换组合，交叉模拟了生物进化过程中的繁殖现象，通过两个染色体的交换组合，来产生新的优良品种。来产生新的优良品种。交叉的过程为：在匹配池中任选两个染色体，随机选择一点或多点交叉的过程为：在匹配池中任选两个染色体，随机选择一点或多点交换点位置；交换双亲染色体交换点右边的部分，即可得到两个新的染交换点位置；交换双亲染色体交换点右边的部分，即可得到两个新的染色体数字串。色体数字串。交叉体现了自然界中信息交换的思想。交叉有一点交叉、多点交叉、交叉体现了自然界中信息交换的思想。交叉有一点交叉、多点交叉、还有一致交叉、顺序交叉和周期交叉。一点交叉是最基本的方法，应用还有一致交叉、顺序交叉和周期交叉。一点交叉是最基本的方法，应用较广。它是指染色体切断点有一处，例：较广。它是指染色体切断点有一处，例：1.3 遗传算法的基本操作遗传算法的基本操作（3 3）变异变异(Mutation Operator)(Mutation Operator)变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素引起的变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变，它以很小的概率随机地改变遗传基因（表示染色体的符号串基因突变，它以很小的概率随机地改变遗传基因（表示染色体的符号串的某一位）的值。在染色体以二进制编码的系统中，它随机地将染色体的某一位）的值。在染色体以二进制编码的系统中，它随机地将染色体的某一个基因由的某一个基因由1 1变为变为0 0，或由，或由0 0变为变为1 1。若只有选择和交叉，而没有变异，则无法在初始基因组合以外的空若只有选择和交叉，而没有变异，则无法在初始基因组合以外的空间进行搜索，使进化过程在早期就陷入局部解而进入终止过程，从而影间进行搜索，使进化过程在早期就陷入局部解而进入终止过程，从而影响解的质量。为了在尽可能大的空间中获得质量较高的优化解，必须采响解的质量。为了在尽可能大的空间中获得质量较高的优化解，必须采用变异操作。变异操作如下所示：用变异操作。变异操作如下所示：1.4 遗传算法的构成要素遗传算法的构成要素 遗传算法的构成要素主要有：遗传算法的构成要素主要有：染色体编码方法染色体编码方法、个体适应度个体适应度评价评价、遗传算子遗传算子及及遗传算法的运行参数遗传算法的运行参数。（1 1）染色体编码方法染色体编码方法 基本遗传算法使用固定长度的二进制符号来表示群体中的个体，基本遗传算法使用固定长度的二进制符号来表示群体中的个体，其等位基因是由二值符号集其等位基因是由二值符号集0,10,1所组成。初始个体基因值可用均匀分布所组成。初始个体基因值可用均匀分布的随机值生成，如：的随机值生成，如：就可表示一个个体，该个体的染色体长度是就可表示一个个体，该个体的染色体长度是1818。1.4 遗传算法的构成要素遗传算法的构成要素（2 2）个体适应度评价个体适应度评价 基本遗传算法与个体适应度成正比的概率来决定当前群体中每个个基本遗传算法与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的概率多少。为正确计算这个概率，要求所有个体遗传到下一代群体中的概率多少。为正确计算这个概率，要求所有个体的适应度必须为正数或零。因此，必须先确定由目标函数值体的适应度必须为正数或零。因此，必须先确定由目标函数值J J到个体适到个体适应度应度f f之间的转换规则。之间的转换规则。（3 3）遗传算子遗传算子 基本遗传算法使用下述三种遗传算子：基本遗传算法使用下述三种遗传算子：选择运算选择运算:使用比例选择算子；使用比例选择算子；交叉运算交叉运算:使用单点交叉算子；使用单点交叉算子；变异运算变异运算:使用基本位变异算子或均匀变异算子。使用基本位变异算子或均匀变异算子。1.4 遗传算法的构成要素遗传算法的构成要素（4 4）基本遗传算法的运行参数基本遗传算法的运行参数 有下述有下述4 4个运行参数需要提前设定：个运行参数需要提前设定：M M：群体大小，即群体中所含个体的数量，一般取为：群体大小，即群体中所含个体的数量，一般取为20-10020-100；G G：遗传算法的终止进化代数，一般取为：遗传算法的终止进化代数，一般取为100-500100-500；PcPc：交叉概率，一般取为：交叉概率，一般取为0.4-0.990.4-0.99；PmPm：变异概率，一般取为：变异概率，一般取为0.0001-0.10.0001-0.1。1.5 遗传算法的操作步骤遗传算法的操作步骤 对于一个需要进行优化的实际问题，一般可按下述步骤构造遗对于一个需要进行优化的实际问题，一般可按下述步骤构造遗传算法：传算法：第一步第一步：确定决策变量及各种约束条件；：确定决策变量及各种约束条件；第二步第二步：建立优化模型，即确定出目标函数的类型及数学描述形式或：建立优化模型，即确定出目标函数的类型及数学描述形式或量化方法；量化方法；第三步第三步：确定表示可行解的染色体编码方法；：确定表示可行解的染色体编码方法；第四步第四步：确定解码方法；：确定解码方法；第第四四步步：确确定定个个体体适适应应度度的的量量化化评评价价方方法法，即即确确定定出出由由目目标标函函数数值值到到个体适应度的转换规则；个体适应度的转换规则；第第五五步步：设设计计遗遗传传算算子子，即即确确定定选选择择运运算算、交交叉叉运运算算、变变异异运运算算等等遗遗传算子的具体操作方法。传算子的具体操作方法。第六步第六步：确定遗传算法的有关运行参数，即：确定遗传算法的有关运行参数，即M,G,Pc,PmM,G,Pc,Pm等参数。等参数。1.5 遗传算法的操作步骤遗传算法的操作步骤 遗传算法流程图：遗传算法流程图：1.6 遗传算法的特点遗传算法的特点遗传算法的主要特点有：遗传算法的主要特点有：（1 1）遗传算法是对参数的编码进行操作，而非对参数本身，遗传算法是对参数的编码进行操作，而非对参数本身，这就是使得我们这就是使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念，模仿自然界中生物的在优化计算过程中可以借鉴生物学中染色体和基因等概念，模仿自然界中生物的遗传和进化等机理；遗传和进化等机理；（2 2）遗传算法同时使用多个搜索点的搜索信息。遗传算法同时使用多个搜索点的搜索信息。传统的优化方法往往是从解传统的优化方法往往是从解空间的单个初始点开始最优解的迭代搜索过程，单个搜索点所提供的信息不多，空间的单个初始点开始最优解的迭代搜索过程，单个搜索点所提供的信息不多，搜索效率不高，有时甚至使搜索过程局限于局部最优解而停滞不前。搜索效率不高，有时甚至使搜索过程局限于局部最优解而停滞不前。遗传算法从由很多个体组成的一个初始群体开始最优解的搜索过程，而不是遗传算法从由很多个体组成的一个初始群体开始最优解的搜索过程，而不是从一个单一的个体开始搜索，这是遗传算法所特有的一种隐含并行性，因此遗传从一个单一的个体开始搜索，这是遗传算法所特有的一种隐含并行性，因此遗传算法的搜索效率较高。算法的搜索效率较高。（3 3）遗传算法直接以目标函数作为搜索信息。遗传算法直接以目标函数作为搜索信息。传统的优化算法不仅需要利用传统的优化算法不仅需要利用目标函数值，而且需要目标函数的导数值等辅助信息才能确定搜索方向。而遗传目标函数值，而且需要目标函数的导数值等辅助信息才能确定搜索方向。而遗传算法仅使用由目标函数值变换来的适应度函数值，就可以确定进一步的搜索方向算法仅使用由目标函数值变换来的适应度函数值，就可以确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助信息。和搜索范围，无需目标函数的导数值等其他一些辅助信息。1.6 遗传算法的特点遗传算法的特点 遗传算法可应用于目标函数无法求导数或导数不存在的函数的优化问题，以遗传算法可应用于目标函数无法求导数或导数不存在的函数的优化问题，以及组合优化问题等。及组合优化问题等。（4 4）遗传算法使用概率搜索技术。遗传算法使用概率搜索技术。遗传算法的选择、交叉、变异等运算都是遗传算法的选择、交叉、变异等运算都是以一种概率的方式来进行的，因而遗传算法的搜索过程具有很好的灵活性。随着以一种概率的方式来进行的，因而遗传算法的搜索过程具有很好的灵活性。随着进化过程的进行，遗传算法新的群体会更多地产生出许多新的优良的个体。进化过程的进行，遗传算法新的群体会更多地产生出许多新的优良的个体。（5 5）遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜索；索；（6 6）遗传算法对于待寻优的函数基本无限制，遗传算法对于待寻优的函数基本无限制，它既不要求函数连续，也不要它既不要求函数连续，也不要求函数可微，既可以是数学解析式所表示的显函数，又可以是映射矩阵甚至是神求函数可微，既可以是数学解析式所表示的显函数，又可以是映射矩阵甚至是神经网络的隐函数，因而应用范围较广；经网络的隐函数，因而应用范围较广；（7 7）遗传算法具有并行计算的特点，遗传算法具有并行计算的特点，因而可通过大规模并行计算来提高计算因而可通过大规模并行计算来提高计算速度，适合大规模复杂问题的优化。速度，适合大规模复杂问题的优化。1.7 遗传算法的应用领域遗传算法的应用领域 遗传算法的应用领域主要有：遗传算法的应用领域主要有：函数优化函数优化、组合优化组合优化、生产调生产调度问题度问题、自动控制自动控制、机器人机器人、图像处理等图像处理等。（1 1）函数优化函数优化 函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例。尤其是对非线性、多模型、多目标的函数优化问题，采用的常用算例。尤其是对非线性、多模型、多目标的函数优化问题，采用其他优化方法较难求解，而遗传算法却可以得到较好的结果。其他优化方法较难求解，而遗传算法却可以得到较好的结果。（2 2）组合优化组合优化。随着问题的增大，组合优化问题的搜索空间也急剧扩大，采用传统随着问题的增大，组合优化问题的搜索空间也急剧扩大，采用传统的优化方法很难得到最优解。遗传算法是寻求这种满意解的最佳工具。的优化方法很难得到最优解。遗传算法是寻求这种满意解的最佳工具。例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。分问题等方面得到成功的应用。1.7 遗传算法的应用领域遗传算法的应用领域（3 3）生产调度问题生产调度问题 在很多情况下，采用建立数学模型的方法难以对生产调度问题进行精在很多情况下，采用建立数学模型的方法难以对生产调度问题进行精确求解。在现实生产中多采用一些经验进行调度。遗传算法是解决复杂确求解。在现实生产中多采用一些经验进行调度。遗传算法是解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。产规划、任务分配等方面遗传算法都得到了有效的应用。（4 4）自动控制自动控制 在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已经在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已经在其中得到了初步的应用。例如，利用遗传算法进行控制器参数的优化、在其中得到了初步的应用。例如，利用遗传算法进行控制器参数的优化、基于遗传算法的模糊控制规则的学习、基于遗传算法的参数辨识、基于基于遗传算法的模糊控制规则的学习、基于遗传算法的参数辨识、基于遗传算法的神经网络结构的优化和权值学习等。遗传算法的神经网络结构的优化和权值学习等。1.7 遗传算法的应用领域遗传算法的应用领域（5 5）机器人机器人 例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人结构优化和行为协调等方面得到研究和应用。规划、机器人结构优化和行为协调等方面得到研究和应用。（6 6）图像处理图像处理 遗传算法可用于图像处理过程中的扫描、特征提取、图像分割等的遗传算法可用于图像处理过程中的扫描、特征提取、图像分割等的优化计算。目前遗传算法已经在模式识别、图像恢复、图像边缘特征提优化计算。目前遗传算法已经在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。取等方面得到了应用。1.8 遗传算法的应用举例遗传算法的应用举例1 1 用遗传算法求函数极值用遗传算法求函数极值利用遗传算法求利用遗传算法求RosenbrockRosenbrock函数的极大值：函数的极大值：求解该问题遗传算法的构造过程：求解该问题遗传算法的构造过程：（1 1）确定决策变量和约束条件）确定决策变量和约束条件决策变量为：决策变量为：（2 2）建立优化模型）建立优化模型1.8 遗传算法的应用举例遗传算法的应用举例（3 3）确定编码方法）确定编码方法 用长度为用长度为1010位的二进制编码串来分别表示两个决策变量位的二进制编码串来分别表示两个决策变量x1,x2x1,x2。1010位二进位二进制编码串可以表示从制编码串可以表示从0 0到到10231023之间的之间的10241024个不同的数，故将个不同的数，故将x1,x2x1,x2的定义域离散的定义域离散化为化为10231023个均等的区域，包括两个端点在内共有个均等的区域，包括两个端点在内共有10241024个不同的离散点。个不同的离散点。从离散点从离散点-2.048-2.048到离散点到离散点2.048 2.048，分别对应于从，分别对应于从0000000000(0)0000000000(0)到到1111111111(1023)1111111111(1023)之间的二进制编码。之间的二进制编码。将将x1,x2x1,x2分别表示的两个分别表示的两个1010位长的二进制编码串连接在一起，组成一个位长的二进制编码串连接在一起，组成一个2020位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。使用位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。使用这种编码方法，解空间和遗传算法的搜索空间就具有一一对应的关系。这种编码方法，解空间和遗传算法的搜索空间就具有一一对应的关系。例如：例如：表示一个个体的基因型，其中前表示一个个体的基因型，其中前1010位表示位表示x x1 1，后，后1010位表示位表示x x2 2。1.8 遗传算法的应用举例遗传算法的应用举例（4 4）确定解码方法）确定解码方法 解码时需要将解码时需要将2020位长的二进制编码串切断为两个位长的二进制编码串切断为两个1010位长的二进制编码串，位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为然后分别将它们转换为对应的十进制整数代码，分别记为y y1 1和和y y2 2。依据个体编码方法和对定义域的离散化方法可知，将代码依据个体编码方法和对定义域的离散化方法可知，将代码y y转换为变量转换为变量x x的的解码公式为：解码公式为：例如，例如，对个体：对个体：它由两个代码所组成它由两个代码所组成上述两个代码经过解码后，可得到两个实际的值上述两个代码经过解码后，可得到两个实际的值1.8 遗传算法的应用举例遗传算法的应用举例（5 5）确定个体评价方法）确定个体评价方法 由于由于RosenbrockRosenbrock函数的值域总是非负的，并且优化目标是求函数的最大值，函数的值域总是非负的，并且优化目标是求函数的最大值，故可将个体的适应度直接取为对应的目标函数值，即故可将个体的适应度直接取为对应的目标函数值，即选个体适应度的倒数作为目标函数选个体适应度的倒数作为目标函数 选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变异算子。使用基本位变异算子。（6 6）确定个体评价方法）确定个体评价方法 群体大小群体大小M=80M=80，终止进化代数，终止进化代数G=100G=100，交叉概率，交叉概率Pc=0.60Pc=0.60，变异概率，变异概率Pm=0.10Pm=0.10。（7 7）确定遗传算法的运行参数）确定遗传算法的运行参数1.8 遗传算法的应用举例遗传算法的应用举例（8 8）实验过程）实验过程完全随机生成初始种群完全随机生成初始种群 循环八次，达循环八次，达到暂时的最优值：到暂时的最优值：3414.8 对应的对应的x x1 1、x x2 2坐标为：坐标为：(-1.9799,-1.9159)种群向暂时的种群向暂时的最优染色体靠近。最优染色体靠近。1.8 遗传算法的应用举例遗传算法的应用举例平均分配坐标轴生成初始种群平均分配坐标轴生成初始种群 循环八次，达循环八次，达到最优值：到最优值：3905.9 对应的对应的x x1 1、x x2 2坐标为：坐标为：(-2.0480,-2.0480)种群向最优染种群向最优染色体靠近。色体靠近。1.8 遗传算法的应用举例遗传算法的应用举例 上述七个步骤构成了用于求函数极大值的优化计算基本遗传算法。上述七个步骤构成了用于求函数极大值的优化计算基本遗传算法。采用上述方法进行仿真，经过采用上述方法进行仿真，经过100100步迭代，最佳样本为步迭代，最佳样本为即当即当时，时，RosenbrockRosenbrock函数具有极大值，极大值为函数具有极大值，极大值为3905.93905.9。1.8 遗传算法的应用举例遗传算法的应用举例2 2 用遗传算法进行图像匹配用遗传算法进行图像匹配（1 1）问题描述：）问题描述：从一张图片中找出与另一张图片相似的部分。（为了便于说明从一张图片中找出与另一张图片相似的部分。（为了便于说明问题，本实验中目标图片为匹配图片加黑色背景随机生成，如下图问题，本实验中目标图片为匹配图片加黑色背景随机生成，如下图所示：）所示：）1.8 遗传算法的应用举例遗传算法的应用举例2 2 用遗传算法进行图像匹配用遗传算法进行图像匹配（2 2）编码）编码 对匹配图片左上角第一个像素在目标图片内的位置进行编码（要求匹配对匹配图片左上角第一个像素在目标图片内的位置进行编码（要求匹配图片不能超出目标图片的边界），采用二进制编码。图片不能超出目标图片的边界），采用二进制编码。（3 3）计算适应度）计算适应度 适应度函数取为两幅图片对应位置上的值差的平方和的倒数。适应度函数取为两幅图片对应位置上的值差的平方和的倒数。（4 4）选择）选择 按适应度函数的大小计算种群中某个体被选中的概率，按概率选择下一按适应度函数的大小计算种群中某个体被选中的概率，按概率选择下一代种群。代种群。1.8 遗传算法的应用举例遗传算法的应用举例2 2 用遗传算法进行图像匹配用遗传算法进行图像匹配（5 5）交叉）交叉 单点交叉、多点交叉（要求匹配图片不能超出目标图片的边界）。单点交叉、多点交叉（要求匹配图片不能超出目标图片的边界）。（6 6）变异）变异 要求匹配图片不能超出目标图片的边界。要求匹配图片不能超出目标图片的边界。1.8 遗传算法的应用举例遗传算法的应用举例（7 7）实验结果与分析）实验结果与分析 对于此类简单的图片匹配的问题，遗传算法通常能较快的收敛到一个较对于此类简单的图片匹配的问题，遗传算法通常能较快的收敛到一个较好的位置，但对于复杂一些的图片匹配问题，容易收敛到局部极值点。好的位置，但对于复杂一些的图片匹配问题，容易收敛到局部极值点。2.蚁群算法蚁群算法2.1 2.1 蚂蚁生物学特征蚂蚁生物学特征2.2 Deneubourg2.2 Deneubourg双桥实验双桥实验2.32.3 蚁群算法的定义蚁群算法的定义2.42.4 蚁群算法的原理蚁群算法的原理2.5 2.5 蚁群算法的规则蚁群算法的规则2.6 2.6 蚁群算法的特点蚁群算法的特点2.7 2.7 蚁群算法的应用领域蚁群算法的应用领域2.8 2.8 蚁群算法的应用举例蚁群算法的应用举例2.1 蚂蚁的生理学特征蚂蚁的生理学特征 蚂蚁在蚂蚁在80008000万年前就建立起了自己的社会。许多万年前就建立起了自己的社会。许多“蚂蚁城市蚂蚁城市”往往由往往由50005000万个成员组成，并且是一个组织完好的复杂万个成员组成，并且是一个组织完好的复杂“城市城市”。蚂蚁的群体行为主要包括蚂蚁的群体行为主要包括寻找食物寻找食物、任务分配任务分配和和构造墓穴构造墓穴。研究中主要是以蚂蚁寻找食物之后能选择一条研究中主要是以蚂蚁寻找食物之后能选择一条最短路径最短路径来连来连接蚁穴和食物源。接蚁穴和食物源。蚂蚁具有智能么？蚂蚁具有智能么？生物学家通过对蚂蚁的长期观察研究发现，每只蚂蚁的智能并不高，生物学家通过对蚂蚁的长期观察研究发现，每只蚂蚁的智能并不高，看起来没有集中的指挥，但他们却能协同的工作，集中食物建立起稳固看起来没有集中的指挥，但他们却能协同的工作，集中食物建立起稳固的蚁穴，依靠群体的能力发挥出了超出个体的智能。的蚁穴，依靠群体的能力发挥出了超出个体的智能。2.2 Deneubourg双桥实验双桥实验 PasteelsPasteels，DeneubourgDeneubourg和和GossGoss（19871987）全部都在实验中研究）全部都在实验中研究真实蚂蚁信息素的遗留行为，他们称之为真实蚂蚁信息素的遗留行为，他们称之为“双桥实验双桥实验”。在这个。在这个双桥实验模型中，蚁穴通过一个蚁穴和食物源之间用两个长度相双桥实验模型中，蚁穴通过一个蚁穴和食物源之间用两个长度相等的桥连接。作者使用能够辨认路径的阿根廷蚂蚁，简而言之这等的桥连接。作者使用能够辨认路径的阿根廷蚂蚁，简而言之这些蚂蚁可以预测或者搜索他们的群类。些蚂蚁可以预测或者搜索他们的群类。2.2 Deneubourg双桥实验双桥实验等长双桥实验等长双桥实验 在前面的设定下，蚂蚁开始在前面的设定下，蚂蚁开始探索蚁穴周围的环境最终到达食探索蚁穴周围的环境最终到达食物源。沿着他们的在蚁穴和食物物源。沿着他们的在蚁穴和食物源之间的路径，阿根廷释放信息源之间的路径，阿根廷释放信息素，开始每个蚂蚁都随机选择两素，开始每个蚂蚁都随机选择两条桥之间的的一个，在随后的阶条桥之间的的一个，在随后的阶段里因为随机的波动，其中一个段里因为随机的波动，其中一个桥的信息素表现出比另外一条的桥的信息素表现出比另外一条的信息素更为集中，因此吸引了更信息素更为集中，因此吸引了更多的蚂蚁。这个行为增加了这个多的蚂蚁。这个行为增加了这个桥上的信息素，也就吸引了更多桥上的信息素，也就吸引了更多的蚂蚁。因此，过了一段时间以的蚂蚁。因此，过了一段时间以后，整个种群都聚合于使用这个后，整个种群都聚合于使用这个高度集中的桥运送。高度集中的桥运送。2.2 Deneubourg双桥实验双桥实验 Goss Goss，AronAron，DeneubourgDeneubourg和和PasteelPasteel（19891989）提出上述双桥实验的）提出上述双桥实验的变种，在其中一个桥要比另一个桥更长，如下图所示；在这种情况下，变种，在其中一个桥要比另一个桥更长，如下图所示；在这种情况下，蚂蚁选择了近的路径首先到达了蚁穴。因此，短桥比长桥得到了更为蚂蚁选择了近的路径首先到达了蚁穴。因此，短桥比长桥得到了更为密集的信息素增长了蚂蚁选择短桥的的可能性。密集的信息素增长了蚂蚁选择短桥的的可能性。GossGoss，AronAron，DeneubourgDeneubourg和和PasteelPasteel（19901990）将观察的的真实的蚂蚁建立到假设的模）将观察的的真实的蚂蚁建立到假设的模型中。首先，假设桥上残留的信息素量和过去一段时间经过该桥的蚂型中。首先，假设桥上残留的信息素量和过去一段时间经过该桥的蚂蚁数成正比蚁数成正比(信息素挥发的情况信息素挥发的情况););其次某一时刻蚂蚁按照桥上信息素量其次某一时刻蚂蚁按照桥上信息素量的多少来选择某支桥，即蚂蚁选择某支桥的概率与经过该桥的蚂蚁数的多少来选择某支桥，即蚂蚁选择某支桥的概率与经过该桥的蚂蚁数成正比。当所有的成正比。当所有的m m只蚂蚁都经过两支桥以后，设只蚂蚁都经过两支桥以后，设AmAm和和BmBm分别为经过分别为经过A A桥和桥和B B桥的蚂蚁数桥的蚂蚁数(Am+Bm=m)(Am+Bm=m)，则第，则第m+1m+1只蚂蚁选择只蚂蚁选择A(B)A(B)桥的概率为桥的概率为:2.2 Deneubourg双桥实验双桥实验公式表明：往公式表明：往A A走的蚂蚁越多，选择分支走的蚂蚁越多，选择分支A A的概率就越高。的概率就越高。n n和和k k用以匹配真实实验数据。用以匹配真实实验数据。“n”n”决定选择公式的非线性程度。（决定选择公式的非线性程度。（n n越大，信息素多一点越大，信息素多一点的分支选择概率越高）的分支选择概率越高）“k”k”表示对未标记的分支的吸引程度。（表示对未标记的分支的吸引程度。（k k越大，则进行非越大，则进行非随机化选择所需的信息素浓度越高）随机化选择所需的信息素浓度越高）这种概率的表达方式是实际的蚂蚁路径选择实验推导而来这种概率的表达方式是实际的蚂蚁路径选择实验推导而来的，比较符合实验的参数设置是的，比较符合实验的参数设置是n=2n=2和和k=20.k=20.2.3 蚁群算法的定义蚁群算法的定义 蚁群算法蚁群算法(ant colony optimization,ACO)(ant colony optimization,ACO)，又称蚂蚁算法，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。是一种用来在图中寻找优化路径的机率型算法。这种算法具有分布计算、信息正反馈和启发式搜索的特征，本质这种算法具有分布计算、信息正反馈和启发式搜索的特征，本质上是进化算法中的一种新型的启发式优化算法。上是进化算法中的一种新型的启发式优化算法。人工蚁群与真实蚂蚁的异同比较：人工蚁群与真实蚂蚁的异同比较：相同点：相同点：（1 1）都存在一个群体中个体相互交流通信的机制）都存在一个群体中个体相互交流通信的机制 （2 2）都要完成一个相同的任务）都要完成一个相同的任务 （3 3）利用当前信息进行路径选择的随机选择策略）利用当前信息进行路径选择的随机选择策略不同点：不同点：（1 1）人工蚂蚁他们的移动是从一个状态到另一个）人工蚂蚁他们的移动是从一个状态到另一个 状态的转换状态的转换 （2 2）人工蚂蚁具有一个记忆其本身过去行为的内在状态）人工蚂蚁具有一个记忆其本身过去行为的内在状态 （3 3）人工蚂蚁存在于一个与时间无关联的环境之中）人工蚂蚁存在于一个与时间无关联的环境之中 （4 4）人工蚁不是盲从的，受环境空间的启发）人工蚁不是盲从的，受环境空间的启发 （5 5）人工蚁可以根据要求增加功能）人工蚁可以根据要求增加功能2.4 蚁群算法的原理蚁群算法的原理 蚂蚁在运动过程中会通过在路上释放一种特殊的分泌物蚂蚁在运动过程中会通过在路上释放一种特殊的分泌物信息素来寻找路径。当它碰到一个还没有走过的路口是就随机的信息素来寻找路径。当它碰到一个还没有走过的路口是就随机的选择一条路径前行，同时释放出与路径长度有关的选择一条路径前行，同时释放出与路径长度有关的信息素信息素。蚂蚁。蚂蚁走的路越长，则释放的信息量越小。当后来的蚂蚁再次碰到这个走的路越长，则释放的信息量越小。当后来的蚂蚁再次碰到这个路口时，路口时，选择信息量较大的路径的概率相对较大选择信息量较大的路径的概率相对较大，这样便形成了，这样便形成了一个正反馈机制。一个正反馈机制。最优路径上得信息量越来越大，而其他路径上最优路径上得信息量越来越大，而其他路径上的信息量却随时间逐渐减少最终整个蚁群会找出最优路径。的信息量却随时间逐渐减少最终整个蚁群会找出最优路径。（1 1）蚁群之间通过信息素和环境进行通信。）蚁群之间通过信息素和环境进行通信。（2 2）蚂蚁对环境的反应由其内部模式决定。）蚂蚁对环境的反应由其内部模式决定。（3 3）个体水平上，每个蚂蚁相对独立；群体水平上，每只蚂蚁的）个体水平上，每个蚂蚁相对独立；群体水平上，每只蚂蚁的行为是随机的。行为是随机的。蚁群算法的理论假设蚁群算法的理论假设2.5 蚁群算法的规则蚁群算法的规则蚁群算法中的蚂蚁满足的规则主要有以下几个方面：蚁群算法中的蚂蚁满足的规则主要有以下几个方面：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是（一般是3 3），那么它能观察到的范围就是），那么它能观察到的范围就是3*33*3个方格世界，并且能移个方格世界，并且能移动的距离也在这个范围之内。动的距离也在这个范围之内。（1 1）范围）范围 蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内环境信息。环境以一定的速率让信息素消失它范围内环境信息。环境以一定的速率让信息素消失 。（2 2）环境）环境2.5 蚁群算法的规则蚁群算法的规则 在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁都会以小概率犯多，这样，它就朝信息素多的地方走，并且每只蚂蚁都会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。样，只不过它对窝的信息素做出反应，而对食物信息素没反应。（3 3）觅食规则）觅食规则 每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。它就会尽量避开。（4 4）移动规则）移动规则2.5 蚁群算法的规则蚁群算法的规则 如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。向，并且有信息素指引的话，它会按照觅食的规则行为。（5 5）避障规则）避障规则 每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。它走远的距离，播撒的信息素越来越少。（6 6）撒播信息素规则）撒播信息素规则 根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都根据这几条规则，蚂蚁之间并没有直接的关系，但是每