健之的头脑风暴
注册日期:
2003-6-21
上次登录:
邮件地址:
liukzg@gmail.com
兴趣领域:
人工智能,计算机科学,
  健之的头脑风暴
健之的更多标签
1
2003-10-12 18:36:53  人工生命 
下面是我最近刚写的一篇关于蚁群的文章,用Word2000写的,先贴到这里,大家提提意见。但可能公式等不能正确显示,没办法。 0. 引言 蚁群算法是由意大利学者Dorigo M等首先提出的一种模拟蚂蚁行为进行优化的新的启发式优化算法。同其它进化算法一样,它具有群体智能算法的许多优越性,已经成功地应用于TSP问题[1],指派问题[2],Job-shop问题[3]。目前,在蚁群算法的研究方面已取得了一些研究成果,但如何将蚁群算法应用于连续空间,仍是蚁群算法研究热点和没有完全解决的问题。本文通过对关于TSP问题的基本蚁群算法的讨论,初步分析了构造一个通用的,应用于连续空间的蚁群算法的几个关键问题,并进一步提出了一个通用连续空间蚁群算法的基本框架,对该方面问题的深入研究有积极意义。 1. 基本蚁群算法 在自然界中,单个的蚂蚁个体行为极为简单,但由多个蚂蚁所组成的群体却成功地在搜寻食物等方面表现出复杂的行为。通过研究发现,蚂蚁个体之间通过一种称为外激素(pheromone)的物质进行信息传递,蚂蚁在移动过程中通过感知遗留在路上的该种物质来指导自己的运动方向,并在自己经过的路径上留下该类物质。这样,大量蚂蚁所组成的群体便构成了一种信息正反馈,从而成功地实现了食物搜索,最短路径选择等行为。蚁群算法正是通过模拟蚂蚁的这种行为来达到目的。我们以求解n城市的TSP问题为背景来说明基本的蚁群算法。 设m为蚁群中蚂蚁的数量,n为旅行商要走过的城市数,dij(i,j=1,2,3,…,n)为城市i到j的距离,bi(t)为t时刻位于城市i的蚂蚁个数,则 。又设τij(t)为t时刻在ij连线上残留的信息量,而初始时刻各条路径上的信息量相等,即τij(1)=C。如果在时间间隔(t,t+1)中m个蚂蚁都从当前城市选择下一个城市,则经过n个时间间隔,所有蚂蚁都走完n个城市,构成一轮循环,此时,按如下方法修改各条路径上的残留信息 式中,ρ为信息残留系数,ρ-1表征了从时刻t到t+n路径ij上残留信息的挥发程度。 为本次循环留在路径ij上的信息量。 。根据Dorigo的Ant-Circle System模型,有 式中,Q为常量,Lk为第k只蚂蚁在本次循环中所走路径的长度。 定义 为t时刻蚂蚁k(k=1,2,3,…,n)由城市i到城市j的选择概率,并定义tabuk为一动态增长的列表,其中记录了蚂蚁k所经过的所有城市号。取 式中,allowed=(1,2,…,n)-tabuk为在城市i蚂蚁k允许选择的城市, 为t时刻蚂蚁由城市i选择城市j的某种启发信息,在TSP问题中,通常取 ,而α和β则分别为残留信息和启发信息的相对重要程度系数。关于TSP问题的基本蚁群算法可以由如下的伪代码描述 (1)初始化 Set t:=0 (t为时间计数器) Set NC:=0 (NC为循环次数计数器) 对每条边ij,设 将m个蚂蚁放置到n个节点 (2)Set s:=1 (s为tabu列表索引) For k:=1 to m, do 将第k个蚂蚁的开始城市置于tabu列表 (3)重复下列操作至tabu列表满 Set s:=s+1 For k:=1 to m, do 根据 移动蚂蚁k到城市j 将城市j加入tabuk(s)列表 (4)For k:=1 to m do 清空tabuk(n)到tabuk(1) 计算第k个蚂蚁路径长度Lk 修改找到的最短路径 For 每条边(i,j) For k:=1 to m do 计算 (5)对每条边(i,j),计算 Set t:=t+n Set NC:=NC+1 对每条边(i,j),置 (6)若没达到收敛条件(NC
2003-10-13 11:46:58
   关于连续问题部分我觉得非常好,尤其是那个链表的构件,其实“蚁迹寻踪”里面的信息素就是这样处理的。不过问题是,在连续空间中,如果找到蚂蚁感兴趣的范围和信息素的范围的交集是不是要消耗大量的计时呢?你有没有进行一个实际函数的优化试验? >健之():下面是我最近刚写的一篇关于蚁群的文章,用Word2000写的,先贴到这里,大家提提意见。但可能公式等不能正确显示,没办法。 >健之(): >健之():0. 引言 >健之():蚁群算法是由意大利学者Dorigo M等首先提出的一种...
2003-10-13 13:12:19
   因为这是一篇约稿,并且时间到了,所以我只来得及把思考的初步结果写出来,还没有来得及实现它。不过我准备尽快实现它,实验函数准备找一些常见的连续优化问题,也准备实验一下TSP问题的连续版本。其实蚂蚁的路径选择本质上是连续问题,简单到从A点到B点,其路径选择也是无限条的连续问题,当然,最优结果是明确的:连接A、B两点的直线,如果能实现这样的蚂蚁,才能说是真正意义上的蚂蚁,也是连续性版本的蚂蚁。 对于蚂蚁可视范围与信息残留范围交叉后的选择概率函数计算问题,应该是可视函数与残留函数交集部分的积分,这个积分计算与两个函数的类型密切相关,而优化性能应该也与函数形态有直接关系,这也是研究的重要内容,定性的考虑是确定的,定量的考虑可以根据具体问题而有所区别,所以,目前我认为暂时留为虚接口是可以的,定量实验后可能推荐一些函数。
2003-10-13 17:55:29
   关于连续优化问题,我曾经在一篇博士论文上看过,你可以参考一下 > 健之():因为这是一篇约稿,并且时间到了,所以我只来得及把思考的初步结果写出来,还没有来得及实现它。不过我准备尽快实现它,实验函数准备找一些常见的连续优化问题,也准备实验一下TSP问题的连续版本。其实蚂蚁的路径...
2003-10-15 11:57:14
   谁的论文,哪里有?
2003-10-17 10:28:31
   马良 <<全局优化的一种新方法>>------系统工程与电子技术 vol.22; no.9 ; 2000年 没有仔细看过,似乎和基本蚁群算法表达差不多,呵呵,引进了领域搜索的概念. 你可以去看看. >健之():谁的论文,哪里有?...
2004-1-31 13:54:19
   在进化计算中,我最先感兴趣的是遗传算法,然后是微粒群算法,目前在考虑一些蚁群算法的东西。这几样东西我都做了自己的类库来用。不过根据我自己程序的实验结果来看,对于难优化的多峰值函数,遗传算法的全局寻优效果并不是最好的。微粒群算法似乎更有优越性一些。蚁群算法主要用于TSP一类的离散问题,连续问题值得考虑。前面给出的是一个方案,这段时间正在实现,从初步的结果来看,效果还不错,似乎能够避免遗传算法的会聚问题,或者这样说吧,从模拟的二维图看,蚁群容易呈现一种在定义域区域中分群搜索的情况,而不会很快收缩到一个局部的区域中,这是他的优点。我上传了一个运行样例程序,诸位可以参考参考。 >hisky(苍竹琴声):看了一下这篇paper,发现他的思想没有突破多少禁忌搜索的圈子。 >hisky(苍竹琴声):禁忌搜索的效率和遗传算法差不多,所以他给出的好效率我有点怀疑。但是没有自己实验,所以姑妄言之。 >hisky(苍竹琴声):如果真的有什么好的方法比遗传算法在...
2004-2-2 16:00:42
   你的样例程序上传到哪里了? >健之():在进化计算中,我最先感兴趣的是遗传算法,然后是微粒群算法,目前在考虑一些蚁群算法的东西。这几样东西我都做了自己的类库来用。不过根据我自己程序的实验结果来看,对于难优化的多峰值函数,遗传算法的全局寻优效...
2004-2-3 8:12:54
   我还想修改一下,所以把它删了 >jake(sage):你的样例程序上传到哪里了? >jake(sage): >jake(sage): >jake(sage):>健之():在进化计算中,我最先感兴趣的是遗传算法,然后是微粒群算法,目前在考虑一些蚁群算法的东西。这几样东西我都做了自己的类库来用。不过根据我自己程序的实验结果...
2004-2-3 20:00:19
   晕啊,期待中~~~ 你那还有什么收集到的好东西也可以传上来,但不好意思,空间有限。省着用吧。 >健之(): >健之():我还想修改一下,所以把它删了 >健之(): >健之():>jake(sage):你的样例程序上传到哪里了? >健之():>jake(sage): >健之():>jake(sage): >健之():>jake(sage):>健之():在进化计算中,...
登录后才可以评论,马上登录
2012-2022 www.swarma.org, all rights reserved