最近心血来潮,重新拾起大学毕业设计时研究过的遗传算法。去年做毕业设计时还觉得遗传算法是一种多么神秘的算法,但是今天看来,遗传算法也就和冒泡排序算法差不多,都是通用的算法,只不过遗传算法实现起来稍微复杂一点而已。
我曾经被遗传算法的名字所疑惑,还以为遗传算法会改变程序的形态,使得程序就好像生物一样进化,过了几天去看程序已经变得连编写程序的人都认不出来了,汗!大二时的幼稚想法。
遗传算法其实是一种求函数极值的随机搜索算法,但它又不是毫无规则地随机搜索,而是基于一种假设:假设函数值的分布是有一定的连续性的,换句话说函数的极值出现在一个较优值附近的概率要大于出现在一个较差值附近的概率。基于这个假设,遗传算法总是以较大概率保留较优值所代表的搜索方向,而以较低概率保留较差值所代表的搜索方向。这并不是说不去搜索较差值的附近区域,只是搜索的概率较低而已。这个思想与模拟退火算法相似,对于能量较高的系统状态,程序仍然以一定的概率接受,只不过这个概率小于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次
导读:研学论坛 最近心血来潮,重新拾起大学毕业设计时研究过的遗传算法。去年做毕业设计时还觉得遗传算法是一种多么神秘的算法,但是今天看来,遗传算法也就和冒泡排...
相关内容
- 全球工业机器人龙头积极布局AI 机构看好AI赋能机器人趋势
- AI大模型火爆,汽车“机器人化”成趋势,极越人车家生态正式上车
- 机器人行业调研-投资篇
- 全球首个OpenAI机器人诞生,可与人自主互动丨科技周览
- 特斯拉正开发“私有5G”基站,为电动汽车及人形机器人提供支持
- 手指灵活又精细:Sanctuary AI发布自主完成人类任务机器人
- 工业机器人龙头接连收购AI企业:ABB将人工智能嵌入全线业务
- OpenAI大模型加持机器人问世 神经网络受关注
- 重载AGV助攻年营收过亿 朗誉机器人:2024年重在出海 2026年计划上市
- AI大模型时代,如何用RAG技术重塑传统智能客服问答机器人?
- Figure首发OpenAI机器人,人形机器人产业进入快速发展期,科技巨头纷纷加速布局
- 估值26亿美元!人形机器人公司获英伟达、微软、亚马逊投资 与OpenAI合作
- 机器人行业的调研(一)
- 小i机器人创始人袁辉谈中美AI领域差距
- 英伟达发布新的机器人制造平台,添加生成式AI功能
- 基于生成式 AI 技术,汤姆猫正在研发一款语音交互陪伴机器人
- 炸裂更新!这个最像人类的机器人又进化了,还能模仿马斯克
- 历史与AI的距离:聊天机器人在历史学科科研中的应用
- 人形机器人公司Figure获OpenAI等巨头投资 估值飙升至26亿美元
- 全球首个OpenAI机器人诞生!Figure 01碾压马斯克擎天柱,10亿机器人大军正式启动
AiLab云推荐
最新资讯
本月热点
- 斯坦福家政机器人火了但又翻车了!多数是真人操控编排的
- 斯坦福团队发布新机器人Mobile Aloha,人形机器人将迎来产业元年?
- 我的同事是 GPT-4 机器人,我们在 Slack 上一起工作
- 谷歌起草“机器人宪法”,以确保 AI 机器人不会伤害人类
- 长江电力申请机器人巡检方法及系统专利,提高效率的同时也避免过多机器人参与到任务中造成碰撞风险
- 均普智能:公司会持续对人形机器人领域进行研发投入,当前没有交付丝杠终端产品
- 特斯拉“擎天柱”机器人视频涉嫌造假 马斯克“承认”
- 国际最新研发出人工智能机器人平台 改造蛋白质速度超过人类
- 国盛证券:未来大模型将会赋予机器人更强的能力
- 人形机器人“进厂”颠覆汽车制造?
热门排行
-
斯坦福家政机器人火了但又翻车了!多数是真人操控编排的
阅读量:152042
-
斯坦福团队发布新机器人Mobile Aloha,人形机器人将迎来产业元年?
阅读量:149895
-
我的同事是 GPT-4 机器人,我们在 Slack 上一起工作
阅读量:146367
-
谷歌起草“机器人宪法”,以确保 AI 机器人不会伤害人类
阅读量:142408
-
人形机器人崛起:OpenAI、微软洽谈投资Figure AI,望募资5亿美元
阅读量:86916
-
大疆回应停售青少年教育产品:将资源聚焦在大学生高校机器人赛事
阅读量:52234
推荐内容
- 2024第25届中国兰州国际医疗器械博览会
- 2024第九届中国西安丝绸之路国际旅游博览会
- 2024第27届重庆都市文化旅游节暨城际旅游交易会
- 2024年第25届广西广告展览会
- 2024宁夏(银川)国际广告节
- 2024中国(青岛)国际户外用品暨房车露营装备博览会、2024中国(青岛)国际体育用品、健身器材暨泳池设施装备博览会、第五届新电商产业博览会
- 2024第二十三届中国西部国际广告节
- IBS 2024第十二届生物质能源与有机固废资源化利用高峰论坛
- 2024第二届中国(西安)国际消防技术装备展览会
- 2024长三角国际环保产业展览会
- FEC2024第17届广州国际服装供应链博览会
- 2024第60届沈阳医疗器械展3月28日盛大召开!!!
- 2024第二届成渝经济圈表面工程博览会
- 2024南京充电桩展览会
- 2024第十四届中国(郑州)塑料产业博览会
- 2024HOTELEX第32届上海国际酒店及餐饮业博览会 HOTELEX上海展
- 海名·2024上海火锅食材及用品展览会
- 2024第29届中国(北京)国际美博会
- 2024宁波国际文具展
- 第二十届中国(重庆)国际润滑油、脂、添加剂、养护用品及技术设备展览会
- 2024上海国际酒店工程设计与用品博览会