用户:  密码: 记住我     找回密码 
| 文章 >> 编程通用 >> 算法

遗传和蚁群优化算法

日期 | 作者彼得Kohout | 浏览86 | 评分100 | 标签算法 评论
{A}{S0}简介
我最近成为在遗传算法和蚁群优化技术领域非常感兴趣。我下定决心写一个完整的程序,证明这两种技术。我特别想比较这两种方法的效率,在寻找解决旅行商问题(TSP)的面积。旅行商问题
巴克兰(2002年,第118页)简明扼要地总结了问题,由于城市的集合,旅行商必须确定,将使他访问每个城市,正是一次,然后回到他的出发点的最短路线??
他接着解释​​说,这是一个什么数学家称之为NP -完全问题的例子。随着越来越多的城市正在增加,所需的计算能力来解决问题成倍增加。的计算机上实现了一个算法,解决了五十个城市的TSP将需要在计算机电源的一千倍的增加,只是增加一个额外的十个城市。下表显示的问题:
显然,如果为这个问题找到一个解决办法是,需要采用一个quot;蛮力forcequot;方式变得不可能大量的城市和替代算法。背景算法的说明遗传算法
该算法包括以下基本步骤:{S2}初始化:染色体是随机生成的。在这一点上,这是非常重要的人口是多样的。否则,算法可能不会产生很好的解决方案。评价:每个染色体是额定染色体如何解决手头的问题。一个健身价值是分配给每个染色体。选择:优胜劣汰的染色体为传播到他们是如何适应基于下一代选定的。重组:个体染色体和染色体重组,修改,然后投入的人口。
我不打算讨论遗传算法的细节,因为这些是更好地解释其他地方,除了讨论用来产生有效的交叉运营商和轮盘赌选择的机制。每个染色体编码作为一种可能的巡演。例如,可能被编码为3,4,0,1,2的五个城市之旅。与TSP的一个困难是,一个简单的交叉将无法工作。考虑下面的情况交叉发生位置3。亲本11 2 3 4 5家长23 5 2 1 4 儿童11 2 3 1 4儿童23 5 2 4 5
这里发生的一个问题是,儿童1访问了两次,这是不允许的,儿童2没有访问所有城市1市1。必须使用一个污损编码,以确保只有有效的旅游生产。一个众所周知的也许是最简单的理解交叉算子是称为部分匹配交叉。巴克兰(2002年,第130-132页)解释这项技术如下:
一个过路的地区回升。
Parent 1: 12x34x5



Parent 2: 35x21x4

下面的映射是成立的。{C}
现在我们每个父基因循环和交换的地方找到一个基因的基因发生在上面的映射。
第一次迭代(3与2的映射):
Child 1: 13245



Child 2: 25314

第二次迭代(4与1映射):
Child 1: 43215



Child 2: 25341

