智能蚂蚁解决旅行商问题

时间:2017-08-05 06:06:14166网络整理admin

作者:CHARLES ARTHUR为了找到欧洲50个选定城市的最短往返时间,数学家通常会招募大型计算机,复杂程序并留出足够的时间然而,英国电信的研究人员在创纪录的时间内找到了解决方案,其中包括一个工作站和一组“软件蚂蚁” - 几百行的自治程序,它们可以通过处理自己的简单问题来解决极其困难的问题过去一年开发这些项目的英国电信表示,该方法可以应用于许多问题,需要通过一系列复杂的决策来实现资源的最佳利用例子包括搜索许多数据库的信息,在微芯片上设计电路,在多次攻击下建议战斗机飞行员,或派出电话工程师来修复故障蚂蚁还将帮助制作旨在探索信息高速公路的软件“代理”英国电信核心技术研究负责人Peter Cochrane表示,随着从高速公路可以访问的信息量每三年增加一倍,该系统将具有巨大的价值,因为它将使人们能够更快地找到信息找到点之间最短距离的任务被称为旅行商问题可能的解决方案数量有所增加:4个点有24个可行路线,但30个有1065个2.65倍之前世界上最好的解决方案是3000点,这使得Cray超级计算机需要18个月才能完成英国电信的方法在44小时内解决了工作站上涉及30 000点的问题,准确率在4%以内英国电信针对50个城市问题的解决方案就像是在欧洲地图的计算机表示上播放的大型计算机游戏每个蚂蚁在地图上被分配一个位置,从那时起必须遵守简单的规则例如,蚂蚁不能离他们最近的邻居偏离一定距离:它们就好像它们都被串在长长的绳子上如果一只蚂蚁找到了一个可以繁殖的城市,那就制作一份自己的副本距离城市越近,对城市的吸引力越强然而,如果一只蚂蚁花了太长时间远离城市,它就会死亡然后计算机在死者的最近邻居之间的某个其他点生成一个新的为了解决这个问题,计算机会生成50个以循环方式连接的蚂蚁,并根据其简单的指示将它们放松以搜索城市最终他们找到了城市,为此他们得到奖励和生存,或者他们死亡进化完成其余部分设计这种方法的科学家,在伊普斯维奇附近的Martlesham Heath的BT系统研究部门的Shara Amin和Jose-Luis Fernandez认为,通过使蚂蚁更加自给自足,他们仍可以快10倍的速度达到解决方案目前,