在工程实践中,经常会接触到一些比较“新颖”的算法或理论,比如模拟退火,遗传算法,禁忌搜索,神经网络等。这些算法或理论都有一些共同的特性(比如模拟自然过­程),通称为“智能算法”。它们在解决一些复杂的工程问题时大有用武之地。
这些算法都有什么含义?首先给出个局部搜索,模拟退火,遗传算法,禁忌搜索的形象比喻:
为了找出地球上最高的山,一群有志气的兔子们开始想办法。
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 浏览:5726次
导读:模拟退火,遗传算法,西安信息资源网提供,电子书免费下载,,E书下载,JAVA教程下载,教程下载,认证考试,教程下载,教育,培训,免费下载...
相关内容
AiLab云推荐
最新资讯
本月热点
- OpenAI CEO:看好人形机器人,未来人类不必再掌握计算机科学
- Neuralink计划将Link功能扩展到现实世界,以控制机械臂、轮椅等
- 杨鹏:人形机器人进入提速发展阶段
- 特斯拉招聘人形机器人 Optimus 用户手册撰写员,明年开始交付
- 转向机器人!三星电子被曝停止自动驾驶研究:开发难度超预期,商业化难
- 视频|科研教育四足机器人展出
- 出口反超进口,首个国家级机器人产业园出门“掰手腕” | 解码新质园区
- 苹果终止电车项目后大裁员,押注家用机器人,这会是Next Big Thing吗?
- 从液压Atlas到电动Atlas,人形机器人的拐点时刻
- 斯坦福20亿参数多模态AI Agent模型大升级,手机汽车机器人都能用
热门排行
-
斯坦福家政机器人火了但又翻车了!多数是真人操控编排的
阅读量:173655
-
斯坦福团队发布新机器人Mobile Aloha,人形机器人将迎来产业元年?
阅读量:172982
-
我的同事是 GPT-4 机器人,我们在 Slack 上一起工作
阅读量:170372
-
谷歌起草“机器人宪法”,以确保 AI 机器人不会伤害人类
阅读量:168229
-
人形机器人崛起:OpenAI、微软洽谈投资Figure AI,望募资5亿美元
阅读量:109133
-
大疆回应停售青少年教育产品:将资源聚焦在大学生高校机器人赛事
阅读量:77309
推荐内容
- 2024冻立方中国(厦门)冷冻冷藏食品展
- 2024第二十一届中国畜牧业展览会(畜博会CAHE)
- 2024第十三届中国(西安)糖酒食品交易会(西安糖酒会)
- 2024西部乡村振兴博览会暨农业机械装备展
- 2024年第28届伊朗国际石油、天然气、炼油和石化展览会
- 中东石油展 2024年第28届伊朗国际石油展
- 2024重庆国际餐饮(火锅)食材展览会
- 2024深圳国际渔业博览会
- 2024华晨第十一届中国(山东)秋季国际宠物水族展
- 2024中亚一带一路工博会
- 2024第七届雄安城市建设及绿色建筑博览会 第七届雄安装配式建筑及绿色建材展览会 2024中国绿色建筑与智能建造科技大会 第五届雄安金桥梁项目对接会
- 2024第七届中国(新疆)国际智能交通产业博览会
- 2024越南(河内)国际五金及工具展览会
- 2024山东连锁加盟展览会 开年山东首展
- 2024武汉国际电子元器件、材料及生产设备展览会
- 2024山东(济南)连锁加盟博览会助力行业发展
- CRFE国际连锁加盟展览会 -山东招商加盟专业展
- 2024第五届深圳国际老龄博览会
- 2024年山西国际水展览会
- 2024哈尔滨东北亚国际口腔设备及器材展览会
- 2024第二十一届中国(漯河)食品博览会
- 2024第十届中国(北京)国际警用装备及反恐技术装备展览会暨学术研讨会 (CIPATE)
- 2024孟加拉国际暖通、空调制冷、净化、楼宇自控展