智能优化概述ppt课件.ppt

4.1 智能优化概述传统优化理论与方法的局限性qihpigtosubjectfiin, 10)(, 10)(R)(minXXXX函数优化问题定义增广目标函数，转化约束优化问题为无约束优化问题；基于梯度类方法求解无约束优化问题的局部最优解。传统理论方法面向的问题传统方法思路与步骤ktkP0,0kXkkkktPXX 1（1）选取初始点（2）构造下降搜索方向（3）确定搜索方向上的步长（4）（5）满足终止条件，停止迭代，当前解；否则，k=k+1,转第2步传统方法的局限性经典优化算法是局部搜索算法。在其迭代过程中，不断以当前解邻域下降方向上的解替换当前解，即总是以邻域的较好解更新当前解。这是一种基于贪婪思想的做法，无疑会丧失全局优化的能力，从而在搜索过程中不可避免地陷入局部最小。其迭代过程是从初始解开始的确定性的过程，是一个确定性算法。不适用于组合优化问题)(min)(,*21iinsCsCssss涉及排序、分类、筛选等的一类问题旅行商问题（Traveling salesman problem，TSP)加工调度问题(Sheduling problem,如Flow-shop,Job-Shop)0-1背包问题(Knapsack Problem); 装箱问题（Bin packing problem)图着色问题（Graph coloring problem)聚类问题（clustering problem)TSP: 共去n个城市再回到原点，每个城市当且仅当去一次，求最短路径。 n!个排列。已知城市的位置图。加工调度问题：n个工件，m台机器；每个工件在m台机器加工的顺序和操作时间已知，要求安排所有工件的加工次序，使某指标最优。01背包问题：有n个物品（可能不同），1个背包；已知各物品的体积和价值；该背包如何盛放物品，可以使包中物品的价值最大。装箱问题：有已知数量的很多小物品，如何用最少的箱子数去装入。图着色问题：对于n个顶点的无环图，对每个顶点着色，要求相邻的顶点着不同的颜色，怎样着色使颜色种类最少。聚类问题：M维空间上的n个模式聚成k类，使类内距最小。!/kkn划分方式工程代表性智能优化方法模拟退火算法(Simulated Annealing Algorithm)模拟进化算法(Simulated evolutionary algorithm)集群优化方法（Swarm optimization)蚁群优化（Ant Colony Optimization)粒子群优化算法（Particle Swarm Opt.)克隆选择算法(Colonal Selection Algorithm, CSA)是随机性的或貌似随机性的搜索算法，可适用于多种问题，鲁棒性好。往往是一些物理或生物优化过程的模拟算法，或混沌搜索算法。有些智能优化算法，还能根据优化过程的进展情况，对算法自身的参数作出自适应的调整，智能化程度更高。人工免疫系统 (Artificial Immune System, AIS)Biological Inspired ComputaitonBIC混沌搜索算法禁忌搜索(Tabu Search, 或Taboo Search)模拟退火算法(Simulated Annealing)1。随机产生一个点一个点，作为初始最优点，计算函数值，T=T0; t=12。当前最优点处作一随机扰动，计算函数值增量3。若 0,则以概率1转移（替换当前点）；否则以概率 p=exp(-/T)转移。4。若t小于终止步数，则t=t+1,T=T(t)（冷却进度表）,转步骤25。输出最优点模拟退火算法以概率1收敛于目标函数的全局最小点物理退火：包括加热、保温、冷却三个子过程，旨在消除内应力,使固（晶）体的结构状态处于最低自由能状态。Metropolis准则（1953） ：某一温度下，晶体接收一新的较低能量结构状态的概率为1，而接收一较高能量结构状态的概率为p=exp(-/T)，为函数增量；或者说，某一温度下变到能量较高状态的概率总是低于变到较低能量状态的概率，当温度较低时，变到能量较高状态的概率会更小。因此，总的趋势是，在保温和冷却过程中，晶体的结构状态朝着能量较低的方向变化；最后随着冷却过程的结束，晶体结构状态以概率1收敛于晶体的最低能量结构。算法步骤：1。在目标函数的定义（基本）空间随机给出一些点（或个体）作为初始的父代群体2。评价初始父代群体，若满足要求则结束，否则继续。3。通过对父代群体的交叉（crossover）、突变（mutation）、选择(selection)等遗传操作产生新一代群体4。评价新一代群体，若有满足要求的优化解或迭代次数足够多则过程结束，否则将新一代群体置为父代群体又回到步骤三。 模拟进化算法（Simulated EA, EA)自然界中生物进化是一个规律。如何进化的？孟德尔的“遗传变异”理论和达尔文的“自然选择”学说回答了这个问题。模拟进化算法就是一类模拟自然界生物进化过程的优化方法,具有并行、随机、自适应的特点。其中最有名进化算法遗传算法(GA）由Holland于1975年提出。优化步骤：集群优化方法（Swarm optimization)蚁群优化（Ant Colony Optimization, ACO)蚂蚁觅食过程蚁群觅食现象：蚁群从蚁巢出发四处觅食，假设两只蚂蚁找到食物后选择不同路线返回蚁巢，其他蚂蚁将更倾向于（更大概率地）选择实际较短的路线前往食物，结果蚁群会找到一条最短的去食物的路径。物理解释：蚂蚁在其经过的路途上留下了一种信息素（pheromone）作为标记，信息素浓度与路径的质量成正比，即越短浓度越大，越吸引后面蚂蚁；另外，一条路线上走过的蚂蚁越多，信息素浓度就越高，也越能吸引蚁群；最终，蚁群将找到距离食物最近的路线。ACO算法就是模拟蚁群觅食路径优化过程的算法。已被成功地用于解决旅行商问题、图着色问题等大搜索空间的离散优化问题，特别是在电信路由选择方面取得了很好的实际应用效果。方法具有健壮性、灵活性、并行性等特点。1. 初始化：所有边上的信息素量设为相同值0。2. 多只人工蚁从顶点c1开始随机行走，选择下一顶点的概率和连接两顶点的边上的信息素量成正比，行走一直继续，直至构造成功一个候选解，或没有合法顶点可选择。3. 所有人工蚁完成行走后，计算候选解的适应度值，并分两步进行信息素更新：模拟信息素挥发，按固定比例减少所有边上的信息素量；增加人工蚁经过的边上的信息素量，增加量与候选解的适应度值成正比。4. 若达到最大循环次数或取得满意解则结束流程，否则转。ACO算法步骤如下：粒子群优化算法（Particle Swarm Opt.， PSO)鸟群觅食现象：鸟群在一片只有一块食物的区域内随机觅食，所有的鸟都不知道食物的位置，它们能在不断往复的搜索中发现食物，并得知与食物间的距离，然后跟随目前离食物最近的鸟飞行过去。PSO算法正是从鸟群觅食的行为中得到启示而产生的优化算法。在PSO算法中，候选解称为粒子，被看作是解空间中的一只“鸟”，编码为粒子在D维解空间中所处的位置。粒子被赋以适应度值和速度，通过在解空间中的移动实现解的优化，移动前需要获取两个参数，一个是自身截至目前的最优解pbest，另一个则是所有邻近粒子当前的最优解nbest。根据对邻近粒子定义的不同，PSO算法可分为全局模式PSO算法和局部模式PSO算法，前者将整个种群看作邻近粒子，而后者粒子只将拓扑或空间相邻的粒子视作邻近粒子。在获取了两个参数之后，更新粒子的速度和位置，实现移动：vxxxnbestrandcxpbestrandcvv21其中，v=(v1, v2, vD)是粒子的速度，x=(x1, x2, xD)是粒子当前的位置，rand是0,1之间的随机数，c1、c2是学习因子，通常取c1=c2=2。 1. 初始化，在解空间随机选取粒子组成群体；2. 计算每个粒子的适应度值，若优于其pbest，则设当前粒子取得的解为pbest；3. 根据公式更新每个粒子的速度和位置；4. 若达到最大循环次数或取得满意解则结束流程，否则转。PSO算法的一般流程如下：PSO算法同GA类似，都是以随机的初始种群开始，以适应度值评价个体，用随机技术进化种群并寻优；但PSO算法并不使用交叉、变异等遗传算子，粒子通过在解空间的移动实现进化。同GA比较，PSO算法的优势在于简单、容易实现、需调整的参数少，目前已广泛应用于函数优化，神经网络训练，模糊系统控制等领域。克隆选择算法(Colonal Selection Algorithm,CSA)人工免疫系统 (Artificial Immune System, AIS)克隆选择学说：当机体受到外来抗原(antigen)刺激时，B淋巴细胞产生附着于细胞表面的抗体(antibody,亦称受体）来作出免疫应答，与抗原具有较高亲合度（affinity）的抗体能够识别抗原并与其结合，并分裂增殖、成长为能够产生更高亲合度抗体的成熟细胞克隆，最后分化为浆细胞（plasma cell）和记忆细胞(memory cell)。浆细胞是一种不能分裂的细胞，是最活跃的抗体分泌者；而记忆细胞则具有较长的寿命，在血液、淋巴和组织中扩散，在下一次受到近似抗原刺激时迅速转变为能够分泌高亲合度抗体的浆细胞。在这一过程中，抗原被看作是细胞克隆的选择因子，因此该理论被命名为克隆选择学说。克隆选择的最初灵感来自于自然选择理论，但它和达尔文进化论之间的联系并不仅限于此，它所具有的种群多样性、遗传变化和自然选择三大特征都说明，克隆选择实质上是一个“迷你的”进化过程。首先，在免疫应答中，不同的B细胞产生了大量特异性抗体，但只有极少数能够成功地识别入侵抗原，并与抗原结合。绝大多数抗体的亲合度都过低，无法被选中增殖，只能在免疫应答过程中充当被动的背景式角色。这体现了克隆选择中的抗体种群多样性。其次，被选中的抗体除增殖外，还将经历亲合度成熟化（affinity maturation）过程，这既是提高抗体质量的重要步骤，同时也是维持抗体种群多样性的有效手段。这一过程通过超变异（hypermutation）和受体编辑（receptor editing）两种类似于遗传变化的机制实现：超变异类似于小范围变异，在负责抗体-抗原结合的基因上引入随机变化，可能偶然地导致亲合度的提高，这些改善抗体质量的基因变化将被引入记忆细胞，这一机制和选择一道提供了一个局部调优的策略；受体编辑类似于交叉重组，B细胞删除自身的低亲合度受体，并通过基因重组来发展出新受体，和遗传学相比，免疫系统中的基因重组更加自由，核苷酸可以被随机插入或删除，这一机制在效果上更接近大范围变异，提供了逃出局部最优、找到全局最优的可能性。最后，只有识别抗原并与其结合的抗体才能增殖和保存于记忆细胞中，低质量抗体则被排除在进一步的免疫应答过程之外，这体现了克隆选择的自然选择特性。与进化的关系4. 对克隆种群中的所有个体施以超变异，产生成熟克隆种群C*，实现克隆种群的亲合度成熟化；5. 计算成熟克隆种群中各个体的亲合度，选择每组克隆中亲合度最高的个体，共n个个体组成新的Abn；6. 随机产生d个新的抗体，取代Ab中亲合度最低的d个抗体，以模拟受体编辑机制。至此完成一个循环，若达到事先设定的终止条件（如达到最大代数、取到满意解等）终止算法，否则转继续。1. 随机产生规模为N的初始抗体种群Ab2. 对于种群中的每个抗体Abi，计算其亲合度，并选择n个亲合度最高的抗体组成Abn3. 为Abn中的每个抗体产生与其亲合度成比例的数目的克隆，组成克隆种群C克隆选择算法步骤禁忌搜索(Tabu Search, 或Taboo Search，TS)禁忌搜索是邻域搜索的一种扩展，其最重要的思想是：标记已搜索过的若干历史最优点，并在进一步的迭代搜索中尽量避开这些对象，即采用禁忌策略（但不是绝对禁止），从而保证对不同的有效搜索途径的搜索。禁忌搜索涉及到邻域(Neighborhood)，禁忌表(Tabu list)，禁忌长度(Tabu length),候选解（Candidate），藐视准则(Aspiration criterion)等概念。通过禁忌表禁忌一些已经历的操作；并用藐视准则来奖励一些优良状态。禁忌搜索算法步骤：1. 给出初始解x ,令最优解xg=x，令迭代步数i=0, 禁忌表T= ;2. 从x的邻域中选择一定数量的解构成候选解集合N(x);3. 如果N(x)为非空集,从N(x)中找出最优解x ；否则，转到步骤2 。4. 如果x不属于T，或属于T但满足激活条件，则令x=x；如果x属于T且x不满足激活条件，则令N(x)=N(x)-x, 转到步骤3 。 5. 如果x的性能比xg的性能好，则xg=x;6. 令T=TUx；如果禁忌表长度等于规定长度，则去掉最早进入表中的解，即FIFO。7. 如果满足条件，则算法结束，xg为最终解；否则，令i=i+1,转步骤2混沌搜索算法混沌搜索是一种确定性的搜索算法，但混沌具有遍历性，能够不重复地历经一定范围内的所有状态，因此它可以作为搜索过程中避免局部最小的一种优化机制。) 1 , 0()1 (41nnnnxxxx1. 给出一个xn的初值，换算到定义区间，计算其函数f0，fmin=f0, i=1;2. 迭代第i次产生xn+1，换算到定义区间，计算其函数值fi;3. 比较当前fmin与fi,更新fmin=min(fmin,fi)，4. 结束条件满足，则输出xmin和fmin,否则i=i+1;xn=xn+1,转步骤2设定义了一个集合F，它是所有优化问题的全集，对于任意两个作用于该全集的优化算法，其平均优化效率是完全等同的（原文为: for any algorithm, any elevated performance over one class of problems is exactly paid for in performance over another class.）。也就是说，如果一个算法A，对问题集F1(F1F)中的优化问题优化性能高于算法B，则必然有问题集F2(F2F)，对F2中的优化问题，算法B又优于算法A。用数学公式描述为：NFL是英语谚语“no free lunch”的缩写，可译为“有得必有失”。NFL定理其中，是代价函数的概率分布曲线，m是问题集中问题的采样数目，f是代价函数，a1、a2分别是任意两种优化算法。12( |,)( |,)ffP c f m aP c f m accNFL定理提出后的一个直接后果就是使评价一个算法整体优于另一种算法的比较研究失去了意义。因为，按照NFL定理，所有的优化算法对于所有优化问题的集合，都是等效率的。但对具体的问题，算法还是有优劣之分的。