- IT is banking -
|
关于Google的问题的问题的问题 - [Google IT ]
熟悉我的人都知道我喜欢Google，而且总是不遗余力地向别人推荐它的服务和产品。我很多朋友已经在我的影响下都喜欢上了Google，不过在另一些人眼中我像个推销员，他们带着诧异的目光望着我：“Google给你多少钱了？”我还真希望有朝一日我能从Google收点工资，那是多少人的梦想啊……:-)
新的故事，旧的回忆 - [Study University ]
终于考完试，一天都没有休息，学校软件工厂的培训就开始了。现在每天上六个小时课，放假比上课还忙。 一年过后作点总结总是对的，不过要保持一种正确的心态去回顾过去不是一件容易的事。06年发生了太多的事，多到回忆都成为了压力，所以下半年以来一直都只敢向前看，就像走钢丝的人…… 重新向前看，学校软件工厂的培训内容一天比一天艰深了，在空气不流通的实验室进行高密度的填鸭式教学效果实在不怎么样。不过因为有一点点基础，我面对的压力还不算很大。05的师弟们似乎就跟得比较辛苦了，想想如果换作一年前的我也许状况更糟，这更让我庆幸自己一年来做的事都没白费。人总是要进步的。
Codin' into 2007 - [IT Study University ]
06年的回顾还是等学期结束再写吧。
每年一月都是考试月，这次还是作业月，课程设计完成了两个，还剩数据库应用做了一半。另外新加入队列的有操作系统四个实验报告（吃苹果、生产者消费者、虚拟内存、快速文件系统），MFC的几个小作业和一个自由的大作业，选修课“科学哲学”的论文，都是要花时间做的东西，都要在考试期间完成。于是最近经常挂在嘴边的一句话是：“不要急，慢慢来，一个一个做……”
今天凌晨，在学校写着程序进入新的一年，很牵强，也很形式，不过心里舒服。没有喧哗，没有祝福，只有远处的焰火灿烂。时间本来是没有感情的，节日是人赋予时间的意义。 2007年也许会成为影响我以后人生的重要一年，学习、实习、出国的路都进入了Critical Section。在06的后半年，觉得自己开始进入状态了，希望能在今年更进一步，一年后回头看这些文字，不会觉得对不起自己。自我提升的路总是艰难的，尤其是当你起点比别人低，所以坚持不懈是最重要的精神，也是最难达到的。还有，一切进步都要求不断挑战自己的极限。自己折磨自己，总是不够残酷的。
2007年，继续Codin’ on IT。 IT可以表示一种技术、一个产业，是现实世界在电子世界的投影。这里有创造、有挑战、有荣耀、有落寞、还有利益和政治。中国的IT在努力挣扎着发展，最终是要和世界同步的。瀛海威远去了，但它的广告语仍然鲜活：“中国人离信息高速公路还有多远——向北1500米”。这句话标志了一个时代的开始，多少人曾为之振奋，多少人仍受其鼓舞…… IT也是中山大学软件学院04级一个普通的专业，这个班曾经自由散漫，孤立无援，以至于受人冷落，被人轻视。然而今天，一股新的力量正在他们中间涌动，他们正在厉兵秣马、重整旗鼓，开始在不同的领域中提高自己、发挥自己。 在这班同学中，一些人物注定诞生。 用自适应的遗传算法解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... [转载] 2006年中文博客封神榜：中文108 Blogger - [Listing ]
老文了，似乎是一个大网站评出来的，涵盖各路英雄草根，看看都能长见识~ 双核 要做课程设计了 - [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，每个作业都和不同的人一组，我自己都有点乱。而且因为对软件工程的思想和过程还没有了解，我们的团队里面是只有分工，没有合作。不过反正大家都还是学生，也是边做边学吧。希望能做出不错的成绩: ) 杂烩Listing - [Listing Java Google NewEco ]
最近在做Java的课程设计，一个简单的电影院售票系统，想试试db4o (DataBase for Objects) ，正在啃它的API，还好找到一篇学习者的文章，值得推荐。顺便列一下最近看到的一些好文： Object DataBase －－DB4O之旅 -linugb118- （迟点我也写一下） 东拉西扯：反商业作为一种商业 -keso- （keso的文章，不得不看） 东拉西扯：Google应该收购什么 -keso- （对Google提出好的建议，有机会加入Google！） 企业家的google排名 -吴晓波- （Google一下自己……唉~还是算了） 长尾理论的误区 -Owen- （《长尾理论》中文版的第一批读者） 用户为什么创建百度贴吧（上），（下） -麦田- （麦田最近忙于搞蚂蚁社区，也在研究社区） 遗传算法算子设计与参数调整 - [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附近，我们都看作是收敛），这样计算效率就比较低了。于是，如何提高算法效率（以收敛性为目标），是我们的下一步工作。 《长尾理论》到手！并附两个长尾文章链接 - [IT NewEco ]
盼星星盼月亮，卓越网终于送来了这本《长尾理论(The Long Tail)》 到底什么是长尾呢？可以表示为这个图，产品流行度曲线中右边的部分：
这些产品需求量都很少，但是由于数量巨大，产生的利润也将是巨大的。用简单的微积分思想可以知道，图中橙色的面积占了总面积的很大一部分。当头部的争夺越来越激烈，长尾所带来的效益就越来越明显。这个道理在扩张成本非常低的互联网商业模式下更加适用！ 具体的内容可以参考以下文章（版权属于原作者）： 遗传算法简介 - [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共5页 第一页 上一页 1 2 3 4 5 下一页 最后一页 |
about
RSS Feed  or  Gmail me  search
saying
tags
latest
comments
archive
links
reading
duron2g的豆瓣 user login
counter
Total: |