最后划线以上的基因是不重复的有效排列。
轮盘赌选择的选择染色体的人口成正比,他们的健身方式,是从成员技术。巴克兰说明,假设总人口的健身得分是由代表饼图或轮盘赌。现在,你分配一个车轮的每个成员的人口片。切片的大小是成正比的,染色体健身得分:成员是钳工,更大的分一杯羹。现在,选择一个染色体,所有你所要做的的是旋转的车轮,折腾球,抢到球停在染色体??巴克兰(2002年,第100)蚂蚁算法
这个算法的灵感来自于观察真正的蚂蚁。独立,每个蚂蚁是盲目的,体弱多病,几乎微不足道。然而,能够相互合作,蚂蚁殖民地的演示复杂的行为。其中之一是能够找到食物来源或其他一些有趣的地标最接近的路线。这是放下特殊化学品称为quot; pheromones.quot的;,随着越来越多的蚂蚁使用一个特定的线索,它的信息素浓度的增加,从而吸引更多的蚂蚁。在我们的例子中,人工蚂蚁是随机放置在每个城市,并在每次迭代中,选择下一个城市去。这种选择是由下面的公式,虎视眈眈(1997年)中所述:
我啤酒花尚未被访问的概率之间的城市中选择一个城市j位于城市的每个蚂蚁:
{S3},其中:{S4}的概率,蚂蚁k在城市,我会去城市J.{五}是城市尚未被蚂蚁k在市一访问是信息素轨迹的相对重要性。 {七}是城市之间的距离的相对重要性。
因此,选择一个城市的概率是一个城市是如何关闭的功能和信息素已在线索存在多少。这是进一步的可能,以确定这些通过调整有较大} {中六的重量和{七}参数。一旦旅游已完成(即每个城市已被访问一次蚂蚁),信息素挥发的边缘计算。然后每只蚂蚁存款上完整的旅游信息素的一个数量,这是从下列公式(虎视眈眈1991)计算:
,其中:乘以P(RHO),这就是所谓的quot的边缘城市i和j之间的信息素浓度;蒸发constant.quot;此值可以为0和1之间。信息素的蒸发更迅速地为较低值。是信息素的一个边缘上的蚂蚁k存款的金额,由定义,这是这个蚂蚁创建旅游长度。直观地看,短期旅游,将导致更高水平的信息素的边缘沉积。快速使用手册
在应用程序的心脏在于两个用于解决旅行商问题的算法。每个算法是从主框架的工具栏选择带入一个观点。视图是一个窗口,这是呈现给用户。遗传算法的观点如下:{S2}
每个视图分为两个水平段。上半部分显示的图形视图中的每个算法的当前性能。 下半部分显示了对知道最好的解决方案指明了当前的解决方案的图形。在TSP的最示威,随机放置在城市。我选择循环方式分配的城市。这使得一个简单的方法来计算城市之间的最短路径,以及视觉评估算法从最佳的解决方案是如何远离。通过控制按钮控制模拟
每个按钮是不言自明。 "开始"按钮是用来启动应用程序和"停止"按钮是用来停止模拟。而步按钮是用来通过模拟步骤复位按钮复位模拟。文本信息显示以下信息:大纪元代表通过每个周期的仿真模拟运行时间。最佳到目前为止到目前为止是最短的游览。最好的代表对当前旅游的最佳解决方案。经过的时间内算法所花费的时间。这不包括花费的时间quot; drawingquot;屏幕的解决方案。进一步信息,请参见下面。
上述信息的图表:
蓝线是一个具有划时代的情节与算法迄今为止所发现的最短距离。绿线代表在最短的旅游(最优解)。当两线衔接,已经找到一个解决方案。设计与实现
我选择语言程序英寸编译的程序申请彗星将始终快于解释的程序。两种算法的计算相当昂贵,所​​以可视化的过程。潜在彗星更快,但选择这种语言的面向对象的好处都将丢失。其他可能使用的语言是德尔福,Visual Basic和C#的,但我不有足够的经验,在这些语言中的任何尝试这种规模的项目。我选择了使用Microsoft基础类(MFC)应用框架。使用这个的好处是:应用框架的应用程序是小型,快速在Visual C工具减少编码苦差事该框架是具有丰富的功能
的一个主要缺点是,它需要很长的时间来了解底层模型的复杂性。同时,一旦开发人员试图从向导生成的代码,这是很容易得到失去与调试的代码。该项目的开发和编译使用Visual Studio。NET学术版7.1.3088。垫巴克兰(2002)在他的著作quot工作;用于实现遗传算法的代码是基于人工智能技术为游戏Programming.quot;蚁群算法的代码是部分M的琼斯(2003年)的工作基础上在他的著作"人工智能应用Programming.quot;还使用了一些其他的代码源:是一类用于双缓冲。这是一种技术,在电脑动画中使用,以避免屏幕闪烁,这是一个重大问题,由于屏幕更新(粉刷)数次第二。这里所用的技术是创建一个脱屏绘制图像的缓冲区。最终的图像,然后复制到屏幕上。是一类用于字体操纵。是一类用于为图表。是用于计时。CSideBannerWnd是用来显示窗口的左侧面板。
起初,我认为,该文件将保存信息常见的两种算法,包括城市,城​​市的地位和最短的参观人数。然而,随着项目的进展,我意识到,每个算法不同,足以保证自己的数据结构。所需要的是一种方式之间进行切换不同的看法(从一个共同的祖先派生)。
有时候,一个文件的方式是被可视化的需求将显着改变。例如,在PowerPoint中,你可以看到在一个所见即所得的表单的幻灯片或查看在一个文本编辑窗口只有文字。在MFC的世界,人们可以发现一个令人惊讶的大量方案,实施这种行为,定义一个CView的后裔,它负责为所有可视化的变化。这条道路有几个缺点:大,难以管理类定义文件。减少的可重用性:你可以重用一个大CView的后裔或没有。 难以维持(如果你想修改或添加一个新的quot; lookquot文档?)。内存浪费:一些变量(对象),将存在于内存中,并不会成为使用.???( Lodos,1999年)
作者接着解释,这怎么可能,并给出了一个代码示例定义了不同的看法,以及如何在它们之间切换。
下面的序列图显示CACOView和CAntSystem类之间的基本交互。
下面的序列图显示CGAView和CGASystem类之间的基本交互。性能
我旁边打开了我的注意的ACO和算法中的某些参数如何影响性能的。
这里使用的参数是市编号:40,α:1,β1和Rho:0.6。这些结果表明,有可能写一个遗传算法的优化参数。这可能使一个有趣的项目,走下赛场的某处。结论
这既是一种有益的和艰巨的工程。我以前MFC编程的小知识,并认为这将是比较容易掌握。事实证明,我错了,我花了很长的时间和运行程序。尽管陡峭的学习曲线,我很高兴实际生产的工作方案,并沿关于遗传算法和蚁群优化算法的方式了解到了很多。我非常感谢所有的人谁促成了这个梦幻般的网站的。我发现在这个项目中非常有用的文章很多。保持良好的工作,伙计们。参考文献巴克兰,M.,2002年,为游戏开发人工智能技术,按总理,美利坚合众国。虎视眈眈,M.,放大器; Gambardella,L. M(1997)旅行商问题的蚁群。生物系统公司,43 ,73 - 81Jearakul,C,1999年2D和3D Watefall图表控件,[在线],可用:http:/www.codeguru.com.controls/Waterfall.shtml [访问2003年3月9日]琼斯,M.,2003年,AI应用程序编程,发布者:大卫Pallali。1999年,J Lodos更换一个文档视图应用程序,[在线]:http:/www.codeguru.com/doc_view/ReplacingView.shtml [访问2003年2月9日]Nordmeyer,J.,字体自动处理类,[在线],可用:http://www.codeproject.com/gdi/autofont.asp [访问28/10/2003]Prosise,J,1999年,Windows程序使用MFC,第二版,微软出版社,华盛顿雷德蒙规则,K 0.1999闪烁在MFC中自由绘图,[在线],可用:http:/www.codeproject.com/gdi/flickerfree.asp [访问24/9/2003]Wyant,D.,2002年,CPerfTimer定时器类,[在线]:http:/www.codeproject.com/datetime/perftimer.asp [访问24/9/2003]
关于作者:彼得Kohout


中国
我是一名编程爱好者,
谢谢orcode.com为我们提供一个学习和分享的平台。
有什么问题。可以就本内容回复,我看到时。会尽量回复的。
评论会员:pushkarcdacnoida11 时间:2011/11/30
亲爱的主席先生,
 60; "蚂蚁的Steine​​r问题的蚁群算法"我的大学项目。
请帮助我完成我的项目在"C语言"
评论会员:。napsterboyz 时间:2011/11/30
主席先生,ü可以给我在Delphi或VB程序的源代码???帮我主席先生,(发送:napster.boyz @ gmail.com)
评论会员:e_live 时间:2011/11/30
我要找的蜂群遗传算法的调度​​multiprocessor.does人存在帮我

关于
评论会员:supasasi 时间:2011/11/30
我需要帮助我的研究生项目我的项目是"寻找用蚂蚁算法的最佳途径"。但我只想在地图上找到的,我把自己的最佳路线。
但是,现在我不知道"如何开始?"我的教授说,让我首先创建的地图,但我不知道什么,我要去使用程序创建的地图?以及如何开始编写代码

请帮助我吗?
蓝月
评论会员:游客 时间:2011/11/30
sailish:|嗨,PLZ送我的源代码蚁群和局部搜索算法
engriham
评论会员:游客 时间:2011/11/30
我需要蚂蚁最佳的相量neasurement的单元(PMU)的位置殖民地代码如果任何一个可以帮助我,请把我的代码我的电子邮件是rhm_salem@yahoo.com谢谢
hgzel
评论会员:游客 时间:2011/11/30
。嗨你能帮助我蚁群的MATLAB代码?我在非常困难的情况下。我需要一个蚂蚁colony.I的帮助下做matlab代码。我会很高兴给你,如果你能帮助我..我期待着你头联系我hgzel@hotmail.com
hossein_64
评论会员:游客 时间:2011/11/30
您好我要为我的项目蚁群MATLAB代码请帮助我我的电子邮件:hossein_gcd@yahoo.com
会员7819842
评论会员:游客 时间:2011/11/30
胡胡感谢您的工作
wxl24life
评论会员:游客 时间:2011/11/30
前提是-任何两个城市A和B,可以有一个从A到B但在现实世界中TSP将是很多复杂的
流星zarei
评论会员:游客 时间:2011/11/30
嗨,我需要的彗星#的我在大学的最后项目蚁群算法的源代码和这将是对我如此的帮助,我将可以使欣赏如果你能帮助我imgsrc=http://www.orcode.com/upimg/2011_11_30_15_53_25_24.gif
saNdEep8099154​​242
评论会员:游客 时间:2011/11/30
主席先生,PLZ发送MATLAB代码蚂蚁聚类算法..........我的电子邮件是sandeeppalaparthi918@gmail.com...
余泥Ardita纱丽DEWI
评论会员:游客 时间:2011/11/30
嗨,我的最后一年,在那里我有下面的说明建立在Java界面应用程序的项目。我有搜索互联网的ACO算法在JAVA,但没有成功。可能有人请帮我出imgsrc=http://www.orcode.com/upimg/2011_11_30_15_53_25_24.gif我想至少在Java中,如简单的算法:蚂蚁系统(变体:蚂蚁循环),蚁群系统,以及其他一些你觉得像将伟大的一个例子(比较将通过我的创造应用程序)**最后一年项目简介:我要一个交互式应用程序,包括一个GUI。我的应用程序基本上是要解决的最短路径问题(SPP),使用的算法:蚁群优化(ACO)。蚁群算法的动画需要,而其解决一个给定的最高人民检察院测试的显示。此测试可随机生成的随机坐标:X城市,或者它可能是用户输入一个设置的号码或城市和手动把坐标(也许是通过一个下拉菜单?)。还应该创建与其他测试显示该算法的有效性,以及各种图形/图表。我有基本的了解,在编程和学习如何实现Swing和事件处理。我失去了我应该开始。我想知道,如果你可以列出我的事情(类,函数,进口),我应该使用(或哪个更有效,并希望更容易imgsrc=http://www.orcode.com/upimg/2011_11_30_15_53_25_24.gif,我将使用NetBeans设计的应用程序。在此先感谢。最好的问候,余泥Ardita
Shibhu2002
评论会员:游客 时间:2011/11/30
,如果有人知道如何实现区域蚁群的MANET路由算法请解释与实施细则,我净(CSHARP)谢谢
Donia苏尔曼
评论会员:游客 时间:2011/11/30
我要蚁群,SMATLABcode.please发送到我的邮箱:dddsss2004@yahoo.com我会用蚁群图像分割需要的任何代码或ducoment帮我请你Tanke
拉贾落第
评论会员:游客 时间:2011/11/30
您好先生...你可以plese帮我在解决蚁群聚类记录......我想知道如何找到质心和alpha值?这将有助于我完成我projecet..如果可能的话PLZ发送给我的邮件rajaladi@gmail.com
doityth777
评论会员:游客 时间:2011/11/30
您好,我尝试在我的对话框或SDI计划在VC2008中使用UNICODE的条件下方位的工作。我在我的程序包括chart.h。就像以下内容:codeprespanclass="code-preprocessor"#include/spanspanclass="code-preprocessor"spanclass="code-string""/spanspanclass="code-string"Chart.h"/span/spanspanclass="code-preprocessor"#include/spanspanclass="code-preprocessor"spanclass="code-string""/spanspanclass="code-string"MemDC.h"/span/spanspanclass="code-preprocessor"#include/spanspanclass="code-preprocessor"spanclass="code-string""/spanspanclass="code-string"Utils.h"/span/spanspanclass="code-comment"///spanspanclass="code-comment"CANN_TRAINDlgdialog/spanspanclass="code-keyword"class/spanCANN_TRAINDlg:spanclass="code-keyword"public/spanCDialog/pre/codecodeprespanclass="code-keyword"void/spanCANN_TRAINDlg::OnBnTrain_ANN(){ spanclass="code-comment"///spanspanclass="code-comment"TODO:Addyourcontrolnotificationhandlercodehere/span m_pChart->Create(WS_VISIBLE|WS_CHILD,m_rectCln,pwnd,spanclass="code-digit"12000/span);}/pre/code与包括所有上述所有代码,我调试它----它成功!但是当我运行程序,它破坏!显示PreCreateWindow工程anormally:
bijay mahato
评论会员:游客 时间:2011/11/30
我需要在蚁群optimiizationmatlab源代码获得您的青睐。我会感激,如果我通过邮件发送
naghikhani
评论会员:游客 时间:2011/11/30
我要蚁群,SMATLABcode.please发送到我的邮箱:mohammad.naghikhan@gmail.com感谢
bhuvanes
评论会员:游客 时间:2011/11/30
主席先生,我做沿茶匙在AOC的工程项目我想在AOC的代码沿茶匙imgsrc=http://www.orcode.com/upimg/2011_11_30_15_53_25_24.gifPLZ发送..这将有助于我imgsrc=http://www.orcode.com/upimg/2011_11_30_15_53_25_28.gif
elnaz65d
评论会员:游客 时间:2011/11/30
您好先生..我需要蚁群MATLAB为我的项目的源代码,对我非常有用,如果你对我来说发送,请给我的源代码。最佳的问候电子邮件:atikah.razi@yahoo.comP/S:人有蚁群MATLAB源代码,可以ü与我guyz分享吗?PLZ...
soheilasharifi
评论会员:游客 时间:2011/11/30
亲爱的主席先生,目前我有旅行商问题的MATLAB代码(TSP)但我不蚁群优化代码(ACO)你可以PLS给我的ACO代码。我不知道如何实现TSP内的MATLAB代码ACO的代码。TQ
 文章分类
 桌面
 网页开发
 移动开发
 数据库
 多媒体
 编程语言
 平台,框架和库
 编程通用
 图形/设计
 开发周期
 一般阅读
 第三方产品
 作者资源
 其他
快速解答标签
c x 6850
VC x 7405