启发式算法.ppt

1、启发式算法,一、组合优化问题二、启发式算法三、模拟退火算法四、遗传算法,解决离散的优化问题运筹学分支。通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，可以涉及信息技术、经济管理、工业工程、交通运输和通信网络等诸多领域。,一.组合优化问题,1.1 组合优化问题的基本概念,一般模型,目标函数,约束函数,D是有限个点构成的集合,0-1背包问题（Knapsack Problem） 加工调度问题（Scheduling Problem） 旅行商问题（Travelling Salesman Problem-TSP） 装箱问题（Bin Packing Problem） 图着色问题（Graph

2、 Coloring Problem）,经典的组合优化问题：,0-1背包问题,设有一个容积为b的背包，n件体积分别为 ，价值分别为 的物品，如何以最大的价值装包？,旅行商问题,给定n个城市和每两个城市间的距离。一个货郎自某一城市出发巡回售货，问这个货郎应该如何选择路线，使每个城市经过一次且仅一次，并且路径长度最短。,基于图论的0-1规划模型,1.2 计算复杂性的概念,例：TSP枚举法的基本计算量是n！,随着n的增加，计算量急剧增加。,算法复杂性分析,NP问题,这些问题描述非常简单，并且有很强的工程代表性，但最优化求解很困难； 其主要原因是求解这些问题的算法需要极长的运行时间与极大的存储空间，以致

3、根本不可能在现有计算机上实现，即所谓的“组合爆炸”。,组合优化问题的特点：,兼顾解的质量以及运行时间的较好算法： （1）设计平均形态良好的概率算法 （2）设计求近似最优解的近似算法,1.3 邻域结构与局部最优,如何求解全局最优解？,基于直观或经验构造的算法，在可接受的花费（时间、空间）下，给出待解决优化问题每个实例的一个可行解，该可行解与最优解的偏差不一定事先可以估计。 启发式算法是一种技术，在可接受的计算费用内去寻找最好的解，但不一定能保证解的可行性与最优性，多数情况下无法描述该解与最优解的近似程度。 特点（与传统优化方法不同）：不考虑算法所得解与最优解的偏离程度。,二.启发式算法,例：TS

4、P的近似算法：最近邻法、最近插入法、最小支撑树法、局部搜索法等,算法（最近邻法）： (1)任选一个城市c1为出发点； (2)根据与出发城市最近的原则，在c1以外的n-1个城市中选取第二个经过城市； (3)再以c2为出发城市，在尚未经过的按最近邻原则选取c3，如此重复，直至所有城市都被经过，最后到达的城市是cn； （4）从cn返回c1，构成一条路径。,例：0-1背包问题：greedy algorithm,启发式算法的优点与缺点,数学模型本身是实际问题的简化 有些难的组合优化问题还没有最优算法或过于复杂 一些启发式算法可用在最优算法中 简单易行，比较直观 速度快 多数情况下，程序简单，易于修改,不

5、能保证求得最优解 表现不稳定 算法的好坏依赖于实际问题、经验和设计者的技术,一步算法 改进算法 数学规划算法 解空间松弛算法 现代优化算法,启发式算法的分类,现代优化算法：上世纪80年代初兴起,禁忌搜索（tabu search） 模拟退火（simulated annealing） 遗传算法（genetic algorithms） 神经网络（neural networks） 蚁群算法（ant algotithms） 其他方法,局部搜索算法：,Step2：当 或满足其他停止运算准则时, 输出计算结果，停止运算；否则，从P中选一集合S，得到S中的最优解 ；,若,则,否则 重复step2.,改善局部搜

6、索算法性能的途径： (1)对大量初始解执行算法，再从中选优 (2)引入更复杂的邻域结构，使算法能对解空间的更大范围进行搜索 (3)改变局部搜索算法只接受优化解迭代的准则，在一定限度接受恶化解。,禁忌搜索：是一种人工智能算法，是局部搜索算法的扩展。其重要思想是标记已得到的局部最优解，并在进一步的迭代中避开这些局部最优解。,三.模拟退火算法,3.1 起源：固体退火过程,类比：,组合优化问题 解 最优解 费用函数,金属物体 状态 能量最低的状态 能量,(simulated annealing algorithm),1983，Kirkpatrick成功应用于组合优化问题,3.2 模拟退火算法流程：,1

7、）随机产生一个初始解 ，令 ，并计算目标函数值 2）设置初始温度 t=T(0)，终止温度 降温系数 3）while tTmin i)for j=1:k ii)对当前最优解 按照某一邻域函数,产生一新的解 计算新的目标函数值 并计算目标函数值的增量,iii) 如果 则 iv）如果 则如果 否则 v）end for,4）降温 5）end while 6）输出当前最优点，计算结束。,3.3 模拟退火算法要素,1）状态空间与状态生成函数（邻域函数）,搜索空间（状态空间）：由经过编码的可行解的集合所组成 状态生成函数（邻域函数）应尽可能保证产生的候选解遍布全部解空间。通常由两部分组成，即产生候选解的方式

