几种智能算法的原理几种智能算法的原理及应用介绍及应用介绍学学 院：院：数学与统计学院指导教师：指导教师：阮小娥汇汇 报报 人：人：王 彭————讨论班报告讨论班报告1. 主要内容：主要内容：1. 1. 遗传算法遗传算法2. 2. 蚁群算法蚁群算法3. 3. 模拟退火算法模拟退火算法4. 4. 粒子群算法粒子群算法5. 5. 总结与体会总结与体会2. 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 遗传算法的应用举例遗传算法的应用举例3. 1.1 遗传算法简介遗传算法简介 遗传算法简称遗传算法简称GAGA（（Genetic AlgorithmsGenetic Algorithms）是）是19621962年由美国年由美国MichiganMichigan大学的大学的HollandHolland教授提出的模拟自然界遗传机制和生物进教授提出的模拟自然界遗传机制和生物进化论而成的一种并行随机搜索最优化方法。
化论而成的一种并行随机搜索最优化方法 遗传算法是以达尔文的遗传算法是以达尔文的自然选择学说自然选择学说为基础发展起来的为基础发展起来的自然选择学说自然选择学说包括以下三个方面：包括以下三个方面： （（1 1））遗遗传传：：这这是是生生物物的的普普遍遍特特征征，，亲亲代代把把生生物物信信息息交交给给子子代代，，子子代代总总是是和和亲亲代代具具有有相相同同或或相相似似的的性性状状生生物物有有了了这这个个特特征征，，物物种种才才能能稳稳定存在 （（2 2））变变异异：：亲亲代代和和子子代代之之间间以以及及子子代代的的不不同同个个体体之之间间的的差差异异，，称称为为变异变异是随机发生的，变异的选择和积累是生命多样性的根源变异是随机发生的，变异的选择和积累是生命多样性的根源 （（3 3））生生存存斗斗争争和和适适者者生生存存：：具具有有适适应应性性变变异异的的个个体体被被保保留留下下来来，，不不具具有有适适应应性性变变异异的的个个体体被被淘淘汰汰，，通通过过一一代代代代的的生生存存环环境境的的选选择择作作用用，，性状逐渐逐渐与祖先有所不同，演变为新的物种。
性状逐渐逐渐与祖先有所不同，演变为新的物种4. 1.2 遗传算法的基本思想遗传算法的基本思想 遗传算法将遗传算法将““优胜劣汰，适者生存优胜劣汰，适者生存””的生物进化原理引入优的生物进化原理引入优化参数形成的编码串联群体中，按所选择的适应度函数并通过遗化参数形成的编码串联群体中，按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，使适适应度高的个体传中的复制、交叉及变异对个体进行筛选，使适适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代这样周而复始，群体中个体适应度不断提高，直又优于上一代这样周而复始，群体中个体适应度不断提高，直到满足一定的条件遗传算法的算法简单，可并行处理，并能到到满足一定的条件遗传算法的算法简单，可并行处理，并能到全局最优解全局最优解5. 1.3 遗传算法的基本操作遗传算法的基本操作 遗传算法的基本操作主要有：遗传算法的基本操作主要有：复制复制、、交叉交叉、、变异变异1 1））复制（复制（Reproduction OperatorReproduction Operator）） 复制是从一个旧种群中选择生命力强的个体位串产生新种群的过程。
复制是从一个旧种群中选择生命力强的个体位串产生新种群的过程具有高适应度的位串更有可能在下一代中产生一个或多个子孙具有高适应度的位串更有可能在下一代中产生一个或多个子孙 复制操作可以通过随机方法来实现首先产生复制操作可以通过随机方法来实现首先产生0~10~1之间均匀分布的随之间均匀分布的随机数，若某串的复制概率为机数，若某串的复制概率为40%40%，则当产生的随机数在，则当产生的随机数在0.40~1.00.40~1.0之间时，之间时，该串被复制，否则被淘汰该串被复制，否则被淘汰6. 1.3 遗传算法的基本操作遗传算法的基本操作（（2 2））交叉（交叉（Crossover OperatorCrossover Operator）） 复制操作能从旧种群中选择出优秀者，但不能创造新的染色体而复制操作能从旧种群中选择出优秀者，但不能创造新的染色体而交叉模拟了生物进化过程中的繁殖现象，通过两个染色体的交换组合，交叉模拟了生物进化过程中的繁殖现象，通过两个染色体的交换组合，来产生新的优良品种来产生新的优良品种 交叉的过程为：在匹配池中任选两个染色体，随机选择一点或多点交叉的过程为：在匹配池中任选两个染色体，随机选择一点或多点交换点位置；交换双亲染色体交换点右边的部分，即可得到两个新的染交换点位置；交换双亲染色体交换点右边的部分，即可得到两个新的染色体数字串。
色体数字串 交叉体现了自然界中信息交换的思想交叉有一点交叉、多点交叉、交叉体现了自然界中信息交换的思想交叉有一点交叉、多点交叉、还有一致交叉、顺序交叉和周期交叉一点交叉是最基本的方法，应用还有一致交叉、顺序交叉和周期交叉一点交叉是最基本的方法，应用较广它是指染色体切断点有一处，例：较广它是指染色体切断点有一处，例：7. 1.3 遗传算法的基本操作遗传算法的基本操作（（3 3））变异变异(Mutation Operator)(Mutation Operator) 变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素引起的变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变，它以很小的概率随机地改变遗传基因（表示染色体的符号串基因突变，它以很小的概率随机地改变遗传基因（表示染色体的符号串的某一位）的值在染色体以二进制编码的系统中，它随机地将染色体的某一位）的值在染色体以二进制编码的系统中，它随机地将染色体的某一个基因由的某一个基因由1 1变为变为0 0，或由，或由0 0变为变为1 1 若只有选择和交叉，而没有变异，则无法在初始基因组合以外的空若只有选择和交叉，而没有变异，则无法在初始基因组合以外的空间进行搜索，使进化过程在早期就陷入局部解而进入终止过程，从而影间进行搜索，使进化过程在早期就陷入局部解而进入终止过程，从而影响解的质量。
为了在尽可能大的空间中获得质量较高的优化解，必须采响解的质量为了在尽可能大的空间中获得质量较高的优化解，必须采用变异操作变异操作如下所示：用变异操作变异操作如下所示：8. 1.4 遗传算法的构成要素遗传算法的构成要素 遗传算法的构成要素主要有：遗传算法的构成要素主要有：染色体编码方法染色体编码方法、、个体适应度个体适应度评价评价、、遗传算子遗传算子及及遗传算法的运行参数遗传算法的运行参数1 1））染色体编码方法染色体编码方法 基本遗传算法使用固定长度的二进制符号来表示群体中的个体，基本遗传算法使用固定长度的二进制符号来表示群体中的个体，其等位基因是由二值符号集其等位基因是由二值符号集{0,1}{0,1}所组成初始个体基因值可用均匀分布所组成初始个体基因值可用均匀分布的随机值生成，如：的随机值生成，如：就可表示一个个体，该个体的染色体长度是就可表示一个个体，该个体的染色体长度是18189. 1.4 遗传算法的构成要素遗传算法的构成要素（（2 2））个体适应度评价个体适应度评价 基本遗传算法与个体适应度成正比的概率来决定当前群体中每个个基本遗传算法与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的概率多少。
为正确计算这个概率，要求所有个体遗传到下一代群体中的概率多少为正确计算这个概率，要求所有个体的适应度必须为正数或零因此，必须先确定由目标函数值体的适应度必须为正数或零因此，必须先确定由目标函数值J J到个体适到个体适应度应度f f之间的转换规则之间的转换规则3 3））遗传算子遗传算子 基本遗传算法使用下述三种遗传算子：基本遗传算法使用下述三种遗传算子： ① ① 选择运算选择运算: :使用比例选择算子；使用比例选择算子； ② ② 交叉运算交叉运算: :使用单点交叉算子；使用单点交叉算子； ③ ③ 变异运算变异运算: :使用基本位变异算子或均匀变异算子使用基本位变异算子或均匀变异算子10. 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。
11. 1.5 遗传算法的操作步骤遗传算法的操作步骤 对于一个需要进行优化的实际问题，一般可按下述步骤构造遗对于一个需要进行优化的实际问题，一般可按下述步骤构造遗传算法：传算法： 第一步第一步：确定决策变量及各种约束条件；：确定决策变量及各种约束条件； 第二步第二步：建立优化模型，即确定出目标函数的类型及数学描述形式或：建立优化模型，即确定出目标函数的类型及数学描述形式或量化方法；量化方法； 第三步第三步：确定表示可行解的染色体编码方法；：确定表示可行解的染色体编码方法； 第四步第四步：确定解码方法；：确定解码方法； 第第四四步步：：确确定定个个体体适适应应度度的的量量化化评评价价方方法法，，即即确确定定出出由由目目标标函函数数值值到到个体适应度的转换规则；个体适应度的转换规则； 第第五五步步：：设设计计遗遗传传算算子子，，即即确确定定选选择择运运算算、、交交叉叉运运算算、、变变异异运运算算等等遗遗传算子的具体操作方法传算子的具体操作方法 第六步第六步：确定遗传算法的有关运行参数，即：确定遗传算法的有关运行参数，即M,G,Pc,PmM,G,Pc,Pm等参数。
等参数12. 1.5 遗传算法的操作步骤遗传算法的操作步骤 遗传算法流程图：遗传算法流程图：13. 1.6 遗传算法的特点遗传算法的特点遗传算法的主要特点有：遗传算法的主要特点有： （（1 1））遗传算法是对参数的编码进行操作，而非对参数本身，遗传算法是对参数的编码进行操作，而非对参数本身，这就是使得我们这就是使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念，模仿自然界中生物的在优化计算过程中可以借鉴生物学中染色体和基因等概念，模仿自然界中生物的遗传和进化等机理；遗传和进化等机理； （（2 2））遗传算法同时使用多个搜索点的搜索信息遗传算法同时使用多个搜索点的搜索信息传统的优化方法往往是从解传统的优化方法往往是从解空间的单个初始点开始最优解的迭代搜索过程，单个搜索点所提供的信息不多，空间的单个初始点开始最优解的迭代搜索过程，单个搜索点所提供的信息不多，搜索效率不高，有时甚至使搜索过程局限于局部最优解而停滞不前搜索效率不高，有时甚至使搜索过程局限于局部最优解而停滞不前 遗传算法从由很多个体组成的一个初始群体开始最优解的搜索过程，而不是遗传算法从由很多个体组成的一个初始群体开始最优解的搜索过程，而不是从一个单一的个体开始搜索，这是遗传算法所特有的一种隐含并行性，因此遗传从一个单一的个体开始搜索，这是遗传算法所特有的一种隐含并行性，因此遗传算法的搜索效率较高。
算法的搜索效率较高 （（3 3））遗传算法直接以目标函数作为搜索信息遗传算法直接以目标函数作为搜索信息传统的优化算法不仅需要利用传统的优化算法不仅需要利用目标函数值，而且需要目标函数的导数值等辅助信息才能确定搜索方向而遗传目标函数值，而且需要目标函数的导数值等辅助信息才能确定搜索方向而遗传算法仅使用由目标函数值变换来的适应度函数值，就可以确定进一步的搜索方向算法仅使用由目标函数值变换来的适应度函数值，就可以确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助信息和搜索范围，无需目标函数的导数值等其他一些辅助信息14. 1.6 遗传算法的特点遗传算法的特点 遗传算法可应用于目标函数无法求导数或导数不存在的函数的优化问题，以遗传算法可应用于目标函数无法求导数或导数不存在的函数的优化问题，以及组合优化问题等及组合优化问题等 （（4 4））遗传算法使用概率搜索技术遗传算法使用概率搜索技术遗传算法的选择、交叉、变异等运算都是遗传算法的选择、交叉、变异等运算都是以一种概率的方式来进行的，因而遗传算法的搜索过程具有很好的灵活性随着以一种概率的方式来进行的，因而遗传算法的搜索过程具有很好的灵活性。
随着进化过程的进行，遗传算法新的群体会更多地产生出许多新的优良的个体进化过程的进行，遗传算法新的群体会更多地产生出许多新的优良的个体 （（5 5））遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜索；索； （（6 6））遗传算法对于待寻优的函数基本无限制，遗传算法对于待寻优的函数基本无限制，它既不要求函数连续，也不要它既不要求函数连续，也不要求函数可微，既可以是数学解析式所表示的显函数，又可以是映射矩阵甚至是神求函数可微，既可以是数学解析式所表示的显函数，又可以是映射矩阵甚至是神经网络的隐函数，因而应用范围较广；经网络的隐函数，因而应用范围较广； （（7 7））遗传算法具有并行计算的特点，遗传算法具有并行计算的特点，因而可通过大规模并行计算来提高计算因而可通过大规模并行计算来提高计算速度，适合大规模复杂问题的优化速度，适合大规模复杂问题的优化 15. 1.7 遗传算法的应用领域遗传算法的应用领域 遗传算法的应用领域主要有：遗传算法的应用领域主要有：函数优化函数优化、、组合优化组合优化、、生产调生产调度问题度问题、、自动控制自动控制、、机器人机器人、、图像处理等图像处理等。
1 1））函数优化函数优化 函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例尤其是对非线性、多模型、多目标的函数优化问题，采用的常用算例尤其是对非线性、多模型、多目标的函数优化问题，采用其他优化方法较难求解，而遗传算法却可以得到较好的结果其他优化方法较难求解，而遗传算法却可以得到较好的结果2 2））组合优化组合优化 随着问题的增大，组合优化问题的搜索空间也急剧扩大，采用传统随着问题的增大，组合优化问题的搜索空间也急剧扩大，采用传统的优化方法很难得到最优解遗传算法是寻求这种满意解的最佳工具的优化方法很难得到最优解遗传算法是寻求这种满意解的最佳工具例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用分问题等方面得到成功的应用16. 1.7 遗传算法的应用领域遗传算法的应用领域（（3 3））生产调度问题生产调度问题 在很多情况下，采用建立数学模型的方法难以对生产调度问题进行精在很多情况下，采用建立数学模型的方法难以对生产调度问题进行精确求解。
在现实生产中多采用一些经验进行调度遗传算法是解决复杂确求解在现实生产中多采用一些经验进行调度遗传算法是解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用产规划、任务分配等方面遗传算法都得到了有效的应用4 4））自动控制自动控制 在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已经在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已经在其中得到了初步的应用例如，利用遗传算法进行控制器参数的优化、在其中得到了初步的应用例如，利用遗传算法进行控制器参数的优化、基于遗传算法的模糊控制规则的学习、基于遗传算法的参数辨识、基于基于遗传算法的模糊控制规则的学习、基于遗传算法的参数辨识、基于遗传算法的神经网络结构的优化和权值学习等遗传算法的神经网络结构的优化和权值学习等17. 1.7 遗传算法的应用领域遗传算法的应用领域（（5 5））机器人机器人 例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人结构优化和行为协调等方面得到研究和应用。
规划、机器人结构优化和行为协调等方面得到研究和应用6 6））图像处理图像处理 遗传算法可用于图像处理过程中的扫描、特征提取、图像分割等的遗传算法可用于图像处理过程中的扫描、特征提取、图像分割等的优化计算目前遗传算法已经在模式识别、图像恢复、图像边缘特征提优化计算目前遗传算法已经在模式识别、图像恢复、图像边缘特征提取等方面得到了应用取等方面得到了应用18. 1.8 遗传算法的应用举例遗传算法的应用举例1 1 用遗传算法求函数极值用遗传算法求函数极值利用遗传算法求利用遗传算法求RosenbrockRosenbrock函数的极大值：函数的极大值：求解该问题遗传算法的构造过程：求解该问题遗传算法的构造过程：（（1 1）确定决策变量和约束条件）确定决策变量和约束条件决策变量为：决策变量为：（（2 2）建立优化模型）建立优化模型19. 1.8 遗传算法的应用举例遗传算法的应用举例（（3 3）确定编码方法）确定编码方法 用长度为用长度为1010位的二进制编码串来分别表示两个决策变量位的二进制编码串来分别表示两个决策变量x1,x2x1,x21010位二进位二进制编码串可以表示从制编码串可以表示从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 220. 1.8 遗传算法的应用举例遗传算法的应用举例（（4 4）确定解码方法）确定解码方法 解码时需要将解码时需要将2020位长的二进制编码串切断为两个位长的二进制编码串切断为两个1010位长的二进制编码串，位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为然后分别将它们转换为对应的十进制整数代码，分别记为y y1 1和和y y2 2。
依据个体编码方法和对定义域的离散化方法可知，将代码依据个体编码方法和对定义域的离散化方法可知，将代码y y转换为变量转换为变量x x的的解码公式为：解码公式为：例如，例如，对个体：对个体：它由两个代码所组成它由两个代码所组成上述两个代码经过解码后，可得到两个实际的值上述两个代码经过解码后，可得到两个实际的值21. 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）确定遗传算法的运行参数）确定遗传算法的运行参数22. 1.8 遗传算法的应用举例遗传算法的应用举例（（8 8）实验过程）实验过程①①完全随机生成初始种群完全随机生成初始种群 循环八次，达循环八次，达到暂时的最优值：到暂时的最优值：3414.8 对应的对应的x x1 1、、x x2 2坐标为：坐标为：(-1.9799,-1.9159) 种群向暂时的种群向暂时的最优染色体靠近最优染色体靠近23. 1.8 遗传算法的应用举例遗传算法的应用举例②②平均分配坐标轴生成初始种群平均分配坐标轴生成初始种群 循环八次，达循环八次，达到最优值：到最优值：3905.9 对应的对应的x x1 1、、x x2 2坐标为：坐标为：(--2.0480,-2.0480) 种群向最优染种群向最优染色体靠近色体靠近24. 1.8 遗传算法的应用举例遗传算法的应用举例 上述七个步骤构成了用于求函数极大值的优化计算基本遗传算法上述七个步骤构成了用于求函数极大值的优化计算基本遗传算法采用上述方法进行仿真，经过采用上述方法进行仿真，经过100100步迭代，最佳样本为步迭代，最佳样本为即当即当时，时，RosenbrockRosenbrock函数具有极大值，极大值为函数具有极大值，极大值为3905.93905.9。
25. 1.8 遗传算法的应用举例遗传算法的应用举例2 2 用遗传算法进行图像匹配用遗传算法进行图像匹配（（1 1）问题描述：）问题描述： 从一张图片中找出与另一张图片相似的部分为了便于说明从一张图片中找出与另一张图片相似的部分为了便于说明问题，本实验中目标图片为匹配图片加黑色背景随机生成，如下图问题，本实验中目标图片为匹配图片加黑色背景随机生成，如下图所示：）所示：）26. 1.8 遗传算法的应用举例遗传算法的应用举例2 2 用遗传算法进行图像匹配用遗传算法进行图像匹配（（2 2）编码）编码 对匹配图片左上角第一个像素在目标图片内的位置进行编码（要求匹配对匹配图片左上角第一个像素在目标图片内的位置进行编码（要求匹配图片不能超出目标图片的边界），采用二进制编码图片不能超出目标图片的边界），采用二进制编码3 3）计算适应度）计算适应度 适应度函数取为两幅图片对应位置上的值差的平方和的倒数适应度函数取为两幅图片对应位置上的值差的平方和的倒数4 4）选择）选择 按适应度函数的大小计算种群中某个体被选中的概率，按概率选择下一按适应度函数的大小计算种群中某个体被选中的概率，按概率选择下一代种群。
代种群27. 1.8 遗传算法的应用举例遗传算法的应用举例2 2 用遗传算法进行图像匹配用遗传算法进行图像匹配（（5 5）交叉）交叉 单点交叉、多点交叉（要求匹配图片不能超出目标图片的边界）单点交叉、多点交叉（要求匹配图片不能超出目标图片的边界）6 6）变异）变异 要求匹配图片不能超出目标图片的边界要求匹配图片不能超出目标图片的边界28. 1.8 遗传算法的应用举例遗传算法的应用举例（（7 7）实验结果与分析）实验结果与分析 对于此类简单的图片匹配的问题，遗传算法通常能较快的收敛到一个较对于此类简单的图片匹配的问题，遗传算法通常能较快的收敛到一个较好的位置，但对于复杂一些的图片匹配问题，容易收敛到局部极值点好的位置，但对于复杂一些的图片匹配问题，容易收敛到局部极值点29. 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 蚁群算法的应用举例蚁群算法的应用举例30. 2.1 蚂蚁的生理学特征蚂蚁的生理学特征 蚂蚁在蚂蚁在80008000万年前就建立起了自己的社会。
许多万年前就建立起了自己的社会许多““蚂蚁城市蚂蚁城市””往往由往往由50005000万个成员组成，并且是一个组织完好的复杂万个成员组成，并且是一个组织完好的复杂““城市城市”” 蚂蚁的群体行为主要包括蚂蚁的群体行为主要包括寻找食物寻找食物、、任务分配任务分配和和构造墓穴构造墓穴 研究中主要是以蚂蚁寻找食物之后能选择一条研究中主要是以蚂蚁寻找食物之后能选择一条最短路径最短路径来连来连接蚁穴和食物源接蚁穴和食物源 蚂蚁具有智能么？蚂蚁具有智能么？ 生物学家通过对蚂蚁的长期观察研究发现，每只蚂蚁的智能并不高，生物学家通过对蚂蚁的长期观察研究发现，每只蚂蚁的智能并不高，看起来没有集中的指挥，但他们却能协同的工作，集中食物建立起稳固看起来没有集中的指挥，但他们却能协同的工作，集中食物建立起稳固的蚁穴，依靠群体的能力发挥出了超出个体的智能的蚁穴，依靠群体的能力发挥出了超出个体的智能31. 2.2 Deneubourg双桥实验双桥实验 PasteelsPasteels，，DeneubourgDeneubourg和和GossGoss（（19871987）全部都在实验中研究）全部都在实验中研究真实蚂蚁信息素的遗留行为，他们称之为真实蚂蚁信息素的遗留行为，他们称之为““双桥实验双桥实验””。
在这个在这个双桥实验模型中，蚁穴通过一个蚁穴和食物源之间用两个长度相双桥实验模型中，蚁穴通过一个蚁穴和食物源之间用两个长度相等的桥连接作者使用能够辨认路径的阿根廷蚂蚁，简而言之这等的桥连接作者使用能够辨认路径的阿根廷蚂蚁，简而言之这些蚂蚁可以预测或者搜索他们的群类些蚂蚁可以预测或者搜索他们的群类32. 2.2 Deneubourg双桥实验双桥实验等长双桥实验等长双桥实验 在前面的设定下，蚂蚁开始在前面的设定下，蚂蚁开始探索蚁穴周围的环境最终到达食探索蚁穴周围的环境最终到达食物源沿着他们的在蚁穴和食物物源沿着他们的在蚁穴和食物源之间的路径，阿根廷释放信息源之间的路径，阿根廷释放信息素，开始每个蚂蚁都随机选择两素，开始每个蚂蚁都随机选择两条桥之间的的一个，在随后的阶条桥之间的的一个，在随后的阶段里因为随机的波动，其中一个段里因为随机的波动，其中一个桥的信息素表现出比另外一条的桥的信息素表现出比另外一条的信息素更为集中，因此吸引了更信息素更为集中，因此吸引了更多的蚂蚁这个行为增加了这个多的蚂蚁这个行为增加了这个桥上的信息素，也就吸引了更多桥上的信息素，也就吸引了更多的蚂蚁因此，过了一段时间以的蚂蚁。
因此，过了一段时间以后，整个种群都聚合于使用这个后，整个种群都聚合于使用这个高度集中的桥运送高度集中的桥运送33. 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)桥的概率为桥的概率为: :34. 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.35. 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）人工蚁可以根据要求增加功能）人工蚁可以根据要求增加功能36. 2.4 蚁群算法的原理蚁群算法的原理 蚂蚁在运动过程中会通过在路上释放一种特殊的分泌物蚂蚁在运动过程中会通过在路上释放一种特殊的分泌物————信息素来寻找路径。
当它碰到一个还没有走过的路口是就随机的信息素来寻找路径当它碰到一个还没有走过的路口是就随机的选择一条路径前行，同时释放出与路径长度有关的选择一条路径前行，同时释放出与路径长度有关的信息素信息素蚂蚁走的路越长，则释放的信息量越小当后来的蚂蚁再次碰到这个走的路越长，则释放的信息量越小当后来的蚂蚁再次碰到这个路口时，路口时，选择信息量较大的路径的概率相对较大选择信息量较大的路径的概率相对较大，这样便形成了，这样便形成了一个正反馈机制一个正反馈机制最优路径上得信息量越来越大，而其他路径上最优路径上得信息量越来越大，而其他路径上的信息量却随时间逐渐减少最终整个蚁群会找出最优路径的信息量却随时间逐渐减少最终整个蚁群会找出最优路径 （（1 1）蚁群之间通过信息素和环境进行通信蚁群之间通过信息素和环境进行通信 （（2 2）蚂蚁对环境的反应由其内部模式决定蚂蚁对环境的反应由其内部模式决定 （（3 3）个体水平上，每个蚂蚁相对独立；群体水平上，每只蚂蚁的）个体水平上，每个蚂蚁相对独立；群体水平上，每只蚂蚁的行为是随机的行为是随机的 蚁群算法的理论假设蚁群算法的理论假设37. 2.5 蚁群算法的规则蚁群算法的规则蚁群算法中的蚂蚁满足的规则主要有以下几个方面：蚁群算法中的蚂蚁满足的规则主要有以下几个方面： 蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是（一般是3 3），那么它能观察到的范围就是），那么它能观察到的范围就是3*33*3个方格世界，并且能移个方格世界，并且能移动的距离也在这个范围之内。
动的距离也在这个范围之内 （（1 1）范围）范围 蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素每个蚂蚁都仅仅能感知素，一种是找到窝的蚂蚁洒下的窝的信息素每个蚂蚁都仅仅能感知它范围内环境信息环境以一定的速率让信息素消失它范围内环境信息环境以一定的速率让信息素消失 （（2 2）环境）环境38. 2.5 蚁群算法的规则蚁群算法的规则 在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁都会以小概率犯多，这样，它就朝信息素多的地方走，并且每只蚂蚁都会以小概率犯错误，从而并不是往信息素最多的点移动。
蚂蚁找窝的规则和上面一错误，从而并不是往信息素最多的点移动蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应样，只不过它对窝的信息素做出反应，而对食物信息素没反应 （（3 3）觅食规则）觅食规则 每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动为了防止蚂蚁原地转圈，它会在运动的方向有一个随机的小的扰动为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开它就会尽量避开 （（4 4）移动规则）移动规则39. 2.5 蚁群算法的规则蚁群算法的规则 如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。
向，并且有信息素指引的话，它会按照觅食的规则行为 （（5 5）避障规则）避障规则 每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少它走远的距离，播撒的信息素越来越少 （（6 6）撒播信息素规则）撒播信息素规则 根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了比如，当一只蚂蚁找到了食物，它并没有直接告诉其间关联起来了比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物40. 2.6 蚁群算法的特点蚁群算法的特点 在系统论中，自组织和它组织是组织的两个基本分类，其区别在在系统论中，自组织和它组织是组织的两个基本分类，其区别在于组织力或组织指令是来自于系统的内部还是来自于系统的外部，来于组织力或组织指令是来自于系统的内部还是来自于系统的外部，来自于系统内部的是自组织，来自于系统外部的是他组织。
如果系统在自于系统内部的是自组织，来自于系统外部的是他组织如果系统在获得空间的、时间的或者功能结构的过程中，没有外界的特定干预，获得空间的、时间的或者功能结构的过程中，没有外界的特定干预，我们便说系统是自组织的在抽象意义上讲，自组织就是在没有外界我们便说系统是自组织的在抽象意义上讲，自组织就是在没有外界作用下使得系统墒增加的过程作用下使得系统墒增加的过程( (即是系统从无序到有序的变化过程即是系统从无序到有序的变化过程) )蚁群算法充分休现了这个过程，以蚂蚁群体优化为例子说明当算法蚁群算法充分休现了这个过程，以蚂蚁群体优化为例子说明当算法开始的初期，单个的人工蚂蚁无序的寻找解，算法经过一段时间的演开始的初期，单个的人工蚂蚁无序的寻找解，算法经过一段时间的演化，人工蚂蚁间通过信息激素的作用，自发的越来越趋向于寻找到接化，人工蚂蚁间通过信息激素的作用，自发的越来越趋向于寻找到接近最优解的一些解，这就是一个无序到有序的过程近最优解的一些解，这就是一个无序到有序的过程1 1）蚁群算法是一种自组织的算法蚁群算法是一种自组织的算法41. 2.6 蚁群算法的特点蚁群算法的特点 每只蚂蚁搜索的过程彼此独立，仅通过信息激素进行通信。
所以每只蚂蚁搜索的过程彼此独立，仅通过信息激素进行通信所以蚁群算法则可以看作是一个分布式的多蚁群算法则可以看作是一个分布式的多agentagent系统，它在问题空间的多系统，它在问题空间的多点同时开始进行独立的解搜索，不仅增加了算法的可靠性，也使得算点同时开始进行独立的解搜索，不仅增加了算法的可靠性，也使得算法具有较强的全局搜索能力法具有较强的全局搜索能力2 2）蚁群算法是一种本质上并行的算法蚁群算法是一种本质上并行的算法42. 2.6 蚁群算法的特点蚁群算法的特点 从真实蚂蚁的觅食过程中我们不难看出，蚂蚁能够最终找到最短从真实蚂蚁的觅食过程中我们不难看出，蚂蚁能够最终找到最短路径，直接依赖于最短路径上信息激素的堆积，而信息激素的堆积却路径，直接依赖于最短路径上信息激素的堆积，而信息激素的堆积却是一个正反馈的过程对蚁群算法来说，初始时刻在环境中存在完全是一个正反馈的过程对蚁群算法来说，初始时刻在环境中存在完全相同的信息激素，给予系统一个微小扰动，使得各个边上的轨迹浓度相同的信息激素，给予系统一个微小扰动，使得各个边上的轨迹浓度不相同，蚂蚁构造的解就存在了优劣，算法采用的反馈方式是在较优不相同，蚂蚁构造的解就存在了优劣，算法采用的反馈方式是在较优的解经过的路径留下更多的信息激素，而更多的信息激素又吸引了更的解经过的路径留下更多的信息激素，而更多的信息激素又吸引了更多的蚂蚁，这个正反馈的过程使得初始的不同得到不断的扩大，同时多的蚂蚁，这个正反馈的过程使得初始的不同得到不断的扩大，同时又引导整个系统向最优解的方向进化。
因此，正反馈是蚂蚁算法的重又引导整个系统向最优解的方向进化因此，正反馈是蚂蚁算法的重要特征，它使得算法演化过程得以进行要特征，它使得算法演化过程得以进行 （（3 3）蚁群算法是一种正反馈的算法蚁群算法是一种正反馈的算法43. 2.6 蚁群算法的特点蚁群算法的特点 相对于其它算法，蚁群算法对初始路线要求不高，即蚁群算法的相对于其它算法，蚁群算法对初始路线要求不高，即蚁群算法的求解结果不依赖子初始路线的选择，而且在搜索过程中不需要进行人求解结果不依赖子初始路线的选择，而且在搜索过程中不需要进行人工的调整其次，蚁群算法的参数数目少，设置简单，易于蚁群算法工的调整其次，蚁群算法的参数数目少，设置简单，易于蚁群算法应用到其它组合优化问题的求解应用到其它组合优化问题的求解 （（4 4）蚁群算法具有较强的鲁棒性蚁群算法具有较强的鲁棒性44. 2.7 蚁群算法的应用领域蚁群算法的应用领域 蚁群算法主要应用于：蚁群算法主要应用于：组合优化问题组合优化问题、、车间作业调度问车间作业调度问题题、、网络路由问题网络路由问题、、车辆路径问题车辆路径问题、、机器人领域机器人领域、、电力系统电力系统、、故障诊断故障诊断、、控制参数优化控制参数优化、、岩土工程岩土工程、、生命科学等若干领域生命科学等若干领域。
45. 2.8 蚁群算法的应用举例蚁群算法的应用举例蚁群算法解决蚁群算法解决TSPTSP问题问题 旅行商问题，即旅行商问题，即TSPTSP问题（问题（Travelling Salesman ProblemTravelling Salesman Problem）又译）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一假设为旅行推销员问题、货郎担问题，是数学领域中著名问题之一假设有一个旅行商人要拜访有一个旅行商人要拜访n n个城市，他必须选择所要走的路径，路径的限个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市路径制是每个城市只能拜访一次，而且最后要回到原来出发的城市路径的选择目标是要求得的路径路程为所有路径之中的最小值的选择目标是要求得的路径路程为所有路径之中的最小值 TSP TSP问题是一个组合优化问题该问题可以被证明具有问题是一个组合优化问题该问题可以被证明具有NPCNPC计算复计算复杂性因此，任何能使该问题的求解得以简化的方法，都将受到高度杂性因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。
的评价和关注2.8.1 2.8.1 问题描述问题描述46. 2.8 蚁群算法的应用举例蚁群算法的应用举例（（1 1）蚂蚁主体具有的特征：）蚂蚁主体具有的特征：2.8.2 2.8.2 用蚁群算法解决用蚁群算法解决TSPTSP问题问题 ① ①在从城市在从城市i i到到j j的过程中或者一次循环结束，在边（的过程中或者一次循环结束，在边（i i，，j j）释放信息素释放信息素 ② ②有概率的访问下一个城市，这个概率是两城市间和连接两城市的路径有概率的访问下一个城市，这个概率是两城市间和连接两城市的路径上存有轨迹量的函数上存有轨迹量的函数 ③ ③不允许蚂蚁访问已经访问过的城市不允许蚂蚁访问已经访问过的城市47. 2.8 蚁群算法的应用举例蚁群算法的应用举例（（2 2）引入相关记号）引入相关记号 为了模拟实际蚁群的行为首先引入以下记号：为了模拟实际蚁群的行为首先引入以下记号：48. 2.8 蚁群算法的应用举例蚁群算法的应用举例（（3 3）蚂蚁从一个城市移动到另一个城市的概率）蚂蚁从一个城市移动到另一个城市的概率 在初始时刻，各条路径上的信息素量相等，设在初始时刻，各条路径上的信息素量相等，设。
蚂蚁蚂蚁k k（（k=1k=1，，2…2…，，m m）在运动中根据各条路径上的信息素量决定转）在运动中根据各条路径上的信息素量决定转移方向 位于城市位于城市i i的蚂蚁的蚂蚁k k选择移动到城市选择移动到城市j j的概率的概率为：为：公式公式 149. 2.8 蚁群算法的应用举例蚁群算法的应用举例（（4 4）禁忌表）禁忌表 与真实蚁不同，人工蚁群系统具有记忆功能为了满足蚂蚁必须经与真实蚁不同，人工蚁群系统具有记忆功能为了满足蚂蚁必须经过所有过所有n n个不同的城市这个约束条件，为每只蚂蚁都设计了一个数据结构，个不同的城市这个约束条件，为每只蚂蚁都设计了一个数据结构，成为禁忌表用来记录了成为禁忌表用来记录了t t时刻蚂蚁已经经过的城市，不允许该蚂蚁在本时刻蚂蚁已经经过的城市，不允许该蚂蚁在本次循环中再经过这些城市当本次循环结束后禁忌表被用来计算该蚂蚁次循环中再经过这些城市当本次循环结束后禁忌表被用来计算该蚂蚁所建立的解决方案之后禁忌表清空蚂蚁又可以自由地选择所建立的解决方案之后禁忌表清空蚂蚁又可以自由地选择50. 2.8 蚁群算法的应用举例蚁群算法的应用举例（（5 5）信息素的调整）信息素的调整 经过经过n n个时刻，蚂蚁完成一次循环，各路径上的信息素根据如下公式个时刻，蚂蚁完成一次循环，各路径上的信息素根据如下公式调整：调整：其中：其中：表示第表示第k k只蚂蚁在时刻只蚂蚁在时刻(t,t+1)(t,t+1)留在路径留在路径(i,j)(i,j)上的信息素。
上的信息素表示本次循环路径表示本次循环路径(i,j)(i,j)上的信息素增量上的信息素增量公式公式 351. 2.8 蚁群算法的应用举例蚁群算法的应用举例（（6 6）实现过程）实现过程52. 2.8 蚁群算法的应用举例蚁群算法的应用举例53. 2.8 蚁群算法的应用举例蚁群算法的应用举例54. 2.8 蚁群算法的应用举例蚁群算法的应用举例（（5 5）仿真结果）仿真结果 采用采用MATLABMATLAB来仿真实现蚁群算法解来仿真实现蚁群算法解TSPTSP问题问题 对全国3131个省会城市个省会城市的一个的一个TSPTSP计算通过程序仿真得到实验结果非常好！计算通过程序仿真得到实验结果非常好！55. 2.8.3 用遗传算法解决用遗传算法解决TSP问题问题（（1 1）用遗传算法解）用遗传算法解TSPTSP问题主要集中在以下几个方面：问题主要集中在以下几个方面：2.8.3 2.8.3 用遗传算法解决用遗传算法解决TSPTSP问题问题 ① ①采用适当的表示方法表示个体的编码；采用适当的表示方法表示个体的编码； ② ②设计可用的遗传算子，以保持父代的特性避免新个体的不可行性；设计可用的遗传算子，以保持父代的特性避免新个体的不可行性； ③ ③防止算法过早的收敛。
防止算法过早的收敛2 2）编码）编码 路径表示是路径表示是TSPTSP问题最自然、最直接的表示方式它直接采用城市在路问题最自然、最直接的表示方式它直接采用城市在路径中的相对位置来进行表示径中的相对位置来进行表示 例如，路径例如，路径5—1—7—8—6—2—9—3—45—1—7—8—6—2—9—3—4直接表示成（直接表示成（5 1 7 8 6 2 9 3 5 1 7 8 6 2 9 3 4 4）56. 2.8.3 用遗传算法解决用遗传算法解决TSP问题问题（（3 3）交叉）交叉部分映射杂交部分映射杂交 首先随机地在父体中选取两个杂交点，并交换相应的段，再根据该段内首先随机地在父体中选取两个杂交点，并交换相应的段，再根据该段内的城市确定部分映射在每个父体上先填入无冲突的城市，而对有冲突的城的城市确定部分映射在每个父体上先填入无冲突的城市，而对有冲突的城市依照映射关系选择候选的城市，直到找到无冲突的城市填入，按此方法获市依照映射关系选择候选的城市，直到找到无冲突的城市填入，按此方法获得了杂交后的两个后代得了杂交后的两个后代 实例：如两父串及匹配区域为实例：如两父串及匹配区域为 A A＝＝9 8 4 | 9 8 4 | 5 6 7 5 6 7 | 1 3 2 0| 1 3 2 0 B B＝＝8 7 1 | 8 7 1 | 2 3 0 2 3 0 | 9 5 4 6| 9 5 4 6 首先交换首先交换A A和和B B的两个匹配区域，得到的两个匹配区域，得到 A’A’＝＝9 8 4 | 9 8 4 | 2 3 0 2 3 0 | l 3 2 0| l 3 2 0 B’ B’＝＝8 7 1 | 8 7 1 | 5 6 7 5 6 7 | 9 5 4| 9 5 4 对于对于A’A’、、B’B’两子串中匹配区域以外出现的遍历重复，依据匹配区域内两子串中匹配区域以外出现的遍历重复，依据匹配区域内的位置映射关系，逐一进行交换。
对于的位置映射关系，逐一进行交换对于A’A’有有2 2到到5 5，，3 3到到6 6，，0 0到到7 7的位置符号的位置符号映射，对映射，对A’A’的匹配区以外的的匹配区以外的2 2，，3 3，，0 0分别以分别以5 5，，6 6，，7 7替换替换，则得，则得 A”A”＝＝9 8 4 | 2 3 0 | 1 9 8 4 | 2 3 0 | 1 6 5 76 5 7同理可得：同理可得： B”B”＝＝8 8 0 0 1 | 5 6 7 | 9 1 | 5 6 7 | 9 2 2 4 4 3 3这样，每个子串的次序部分地由其父串确定这样，每个子串的次序部分地由其父串确定 57. 2.8.3 用遗传算法解决用遗传算法解决TSP问题问题（（3 3）变异）变异倒置变异倒置变异 利用简单的倒置操作来进行变异即首先在父体中随机地选择两个截断利用简单的倒置操作来进行变异即首先在父体中随机地选择两个截断点，然后将该两点内的子串中的城市进行反序操作点，然后将该两点内的子串中的城市进行反序操作 A A ＝＝1 2 3 | 1 2 3 | 4 5 6 4 5 6 | 7 8 9 0| 7 8 9 0A’A’＝＝1 2 3 | 1 2 3 | 6 5 4 6 5 4 | 7 8 9 0| 7 8 9 0插入变异插入变异插入算子就是随机选择一个城市，并将它插入到一个随机位置中去。
插入算子就是随机选择一个城市，并将它插入到一个随机位置中去 A A ＝＝1 2 3 4 1 2 3 4 5 5 6 7 8 9 6 7 8 9 A’ A’＝＝1 2 1 2 5 5 3 4 6 7 8 9 3 4 6 7 8 9移位变异移位变异 移位算子是选择一个子路径巡回，然后把它插入一个随机的位置移位算子是选择一个子路径巡回，然后把它插入一个随机的位置 互换变异互换变异互换变异也被称作基于次序的变异（互换变异也被称作基于次序的变异（order-based mutationorder-based mutation），操作方），操作方法是：随机的选择两个城市，并交换其所处的位置法是：随机的选择两个城市，并交换其所处的位置对于串对于串A AA A ＝＝1 2 3 1 2 3 4 4 | 5 6 | 5 6 7 7 | 8 9| 8 9若对换点为若对换点为4 4，，7 7，则经对换后，，则经对换后，A’A’为为A’A’＝＝1 2 3 1 2 3 7 7 | 5 6 | 5 6 4 4 | 8 9| 8 958. 2.8.3 用遗传算法解决用遗传算法解决TSP问题问题 从群体规模来看，有变化规模的方式，也有恒定规模的群体构成方式等。
从群体规模来看，有变化规模的方式，也有恒定规模的群体构成方式等 在遗传算法中，最常见的选择机制是依据适应度的比例概率选择机制；在遗传算法中，最常见的选择机制是依据适应度的比例概率选择机制；在有限规模的群体中，适应度较高的个体有较大的机会繁殖后代，即生物进在有限规模的群体中，适应度较高的个体有较大的机会繁殖后代，即生物进化论上的适者生存规则化论上的适者生存规则在新一代群体构成方法方面存在：在新一代群体构成方法方面存在： N N方式：全部替换上一代群体的全刷新代际更新方式方式：全部替换上一代群体的全刷新代际更新方式 E E方式：保留一个最好的父串的最佳保留（方式：保留一个最好的父串的最佳保留（elitistelitist）群体构造方式群体构造方式 G G方式：按一定比例更新群体中的部分个体的部分更新方式（或称代沟方式：按一定比例更新群体中的部分个体的部分更新方式（或称代沟方法，这种情况的极端是每代仅删去一个最不适的个体的最劣死亡方式）方法，这种情况的极端是每代仅删去一个最不适的个体的最劣死亡方式） B B方式：从产生的子代和父代中挑选最好的若干个个体的群体构成形式。
方式：从产生的子代和父代中挑选最好的若干个个体的群体构成形式 一般讲，一般讲，N N方式的全局搜索性能最好，但收敛速度最慢；方式的全局搜索性能最好，但收敛速度最慢；B B方式收敛速度方式收敛速度最快，但全局搜索性能最差；最快，但全局搜索性能最差；E E方式和方式和G G方式的性能介于方式的性能介于N N方式和方式和B B方式之间方式之间在求解货郎担问题的应用中，多选用在求解货郎担问题的应用中，多选用E E方式 （（4 4）选择机制和群体构成）选择机制和群体构成59. 2.8.3 用遗传算法解决用遗传算法解决TSP问题问题 算法简单，从总体趋势上看，算法总是朝着路径和变小的方向收敛的，算法简单，从总体趋势上看，算法总是朝着路径和变小的方向收敛的，得到的结果也较好，不过收敛速度较慢，且存在比较好的染色体（路径）被得到的结果也较好，不过收敛速度较慢，且存在比较好的染色体（路径）被淘汰的情况淘汰的情况5 5）实验结果与分析）实验结果与分析60. 3.模拟退火模拟退火 算法算法3.1 3.1 模拟退火算法简介模拟退火算法简介3.2 3.2 模拟退火算法基本原理模拟退火算法基本原理3.33.3 优化问题与物理退火的类比优化问题与物理退火的类比61. 3.1 模拟退火算法简介模拟退火算法简介模拟退火的思想模拟退火的思想 开始使劲晃动开始使劲晃动( (先高温加热先高温加热) )然后慢慢降低摇晃的强度然后慢慢降低摇晃的强度( (逐渐降温逐渐降温)[)[退退火过程火过程] ]。
想象在不平的表面上如何使一个乒乓球掉到最深的裂缝中想象在不平的表面上如何使一个乒乓球掉到最深的裂缝中——如果只如果只让其在表面滚动，则它只会停留在局部极小点让其在表面滚动，则它只会停留在局部极小点/ / 如果晃动平面，可以使如果晃动平面，可以使乒乓球弹出局部极小点乒乓球弹出局部极小点/ / 技巧是晃动足够大使乒乓球弹出局部极小点，技巧是晃动足够大使乒乓球弹出局部极小点，但又不能太大把它从全局极小点中赶出但又不能太大把它从全局极小点中赶出模拟退火的思路模拟退火的思路算法的目的算法的目的 解决解决NPNP复杂性问题；复杂性问题； 克服优化过程陷入局部极小；克服优化过程陷入局部极小； 克服初值依赖性克服初值依赖性62. 3.2 模拟退火算法基本原理模拟退火算法基本原理（（1 1）物理退火过程）物理退火过程 ① ①加温过程加温过程其目的是增强粒子的热运动，使其偏离平衡位置当温度足够其目的是增强粒子的热运动，使其偏离平衡位置当温度足够高时，固体将溶解为液体，溶解过程与系统的熵增过程联系，系统能量也随温度高时，固体将溶解为液体，溶解过程与系统的熵增过程联系，系统能量也随温度的升高而增大，使得每一粒子的状态都具有充分的的升高而增大，使得每一粒子的状态都具有充分的随机性随机性。
② ②等温过程等温过程物理学的知识告诉我们，对于与周围环境交换热量而温度不变物理学的知识告诉我们，对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到最小时，系统达到平衡态平衡态 ③ ③冷却过程冷却过程目的是使粒子的热运动减弱并渐趋有序，系统能量目的是使粒子的热运动减弱并渐趋有序，系统能量逐渐逐渐下降，下降，从而得到低能的晶体结构在常温时达到基态，内能减为从而得到低能的晶体结构在常温时达到基态，内能减为最小最小 退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，后逐步降温使之冷却，最后分子以低能状态排列， 固体达到某种稳定状固体达到某种稳定状态 物理退火过程的发展阶段物理退火过程的发展阶段63. 3.2 模拟退火算法基本原理模拟退火算法基本原理（（2 2）数学表述）数学表述 物体加热至一定温度后，所有分子在状态空间物体加热至一定温度后，所有分子在状态空间D D中自由运动，随着温中自由运动，随着温度的下降，分子逐渐停留在不同的状态。
在温度最低时，分子重新以一度的下降，分子逐渐停留在不同的状态在温度最低时，分子重新以一定的结构排列定的结构排列 在温度在温度T, T, 分子停留在状态分子停留在状态r r满足满足BoltzmannBoltzmann概率分布概率分布: :其中：其中：表示分子能量的一个随机变量；表示分子能量的一个随机变量；表示状态表示状态r r的能量；的能量；为为BoltzmannBoltzmann常数，常数，为概率分布的标准化因子：为概率分布的标准化因子：；；64. 3.2 模拟退火算法基本原理模拟退火算法基本原理在同一个温度在同一个温度T T，选定两个能量，选定两个能量E1
在一定温度下，搜索从一个状态随机地变化到另一个状态；随着温在一定温度下，搜索从一个状态随机地变化到另一个状态；随着温度的不断下降直到最低温度，搜索过程以概率度的不断下降直到最低温度，搜索过程以概率1 1停留在最优解停留在最优解上表表明：上表表明：模拟退火算法求解思路：模拟退火算法求解思路：66. 3.3 优化问题与物理退火的类比优化问题与物理退火的类比优化问题优化问题物理退火物理退火解解分子状态分子状态最优解最优解能量最低状态能量最低状态目标函数目标函数能量能量设定初始温度设定初始温度熔解过程熔解过程Metropolis抽样抽样等温过程等温过程温度的下降温度的下降冷却过程冷却过程67. 4.粒子群算法粒子群算法4.1 4.1 粒子群算法简介粒子群算法简介4.2 4.2 粒子群算法的基本原则粒子群算法的基本原则4.34.3 粒子群算法的基本条件粒子群算法的基本条件4.4 4.4 粒子群算法的数学表述粒子群算法的数学表述68. 4.1 粒子群算法简介粒子群算法简介 粒子群算法粒子群算法(particle swarm optimization(particle swarm optimization，，PSO)PSO)由由KennedyKennedy和和EberhartEberhart在在19951995年提出，该算法年提出，该算法模拟鸟集群飞行觅食模拟鸟集群飞行觅食的行为，的行为，鸟之间通过集体的协作使群体达到最优目的，是一种基于鸟之间通过集体的协作使群体达到最优目的，是一种基于Swarm Swarm IntelligenceIntelligence的优化方法。
同遗传算法类似，也是一种基于群体的优化方法同遗传算法类似，也是一种基于群体叠代的，但并没有遗传算法用的交叉以及变异，而是粒子在解空叠代的，但并没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子进行搜索间追随最优的粒子进行搜索 PSO PSO的优势在于简单容易实现同时又有深刻的智能背景，既适的优势在于简单容易实现同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用，并且没有许多参数需要调整合科学研究，又特别适合工程应用，并且没有许多参数需要调整69. 4.1 粒子群算法简介粒子群算法简介鸟食鸟优化策略为两个动作的合成：优化策略为两个动作的合成：（（1）鸟群向距离食物最近的那只鸟的方向飞行）鸟群向距离食物最近的那只鸟的方向飞行（（2）每只鸟向自身的最优方向飞行）每只鸟向自身的最优方向飞行已知：（已知：（1 1）鸟的位置）鸟的位置（（2 2）距离食物最近的那）距离食物最近的那只鸟只鸟求解：这群鸟在最短时求解：这群鸟在最短时间搜寻到这块食物的飞行间搜寻到这块食物的飞行策略策略模拟群鸟觅食过程模拟群鸟觅食过程70. 4.2 粒子群算法的基本原则粒子群算法的基本原则 粒子群优化算法源于粒子群优化算法源于19871987年年ReynoldsReynolds对鸟群社会系统对鸟群社会系统boidsboids的的仿真研究，仿真研究，boidsboids是一个是一个CASCAS。
在在boidsboids中，一群鸟在空中飞行，每中，一群鸟在空中飞行，每个鸟遵守以下三条规则：个鸟遵守以下三条规则： （（1 1）避免与相邻的鸟发生碰撞冲突；）避免与相邻的鸟发生碰撞冲突； （（2 2）尽量与自己周围的鸟在速度上保持协调和一致；）尽量与自己周围的鸟在速度上保持协调和一致； （（3 3）尽量试图向自己所认为的群体中靠近尽量试图向自己所认为的群体中靠近 仅通过使用这三条规则，仅通过使用这三条规则，boidsboids系统就出现非常逼真的群体聚集行为，系统就出现非常逼真的群体聚集行为，鸟成群地在空中飞行，当遇到障碍时它们会分开绕行而过，随后又会重鸟成群地在空中飞行，当遇到障碍时它们会分开绕行而过，随后又会重新形成群体新形成群体 71. 4.3 粒子群算法的基本条件粒子群算法的基本条件基本条件基本条件（（1 1）目标搜索空间为）目标搜索空间为D D维空间2 2）粒子群由）粒子群由m m个粒子组成个粒子组成3 3）第）第i i个粒子在个粒子在D D维空间的位置为维空间的位置为 （（4 4）第）第i i个粒子的飞翔速度为个粒子的飞翔速度为 （（5 5）第）第i i个粒子的最优位置个粒子的最优位置（（6 6）全局最优位置）全局最优位置 72. 4.2 粒子群算法的数学表述粒子群算法的数学表述PSOPSO算法数学表示如下：算法数学表示如下： 设搜索空间为设搜索空间为D D维，总粒子数为维，总粒子数为n n。
第第i i个粒子位置表示为向量个粒子位置表示为向量Xi=( Xi=( xi1, xi2,…, xiD )xi1, xi2,…, xiD )；第；第i i个粒子个粒子 “ “飞行飞行””历史中的过去最优位置（即历史中的过去最优位置（即该位置对应解最优）为该位置对应解最优）为Pi=( pi1,pi2,…,piD )Pi=( pi1,pi2,…,piD )，其中第，其中第g g个粒子的过去个粒子的过去最优位置最优位置PgPg为所有为所有Pi ( i=1, …,n)Pi ( i=1, …,n)中的最优；第中的最优；第i i个粒子的位置变化率个粒子的位置变化率（速度）为向量（速度）为向量Vi=(vi1, vi2,…, viD)Vi=(vi1, vi2,…, viD)每个粒子的位置按如下公式每个粒子的位置按如下公式进行变化（进行变化（““飞行飞行””）：）：73. 4.2 粒子群算法的数学表述粒子群算法的数学表述（1）（2） 其中，其中，C C1,C21,C2为正常数，称为加速因子；为正常数，称为加速因子；randrand( )( )为为[0[0，，1]1]之间的随机之间的随机数；数；w w称惯性因子，称惯性因子，w w较大适于对解空间进行大范围探查较大适于对解空间进行大范围探查(exploration)(exploration)，，w w较小适于进行小范围开挖较小适于进行小范围开挖(exploitation)(exploitation)。
第第d d（（1 1≤d≤≤d≤D D）维的位置变化）维的位置变化范围为范围为[-XMAXd , XMAXd][-XMAXd , XMAXd]，速度变化范围为，速度变化范围为[-VMAXd , VMAXd][-VMAXd , VMAXd]，迭代中若，迭代中若位置和速度超过边界范围则取边界值位置和速度超过边界范围则取边界值 74. 4.2 粒子群算法的数学表述粒子群算法的数学表述 粒子群初始位置和速度随机产生，然后按公式粒子群初始位置和速度随机产生，然后按公式(1)(2)(1)(2)进行进行迭代，直至找到满意的解目前，常用的粒子群算法将全体粒迭代，直至找到满意的解目前，常用的粒子群算法将全体粒子群子群(Global)(Global)分成若干个有部分粒子重叠的相邻子群，每个粒分成若干个有部分粒子重叠的相邻子群，每个粒子根据子群子根据子群(Local)(Local)内历史最优内历史最优PlPl调整位置，即公式调整位置，即公式(2)(2)中中PgdPgd换换为为PldPld 75. 5 总结与体会总结与体会 （（1 1）智能算法源于对现实生活中事物的观察与思考。
智能算法源于对现实生活中事物的观察与思考 （（2 2）智能算法普遍原理简单，易于理解，且结果较好智能算法普遍原理简单，易于理解，且结果较好 （（3 3）可以解决很难给出解析表达式的问题可以解决很难给出解析表达式的问题 （（4 4）当把实际问题编码等手段抽象为智能模型的时候，与问）当把实际问题编码等手段抽象为智能模型的时候，与问题本身的实际意义关系不大，易于推广题本身的实际意义关系不大，易于推广 （（5 5）算法的收敛性证明较麻烦算法的收敛性证明较麻烦 （（6 6）算法收敛较慢，有时候与初值的选取关系较大，算法的）算法收敛较慢，有时候与初值的选取关系较大，算法的收敛速度及结果好坏有时候有收敛速度及结果好坏有时候有““看脸看脸””的成分这正与日常事的成分这正与日常事物的运行规律相符）物的运行规律相符） （（7 7）在以后的学习研究过程中应善于观察、善于思考，灵感）在以后的学习研究过程中应善于观察、善于思考，灵感来源于生活！来源于生活！76. That’s all!Thank you for attending!77. 。