最近心血来潮,重新拾起大学毕业设计时研究过的遗传算法。去年做毕业设计时还觉得遗传算法是一种多么神秘的算法,但是今天看来,遗传算法也就和冒泡排序算法差不多,都是通用的算法,只不过遗传算法实现起来稍微复杂一点而已。
我曾经被遗传算法的名字所疑惑,还以为遗传算法会改变程序的形态,使得程序就好像生物一样进化,过了几天去看程序已经变得连编写程序的人都认不出来了,汗!大二时的幼稚想法。
遗传算法其实是一种求函数极值的随机搜索算法,但它又不是毫无规则地随机搜索,而是基于一种假设:假设函数值的分布是有一定的连续性的,换句话说函数的极值出现在一个较优值附近的概率要大于出现在一个较差值附近的概率。基于这个假设,遗传算法总是以较大概率保留较优值所代表的搜索方向,而以较低概率保留较差值所代表的搜索方向。这并不是说不去搜索较差值的附近区域,只是搜索的概率较低而已。这个思想与模拟退火算法相似,对于能量较高的系统状态,程序仍然以一定的概率接受,只不过这个概率小于1。
遗传算法的局部搜索能力较强,但是很容易陷入局部极值,毕业设计的时候曾经认为只要增加变异概率就可以跳出局部极值,还美其名曰自适应,现在想想这种想法是错误的:虽然增加变异概率可以搜索到远离当前极值的点,但是新点的值往往不能和当前保留下来的较优值相提并论,因为这些较优值都是经过千百代的进化而存留下来的,于是远离当前极值的点往往在两到三代以内就被淘汰掉了。增加变异概率实际上是把遗传算法退化成了一种纯粹的随机搜索,所谓的自适应也无从谈起!
那么如何解决遗传算法容易陷入局部极值的问题呢?让我们来看看大自然提供的方案。六千五百万年以前,恐龙和灵长类动物并存,恐龙在地球上占绝对统治地位,如果恐龙没有灭绝灵长类动物是绝没有可能统治地球的。正是恐龙的灭绝才使灵长类动物有了充分进化的余地,事实上地球至少经历了5次物种大灭绝,每次物种灭绝都给更加高级的生物提供了充分进化的余地。所以要跳出局部极值就必须杀死当前所有的优秀个体,从而让远离当前极值的点有充分的进化余地。这就是灾变的思想。
下一个问题是什么时候进行灾变,换句话说什么时候局部搜索已经充分了呢?我用了一个灾变倒计数的概念:从500开始递减,每一代递减一次,如果出现了新的最优值,就从新开始计数,如果出现新最优值的时候倒计数递减次数的2.5倍已经超过500则从新的初始值开始倒数。例:初始倒数500,如果倒数到200时出现新最优值,则从(500 - 200) * 2.5 = 750开始从新倒数,下一次如果倒数到100时出现新最优值,则从(750 - 100) * 2.5 = 1625开始倒计数(这里的2.5是一个经验值,可以在全局参数设置里面调整)。也就是说倒计数的长度取决于进化的速度,进化速度越慢倒计数长度越长。如果倒计数完毕还没有新的最优值,就认为局部搜索已经充分,就发生灾变。
基于上诉思想我写了一个程序来计算旅行商问题。我现在终于体会到旅行商问题为什么会这么有名,有很多算法都可以解决旅行商问题,问题描述简单,评价函数也不复杂,问题的解可以
【原创】用遗传算法解决旅行商问题(附源代码)
来源:互联网 发布日期:2011-08-30 20:15:15 浏览:16220次
导读:研学论坛 最近心血来潮,重新拾起大学毕业设计时研究过的遗传算法。去年做毕业设计时还觉得遗传算法是一种多么神秘的算法,但是今天看来,遗传算法也就和冒泡排...
相关内容
- 马斯克:可能在明年年底前出售特斯拉人形机器人 Optimus
- 因会产生烧焦气味,日本世嘉玩具公司召回猫咪机器人
- 人形机器人公司星动纪元携手临港集团,其“小星家族”获姚期智点赞
- 基于软体机器人的开发,港中深教授打造硅胶3D打印机 | 早期项目
- 上市公司积极布局人形机器人赛道
- 第一个具有情商的聊天机器人来了,这可能是未来 Siri 的样子
- “下一个大事件”,消息称苹果公司将进入家庭机器人领域
- 机器人即将迎来“ChatGPT时刻”的三个原因
- 苹果欲进军家用机器人领域!这些A股上市公司布局相关业务
- 投资300亿!机器人产业爆发:几大趋势
- 波士顿动力推出全新电动 Atlas 人形机器人:更强更灵活
- Kria开发板搭配QNX软件,AMD、黑莓宣布合作推进下一代机器人系统
- 人形机器人登陆英伟达GTC大会,产业发展已成趋势
- 外媒:马斯克透露,“擎天柱”机器人仍在试验阶段,最早明年年底上市
- 李彦宏上车直播:汽车机器人就是未来,相当于司机和助理
- 从液压Atlas到电动Atlas,人形机器人的拐点时刻
- 人形机器人进厂“打工”,商业化前景广阔
- 特斯拉或将在2025年底前销售人形机器人Optimus,机器人100ETF(159530)一度涨超1%
- 昊志机电:目前公司谐波减速器等产品尚未应用于人型机器人领域
- 苹果从汽车转向家用机器人,机器人100ETF(159530)投资机会备受关注
AiLab云推荐
最新资讯
- 全球首台商用协作机器人制造商:拒绝价格战,大力引入人工智能
- 马斯克:可能在明年年底前出售特斯拉人形机器人 Optimus
- 苹果中国工厂回收机器人首次露面,规避了哪些电子回收弊端?
- 特斯拉或将在2025年底前销售人形机器人Optimus,机器人100ETF(159530)一度涨超1%
- 马斯克:“擎天柱”机器人仍在试验阶段 最早明年年底上市
- 马斯克称最快明年底前开卖人形机器人Optimus!网友:真能那么快吗?
- 外媒:马斯克透露,“擎天柱”机器人仍在试验阶段,最早明年年底上市
- 投资300亿!机器人产业爆发:几大趋势
- 人形机器人公司星动纪元携手临港集团,其“小星家族”获姚期智点赞
- 因会产生烧焦气味,日本世嘉玩具公司召回猫咪机器人
本月热点
- 人形机器人崛起:OpenAI、微软洽谈投资Figure AI,望募资5亿美元
- OpenAI 悄悄升级 ChatGPT:可在对话中调用不同的自定义聊天机器人 | 懂点AI
- Limbic开发AI心理咨询机器人,帮用户避免与人类交流可能引发的焦虑感
- 麒麟信安入股超能机器人 或尝试打开新业绩增长点?公司最新回应来了
- 灿瑞科技:已有产品应用于消费级机器人领域
- 英伟达官宣AI聊天机器人,本地RTX显卡运行,这是要挑战OpenAI?
- 人形机器人企业暂时得救了
- Meta联合研发家务机器人,能在零人力帮助下自主整理房间
- 端到端纯视觉!OpenAI押注的人形机器人献艺拜年了
- 波士顿动力 Atlas 机器人能力升级,可灵活搬运汽车零件
热门排行
-
斯坦福家政机器人火了但又翻车了!多数是真人操控编排的
阅读量:166287
-
斯坦福团队发布新机器人Mobile Aloha,人形机器人将迎来产业元年?
阅读量:164211
-
我的同事是 GPT-4 机器人,我们在 Slack 上一起工作
阅读量:160940
-
谷歌起草“机器人宪法”,以确保 AI 机器人不会伤害人类
阅读量:158823
-
人形机器人崛起:OpenAI、微软洽谈投资Figure AI,望募资5亿美元
阅读量:103097
-
大疆回应停售青少年教育产品:将资源聚焦在大学生高校机器人赛事
阅读量:67620
推荐内容
- CIBF2024
- 2024年香港礼品及赠品展览会
- 2024第26届山东国际水展
- 2024第19届潍坊春季茶业博览会暨紫砂展
- 2024CXBE厦门美妆供应链博览会
- 2024厦门日化产品技术供应链博览会-打造东南国际市场新坐标!
- 2024深圳国际文创新品展
- 2024第10届深圳国际IP授权产业博览会(CIPE)
- 2024晋冀鲁豫国际门窗幕墙展览会
- 2024中国昆山第二十四届国际机床及智能装备展览会
- 2024长春第十八届连锁加盟创业项目展览会暨2024 东北长春餐博会暨首届预制菜展览会
- 2024第二十六届山东国际供热供暖、暖炉及空调技术与设备展览会(JINNOC国际供热展)
- 2024第七届中国(昆明)南亚社会公共安全科技博览会
- 2024第三十二届中国(深圳)国际礼品及家居用品展览会(深圳礼品展)