8、和候选解产生的概率分布 候选解一般采用按照某一概率密度函数对解空间进行随机采样来获得 概率分布可以是均匀分布、正态分布、指数分布等等,2）状态转移概率（接受概率）p,状态转移概率是指从一个状态xold（一个可行解）向另一个状态xnew（另一个可行解）的转移概率 通俗的理解是接受一个新解为当前解的概率 它与当前的温度参数T有关，随温度下降而减小 一般采用Metropolis准则,3）冷却进度T(t),冷却进度表是指从某一高温状态T0向低温状态冷却时的降温管理表。,假设时刻t的温度用T(t)表示，则经典模拟退火算法的降温方式为：,而快速模拟退火算法的降温方式为：,这两种方式都能使模拟退火算法收敛。

9、,4）初始温度T0 实验表明，初温越大，获得高质量解的几率越大，但花费的计算时间将增加。因此，初温的确定应折中考虑优化质量和优化效果。,5）内循环终止准则 或称Metropolis抽样稳定准则，用于决定在各温度下产生候选解的数目。,6）外循环终止准则 即算法终止准则，常用的包括： 设置终止温度的阀值 设置外循环迭代次数 算法搜索到的最优值连续若干步保持不变 检查系统熵是否稳定,3.4 模拟退火算法实验性能分析： 1）模拟退火法与局部搜索算法的差异 2）优点：高效、健壮、通用、灵活 3）不足：返回一个高质量近似解的时间花费较多，当问题规模不可避免增大时，难于承受的运行时间将使算法丧失可行性。 如

10、何改进？,3.5 模拟退火算法的matlab实现,利用模拟退火算法求函数极小：无约束或有界约束,x = simulannealbnd(fun,x0) x = simulannealbnd(fun,x0,lb,ub) x = simulannealbnd(fun,x0,lb,ub,options) x,fval = simulannealbnd(.) x,fval,exitflag = simulannealbnd(.) x,fval,exitflag,output = simulannealbnd(.),dejong5fcn,x0 = 0 0; x,fval = simulannealbnd(

11、dejong5fcn,x0),Optimization terminated: change in best function value less than options.TolFun. x = 0.0216 -31.9955 fval = 2.9821,Optimization terminated: change in best function value less than options.TolFun. x = -15.9669 -31.9749 fval = 1.9920 exitflag = 1 output = iterations: 1608 funccount: 162

12、1 message: 1x80 char randstate: 625x1 uint32 randnstate: 2x1 double problemtype: unconstrained temperature: 2x1 double totaltime: 0.8268,x,fval,exitflag,output = simulannealbnd(dejong5fcn,0,0),x0 = 0 0; lb = -64 -64; ub = 64 64; x,fval = simulannealbnd(dejong5fcn,x0,lb,ub),Optimization terminated: c

