资源描述
优化算法基础,马建华2011年7月,进化算法,算法基础遗传算法,算法基础,算法的概念算法分类算法的评价,算法的概念,算法计算方法把求解问题的方法程式化、规范化算法是程序的依据、程序是算法的计算机实现算法思想与依据实现技术算法步骤算法构成,算法组成,初始条件指定参数、初始解迭代方法转移规则、生成新可行解的方法终止条件最优性条件或可接受条件输出结果最优解或可接受解,算法的分类,构造算法搜索算法启发式算法进化算法,构造算法,明确知道最优解的结构特征直接构建最优解，中间过程得到的是最优解的部分，不是可行解；最小支撑树的算法,最小支撑树的算法,算法思想算法构成关键技术,算法思想,依据-加上支撑树外的任一边构成唯一的圈，树外边是该圈中权最大的。从权重小的边开始加边，新拿的边如果和已加入的边构成圈就不加，否则就加入。,关键技术,选择圈中最小的边按权重从小到大排序判断是否构成圈,算法构成,初始条件：已加边集为空集，未拿边集为全体边迭代规则：从未拿的边中选一个权重最小的，如果该边与已加入边构成权就舍去，否则就加入停止规则：已加边的个数等于顶点数减1或者没有未拿边输出结果：已加边集或没有支撑树,搜索算法,知道最优解满足的条件，但不知道其结构从一个可行解出发按某种规则生成新的可行解直到满足最优性条件单纯形算法,单纯形算法,算法思想关键技术算法构成,算法思想,从基可行解中找最优解，从一个基可行解开始，判断是否满足最优性条件，如果满足就停止，否则看是否没有最优解，如果没有最优解就停止，否则生成一个新的最优解,关键技术,初始基可行解计算检验数和典式生成新基可行解,算法构成,初始条件：初始基可行解迭代方法：计算典式和检验数，找初级变量和入基变量终止条件：检验数小于等于零或检验数大于零的分量对应典式列小于等于零输出结果：最优基可行解或没有最优解,启发式算法,不知道最优解的结构和最优性条件模拟人们的思路或经验贪心算法,最短路贪心算法,算法思想关键技术算法组成,算法思想,从起点开始，每一步都选最短的边，直到终点,关键技术,确定每个点关联的未选的边中权重最小的,算法构成,初始条件：已选边为空集，当前点为发点迭代规则：从当前点出发的边中选择一个权重最小的边，其头部点为新的当前点。如果没有出点则返回上一个点重新选择。终止条件：当前点为终点，或当前点没有出发点输出结果：一条从起点到终点的路或没有路,1.3启发式算法_定义,启发式算法（heuristicalgorithm）定义1.基于直观或经验构造的算法，在可接受的花费（时间、空间）下，给出待解组合优化问题的每个实例的一个可行解，该可行解与最优解偏差事先不一定可以预计.定义2.启发式算法是一种技术，在可接受的计算费用内寻找最好解，但不保证该解的可行性与最优性，无法描述该解与最优解的近似程度。特点（与传统优化方法不同）：凭直观和经验给出算法；不考虑所得解与最优解的偏离程度.,1.3启发式算法_优点,优点：（1）有可能比简化数学模型解的误差小；（2）对有些难题，计算时间可接受；（3）可用于某些最优化算法（如分支定界算法）之中的估界；（4）直观易行；（5）速度较快；（6）程序简单，易修改。,1.3启发式算法_不足,不足：（1）不能保证求得全局最优解；（2）解的精度不稳定，有时好有时坏；（3）算法设计与问题、设计者经验、技术有关，缺乏规律性；（4）不同算法之间难以比较。,1.3启发式算法_分类,（1）一步算法（2）改进算法（迭代算法）（3）数学规划算法（4）解空间松弛法,1.3启发式算法_分类,（5）现代优化算法：80年代初兴起禁忌搜索（tabusearch）模拟退火（simulatedannealing）遗传算法（geneticalgorithms）神经网络（neuralnetworks）蚂蚁算法（AntAlgorithm，群体（群集）智能，SwarmIntelligence）（6）其他算法：多种启发式算法的集成.,1.3启发式算法_性能分析,（1）最坏情形分析（worstcaseanalysis）利用最坏实例分析计算复杂性、解的效果。(2）概率分析（probabilityanalysis）用最坏情况分析，会因一个最坏实例影响总体评价.在实例数据服从一定概率分布情形下，研究算法复杂性和解的效果.(3)大规模计算分析通过大量实例计算，评价算法效果.注意数据的随机性和代表性.,进化算法,不知道最优解的结构和最优性条件模拟生物寻优行为，大规模群体优化群体搜索算法遗传算法,算法的评价,结果评价复杂性评价,结果评价,全局最优算法局部最优算法近似算法有效算法,全局最优算法,全局收敛算法得到全局最优解或收敛到全局最优解分支定界算法,局部最优解,得到局部最优解结果的好坏依赖初始解的选取非线性规划搜索算法,近似算法,得到一个与最优解的差距不超过一定比例的解需要说明与最优解的差距复杂问题的多项时间算法,可接受算法,得到一个比较好的解无法说明与最优解的差距贪心算法不需要太多的理论知识,复杂性评价,算法复杂性多项式时间算法非多项式时间算法,1.2计算复杂性的概念,评价算法的好坏计算时间的多少、解的偏离程度例非对称距离TSP问题的算法实现：所有路径枚举。计算时间：n个城市，固定1个为起终点需要(n-1)!个枚举，设计算机1秒能完成24个城市的枚举，则城市数与计算时间的关系如下表：,1.2计算复杂性的概念,随城市增多，计算时间增加很快。到31个城市时，要计算325年。,描述算法的好坏计算复杂性讨论计算时间与问题规模之间的关系。以目前二进制计算机中的存储和计算为基础，以理论的形式系统描述，是评估算法性能的基础。,1.2计算复杂性的概念,问题（problem）：要回答的一般性提问，通常含有若干个满足一定条件的参数（或自由变量）。可以从两方面描述：（1）对所有参数的一般性描述；（2）答案（或解）必须满足的性质。实例（instance）:给问题的所有参数指定具体值，得到问题的一个实例。这些具体值称为数据；这些数据输入计算机所占的空间称为实例的长度（size）.,1.2计算复杂性的概念,一类最优化问题是由一些类似的具体问题（实例）组成的，每一个具体问题可表达成二元组（F,C）.F为可行解集合;C是费用函数，是由F到R（实数集）的映像。问题是在F中找到一个点f*，使对F中任意的f，有C(f*)C(f),称f*为这一具体问题的最优解（或全局最优解）.,1.2计算复杂性的概念,算法计算量的度量：加、减、乘、除、比较的总运算次数与实例的计算机计算时的二进制输入数据的大小关系。正整数x的二进制位数是:(整数到二进制的转换),1.2计算复杂性的概念,算法计算量的度量之例TSP枚举法,计算量的统计：,1.2计算复杂性的概念,实例的输入长度：,实例的输入长度是n的多项式函数枚举法的基本计算量是n的阶乘函数，随n的增加，比指数函数增加得还快.,1.2计算复杂性的概念,1.2计算复杂性的概念,定义多项式算法给定问题P，算法A，对一个实例I，存在多项式函数g(x)，使（XX）成立，称算法A对实例I是多项式算法；若存在多项式函数g(x)，使（XX）对问题P的任意实例I都成立，称算法A为解决该问题P的多项式算法.当g(x)为指数函数时，称A为P的指数时间算法。,1.2计算复杂性的概念,利用复杂性分析对组合优化问题归类。定义多项式问题给定一个组合优化问题，若存在一个多项式算法，称该问题为多项式时间可解问题，或简称多项式问题(或P问题).所有多项式问题的集合记为P.例：线性规划是否为多项式问题？,1.2计算复杂性参考书,计算复杂性,作者：Christos，Papadimitriou清华大学出版社，2004年9月第1版计算复杂性导论，作者：堵丁柱等，高等教育出版社，2002年8月第1版,遗传算法,基本思想关键技术算法步骤实例,遗传算法起源,遗传算法是由美国的J.Holland教授于1975年在他的专著自然界和人工系统的适应性中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。,遗传算法基本思想,生物进化过程模拟技术,生物进化过程,遗传信息决定个体性能子代信息来自父代个体会发生变异通过自然选择、适者生存具有整体寻优性能,种群,父代群,子群,单亲、双亲繁殖,优胜劣汰,进化过程,遗传算法的搜索机制,遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。,模拟技术,表示可行解初始子集合选择标准生成新的子集合（选择、交叉、变异）,编码方式产生初始种群适应度函数遗传算子（选择、交叉、变异）,编码,GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。SGA使用二进制串进行编码。,函数优化示例,求下列一元函数的最大值：,x-1,2，求解结果精确到6位小数。,GA对于本例的编码,由于区间长度为3，求解结果精确到6位小数，因此可将自变量定义区间划分为3106等份。又因为2213106222，所以本例的二进制编码长度至少需要22位，本例的编码过程实质上是将区间-1，2内对应的实数值转化为一个二进制串（b21b20b0）。,几个术语,基因型：1000101110110101000111,表现型：0.637197,编码,解码,个体（染色体）,基因,初始种群,SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。,适应度函数,遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。,选择算子,遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。,轮盘赌选择方法,轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，个体i的适应度为Fi，则个体i被选中遗传到下一代群体的概率为：,轮盘赌选择方法的实现步骤,（1）计算群体中所有个体的适应度函数值（需要解码）；（2）利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；（3）采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。,交叉算子,所谓交叉运算，是指对两个相互配对的染色体依据交叉概率Pc按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。SGA中交叉算子采用单点交叉算子。,单点交叉运算,交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000,交叉点,变异算子,所谓变异运算，是指依据变异概率Pm将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。SGA中变异算子采用基本位变异算子。,基本位变异算子,基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。,基本位变异算子的执行过程,变异前：000001110000000010000变异后：000001110001000010000,变异点,运行参数,（1）M：种群规模（2）T：遗传运算的终止进化代数（3）Pc：交叉概率（4）Pm：变异概率,算法步骤,3、遗传算法的特点,（1）群体搜索，易于并行化处理；（2）不是盲目穷举，而是启发式搜索；（3）适应度函数不受连续、可微等条件的约束，适用范围很广。,
展开阅读全文