蚁群优化算法讲稿

《蚁群优化算法讲稿》由会员分享，可在线阅读，更多相关《蚁群优化算法讲稿（128页珍藏版）》请在金锄头文库上搜索。

1、数学系数学系 凌军凌军蚁群优化Ant Colony Optimization第篇 组合优化问题与元启发式算法第篇 ACO原理及其实现第篇 ACO理论及应用第篇 组合优化问题与元启发式算法1.1 1.1 组合优化问题组合优化问题 1.2 1.2 计算复杂度计算复杂度 1.3 1.3 组合优化问题求解方法组合优化问题求解方法 1.4 1.4 元启发式算法元启发式算法 1.5 1.5 结语结语第第篇篇 组合优化问题与元启发式算法组合优化问题与元启发式算法1.1 1.1 组合优化问题组合优化问题组合优化问题涉及找到一组离散变量的值，使得所给定组合优化问题涉及找到一组离散变量的值，使得所给定 的目标函数

2、的解达到最优。的目标函数的解达到最优。从形式化的角度来看，组合优化问题是一个三元组从形式化的角度来看，组合优化问题是一个三元组其中其中 是候选解（是候选解（candidate solutioncandidate solution）的集合；）的集合； 是目标函数是目标函数 ，对于每一个候选集，对于每一个候选集 都对应着一个目标函数值都对应着一个目标函数值 ； 是约束条件的集合，集合是约束条件的集合，集合 中满足约束条件中满足约束条件 的解被的解被 称为可行解（称为可行解（feasible solution)feasible solution)。优化的目标就是找出一个全。优化的目标就是找出一个全

3、局最优的可行解局最优的可行解 。求最小值的问题（也就是最小化问题）。求最小值的问题（也就是最小化问题） 就是要找到一个具有最小成本代价的解就是要找到一个具有最小成本代价的解 ，即一个对于所，即一个对于所 有有 都有都有 而求最大值的问题（也就是最大化问题而求最大值的问题（也就是最大化问题 ）就是要找出一个具有最大目标值的解，即一个对于所有的）就是要找出一个具有最大目标值的解，即一个对于所有的 都有都有 。1.2 1.2 计算的复杂度计算的复杂度通常，对算法效率在理论上的探讨又称为算法的通常，对算法效率在理论上的探讨又称为算法的 事前估计，可分为算法的时间复杂度分析和空间复杂事前估计，可分为算法

4、的时间复杂度分析和空间复杂 度分析。度分析。定义定义1.1 1.1 算法空间复杂度算法空间复杂度是指算法执行时间内所占用的是指算法执行时间内所占用的 存储单元的大小。存储单元的大小。定义定义1.2 1.2 算法的时间复杂度算法的时间复杂度是指算法执行基本操作的次是指算法执行基本操作的次 数。这里我们将求解该问题的所有关键操作（如加、数。这里我们将求解该问题的所有关键操作（如加、 减、乘、除、比较等运算）指定为基本操作。减、乘、除、比较等运算）指定为基本操作。定义定义1.3 1.3 最差时间复杂度最差时间复杂度指的是对于每个可能的输入规模为指的是对于每个可能的输入规模为 的的 问题算法求解该问题

5、时找到一个解所需的最长时间。问题算法求解该问题时找到一个解所需的最长时间。一个算法的最差时间复杂度常常采用符号一个算法的最差时间复杂度常常采用符号 来表示。给来表示。给 定两个函数定两个函数 和和 ，若存在两个正常数，若存在两个正常数 与与 ，对一切的，对一切的时有时有 则称则称 是以是以 为界的，那么函数为界的，那么函数 的的 最差时间复杂度就为最差时间复杂度就为 。换句话说，符号。换句话说，符号 给出了算法给出了算法 在最差时间复杂度上的渐进上限值，它表示的是一个数量级的在最差时间复杂度上的渐进上限值，它表示的是一个数量级的 概念。概念。若一个算法对应的时间复杂度为若一个算法对应的时间复杂

6、度为 ，而，而 是一个是一个 多项式函数，则称该算法为多项式时间算法；若多项式函数，则称该算法为多项式时间算法；若 不是多项不是多项 式则称该算法为指数级时间算法。式则称该算法为指数级时间算法。P P、NPNP、NP-CNP-C、NP-hardNP-hard问题描述问题描述一种刻画组合问题难度的重要理论就是一种刻画组合问题难度的重要理论就是 所谓的所谓的NPNP完全性理论，在完全性理论，在NPNP完全性理论中完全性理论中 通常使用图灵机，关于这部分的详细内容通常使用图灵机，关于这部分的详细内容 请参考请参考GareyGarey和和JohnsonJohnson（19791979）的文章。）的文章

7、。图灵（图灵（A.TuringA.Turing）19121912年出生于伦敦。他年出生于伦敦。他19361936 年的论文年的论文论可计算数及其在判定问题中的应用论可计算数及其在判定问题中的应用 是阐明现代计算与计算机原理的开山之作。论是阐明现代计算与计算机原理的开山之作。论 文围绕着一个基础数学问题：只要有足够的计算文围绕着一个基础数学问题：只要有足够的计算 时间数学函数是否都能经过有限次机械步骤得出时间数学函数是否都能经过有限次机械步骤得出 解答？为了弄清楚计算机能够解决哪些问题，他解答？为了弄清楚计算机能够解决哪些问题，他 提出了后来被称作提出了后来被称作“ “图灵机图灵机” ”的可计算

