在工程实践中,经常会接触到一些比较“新颖”的算法或理论,比如模拟退火,遗传算法,禁忌搜索,神经网络等。这些算法或理论都有一些共同的特性(比如模拟自然过­程),通称为“智能算法”。它们在解决一些复杂的工程问题时大有用武之地。
这些算法都有什么含义?首先给出个局部搜索,模拟退火,遗传算法,禁忌搜索的形象比喻:
为了找出地球上最高的山,一群有志气的兔子们开始想办法。
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教程下载,教程下载,认证考试,教程下载,教育,培训,免费下载...
相关内容
- AI 计算时代,为何Arm CPU依然是基石?
- Fedora 发行版调整:KDE桌面环境“上位”,和 GNOME“平起平坐”
- 从断供中国芯片始,三星或加速衰落,韩国距发展中国家有多远
- 登上Nature的AI芯片设计屡遭质疑,谷歌发文反击,Jeff Dean:质疑者连预训练都没做
- OpenAI收购域名Chat.com,传金额超过1000万美元
- 无需开颅将ChatGPT植入大脑,这家比尔盖茨支持的AI硬件公司,要挑战马斯克脑机接口
- 中国的生成式人工智能:创新、文化与全球领导力的桥梁
- 金砖大赛之元宇宙3D数字内容设计创作赛发布3D协同设计实训平台,考察学生3D内容在线编辑创作力
- 脑机接口,从实验室到市场还有多远?
- 2024年TCS网络安全研讨会顺利召开
AiLab云推荐
最新资讯
- 马斯克的脑机接口公司宣布启动新试验:通过大脑植入控制机械臂
- 马斯克旗下Neuralink获批测试用脑机接口控制机械臂,SpaceX获土卫六探测新订单 | 环球科学要闻
- 获准测试机械臂!马斯克的脑机接口公司Neuralink,越来越科幻了
- 中国的生成式人工智能:创新、文化与全球领导力的桥梁
- 航宇微:玉龙810A人工智能芯片已在部分商业卫星上成功实现搭载
- 脑机接口,从实验室到市场还有多远?
- TrendForce 发布 “2025 十大重点科技领域市场趋势预测”
- 科思科技:公司第一代智能无线通信基带芯片已进入商业化推广阶段
- AI 计算时代,为何Arm CPU依然是基石?
- 为开发AI芯片,传特斯拉已要求三星、SK海力士提供HBM4样片
本月热点
热门排行
-
存储芯片年涨七成不算完:AI需求接棒,大厂持续加注
阅读量:18036
-
美大选逼近!传大陆芯片设计业计划从台积电转单三星
阅读量:13772
-
黄仁勋对话扎克伯格:新款芯片样品本周发送,AI行业还有5年产品创新期
阅读量:12017
-
马斯克:Neuralink 今年预计完成 10 例脑机接口植入手术
阅读量:11857
-
应对先进封装挑战,芯碁微装直写光刻技术助力本土创新突破
阅读量:11516
-
黑芝麻智能登陆港交所:智能汽车AI芯片第一股,拥抱广阔机遇
阅读量:11389
推荐内容
- 2024山东国际玻璃工业技术展览会
- 2024中国(东莞)国际包装印刷展览会
- 2024第四届成都国际乐器展览会
- 2024年法国巴黎农业机械展览会SIMA
- DronTechAsia2024亚洲(泰国曼谷)国际无人系统展
- 2024第21届中国(昆明)国际美业博览会(CKBE)
- 2024年第23届伊朗国际电力电工设备及技术展(全球六大电力展)
- 2024中东矿业展|2024年迪拜国际矿业展览会
- 2024年阿联酋迪拜国际矿业展览会
- 2024年埃及国际电力能源及照明展览会
- 2024中国(郑州)数字化与先进装备制造业博览会
- 2024第十一届中国国际工程机械、建材机械、矿山机械、工程车辆及设备博览会(上海宝马展)
- 2024DMP大湾区工业博览会(深圳工博会)