13、hange in best function value less than options.TolFun. x = -32.0169 -31.9879 fval = 0.9980,fun = (x) 3*sin(x(1)+exp(x(2); x = simulannealbnd(fun,1;1,0 0),Optimization terminated: change in best function value less than options.TolFun. x = 896.9234 0.0000,options = saoptimset(PlotFcns,saplotbestf,sap

14、lottemperature,saplotf,saplotstopping); simulannealbnd(dejong5fcn,x0,lb,ub,options);,options = saoptimset(InitialTemperature,300 50); options = saoptimset(options,TemperatureFcn,temperaturefast); options = saoptimset(options,ReannealInterval,50); options = saoptimset(options,Display,iter,DisplayInte

15、rval,400); options = saoptimset(options,TolFun,1e-5);,相关函数： x, fval = threshacceptbnd(objfun, x0),1）加载数据,表1 29个城市的坐标,3.6 模拟退火算法对TSP的应用,inputcities = 1150.0 630.0 40.0 750.0 750.0 1030.0 1650.0 1490.0 . 790.0 710.0 840.0 1170.0 970.0 510.0 750.0 1280.0 230.0 460.0 . 1040.0 590.0 830.0 490.0 1840.0 12

16、60.0 1280.0 490.0 1460.0 . 1260.0 360.0; 1760.0 1660.0 2090.0 1100.0 2030.0 2070.0 650.0 . 1630.0 2260.0 1310.0 550.0 2300.0 1340.0 700.0 900.0 1200.0 . 590.0 860.0 950.0 1390.0 1770.0 500.0 1240.0 1500.0 790.0 . 2130.0 1420.0 1910.0 1980.0;,2）计算总距离的函数 该函数根据给定路径计算该路径对应总路程。 function d = distance(inpu

17、tcities) % d = distance(inputcities)计算TSP问题中n个城市间某路径的总路程 % 输入参数为2*n数组，其中n为城市数目，列为对应城市坐标 d = 0; for n = 1 : length(inputcities) if n = length(inputcities) d = d + norm(inputcities(:,n) - inputcities(:,1); else d = d + norm(inputcities(:,n) - inputcities(:,n+1); end end,3）绘制路线的函数,function f = plotciti

18、es(inputcities) % plotcities(inputcities)从inputcities参数中绘制城市的位置 %输入参数为2*n数组，其中n为城市数目，列为对应城市坐标 temp_1 = plot(inputcities(1,:),inputcities(2,:),b*); set(temp_1,erasemode,none); temp_2 = line(inputcities(1,:),inputcities(2,:),Marker,*); set(temp_2,color,r); x = inputcities(1,1) inputcities(1,length(inp

19、utcities); y = inputcities(2,1) inputcities(2,length(inputcities); x1 = 10*round(max(inputcities(1,:)/10); y1 = 10*round(max(inputcities(2,:)/10); if x1 = 0 x1 = 1; end if y1 = 0 y1 = 1; end axis(0 x1 0 y1); temp_3 = line(x,y); set(temp_3,color,r); dist = distance(inputcities); distance_print = spri

20、ntf(.The roundtrip length for %d cities is % 4.6f units. ,length(inputcities),dist); text(x1/15,1.05*y1,distance_print,fontweight,bold); drawnow;,4）交换城市的函数,% s = swapcities(inputcities,n) n个城市随机的交换返回一组m个城市 s = inputcities; for i = 1 : n city_1 = round(length(inputcities)*rand(1); if city_1 1 city_1

21、= 1; end city_2 = round(length(inputcities)*rand(1); if city_2 1 city_2 = 1; end temp = s(:,city_1); s(:,city_1) = s(:,city_2); s(:,city_2) = temp; end,5）执行模拟退火的函数,function s = simulatedannealing(inputcities,initial_temperature,. cooling_rate,threshold,numberofcitiestoswap) % s = simulatedannealing

22、(inputcities,initial_temperature,cooling_rate,) %通过n 个城市的TSP问题的最优解返回一个新的城市构型。 global iterations; temperature = initial_temperature; initial_cities_to_swap = numberofcitiestoswap; iterations = 1; complete_temperature_iterations = 0; while iterations = 10 temperature = cooling_rate*temperature; comple

23、te_temperature_iterations = 0; end,numberofcitiestoswap = round(numberofcitiestoswap*exp(-diff/(iterations*temperature); if numberofcitiestoswap = 0 numberofcitiestoswap = 1; end iterations = iterations + 1; complete_temperature_iterations = complete_temperature_iterations + 1; else if rand(1) exp(-

24、diff/(temperature) inputcities = temp_cities; plotcities(inputcities); numberofcitiestoswap = round(numberofcitiestoswap*exp(-diff/(iterations*temperature); if numberofcitiestoswap = 0 numberofcitiestoswap = 1; end complete_temperature_iterations = complete_temperature_iterations + 1; iterations = i

25、terations + 1; end end clc fprintf(tttIterations = %dn,iterations); fprintf(tttTemperature = %3.8fn,temperature); fprintf(tttIn current temperature for %d timesn,complete_temperature_iterations); end previous_distance,simulatedannealing(inputcities,2000,0.97,2000,2),四. 遗传算法,4.1 遗传算法简介,19世纪60年代 Holla

26、nd,一族通过模拟自然进化过程搜索最优解的方法,遗传算法是一种概率搜索算法，它是利用某种编码技术作用于称为染色体的二进制数串，其基本思想是模拟由这些串组成的群体的进化过程。遗传算法通过有组织的然而是随机的信息交换来重新结合那些适应性好的串，在每一代中，利用上一代串结构中适应性好的位和段来生成一个新的串的群体；作为额外添加，偶尔也要在串结构中尝试用新的位和段来替代原来的部分。,与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，是适应性好的染色体比适应性差的染色体有更多的繁殖机会。,遗传算法利用简单的编码技术和繁殖机制来表现复

27、杂的现象，从而解决非常困难的问题。特别是它不受搜索空间的限制性假设的约束，不必要求诸如连续性、导数存在、单峰等假设，以及其固有的并行性。,生物遗传概念在遗传算法中的对应关系,遗传算法的优点：,适合数值求解那些带有多参数、多变量、多目标和在多区域但连通性较差的NP-hard优化问题，是一个有普适性的方法 在求解很多组合优化问题时，不需要有很强的技巧和对问题有非常深入的了解 同其他启发式算法有较好的兼容性,遗传算法的缺点：,编码不规范及编码存在表示的不准确性 单一的遗传算法编码不能全面表示优化问题的约束 是否能保证收敛到最优解？,1）编码：将解空间的解数据表示成遗传空间的基因型串结构数据；,4.2

28、 遗传算法流程,0，1二进制编码：0-1背包问题 非常规编码（非0-1编码）：TSP，约束机器排序问题,2）初始化：设置进化代数计数器 t=0，设置最大进化代数T，随机生成M个个体作为初始种群P(0),5 2 1 4 3 5 2 4 3 1 5 2 3 4 2 1 5 3 1 4 5 2 3 1,例如：,群体的规模 初始群体的选择,3）个体评价（适应函数）：计算种群P(t)中各个个体的适应度,非线性加速适应函数,简单适应函数：目标函数,线性加速适应函数,排序适应函数,4）选择运算：将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是

29、建立在群体中个体的适应度评估基础上的。,经典的选择算子：轮盘赌 被选中的概率为：,5）交叉运算：将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子,双亲遗传法 单亲遗传法 非常规码的交配方式,5 2 | 1 4 | 3 5 2 4 | 3 1 | 5 2 3 4 | 2 1 | 5 3 1 4 | 5 2 | 3 1,例：（TSP）有序杂交法：将个体两两配对，并以交叉概率Pc把配对的父代个体加以替换重组而生成新个体,5 2 | 3 1 | 3 5 2 4 | 1 4 | 5 2,倘若交换基因后出现了重复，则将该城市取代字

30、串B1与A1中的城市具有相同位置的新城市，直到与字串A1中的城市均不重复为止。,5 2 | 3 1 | 1 5 2 4 | 1 4 | 5 2,5 2 | 3 1 | 4 5 2 4 | 1 4 | 5 2,6）变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因作变动。,以变异概率Pm对群体中个体串某些基因位上的基因值作变动，若变异后子代的适应度值更加优异，则保留子代染色体，否则，仍保留父代染色体。,例：,5 2 | 3 1 | 4 5,5 2 | 1 3 | 4 5,群体P(t)经过选择、交叉和变异运算之后得到下一代群体P(t+1) 7）终止条件判断：若t=T，则以进化

31、过程中所得到的具有最大适应度个体作为最优解输出，终止计算。,4.3 遗传算法的matlab实现,x = ga(fitnessfcn,nvars) x = ga(fitnessfcn,nvars,A,b) x = ga(fitnessfcn,nvars,A,b,Aeq,beq) x = ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB) x = ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB,nonlcon) x = ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB,nonlcon,options) x, fval

32、= ga(.) x, fval, exitflag, output, population, scores = ga(),解约束优化问题,A = 1 1; -1 2; 2 1; b = 2; 2; 3; lb = zeros(2,1); x, fval, exitflag = ga(lincontest6,2,A,b,lb),Optimization terminated: average change in the fitness value less than options.TolFun. x = 0.7904 1.2094 fval = -8.0180 exitflag = 1,fun

33、ction y = simple_fitness(x) y = 100 * (x(1)2 - x(2) 2 + (1 - x(1)2;,function c, ceq = simple_constraint(x) c = 1.5 + x(1)*x(2) + x(1) - x(2); -x(1)*x(2) + 10; ceq = ;,ObjectiveFunction = simple_fitness; nvars = 2; % Number of variables LB = 0 0; % Lower bound UB = 1 13; % Upper bound ConstraintFunct

34、ion = simple_constraint; x,fval = ga(ObjectiveFunction,nvars,LB,UB, ConstraintFunction),Optimization terminated: average change in the fitness value less than options.TolFun and constraint violation is less than options.TolCon. x = 0.8122 12.3122 fval = 1.3578e+004,gatool,Fitness function：ackleyfcn

35、Number of variables：10 选中Plots中的Best fitness,X = gamultipoj(fitnessfcn,nvars,A,b,Aeq,beq,lb,ub,options),可以处理线性不等式约束、线性等式约束和有界约束,解多目标规划,function y = simple_multiobjective(x) y(1) = (x+2)2 - 10; y(2) = (x-2)2 + 20;,FitnessFunction = simple_multiobjective; numberOfVariables = 1; x,fval = gamultiobj(Fit

36、nessFunction,numberOfVariables);,Optimization terminated: average change in the spread of Pareto solutions less than options.TolFun.,size(x) ans = 15 1 size(fval) ans = 15 2,4.4 遗传算法对TSP的应用,load(usborder.mat,x,y,xx,yy); plot(x,y,Color,red); hold on;,cities = 40; locations = zeros(cities,2); n = 1; while (n = cities) xp = rand*1.5; yp = rand; if inpolygon(xp,yp,xx,yy) locations(n,1) = xp; locations(n,2) = yp; n = n+1; end end plot(locations(:,1),locations(:,2),bo)