8、性理论。的可计算性理论。 19371937年，他的论文年，他的论文基于序数的逻辑系统基于序数的逻辑系统进一进一 步展开了关于这个问题的逻辑探索。步展开了关于这个问题的逻辑探索。定义定义1.4 1.4 图灵机图灵机 图灵机概念最早由英国数学家图灵机概念最早由英国数学家 TuringTuring提出，其本质是由两部分组成：一部分是一提出，其本质是由两部分组成：一部分是一 个无限长的个无限长的磁带磁带，磁带被分割成一个个的小方格，磁带被分割成一个个的小方格 ，每个小方格装有符号，每个小方格装有符号 00或或 11；另一部分是；另一部分是检测检测 头头，它能沿着磁带前后移动，一次移动一个小方，它能沿着

9、磁带前后移动，一次移动一个小方 格，并能读出当前小方格的符号。检测头可以不格，并能读出当前小方格的符号。检测头可以不 改变小方格的值，也能将新值写进小方格。在操改变小方格的值，也能将新值写进小方格。在操 作的每一步，我们假定检测头处于有限设置中的作的每一步，我们假定检测头处于有限设置中的 一个，称其为一个，称其为状态状态。检测头可能采取的行动：检测头可能采取的行动：1. 1. 向左移动一个小方格向左移动一个小方格 2. 2. 向右移动一个小方格向右移动一个小方格 3. 3. 用用1 1改写当前小方格的值改写当前小方格的值 4. 4. 用用0 0改写当前小方格的值改写当前小方格的值 5. 5.

10、保持目前的状态保持目前的状态 6. 6. 从目前的状态改变到其他状态从目前的状态改变到其他状态 7. 7. 停止停止例、用图灵机来计算例、用图灵机来计算1 1加加2 2机器在运行之初，磁带上所有的小方格值均为机器在运行之初，磁带上所有的小方格值均为0 0， 首先，我们把一个首先，我们把一个1 1和另外两个连续的和另外两个连续的1 1放在磁带放在磁带 上，并在它们之间放上上，并在它们之间放上0 0使之分隔，这代表这是两使之分隔，这代表这是两 个独立的数字；个独立的数字； 其次，设计一个计算加法的程序，完成这个运算其次，设计一个计算加法的程序，完成这个运算 的机器需要有三个状态的机器需要有三个状态

11、A A、B B、C C读入的值状 态10A1,R,A1,R,BB1,R,B0,L,CC0,STOPSTOP 这个程序的结果是：当机器停止时，磁带上将会这个程序的结果是：当机器停止时，磁带上将会 出现三个连续的出现三个连续的1 1，其他地方全是，其他地方全是0 0。图灵机是对算法进行分析和研究算法复杂度的图灵机是对算法进行分析和研究算法复杂度的 得力工具，可分为确定性单带图得力工具，可分为确定性单带图 灵（灵（ deterministic deterministic one-tape Turing machine,DTMone-tape Turing machine,DTM）和非确定性单带）和非

12、确定性单带 图灵机（图灵机（nondeterministic onetapeTuringmachingnondeterministic onetapeTuringmaching NDTMNDTM）两大类。）两大类。一个一个DTMDTM程序应包括以下信息：程序应包括以下信息：（1 1）线性带中所用字符的一个有限集合）线性带中所用字符的一个有限集合 。（2 2）一个有限状态集）一个有限状态集 ，它包括初始状态，它包括初始状态 和和 两个特有的停机状态两个特有的停机状态 或或 。（3 3）一个转移函数）一个转移函数 。非确定性单带图灵机非确定性单带图灵机NDTMNDTM完全是一种假象的机完全是一种假

13、象的机 器，通常多用猜想模块来对其进行描述。器，通常多用猜想模块来对其进行描述。猜想模块：猜想模块： （1 1）猜想模块起作用时检测头内的状态模块）猜想模块起作用时检测头内的状态模块 不起作用。不起作用。 （2 2）在被扫描的带格中写下某一字符并左移）在被扫描的带格中写下某一字符并左移 一格。一格。 （3 3）停止。若停止则猜想模块不在起作用。）停止。若停止则猜想模块不在起作用。定义定义1.5 1.5 实例实例 实例是问题的特殊表现，是确实例是问题的特殊表现，是确 定了描述问题特性的所有参数的问题，其中参数定了描述问题特性的所有参数的问题，其中参数 值称为值称为数据数据，这些数据占用计算机的空

14、间称为数，这些数据占用计算机的空间称为数 据实例的据实例的输入长度输入长度。定义定义1.6 1.6 P P类问题类问题 所有可用所有可用DTMDTM在多项式时间在多项式时间 内求解的判定问题内求解的判定问题 的集合，简记为的集合，简记为 。 即即其中其中 表示程序表示程序 所识别的语言。所识别的语言。P P类问题的每个实例只有类问题的每个实例只有“ “是是” ”或或“ “否否” ”两种回答，两种回答， 并称肯定回答为并称肯定回答为“ “是是” ”实例；称否定回答为实例；称否定回答为“ “否否” ”实例。实例。定义定义1.7 1.7 NP(non-deterministic poly-nominalNP(non-deterministic poly-nominal) )类问题类问题 若存在一个多项式函数若存在一个多项式函数 和一个验证算法和一个验证算法 ，对一，对一 类判定问题类判定问题 的任何一个的任何一个“ “是是” ”回答，满足其输入长度回答，满足其输入长度不超过不超过 ，其中，其中 为为 的输入长度，且验证的输入长度，且验证 算法中