智能优化理论和方法.ppt
- 文档编号:18763225
- 上传时间:2023-11-02
- 格式:PPT
- 页数:75
- 大小:1.07MB
智能优化理论和方法.ppt
《智能优化理论和方法.ppt》由会员分享,可在线阅读,更多相关《智能优化理论和方法.ppt(75页珍藏版)》请在冰点文库上搜索。
智能优化理论和方法主讲:
汤可宗,信息工程学院计算机专业教研室2014年10月22日,1,提要,什么是新技术最优化问题与最优化方法概述传统的最优化方法智能优化方法简介-遗传算法智能优化方法对社会的影响力,一.什么是新技术?
1.以前不存在,运用某种学科或多门学科知识发明创造出的能够给人们工作,生活带来方便的技术.如:
电灯,因特网的出现.2.针对某个科学或生产问题,传统的方法不适用或给出的结果不理想,迫切需要找到一种新的解决方法。
如,具有NP难度的组合问题(TSP).,2,新技术的出现将会对事物产生新的理解,这种理解往往会引发出空间和时间的新的概念。
新技术的出现,往往会引发新的问题,并让我们看到新的危机。
3,最优化问题就是在给定条件下寻找最佳方案的问题。
而寻找最佳方案的方法称之为最优化方法(也称之为”运筹学方法”),这种方法的数学理论称之为最优化理论。
最优化问题在工业生产,科学理论研究,以及人们的日常工作学习及生活中无处不在,无处不有。
根据最优化问题的特点需要采用不同的最优化方法。
4,二.最优化问题与最优化方法的概述,最短路径优化最省时间优化管理科学优化工程设计优化市场调度优化城市建设优化,5,2.1为何要研究优化问题,举例1.最短路径优化,6,一个商人拟到n个城市去推销商品,已知每两个城市Ai和Aj之间的距离为dij,如何选择一条道路,使得商人每个城市走一遍后回到起点,且所走的路径最短。
这个问题称为旅行商问题(TravelingSalesmanProblem),简称TSP,举例2:
学习效率问题,学生每天的时间是一定的,在一定的时间里,我们要安排好学习,锻炼,休息等各个环节。
时间安排的是否合理,科学,直接关系到我们每天的学习效率,关系到我们自身的全面发展。
可以围绕”怎样合理安排时间,才能取得好的学习成绩,促进人的全面发展”,为自己设计一个方案.,7,8,1994年全国赛A题:
逢山开路1996年全国赛A题:
最优捕鱼策略2001年全国赛B题:
公交车优化调度2010年东三省A题:
企业的营销管理问题2010年东三省B题:
周游全中国,举例3:
数学建模问题,9,10,11,2.2数学意义,最优化是一门应用十分广泛的学科。
从数学意义上说,最优化方法是一种求极值的方法,即在一组约束为等式或不等式的条件下,使系统的目标函数达到极值,即最大值或最小值。
从经济意义上说,是在一定的人力、物力和财力资源条件下,使经济效果达到最大(如产值、利润),或者在完成规定的生产或经济任务下,使投入的人力、物力和财力等资源为最少。
12,2.3发展简史,公元前500年古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为1.618,称为黄金分割比。
其倒数至今在优选法中仍得到广泛应用。
在微积分出现以前,已有许多学者开始研究用数学方法解决最优化问题。
例如,阿基米德证明:
给定周长,圆所包围的面积为最大。
这就是欧洲古代城堡几乎都建成圆形的原因。
13,最优化方法真正形成为科学方法则在17世纪以后。
17世纪,牛顿和莱布尼茨在他们所创建的微积分中,提出求解具有多个自变量的实值函数的最大值和最小值的方法,后来又出现了Lagrange乘数法。
以后又进一步讨论具有未知函数的函数极值,从而形成变分法。
这一时期的最优化方法可以称为古典最优化方法。
第二次世界大战时期,英国为了最有效地利用有限的战争资源,成立了作战研究小组,取得了了良好的效果。
战后,作战研究的思想被运用于运输管理,生产管理和一些经济学问题中,于是形成了以线性规划,博弈论等为主干的运筹学。
运筹学的英文名正是“作战研究(OperationResearch)”,其精髓就是要在约束条件表述的限制下,实现用目标函数表述的某个函数的最优化。
14,随着工业生产和科学技术的发展需要,许多实际的最优化问题已经无法用古典方法来解决,这就促进了近代最优化方法的产生。
15,近代最优化方法的形成和发展,1847年法国数学家Cauchy研究了函数值沿什么方向下降最快的问题,提出最速下降法。
1939年苏联数学家Kahtoponnh提出了解决下料问题和运输问题这两种线性规划问题的求解方法。
以苏联数学家康托罗维奇和美国丹齐克为代表的线性规划,16,以美国库思和塔克为代表的非线性规划;以美国贝尔曼为代表的动态规划;以苏联庞特里亚为代表的极大值原理等。
上述这些方法后来都形成体系,成为近代很活的学科,对促进运筹学,管理科学,控制论和系统工程等学科的发展起了重要作用。
17,20世纪40年代以来,由于生产和科学研究的飞速发展,特别是电子计算机日益广泛的使用,最优化问题的研究不仅成为一种迫切需要,而且又出现了许多基于生物模拟的新的最优化方法。
因此最优化理论和算法迅速发展起来,成为了一门新的学科。
18,19,2.4举例,田忌赛马,20,21,体会:
做事情要讲究策略,学会优化设计。
在解决问题的多种方案中,要寻求最优方案与原则.,还有就是,让我们在生活中要善于观察、善于思考。
22,结论:
用综合的思维方式来认识事物,23,掌握好系统优化方法必须做到,
(1)着眼于事物的整体性;
(2)遵循系统内部结构的有序性;(3)注重系统内部结构的优化趋向.,24,25,26,三.传统的优化方法,3.1最优化问题的分类,传统的优化方法主要指:
线性规划的单纯形法,非线性规划的基于梯度的各类迭达算法。
基本步骤如右图所示:
27,1.选择一个初始解,2.满足停止准则?
3.向改进方向移动,停止计算,输出结果。
yy,yn,3.2传统优化方法的基本步骤,3.3传统优化方法的局限性,
(1)单点运算方式大大限制了计算效率的提高。
(2)向改进方向移动限制了跳出局部最优的能力。
(3)停止条件只是局部最优性的条件。
(4)对目标函数和约束函数的要求限制了其应用范围,28,任何一种新方法在其产生的初期往往是“方法定向”的,即它只能解决满足该方法适用条件的问题。
要想运用这种方法就必须简化或改变原来的问题,使之能够满足该方法的适用条件。
比如,为了使用线性规划的超强计算能力,实际中往往不得不采用拟线性化或分段线性化的方法把非线性问题转化成线性问题。
29,20世纪70年末流行过这样一个十分形象的比喻,说最优化方法好像是“只卖一个尺码鞋的鞋店,脚小的塞棉花,脚大的砍一截。
30,针对传统优化方法的不足,人们对最优化方法提出了一些新的要求,使其能不局限于某一类问题的解决。
(1)对目标函数和约束函数表达的要求更为宽松,即目标函数和约束函数可以必是解析的,更不必是连续和高阶的。
(2)计算的效率比理论上的最优性更重要,31,四.智能优化方法简介,对于一些复杂制造系统的实时调度问题要求优化算法算得快,能解决的问题规模大。
这就要求优化方法能够高效快速地找到满意解,至于是不是最优解反而并不十分重要。
(3)算法随时终止都能够随时得到较好的解。
对于这类问题,虽然计算更长时间可以获得更好的解,但由于急于使用结果往往要求能够随时终止计算,且能到一个与计算时间代价相当的较好解。
32,(4)对优化模型中数据的质量要求更加宽松。
传统的优化方法是基于精确数学的方法,对数据的确定性和准确性有严格的要求。
但实际生活中很多信息具有很高的不确定性。
因此,迫切需要能够直接对具有不确定性的数据乃至语言变量进行计算的优化方法。
33,面向实际需要,促使最优化方法从“方法定向”向“问题定向”的转换。
于是新的优化方法不断出现。
最优化理论的三大非经典算法:
遗传算法、模拟退火算法、蚁群优化算法。
34,4.1基于遗传算法的随机优化搜索,遗传算法(GA,GeneticAlgorithm),也称进化算法。
遗传算法是受达尔文的进化论的启发,借鉴生物进化过程而提出的一种启发式搜索算法。
因此在介绍遗传算法前有必要简单的介绍生物进化知识。
35,4.1.1生物学进化知识,36,1.个体与种群个体就是模拟生物个体而对问题中的解的一种称呼,一个个体也就是搜索空间中的一个点。
种群(population)就是模拟生物种群而由若干个体组成的群体,它一般是整个搜索空间的一个很小的子集。
37,2.适应度与适应度函数适应度(fitness)就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。
适应度函数(fitnessfunction)就是问题中的体个体与其适应度之间的一个对应关系。
它一般是一个实值函数。
该函数就是遗传算法中指导搜索的评价函数。
38,3.染色体与基因染色体(chromosomechromosome)就是问题中个体的某种字符串形式的编码表示。
字符串中的字符也就称为基因(gene)。
例如:
个体染色体99-10011001(2,5,6)-(010,101,110)010101110,39,4.遗传操作亦称遗传算子(geneticoperator),就是关于染色体的运算。
遗传算法中有三种遗传操作:
选择-复制(selection-reproduction)交叉(crossover,亦称交换、交配或杂交)变异(mutation,亦称突变),40,选择-复制其目的是从种群中按照某种策略选择出若干个体进行遗传运算.通常采用的是正比选择选策略,即每个个体xi被中进行遗传运算的概率P(xi)为该个体的适应值和群体中所有个体适应值总和的比例.,41,在得到选择概率后,采用旋轮法来实现选择操作.令PP0=0,共旋轮N次,每次旋轮时,随机产生rk(0,1),当PPi-1rkPPi,则选择个体i.,42,交叉就是互换两个染色体某些位上的基因。
例如,设染色体P1=01001011,P2=10010101,单点交叉:
双点交叉:
43,变异就是在种群中按照变异概率Pm任选若干基因位改变基位值。
变异概率一般设定为一个比较小的数,在5%以下.例如,设染色体s=11001101将其第三位上的0变为1,IfrPm,则s=1100110111101101=s。
s也可以看做是原染色体s的子代染色体。
44,4.1.2基本遗传算法,45,算法中的一些控制参数:
种群规模最大迭代次数交叉率(crossoverrate)就是指的是两个个体能否进行交叉的概率,记为Pc,取值范围一般为0.40.99。
通常r=Pc,执行交叉操作.变异率(mutationrate)是决定着一个个体上的基因能否进行变异的概率,记为Pm,取值范围一般为0.00010.1。
46,基本遗传算法步1在搜索空间U上定义一个适应度函数f(x),给定种群规模N,交叉率Pc和变异率Pm,代数T;步2随机产生U中的N个个体s1,s2,sN,组成初始种群S=s1,s2,sN,置代数计数器t=1;步3计算S中每个个体的适应度f();步4若终止条件满足,则取S中适应度最大的个体作为所求结果,算法结束。
否则,转步5,47,步5按选择概率P(xi)所决定的选中机会,每次从S中随机选定1个个体并将其染色体复制,共做N次,然后将复制所得的N个染色体组成群体S1;步6从S1中任选两个个体,按交叉率Pc确定两个个体是否能进行交叉操作,从S1中随机确定2个染色体,配对进行交叉操作,并用产生的新染色体代替原染色体,得群体S2;,48,步7按变异率Pm对种群中的每个个体上的基因位进行变异操作,从S2中随机确定m个染色体,分别进行变异操作,并用产生的新染色体代替原染色体,得群体S3;步8将群体S3作为新一代种群,即用S3代替S,t=t+1,转步3;,49,4.1.3遗传算法应用举例,例4.1利用遗传算法求解区间0,31上的二次函数y=x2的最大值。
50,分析原问题可转化为在区间0,31中搜索能使y取最大值的点a的问题。
那么,0,31中的点x就是个体,函数值f(x)恰好就可以作为x的适应度,区间0,31就是一个(解)空间。
这样,只要能给出个体x的适当染色体编码,该问题就可以用遗传算法来解决。
51,解
(1)设定种群规模,编码染色体,产生初始种群。
将种群规模设定为4;用5位二进制数编码染色体;取下列个体组成初始种群S1:
s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)
(2)定义适应度函数,取适应度函数:
f(x)=x2,52,(3)计算各代种群中的各个体的适应度,并对其染色体进行遗传操作,直到适应度最高的个体(即31(11111))出现为止。
53,首先计算种群S1中各个体s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)的适应度f(si)。
容易求得f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361,54,再计算种群S1中各个体的选择概率。
选择概率的计算公式为,由此可求得P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31,55,赌轮选择示意,赌轮选择法,56,在算法中赌轮选择法可用下面的子过程来模拟:
在0,1区间内产生一个均匀分布的随机数r。
若rq1,则染色体x1被选中。
若qk-1rqk(2kN),则染色体xk被选中。
其中的qi称为染色体xi(i=1,2,n)的积累概率,其计算公式为,57,选择-复制,设从区间0,1中产生4个随机数如下:
r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503,58,于是,经复制得群体:
s1=11000(24),s2=01101(13)s3=11000(24),s4=10011(19),59,交叉设交叉率pc=0.9,即S1中的全体染色体都参加交叉运算。
设s1与s2配对,s3与s4配对。
分别交换后两位基因,得新染色体:
s1=11001(25),s2=01100(12)s3=11011(27),s4=10000(16),60,变异设变异率pm=0.001。
每一个个体的基因能够变异的概率为pm,于是,得到第二代种群S2:
s1=11001(25),s2=01100(12)s3=11011(27),s4=10000(16),61,第二代种群S2中各染色体的情况,62,假设这一轮选择-复制操作中,种群S2中的4个染色体都被选中,则得到群体:
s1=11001(25),s2=01100(12)s3=11011(27),s4=10000(16),做交叉运算,让s1与s2,s3与s4分别交换后三位基因,得,s1=11100(28),s2=01001(9)s3=11000(24),s4=10011(19),这一轮仍然不会发生变异。
63,于是,得第三代种群S3:
s1=11100(28),s2=01001(9)s3=11000(24),s4=10011(19),64,第三代种群S3中各染色体的情况,65,设这一轮的选择-复制结果为:
s1=11100(28),s2=11100(28)s3=11000(24),s4=10011(19),做交叉运算,让s1与s4,s2与s3分别交换后两位基因,得,s1=11111(31),s2=11100(28)s3=11000(24),s4=10000(16),这一轮仍然不会发生变异。
66,于是,得第四代种群S4:
s1=11111(31),s2=11100(28)s3=11000(24),s4=10000(16),67,显然,在这一代种群中已经出现了适应度最高的染色体s1=11111。
于是,遗传操作终止,将染色体“11111”作为最终结果输出。
然后,将染色体“11111”解码为表现型,即得所求的最优解:
31。
将31代入函数y=x2中,即得原问题的解,即函数y=x2的最大值为961。
68,69,4.1.4遗传算法的特点与优势,遗传算法的主要特点遗传算法一般是直接在解空间搜索,而不像图搜索那样一般是在问题空间搜索,最后才找到解。
遗传算法的搜索随机地始于搜索空间的一个点集,而不像图搜索那样固定地始于搜索空间的初始节点或终止节点,所以遗传算法是一种随机搜索算法。
70,遗传算法总是在寻找优解,而不像图搜索那样并非总是要求优解,而一般是设法尽快找到解,所以遗传算法又是一种优化搜索算法。
遗传算法的搜索过程是从空间的一个点集(种群)到另一个点集(种群)的搜索,而不像图搜索那样一般是从空间的一个点到另一个点地搜索。
因而它实际是一种并行搜索,适合大规模并行计算,而且这种种群到种群的搜索有能力跳出局部最优解。
71,遗传算法的适应性强,除需知适应度函数外,几乎不需要其他的先验知识。
遗传算法长于全局搜索,它不受搜索空间的限制性假设的约束,不要求连续性,能以很大的概率从离散的、多极值的、含有噪声的高维问题中找到全局最优解。
72,遗传算法的应用遗传算法在人工智能的众多领域便得到了广泛应用。
例如,机器学习、聚类、控制(如煤气管道控制)、规划(如生产任务规划)、设计(如通信网络设计、布局设计)、调度(如作业车间调度、机器调度、运输问题)、配置(机器配置、分配问题)、组合优化(如TSP、背包问题)、函数的最大值以及图像处理和信号处理等等。
73,另一方面,人们又将遗传算法与其他智能算法和技术相结合,使其问题求解能力得到进一步扩展和提高。
例如,将遗传算法与模糊技术、神经网络相结合,已取得了不少成果。
中国知网查找的以“智能优化算法”为主题的文献。
74,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 智能 优化 理论 方法
![提示](https://static.bingdoc.com/images/bang_tan.gif)