在工程实践中,经常会接触到一些比较“新颖”的算法或理论,比如模拟退火,遗传算法,禁忌搜索,神经网络等。这些算法或理论都有一些共同的特性(比如模拟自然过­程),通称为“智能算法”。它们在解决一些复杂的工程问题时大有用武之地。
这些算法都有什么含义?首先给出个局部搜索,模拟退火,遗传算法,禁忌搜索的形象比喻:
为了找出地球上最高的山,一群有志气的兔子们开始想办法。
1.兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是局部搜索,它不能保证局部最优值就是全局最优值。
2.兔子喝醉了。他随机地跳了很长时间。这期间,它可能走向高处,也可能踏入平地。但是,他渐渐清醒了并朝最高方向跳去。这就是模拟退火。
3.兔子们吃了失忆药片,并被发射到太空,然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是,如果你过几年就杀死一部分海拔低的兔子,多产的­兔子们自己就会找到珠穆朗玛峰。这就是遗传算法。
4.兔子们知道一个兔的力量是渺小的。他们互相转告着,哪里的山已经找过,并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这­就是禁忌搜索。
智能优化算法的概述
智能优化算法要解决的一般是最优化问题。最优化问题可以分为(1)求解一个函数中,使得函数值最小的自变量取值的函数优化问题和(2)在一个解空间里面,寻找最­优解,使目标函数值最小的组合优化问题。典型的组合优化问题有:旅行商问题(Traveling
Salesman Problem,TSP),加工调度问题(Scheduling
Problem),0-1背包问题(Knapsack
Problem),以及装箱问题(Bin Packing Problem)等。
优化算法有很多,经典算法包括:有线性规划,动态规划等;改进型局部搜索算法包括爬山法,最速下降法等,本文介绍的模拟退火、遗传算法以及禁忌搜索称作指导性搜­索法。而神经网络,混沌搜索则属于系统动态演化方法。
优化思想里面经常提到邻域函数,它的作用是指出如何由当前解得到一个(组)新解。其具体实现方式要根据具体问题分析来定。
一般而言,局部搜索就是基于贪婪思想利用邻域函数进行搜索,若找到一个比现有值更优的解就弃前者而取后者。但是,它一般只可以得到“局部极小解”,就是说,可能­这只兔子登“登泰山而小天下”,但是却没有找到珠穆朗玛峰。而模拟退火,遗传算法,禁忌搜索,神经网络等从不同的角度和策略实现了改进,取得较好的“全局最小解­”。
模拟退火算法(Simulated Annealing,SA)
模拟退火算法的依据是固体物质退火过程和组合优化问题之间的相似性。物质在加热的时候,粒子间的布朗运动增强,到达一定强度后,固体物质转化为液态,这个时候再­进行退火,粒子热运动减弱,并逐渐趋于有序,最后达到稳定。
模拟退火的解不再像局部搜索那样最后的结果依赖初始点。它引入了一个接受概率p。如果新的点(设为pn)的目标函数f(pn)更好,则p=1,表示选取新点;否­则,接受概率p是当前点(设为pc)的目标函数f(pc),新点的目标函数f(pn)以及另一个控制参数“温度”T的函数。也就是说,模拟退火没有像局部搜索那­样每次都贪婪地寻找比现在好的点,目标函数差一点的点也有可能接受进来。随着算法的执行,系统温度T逐渐降低,最后终止于某个低温,在该温度下,系统不再接受变­化。
模拟退火的典型特征是除了接受目标函数的改进外,还接受一个衰减极限,当T较大时,接受较大的衰减,当T逐渐变小时,接受较小的衰减,当T为0时,就不再接受衰­减。这一特征意味着模拟退火与局部搜索相反,它能避开局部极小,并且还保持了局部搜索的通用性和简单性。
在物理上,先加热,让分子间互相碰撞,变成无序状态,内能加大,然后降温,最后的分子次序反而会更有序,内能比没有加热前更小。就像那只兔子,它喝醉后,对比较­近的山峰视而不见,迷迷糊糊地跳一大圈子,反而更有可能找到珠峰。
值得注意的是,当T为0时,模拟退火就成为局部搜索的一个特例。
模拟退火的伪码表达:
procedure simulated annealing
begin
t:=0;
initialize temperature T
select a current string vc at random;
evaluate vc;
repeat
repeat
select a new string vn in the neighborhood of vc; (1)
if f(vc) then vc:=vn;
else if random [0,1] then vc:=vn;
until (termination-condition) (3)
T:=g(T,t); (4)
T:=t+1;
until (stop-criterion) (5)
end;
上面的程序中,关键的是(1)新状态产生函数,(2)新状态接受函数,(3)抽样稳定准则,(4)退温函数,(5)退火结束准则&nbs
模拟退火,遗传算法,电子书免费下载,E书下载,电子书下载,免费下
来源:互联网 发布日期:2011-08-20 15:20:11 浏览:6849次
导读:模拟退火,遗传算法,西安信息资源网提供,电子书免费下载,,E书下载,JAVA教程下载,教程下载,认证考试,教程下载,教育,培训,免费下载...
相关内容
AiLab云推荐
最新资讯
本月热点
热门排行
-
不被“机器狗之父”看好的人形机器人,未来要如何发展?
阅读量:72828
-
国产版达芬奇手术机器人价格跳水,是价格战要来了吗?
阅读量:67694
-
借势智元机器人,富临精工跨界入局人形机器人,准备好了吗?
阅读量:43585
-
实探全球首个核电灯塔工厂,这里有各式各样的机器人 | 碳访
阅读量:41863
-
追光十年|从工业产线到人形智能,上海抢占机器人产业新高地
阅读量:18060
-
傅盛:我不看好双足机器人的商业化
阅读量:13255
推荐内容
- 2024年德国汉诺威畜牧业展览会
- 2024山东国际玻璃工业技术展览会
- 2024沙特利雅得国际工程机械及混凝土展
- 2024沙特利雅得国际建材展Saudi Build
- 2024第29届欧洲法国(巴黎)国际海事防务展
- 2024 沙特国际照明电力能源展
- 第三届世界材料科学与工程研讨会(SMSE 2024)
- 2024第七届中国国际进口博览会(进博会 CIIE)
- 2024年西班牙国际电气电力照明展览会
- 2024中国(余姚)国际塑料博览会暨第二十五届中国塑料博览会
- 2024第三十届哈尔滨现代农业设施设备展 暨哈尔滨种业博览会/哈尔滨农资博览会
- 2024亚太新材料创新应用博览会(APAME2024)
- 2024第28届亚洲国际动力传动与控制技术展览(PTC)
- 2024年中东欧(塞尔维亚)国际能源展
- 2024第24届亚洲国际物流技术与运输系统展览会(CeMAT 亚洲物流展)
- Indomarine2024第七届印尼(雅加达)国际海事防务展
- 2024年意大利博洛尼亚国际农业及园林机械展EIMA International
- 2024年越南河内食品及食品加工包装展Vietfood&ProPack
- 2024第28届俄罗斯(莫斯科)国际军警展
- Indoaerospace2024第八届印尼(雅加达)国际航空航天展
- Indodefence2024第十届印尼(雅加达)国际防务展
- 2024第二届热管理材料技术博览会
- 2024年韩国釜山国际水产博览会
- 2024亚洲电子生产设备暨微电子工业展览会(NEPCON ASIA)
- 2024年美国盐湖城户外运动用品展览会(冬季)
- 2024深圳国际薄膜与胶带展(FILM & TAPE EXPO)
- 2024深圳国际全触与显示展(2024深圳全触展)
- 2024AMTS第二十届深圳国际汽车制造技术与装备及材料展览会
- 2024深圳国际全触与显示展览会
- 2024 深圳国际薄膜与胶带展览会
- 2024 中亚(哈萨克斯坦)照明及智慧城市展
- 第二届国际催化、化学科学与技术大会(ICCST 2024)
- 2024坦桑尼亚造纸包装、生活用纸和卫生用品展览会
- 2024第9届世界石油天然气装备博览会暨采购大会(WOGE2024)
- 2024第十七届厦门国际美业博览会
- 2024年坦桑尼亚造纸、包装、生活用纸 和卫生用品展
- 2024第十八届深圳国际金融博览会(金博会)
- 2024烟台国际能源低碳产业链展览会
- 2024第七届深圳海外置业移民留学展览会
- 2024(第十五届)重庆汽车消费节暨(第五届)房车生活节(CACF)
- 2024(第二十一届)中国西南(昆明)国际汽车博览会暨智能网联及未来出行汽车博览会
- 2024第十六届郑州国际汽车展览会暨新能源智能网联汽车展览会