- IT is banking -
|
用自适应的遗传算法解TSP问题探索 - [Study GeneticAlgorithms ]
问题描述： 在用遗传算法求解问题时，参数的调整对优化过程有很大的影响： 1. Px: 一个个体与其他个体进行交叉操作的概率；Px提高，种群内部的混合更加充分，有趋同倾向。 2. Pm: 一个个体的某个基因发生变异的概率；Pm提高，引入更多新基因，有随机搜索的倾向。 那么应该怎么样调整这两个参数才能保证算法搜索的广度和深度，从而提高收敛速度呢？ 问题分析： 我们的先从遗传算法的基本思想开始考虑： 1. 选择算子：择优录用，好的个体更有可能被选中，再进行以下两步； 2. 交叉算子：种群内部的配对交叉，以求搭配出最佳的个体，是对内涵的“基因库”进行深度的搜索； 3. 变异算子：为种群引进新的基因，是对外延的“基因库”进行广度的搜索； 针对TSP问题的进一步分析： 由于TSP问题的特殊性，交叉算子不能很好地发挥“搭配”作用，譬如，经过顺序交叉的子代更像是其一个父亲变异的结果。于是，为了实现交叉算子本身的“职责”，我们在算法中加入一种“全局精英”策略：在普通的简单精英策略中，上一代最好的个体被保留，而我们采用的策略是，如果交叉子代比父代优秀，它才能进入下一代。这样，交叉算子对内搜索求优的效果发挥出来了，趋同的效果也更明显了。然而，由于算子对概率参数的敏感度大有增加，我们更容易通过参数调整来对其进行控制了。 实验证实，改进后的交叉算子能够坚守其“职责”，收敛过程对Px更敏感了。典型情形是：当Px增大到0.7以上时，Pm取一个普通值0.01，种群最优解在1000代左右迅速收敛到一个较低的水平（局部最优解），并在之后不再降低。原因是基因同化，不再产生更优秀的解。为了监测这种情况，我们引入基因多样性的概念。实际中我们用基因相似性来实现：Similarity = best fitness / average fitness
大致实验结果如图（popsize = 100, maxgen =10000）: 可以看出，如我们所料，Px和Pm对基因相似程度的作用恰好相反。 参数自适应模型 通过实验，我们对参数的自适应调整有了初步的方向： 在收敛前期，基因随机性大，相似度低，应该用较大的Px和较小的Pm，让算法迅速找到一些比较优秀的解，减少搜索的随机性； 在收敛后期，基因趋同，相似度高，应该用较小的Px和较大的Pm，让算法引入更多新基因，防止落入局部最优解； 总而言之，就是希望把基因相似度控制在一个范围之内。到此，最基本的参数自适应模型就出现了:
Click "Read more" to go on... 要做课程设计了 - [Java Study GeneticAlgorithms University ]
转眼又到期末了，开始投入做各门课的课程设计。题目都是自己选的，而且大部分都是Teamwork，问题本来不大，只是好几个Project堆到一起做，再加上课程本身的复习，问题就比较大了。今天才在Google Calendar上安排了一下时间，发现每个Project都大概只能腾出一个星期时间来做，时间比较紧所以首先整理思路是必须的，按截止日期来排就是： Java（12.15） ——电影院售票软件：目标就是模仿现在电影院所使用的可视化售票软件，最重要的部分是可以让顾客指定座位，主界面的中间部分是一个座位图，空的座位是绿色，选择以后变红色，然后把票打印出来。后台数据库用db4o实现，之前已经提到过。 因为之前自学了Java，这个学期一直没有很重视这门课，听得懂也就算了。遇到的问题是界面编程部分接触比较少，现在才开始尝试，选座位那部分还没有有效的实现。另外就是发现db4o的确是个好东西，面向对象的编程方法可以直接用于数据库，比用SQL简单快捷不少（就我们这点应用而言）。 计算机网络实验（12.23）——遗传算法用于路由路径优化的简单实验：关于遗传算法的研究终于在专业课中找到用处了。这个课题早就被研究透了，我只是想做一个简单的实现，遗传算法的主要程序我们已经有了，剩下的就是网络部分的数据提供和一些针对性的改动，将它变成一个类似于“网络TSP问题”的程序。对于网络数据的提供（测试链路的延迟、负载等情况）我还没什么概念，如果只是算延迟的话，用一些Socket编程应该能实现。 大部分同学都在做网络即时通信(IM)的小程序。因为MFC老师的课件和参考书都有很详细的介绍。我想做点不同的东西应该会不错，也利用自己之前做的工作吧。万一做不出什么东西，再按参考书用Java写个小小的IM也不难。反正这个是实验课，不用出什么有用的成果，自己做了东西，老师接受就行了。 数据库原理与应用（12.30）——CBA比赛数据管理系统：这个是最大的作业，要建立数据库，和写一个与数据库交互的软件，提供数据更新和查询等功能。因为涉及到SQL Sever，界面编程，还有中间环节三个部分，有点像Web应用软件的三层结构了。顺着这个思路，我们准备分模块分工协作，界面和中间部分都用Java写，最后嵌入到（本地的）网页中。我负责做中间部分，就是写一些类和函数，接受界面响应函数的调用，然后往数据库发命令，再把反馈的数据传回界面，说得夸张一点就叫“中间件”了。要自学JDBC（Java DataBase Connectivity）翻开《Thinking in Java》，其中有一章居然叫做"Why JDBC seems so complex? "……汗~~~ 智能优化方法及应用（无限期）——遗传算法参数自适应调整：一直在做的研究，越深入遇到的问题就越多，现在是有点成果，也有点停滞不前。课程成绩应该不成问题（既然老师说上了课就能有成绩），继续研究的动力就是我们之前做的那么多工作，还有对这个课题的兴趣了。希望能继续得到老师的指点，新的进展以后再谈。
以上那么多，归结起来就是两个内容：Java和遗传算法，两个都是自己感兴趣的科目，做起来比较有感觉。至于Teamwork，每个作业都和不同的人一组，我自己都有点乱。而且因为对软件工程的思想和过程还没有了解，我们的团队里面是只有分工，没有合作。不过反正大家都还是学生，也是边做边学吧。希望能做出不错的成绩: ) 遗传算法算子设计与参数调整 - [Study GeneticAlgorithms ]
之前在简介中也说过，由于遗传算法的模块化设计，使其很容易编程实现。编程之前首先要确定算子的设计，也就是具体怎么选择、怎么交叉、怎么变异等等。我们针对TSP问题设计的算法设计如下：
1、先确定几个概念： 种群：包含进行一次遗传算法操作的所有个体。计算过程中个体不断更新，种群大小popsize一般不变，它由问题规模决定。越复杂的问题需要越大的搜索空间； 个体（染色体）：问题的一个可能解，由一组基因组成。TSP问题中的个体就是一个遍历序列，每个城市为一个基因； 适应度：对个体的评价函数。TSP问题中，适应度函数为该路径的总路程（越小越好）。
2、各算子设计： 选择算子——轮盘赌法：对每个个体，求出其适应度在总适应度中占的比例，将总适应度划分出对应的区间。每次选择时生成一个随机数，这个数所处区间对应的个体被选中。就像轮盘游戏，将轮盘分成几部分，随机旋转，看最后指针指哪一块。 交叉算子——顺序交叉：采用Davis等提出顺序交叉、双亲双子遗传的算法。在N位长的序列中随机选择两个交叉点A、B（0<A<b<N 变异算子——按位交换：对于个体的一个基因，如发生变异，则随机与同一个体中另外一个基因交换位置，一个基因发生变异的概率为Pm。
算法流程如图：
3、实验&总结 算子设计好以后，编程不会出现实质性的困难。下一步就是做实验，调整参数Px和Pm。我们实验用的题目是中国大陆31个城市（包括30个省会和桂林市）的TSP问题，数据来源是全国公路里程表。其实具体题目并不重要，我们只是想找到足够的数据量来做实验。31个城市，遍历序列就有31！种，大约是8.2*10^33，如果用随机搜索，要算好一阵的。 我们将程序改写，尝试不同的Px，Pm组合，每个组合运行三十次。我用我自己的电脑来做实验，三轮实验最长的第一轮跑了30个小时，超频后的Athlon64 CPU全程100%运行，实验完全证明了机器的稳定性J 也产生了超过7GB的数据记录文件，数据统计成了更大的问题。在Matlab和Excel的帮助下，我们写出了饱含血汗的报告。初步结论是，使用较低的Px和Pm值，由于随机性的减少，算法的择优功能发挥作用，而且种群人口popsize和遗传代数maxgen越大，越有可能得到最优解。经多次实验得到我们的问题的最优解为19912公里，当然它出现的概率很小，几万次实验中只出现过十来次。 这只是初步的结论，使用很小的Px和Pm会导致算法的搜索能力降低，我们用100、200、400的popsize，一般要起码两万代以后才能收敛（只要结果在20000附近，我们都看作是收敛），这样计算效率就比较低了。于是，如何提高算法效率（以收敛性为目标），是我们的下一步工作。 遗传算法简介 - [GeneticAlgorithms Study ]
这个学期的公选课不小心选到一门叫“智能优化方法与应用”，老师是海外回来的博士，感觉很像TOEFL听力中经常出现的那种professsor。只是他基本不怎么讲课，只是一开始做了个简介，再教我们怎么上IEEE找资料（中大电子图书馆有专门的出口上IEEE，不知道一年多少钱），然后就让我们自己做一份30页综述，吓跑了一半人；然后就让我们自己写程序做实验，让很多文科的同学根本听不懂做不了，总之最后剩下十几人来上课，老师上课都特别郁闷……其中两个小组一直坚持在做：我和我班一牛人的一组、还有以一个ACM校队选手为核心的另一组。 还是入正题：遗传算法（Genetic Algorithms，GA)是用计算机仿真生物遗传过程的优化算法。 说得很玄其实思想很简单：根据达尔文进化论，生物的进化就是物竞天择，优胜劣态。一个生物的种群，自身演变演变的根源在于遗传和变异，演变的效果要接受大自然的选择，能适应环境的就保留下来，然后最终发展出现今的生物多样性。用计算机去模拟这个过程，解一个问题时（譬如一个函数z=3x-2y的最大值）： 1、生成一些可能的解 (x,y)（可能是很随机的）——初始化； 2、用一个规则（z的大小）对各个解进行评价——适应度； 3、从中选出一些比较好的解，抛弃一些差的——选择； 4、将保留的解相互搭配一下（交换x或交换y），看能不能找到更好的解——交叉； 5、引入一些新的解（x,y），或者将已有的某些解随机修改一下，为解集加入“新血”——变异； 6、不断重复以上过程，最后就很有可能找到最优的解。 生物进化的过程是缓慢的，而用计算机来模拟以上步骤则可以非常快，用程序实现以上步骤不会很困难。而且由于GA各步骤之间的独立性，各个算子可以单独设计和优化，不需要对程序整体进行修改对于解某些困难的问题，无论是离散还是连续问题，遗传算法的优化效果是很好的。一个典型的应用是旅行商问题（Traveling Salesman Problem，TSP）：一个商人从一个城市出发要去很多个城市而不想走回头路，求一条最短的遍历路径。用数学语言来描述就是，给出一幅N个节点的无向带权完全图，求最短的哈密顿回路。用一般的方法解这个问题是非常困难的，尤其是当节点数量很大的时候，而GA此时体现出很大的优势。 我们组做的研究专注于遗传算法在TSP问题的应用，目标是寻求更优秀的算子设计方案和调整程序参数，需要大量比较细的实验，然后写实验报告，具体做的工作以后再谈。ACM高手那组就研究其他问题，现在是关于网络的组播分析，还好他们的报告我都听得懂。我的观点是，牛人做大器的设计，凡人先做点小器的调试，学到东西就好。 附上我之前拼凑的遗传算法综述，版权属于引用作者。 Page共1页 1 |
about
RSS Feed  or  Gmail me  search
saying
tags
latest
comments
archive
links
reading
duron2g的豆瓣 user login
counter
Total: |
