科学网—标签 - 遗传算法

相关帖子	版块	作者	回复/查看	最后发表

热度 22 tangchangjie 2012-1-12 08:58

灯谜、外星殖民、愚公移山和进化计算 --- 趣味数据挖掘之九 (唐常杰）本文从《基因表达式编程》的课程 PPT 中取了一些素材，加以简化和趣味化，从猜谜出发，借用外星殖民的科幻，讨论了公式发现的进化算法，分析了其中的愚公移山思想，描述了进化计算的七个特征，为下篇博文做些概念的准备。 1 春节将至，先猜灯谜在童年的一个春节，笔者在走马灯上见过一首字谜诗，韵律规范，对仗工整，令人捧腹，久久回味而不易忘却( 为增加思考的趣味，把窍门放在文末）：谜面假儿真女配为婚真经和尚念假经天上雷公下假雨吓得道士鼓眼睛谜底耍常翁平猜后感： (1)窍门就像窗户纸，一旦捅破，就那么显然，但是，窍门不易找到； (2) 从谜面到谜底比较难，反之，从谜底造谜面较易（可能造出的谜面不唯一，文字没有这样美）。 2 猜大自然之谜与公式发现，表 1 中给出了几个与自然和社会规律相关的谜语，谜面是训练数据。问题 1 告诉了迷底类型是直线，可以用待定系数法 ax+by+c=0 求出 a/c, b/c ，当数据点多于两个，用线性回归，找出一条使均方差最小的直线。问题 2 ，易观察规律，问题 3 将在下面讨论；对于问题 4 ，开普勒用了十年时间，作手工数据挖掘得出了结果；问题 5 事关财产大事，猜对了，可能一夜致富，猜错了，可能倾家荡产。 1 平面直线 2 欧姆定律 3 超越函数 4 自然规律 5 股票谜面 ( 训练数据 ) （ 1, 1 ）（2 .5, 2 ） I, R, V 2, 2, 4 3, 2, 6 2, 4 ,8 某仪器观察到一批数据，共 300 行，波浪式前进且上升。 0.1, 0.1998 0.2 0.3986 0.3 0.5955 0.5 0.9794 ….. 第谷 40 年观察积累的天文数据某股票连续一年数据谜底 2x-3y+1=0 I*R=V Y=x+sin(x) 开普勒行星运动定律下周行情表 1 几个与自然规律和社会相关的问题 3 外星殖民 --- 学当一回上帝地球资源的短缺敦促人类寻找新的宜居星球。假定地球人在太阳系外找到了一个宜居，但还没有较高级生物的星球，不妨取名新大陆，但发现那里的大气、土壤与地球略有不同。怎样把它改造为适宜地球人居住的家园呢？假如那一天真的来临，笔者建议学习大自然的进化算法，要点如下： Begin 。 Step1 ：初始化：带上一些地球上的微生物和低等生物（低等的变异比较大），随机或按一定规则布署； Repeat 让他们在新大陆上生存、变异、发展； until 低等生态环境建立（如大气成分与地球相近，等等）； Step2: 移植一些高等动物植物到新大陆； Repeat 让它们竞争，进化，优胜劣汰；人类随机地，或按一定规则给干预，引导他们的进化，例如制造一点困难（如水旱洪荒），作为适应度函数，淘汰一些适应度数低的物种；如果发生大灾难，送去诺亚方舟， …. ； Until 农牧业环境建立；能够存活下来的物种不是最智慧的；存活下来的物种不是最强壮的；但是存活下来的物种是那些最能够适应其生存的环境变化的物种。） Step3 ：人类进驻新大陆星球； End 这个过程也许需若干世纪；不着急，人类只需抓大放小、做些宏观干预；相信人类的科学家，在地球资源枯竭或被大行星撞击之前，一定能办成这件事。信上帝的人或许会说，此算法知识产权属于上帝。其实，大自然的进化算法与上帝算法有所区别，上帝算法是目的论典范，例如。偶尔听到这种说法：“ 为了能吃到高树叶，长颈鹿的长了长脖子”，而大自然的进化算法是非目的论的，有几个要点：（ 1 ）在多灾多难多变的地球环境中，不善变异的物种容易灭绝，如今不善变异物种不多，如熊猫等活化石物种。大多数物种都善于变异，善于改革开放（改革自身，向环境开放），在变中求存。达尔文的粉丝们，读了《物种起源》后，替他起草了一段“名言”，虽属是枪手之作，但的确符合其本人的核心思想：“ 能够存活下来的物种不是最智慧的；存活下来的物种不是最强壮的；但是存活下来的物种是那些最能够适应其生存的环境变化的物种。（it is not the most intellectual of the species that survives; it is not the strongest that survives; but the species that survives is the one that is able best to adapt and adjust to the changing environment in which it finds itself。）（ 2 ）一将功成万骨枯，当环境变化时，海量的个体中，一部分发生了变异，不变异的被淘汰了，虽变异但仍不适应新环境的也被淘汰了，有那么一只或几只，变异对了路，新性状能适应变化了的环境、生存并繁衍了。（ 3 ）没有“为了”，没有目的，从而也没有上帝。这可能是达尔文学说最犯教会之忌的地方。在下面猜测自然之谜的过程中，要学当一回上帝，要借用大自然进化的方法。 4 明码的进化计算法，挖掘表1第4列的谜底表 1 第 4 列谜面数据是某仪器观察到一批数据，波浪式前进上升。怎样从谜面发现其谜底 y=x+sin(x) 呢？千言难尽，科普博文只能简单说明思路，这里跳过基因编码和基因表达，用不编码的公式进化。这种“明码进化”，效率低，需要人的智能，不适合计算机，但适合初学者理解。准备用多项式去逼近目标：函数 f(x) 可展开成泰勒级数 ( 只需满足不太苛刻的条件 )： f(x) = f(a)+f'(a)*(x-a)+f''(a)/2!*(x-a) 2 +...f n (a)/n!*(x-a) n +... 收敛速度与|x-a| n 相关, 用上式计算f(x)在x=a 附近的近似值,收敛较快，在下面两个公式中，a=0 : Sin( x) = x-x 3 /3!+x 5 /5!-...(-1) k-1 * x 2k-1 /(2k-1)!+…. e x = 1+x+x 2 /2!+x 3 /3!+...+x n /n!+ …. 染色体和基因为简单，用 10 个公式作群体进化（进化计算程序中，群体规模常为 100-1000 ） , 下面随意写出了 4 个公式 : y 1 =1+x 4 , y 2 =5-x ,y 3 =10-x 3 , y 4 =x 2 -X 5 , y 5 =5+x 7 , …… 每个公式个体是一个候选的近似答案，公式可杂交、变异、繁殖，有一定生命力，本博文中暂称为染色体。染色体中的变量、符号（串），如 + ， - ， *, / ， 2 ， x ,x 3 , x 2 , sin(x), e -x 等，既易变异，又可能表达出可遗传的性状，不妨称为基因。例如：含有 sin(x) 的公式，可能有周期性，不妨把 sin(x) 称为周期性基因；含有 e -x 的公式，可能有衰减性；不妨把 e -x 称为衰减性基因。残酷的基因手术杂交，对 1 + x 4 , 5 - x ，施加以换头术，交换红蓝部分，可以杂交出 5 + x 4 ， 1 -x 变异：在染色体中插入、删除、或修改符号或符号片段。 6+x 7 中的“ + ”变为“ * ”，得到 6*x 7 +x 7 中的“ + ”变为“ - ”，得到 -x 7 ， ….. 变异手术中常用换头术、挖心术、加瘤术和移植器官术，比较残酷；早期的进化算法在做变异手术时候，大量的公式都死亡了或伤残了，尽管公式们不会呻吟，也不会抗议，但极大地制约了进化的速度和质量。 Candida Ferreira 于2000年提出了基因表达式编程，由于编码巧妙，可以保证染色体在残酷的变异手术下全部存活。选择标准是进化指挥棒，兼议若干金鱼实为遗传病携带者培养金鱼品种时，通过杂交，变异（如辐射、或化学方法），人工选留下一代。如果培育者喜欢头上长肉瘤的，则美其名曰凤头，如果喜欢浑身长疱块的，则美其名曰珍珠；而高度近视容易受伤的鼓眼，则称为龙睛，并大加培育。其实，这些品种在某种程度上都是遗传病携带者，但是养鱼人喜欢这种病态美（就像宝哥哥喜欢林黛玉），又有观赏和市场价值，从而得到繁衍，设若把这些病态美的金鱼放归大自然，很快就被淘汰了。进化计算中的选留机制是适应度函数，旨在使进化目标在训练数据集上的综合误差最小，当然，为了防止局部收敛和早熟，适当照顾多样性，选留少数适应度不高的个体。适应度函数是指挥棒，它引导着进化的方向，就像高考对中学教育的作用,如今，有识之士已经认识到各种考试的利与弊，拒绝金鱼模式，拒绝病态美。不难想象，经过若干代的进化。种群中的公式中会有迎合训练数据的基因出现，如用 n 个 x 连乘得到 x n ；用x/x得到1，用 1累加得到 n, 也不难进化出 n! ，如果训练数据有衰减性，可能会从多项式基因进化出 e -x 的泰勒级数前面若干项。 5 难能可贵的基因组合。在上面的进化挖掘过程中，经过若干代杂交、变异、和筛选，一个明星突然横空出世： y=2x-x 3 /6+x 5 /120 它对表1第4列的训练数据的适应性比较好，在 0x0.5(弧度）时，误差不超过 1%,(1弧度= 57.3 o ）,其实，只要有0到45 o 的正弦数近似值，利用中学三角函数知识，任意三角函数也能近似计算了。细心一点的观众会发现 y = x + x-x 3 /6+x 5 /120 ≈ x+sin(x) ，它是欲猜之谜底的泰勒展式的前三项。上述过程在基因表达式编程中，在普通 PC 机器上，进化几百代，大约需时几秒。实验表明，单次成功率高于 70% ，即连续做两次，就至少一次成功。 6 愚公移山，回到第 4 节的明码的进化计算。对照寓言中的愚公移山，做两个比喻：训练数据（谜面） --- 王屋山，谜底（ y=x+sin(x) ） --- 挖掉大山后得到的路。注意，在挖掘过程中，有两个不变：山还是那座山（训练数据不变），梁还是那道梁（谜底 y=x+sin (x) ）不变；一个进步：公式群体可不是原来那个公式群体，通过遗传，继承优良基因优势；通过变异，创生新的基因，通过杂交，集中优良基因，群体协同、在适应度函数的选择压力之下，并行地进步，精度一代比一代高。愚公精神：儿子辈公式达不到精度，还有孙子辈公式，子子孙孙没有穷尽，直到达到收敛标准或达到规定的辈数。 7 进化算法的特色：适、指、全、黑、并、渐、通今天，人们把进化计算作为数据挖掘或机器学习的一个分支，实际上进化计算概念是单独提出、独立发展的，由于其复杂性，在硕博士生课程中，常作为单独一门课程开设；数据挖掘的教科书偶尔会蜻蜓点水地提一下。进化计算有多种模型，如遗传算法（G enetic Algorithm ）、遗传编程 (Genetic Programming) ，基因表达式编程 (Gene Expression Programming) ，等等，这三者大概都是一个学期的课程， 2-3 学分。他们的共性可以用七个字描述，即：适、指、全、黑、并、渐、通，解释如下：适 -- 有适应度函数与适应度阈值，它是指挥棒，控制和引导了进化方向；指 -- 有指导的进化；全 -- 全局优化；黑 -- 黑箱特性；并 -- 并行性，是一个种群集体进化，具备先天的并行特性，易在并行计算机上进行；渐 -- 渐进性；通 -- 通用性。有了这些概念的铺垫，下篇准备简介进化计算家族中比较新的成员“基因表达式编程”。关于谜语的窍门：假儿真女配为婚，假儿-- 而，而+女= 耍；真经和尚念假经：真经和尚，尚，假经：巾；尚+ 巾= 常天上雷公下假雨：假雨：羽；公+羽= 翁吓得道士鼓眼睛：道士=倒立的士，干；鼓眼睛后为平参考文献 Russell C. Eberhart and Yuhui Shi,Computational Intelligence: Concepts to Implementations ,Publisher: Morgan Kaufmann; 1 edition (August 24, 2007),ISBN-13: 978-1558607590; Candida Ferreira , Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence (Studies in Computational Intelligence),Publisher: Springer; 2nd edition (July 11, 2006). 相关博文 1 “被打”和“北大” 的关联 --- 趣味数据挖掘系列之一 2 烤鸭、面饼和甜面酱之朴素关联 --- 趣味数据挖掘系列之二 3 一篇它引上万的大牛论文与数据血统论-- 趣味数据挖掘之三 4 巧挖科学博客之均击量公式，兼谈干预规则 ---- 趣味数据挖掘之四 5 听妈妈讲过去的故事，分房与分类 ----- 趣味数据挖掘之五 6 借水浒传故事，释决策树思路--- 趣味数据挖掘之六 7 团拜会和鸡尾酒会上的聚类 — 趣味数据挖掘之七 8 农村中学并迁选址、K-平均聚类及蛋鸡悖论--趣味数据挖掘之八 9 灯谜、外星殖民、愚公移山和进化计算 --- 趣味数据挖掘之九 10 达尔文、孟德尔与老愚公会盟：基因表达式编程--趣味数据挖之十 11 十大算法展辉煌，十大问题现锦绣---趣味数据挖掘之十一 12 数据挖掘中的趣味哲学 --- 趣味数据挖掘之十二其它系列博文的入口唐常杰博客主页科学博客主页

个人分类: 科普札记|15119 次阅读|49 个评论

【我的研究】浙江嵊泗人工鱼礁区渔业资源生态容纳量变动的研究

ljgan 2011-12-26 15:44

摘要人工鱼礁是放置于海底以影响海洋生物资源的物理、生物或社会经济过程的人工设施。科学评价人工鱼礁对渔业资源生态容纳量的改善程度对揭示鱼礁的生态功能和指导鱼礁后续建设具有重要的理论与现实意义。人工鱼礁区鱼类和大型无脊椎动物可分为 3 种类型（即 I 型、Ⅱ型和Ⅲ 型），其中Ⅱ型鱼类和大型无脊椎动物身体不接触鱼礁，但在鱼礁周围游泳和在海底栖息。该种生物学资料可通过拖网调查取样获得。根据 2004 年 10 月至 2007 年 9 月浙江嵊泗人工鱼礁海域渔业资源拖网调查数据，建立了用以模拟礁区渔业资密度随时间变化趋势的 logistic 模型，并据此求解了鱼礁海域资源数量容纳量模型。通过遗传算法求得了 logistic 模型的参数。结果表明人工鱼礁区 II 型鱼类和大型无脊椎动物的原有生态容纳量约为 6.00 ～ 8.03 ind·(km·kw) -1 ，鱼礁投放所产生的新生态容纳量约为 4.40 ～ 5.89 ind·(km·kw) -1 ，容纳量随季节变化而呈周期性波动。 ABSTRACT An artificial reef is one or more objects of natural or human origin deployed purposefully on the seafloor to influence physical, biological, or socioeconomic processes related to living marine resources, which is applied to improving marine entironment and protecting fishery resources. Large numbers of artificial reef projects have been developing in China from the beginning of 21 st century, so as to restore marine habitat. It is realistically very important to the future construction of the artificial reefs that the fishery resources enhancement impact of the artificial reef can be scientifically and roundly evaluated. There are 3 species of fish and macroinvertebrate(i.e. Type I, Ⅱ and III ) in artificial reef area.Type Ⅱ inhabitats surrounding and doesnot contact artificial reef, whose biological data can be obtained by using trawl. Based on the investigated data of fishery resources in artificial reef area of Shengsi in Zhejiang province, the density of fishery resource is analyzed, and the variational tendency of the density of fishery resource is simulated by using improved Logistic’s model. The parameters of the model are caculated via Genetic Algorithm method. The result indicates that the original ecology carrying capacity approximately is 6.00~8.03 ind·(km·kw) –1 , and the enlarged carrying capacity is approximately 4.4~5.89 ind·(km·kw) -1 on type Ⅱ fish and macro-invertebrate in artificial reef area. The carrying capacity has periodically fluctuated along with the seasonal variation. Therefore the carrying capacity of fishery resource has been elevated because of the deploy of the artificial reefs. 发表于《渔业科学进展》2011年05期

3166 次阅读|0 个评论

地学相关模型（3）

热度 2 vcitym 2011-8-10 10:22

3、遗传算法（Genetic Algorithm，简称GA）（1）背景 19的世纪世界四大学说之一是达尔文的自然选择学说。其主要内容有四点：过度繁殖，生存斗争（也叫生存竞争），遗传和变异，适者生存。在生存斗争中，具有有利变异的个体，容易在生存斗争中获胜而生存下去。反之，则容易在生存斗争中失败而死亡。达尔文把在生存斗争中，适者生存、不适者被淘汰的过程叫做自然选择。遗传算法就是根据自然界这个“物竞天择，适者生存”现象而提出来的一种随机搜索算法。遗传算法起源于对生物系统所进行的计算机模拟研究。早在本20世纪世纪1940年代．就有学者开始研究如何利用计算机进行生物模拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遴传过程棋拟等研究工作。进入60 年代后，美国密执安大学的Holland 教授及其学生们受到这种生物模拟技术的启发．创造出了一种基于生物遗传和进化机制的适合子复杂系统优化计算的自适应概率优化技术一遗传算法。 1967年，Holland的学生J.D.Bagley在博士论文中首次提出“遗传算法（Genetic Algorithms）”一词。此后，Holland指导学生完成了多篇有关遗传算法研究的论文。1971年，R.B.Hollstien在他的博士论文中首次把遗传算法用于函数优化。1975年是遗传算法研究历史上十分重要的一年。这一年Holland出版了他的著名专著《自然系统和人工系统的自适应》（Adaptation in Natural and Artificial Systems），这是第一本系统论述遗传算法的专著，因此有人把1975年作为遗传算法的诞生年。Holland在该书中系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极其重要的模式理论（schema theory）。该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年，K.A.De Jong完成了他的博士论文《一类遗传自适应系统的行为分析》。该论文所做的研究工作，可看作是遗传算法发展进程中的一个里程碑，这是因为，他把Holland的模式理论与他的计算实验结合起来。尽管De Jong和Hollstien 一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟（generation gap）等新的遗传操作技术。可以认为，De Jong的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论，迄今仍具有普遍的指导意义。进入20世纪1980年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。1985年，在美国召开了第一届遗传算法国际会议（International Conference on Genetic Algorithms ，ICGA），并且成立国际遗传算法学会（International Society of Genetic Algorithms ，ISGA），以后每两年举行一次。 1989年，Holland的学生D.E.Goldberg出版了专著《搜索、优化和机器学习中的遗传算法》。该书总结了遗传算法研究的主要成果，对遗传算法及其应用作了全面而系统的论述。同年，美国斯坦福大学的Koza基于自然选择原则创造性地提出了用层次化的计算机程序来表达问题的遗传程序设计( genetic programming, GP)方法，成功地解决了许多问题。在欧洲，从1990年开始每隔一年举办一次Parallel Problem Solving from Nature 学术会议，其中遗传算法是会议主要内容之一。此外，以遗传算法的理论基础为中心的学术会议还有Foundations of Genetic Algorithms，该会也是从1990年开始隔年召开一次。这些国际会议论文，集中反映了遗传算法近些年来的最新发展和动向。 1991年，L.Davis编辑出版了《遗传算法手册》（Handbook of Genetic Algorithms），其中包括了遗传算法在工程技术和社会生活中的大量应用实例。 1992年，Koza发表了他的专著《遗传程序设计:基于自然选择法则的计算机程序设计》”。1994年，他又出版了《遗传程序设计，第二册:可重用程序的自动发现》深化了遗传程序设计的研究，使程序设计自动化展现了新局面。有关遗传算法的学术论文也不断在《Artificial Intelligence》、《Machine Learning》、《Information science》、《Parallel Computing》、《Genetic Programming and Evoluable Machine》《IEEE Transactions on Signal Processing》《IEEE Transactions on Neural Networks》等杂志上发表。1993年，MIT出版社创刊了新杂志《Evolutionary Computation》。1997年，IEEE又创刊了《Transactions on Evolutionary Computation》《Advanced Computational Intelligence》杂志即将发刊，由模糊集合创始人L.A.Zadeh教授为名誉主编。目前，关于遗传算法研究的热潮仍在持续，越来越多的从事不同领域的研究人员已经或正在置身于有关遗传算法的研究或应用之中。【1】可以说，进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（Evolution Programming,EP）以及进化策略（Evolution Strategy,ES）等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的只能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。【2】遗传算法的一些应用领域：　　（1）优化。遗传算法可用于各种优化问题。既包括数量优化问题，也包括组合优化问题。　　（2）程序设计。遗传算法可以用于某些特殊任务的计算机程序设计，如元胞计算机。　　（3）机器学习。遗传算法可用于许多机器学习的应用，包括分类问题和预测问题等，如预测天气或预测蛋白质的结构。　　（4）经济学。应用遗传算法对经济创新的过程建立模型，可以研究投标的策略，还可以建立市场竞争的模型。　　（5）免疫系统。应用遗传算法可以对自然界中免疫系统的多个方面建立模型，研究个体的生命过程中的突变现象以及发掘进化过程中的基因资源。　　（6）生态学。遗传算法可以应用于对生态学的一些现象进行建模，包括生物间的生存竞争，宿主——寄生物的共同进化，共生现象，甚至包括生物学“军备竞赛”。　　（7）进化现象和学习现象。遗传算法可以用来研究个体是如何学习生存技巧的，一个物种的进化对其他物种会产生何种影响等等。　　（8）社会经济问题。遗传算法可以用来研究社会系统中的各种演化现象，例如在一个多主体系统中，协作与交流的是如何演化出来的。（2）概念遗传算法是一种通过模拟自然进化过程搜索最优解的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。遗传算法最初被研究的出发点不是为专门解决最优化问题而设计的，它与进化策略、进化规划共同构成了进化算法的主要框架，都是为当时人工智能的发展服务的。迄今为止，遗传算法是进化算法中最广为人知的算法。遗传算法已经成功的应用包括：作业调度与排序、可靠性设计、车辆路径选择与调度、成组技术、设备布置与分配、交通问题等等。有关基本概念：　　群体（population）：又称种群、染色体群，个体（individual）的集合，代表问题的解空间子集。　　串（string）及串空间：串是个体的表达形式，对应着遗传学中的染色体。对应实际问题的一个解。　　群体规模（population size）：染色体群中个体的数目称为群体的大小或群体规模。　　基因（gene）：是指染色体的一个片段，基因可以是一个数值、一组数或一串字符。　　交换（crossover）：指在一定条件下两条染色体上的一个或几个基因相互交换位置。　　交换概率：判断是否满足交换条件的一个小于1的阀值。　　变异（mutation）：指在一定条件下随机改变一条染色体上的一个或几个基因值　　变异概率：判断是否满足变异条件的一个小于1的阀值。　　后代：染色体经过交换或变异后形成的新的个体。　　适应度（fittness）：用来度量种群中个体优劣（符合条件的程度）的指标值，它通常表现为数值形式。　　选择（selection）：根据染色体对应的适应值和问题的要求，筛选种群中的染色体，染色体的适应度越高，保存下来的概率越大，反之则越小，甚至被淘汰。对概念的案例理解： GA对于复杂问题寻找最优解特别适用。如著名的旅行推销员问题：一个推销员希望设计一个送货车的路线计划，送货车需要送到许多商店，商店的先后顺序并不重要，主要是如何确定路线使得总里程最节省。人们已经发现这个问题没有常规的解决策略。然而，通过模拟一大批智能车（每一辆车相当于自然部落中的一个生命个体），开始每辆车都随机地选择行驶路径，通过比较他们完成任务所必须的里程数的长短进行类似自然淘汰的过程（短的在竞争中胜出），然后从这些竞争中胜出的车辆中随机地选择配对，混合他们的路径选择产生新一代的车辆，这样新生代车辆中含有上一代车辆双方的部分特征，那些产生的后代比自己还短的车辆配偶被保留下来，这样慢慢地车辆会变得越来越聪明，选择的路径也越来越优化。（3）原理一般把具有以下 6 个操作的遗传算法称为标准遗传算法：（ 1 ）编码。通过这个步骤，将处理空间的解数据表示成遗传空间的基因型串结构数据。（ 2 ）初始群体的生成。通过随机方法产生初始群体的每个个体，即进化的第一代。（ 3 ）适应度评估检测。构成一个适应度函数，用来评价个体或解的优劣，并作为以后遗传操作的依据。（ 4 ）选择。选择或复制操作的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代，为下一代繁殖子孙。（ 5 ）交叉。对配对库中的个体进行随机配对，并在配对个体中随机设定交叉处，使配对个体彼此交换部分信息。（ 6 ）变异。把某一位的内容进行改变，这是十分微妙的遗传操作，它需要和交叉操作妥善地配合使用。（4）软件工具常用的是 MATLAB 遗传算法工具箱。基于Matlab的遗传算法工具箱有好多种，是不同的人在不同的时间开发的，现在已知的有： GAOT ，中国学术期刊网上大部分研究遗传算法的中文论文都是使用的这个工具箱。这个工具箱用的似乎是最广的，虽然不是Matlab自带的，但在网上也很容易下载到。然而它的版本实在是太老了，是适用于Matlab5.0版的，到目前为止还没有更新版本发布。 GADS 这个是Matlab7.0版本自带的工具箱。在Matlab7.0的Help里面有对这个工具箱的详细介绍，还有很多例子作演示。【1】遗传算法的发展历史， http://www.itpub.net/thread-1204578-1-1.html 【2】 http://dict.youdao.com/search?q=bk%3A%E9%81%97%E4%BC%A0%E7%AE%97%E6%B3%95keyfrom=wiki.index.results#q%3Dbk%253A%25E9%2581%2597%25E4%25BC%25A0%25E7%25AE%2597%25E6%25B3%2595%26keyfrom%3Dwiki.index.results 进一步阅读： 1、浅谈遗传算法 http://bbs.sciencenet.cn/home.php?mod=spaceuid=436243do=blogid=317670 2、遗传算法简介 http://blog.tianya.cn/blogger/post_show.asp?BlogID=312322PostID=3824198 3、遗传算法 http://l-eme.gdcc.edu.cn/ztzs/fzxt/8-2.htm 4、 http://iask.sina.com.cn/b/4311893.html

个人分类: 杂谈|4506 次阅读|5 个评论

大家知道InTech邀请写书是怎么回事。

热度 2 王军强 2011-5-24 01:21

最近收到InTech邀请写书，我不知道这是一个什么级别的机构，大家有知道的帮忙share一下。－－－－－－－－－－－－－－－－－－－ Dear Dr. Wang, As a specialist in your field of research, we are pleased to invite you to contribute to our forthcoming Open Access book, "Genetic Algorithm", ISBN 979-953-307-599-9. The book will be published by InTech, Open Access publisher of books and journals in the fields of science, technology and medicine. InTech is a pioneer in the publication of Open Access books, with a collection currently comprising over 400 books written by more than 25,000 renowned authors. The complete collection is available for free full-text download on our reading platform, www.intechopen.com . This will be a reviewed book that will cover the latest research in the field, and will serve as a free, open access resource for scientists and researchers around the world. The book will be edited by an experienced scientist in the field and written by a team of international experts. When you publish with InTech, you make your paper freely available online Additionally, you: - Increase your visibility, impact and citation rates; - Keep the copyright to your work; - Receive a hard copy of the complete book; - Help speed up research; - Make your work freely available to everyone, benefiting the whole of society. You have been invited to contribute based on your paper "Influence of bottleneck utilization on job shop scheduling under random disturbance", your publishing history and the quality of your research However, we are not asking you to republish your work, but we would like you to publish a new paper on one of the topics this book will cover. I am the Publishing Process Manager for this book, and my role is to assist you throughout the publishing process. You are welcome to contact me at any time. I will do my best to answer your questions and ensure that publishing with InTech is a fast, smooth and pleasant process. NEXT STEP: For further details about this book please visit http://www.intechweb.org/welcome/9025a709550b508f98bdb47a9a856d89/**** On this page you can find a detailed description of the book, its scope and topics, details of the publishing process and a registration form. For further details about InTech and Open Access please visit: - About InTech: http://www.intechweb.org/welcome/9025a709550b508f98bdb47a9a856d89/*** - About Open Access: http://www.intechweb.org/welcome/9025a709550b508f98bdb47a9a856d89/*** If you need more information about this book project, InTech or Open Access, please do not hesitate to contact me. Kind regards, Ms. Marina Jozipovic Publishing Process Manager --- InTech - Open Access Publisher Email: jozipovic@intechweb.org Web: http://www.intechweb.org/ From Europe +43-1-229 7379 From America +1-347-625 3346 From Asia +86-10-8405 3529 Fax: +385-51-686 166 Fax: +385-51-686166 Corporate Address University Campus STeP Ri Slavka Krautzeka 83/A 51000 Rijeka, Croatia

19872 次阅读|2 个评论

完美的缺

热度 1 yaoqizhou 2010-12-12 10:42

遗传算法是模仿生物进化来寻找最优化的一种算法。它是从一些随机初始解出发，按照适者生存的方式，通过遗传、突变、自然选择以及杂交进行一代代的进化来不断优化而寻求最好的解。我们去年发表了一篇论文就用了遗传算法来优化自由能而预测蛋白质的结构。昨天，开会和一个同行吃饭时，他告诉我有一个人用遗传算法来优化风力发电的涡轮，并把这个过程放到了 youtube 上。虽然我对遗传算法比较熟，但从来没有想到利用它可以来搞材料的设计。真是没有做不到的，只有想不到啊！这是一个它山之石可以攻玉的范例。更有意义的发现是最优化的涡轮有一个奇怪的形状，并不是那么光滑，流线型。这个奇怪形状理论上要比商用流线型形状的效率高出很多。不知是否可以用类似方法来重新设计高铁上飞奔的和谐号。也许加些看起来不那么 “和谐”的部件能增加整体的和谐从而改进效率呢。这个结果是否也告诉我们无缺不成完美？想起我们搞理论计算的，常常不得不在这里那里做这样那样的近似。问题在于怎样找到合适的近似（“缺”）来达到比较完美的结果。有妙缺才是最高的境界！所以，做研究也要大胆造“缺”，不怕失败，在缺陷中寻求完美。

个人分类: 心得体会|5701 次阅读|4 个评论

[转载]遗传算法的应用MCM培训7

sobolev 2010-12-2 21:29

见附件遗传算法应用

个人分类: 未分类|2406 次阅读|0 个评论

寓教于乐-十滴水的仿真优化

热度 1 zyw1983 2010-9-18 16:41

最近看到 Master_Chivu 的博文强大的搜索(中) ，博文主人使用深度优先与广度优先相结合的方法搜索放置水滴的最优序列。此游戏可参考十滴水页面。规则比较简单，6X6的棋盘上有大小不同的水滴，共有五种状态，每加入一滴水就会使水滴体积变大，当水滴体积为4的时候，如果有外来水滴汇入，则该水滴会爆裂为上下左右四个方向上飞行的水滴。飞行的水滴将于沿途遇到的其他静止水滴合并（不与飞行的水滴合并），到达边界时消失。游戏的目的是使用最少的水滴（棋盘右侧显示还剩余多少可使用的水滴），利用水滴爆裂的连锁反应消除棋盘上所有的水滴。我尝试了一下，手工玩我也就最多玩到Level4，看来机器求解还是很有发展空间的。 Master_Chivu 给出了搜索算法的源程序，但没有使用启发式策略，按照他的说法称为“裸搜”。但是 Master_Chivu 也提到使用启发式算法会使搜索效率提高，这句话倒给我了启发。我的研究方向是自然计算，而而自然计算很多应用都是优化算法，能不能使用哪一种自然计算算法求解最优序列呢？搜索空间在6步的时候就会达到36^6= 2 176 782 336 ，20多亿种状态，枚举当然不行，随机搜索更不行。由于状态之间是离散的，粒子群算法和差分进化并不能体现很大的优势。选来选去，还是传统的遗传算法实现最简单。具体实施方法如下 1）令最大序列为N，种群规模为D，随机生成2DXN的矩阵XX，并满足奇数行为序列的横坐标，偶数行为序列纵坐标，每两行组成一条染色体。 2）使用每条染色体代表的序列，应用于初始棋盘状态AA，AA满足每次在染色体代表的一个坐标相对应的棋盘位置上加以水滴，待棋盘状态稳定（没有处在飞行状态中的水滴）后，按顺序应用序列中第二组坐标，直到棋盘上元素之和为0或到达序列尾部。 3）记录每条染色体使棋盘清零所需的步数，若未清零，则步数为N。 4）按照染色体清零棋盘步数大小排序，使用步数的倒数为适应度，并使用轮盘赌按照选择概率Ps选出Ps×D条染色体。使用随机值重新生成剩下的D-D×Ps条染色体，组成新的种群。 5）按照交叉概率Pc选择D×Pc条染色体，随机进行单点交叉。新生成的染色体与未交叉的组成新种群。 6）按照变异概率Pm随机选择D×Pm条染色体，并在随机的位置初始化一对坐标。 7）返回第2步或到达最大迭代次数后终止，返回清零步数最小的序列与所需步数。上面的算法使用Matlab实现，并测试了效果。在Level10之前，基本上种群数20，最大序列25，迭代次数500就可以找到比较好的解，每次寻优过程在我的老机器上大概需要30秒。我用这个程序给出的序列去玩十滴水，效果还真不错。如图打到Level16的时候还有42个水滴，到达Level20应该不成问题。存在的问题： Level10以后出解的效率降低，经常出现十步以上的最优序列，而根据经验，如果要一直持续的进行升级，步数应该控制在12以下。增加了最优个体保存策略，并降低了选择概率（剔除很多无用的染色体，他们的清零步长全是最大值），提高变异概率后，可以坚持到Level16以后。但在测试中，这一局却始终找不到满意解（低于20），尽管曾经解出过18步的解，但由于对水滴消耗太大，暂时没有采用。改进的建议：适应度选取了清零步长的倒数，可以使清零步长最小化，但是游戏过程中每连续消除三个水滴将会获得一个奖励水滴，这个并没有计算在内。由于游戏的目的应该是在一局结束的时候使剩余水滴数达到最大，那么使用步长（消耗水滴）+奖励水滴=剩余水滴作为适应度应该更为合理。此外，由于能力有限，找不到很好的描述棋盘特性的数学表达，这也制约了算法设计。转化为纯数学问题的求解应该效率更高。总结：很多益智游戏的本质是求解最优序列，而且他们的求解难度并不比常用的标准测试函数低。测试一种算法最好的办法就是拿到实际中使用。水平所限，文中内容难免出现错误，请看官不吝赐教。也希望本文能起到抛砖引玉的作用，引起大家对智能计算的兴趣。作者：张永韡出处： http://www.sciencenet.cn/u/zyw1983/ 本文版权归作者和科学网共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。

个人分类: 快乐学习|6163 次阅读|0 个评论

遗传算法(GA)解决在不同制造环境下设施布置问题

putin24 2010-6-3 22:16

摘要此论文描述的是遗传算法 (GA) 解决是在制造系统设计中产生最优设施布局而使物料搬运成本最低 . 此论文认为 GA 在不同的物料流形式在流水线 : 流水线 ( 单线 ) 多品种 , 多线布置 , 半圆形布置 , 环路布置 , 相比其它方法具有量化特性且更有效 . 结果显示 GA 在解决设施规划问题中是一个有效的工具。关键字 : 设施规划 ; GA ; 组合最优化 ; 物料流 1. 引言有效的设施布置设计减少产品制造周期 , 增加产量 . 因此提高了工厂总的生产率 . 在制造系统中主要布置类型有按流程布置 , 流水线布置 , 单线 , 多线 , 半圆形 , 环形布置 . 在图 1 中列出了这些不同的布置形式 . 在图中每一个方格表示相应编号设备的位置序号。单线设施规划问题在制造不同产量和不同工艺的产品时被考虑到。选择不同的特定的布置方式由从设备到设备的不同的搬运方式来决定。图 1 不同的布置方式选择一类设备的布置方式，是受多项因素影响，即有多少机器，可用空间，相似的工艺流程和物料搬运系统的使用情况。有许多类型的物料搬运设备，其中包括：自动导引车、输送机系统、机器人等。在现代化制造系统的设施规划设计中，选用何种物料搬运系统设备是非常重要的。本文使用的方法是在设备布局设计中，新设备被安排进某一个特定的车间设备布置问题得到优化的一种方法。本文的方法是最小化物料搬运成本。此问题属于非约束多项式类（ NP 约束）。问题的复杂性指数大大增加由于设备大量的可能放置点。这项研究提出了一种遗传算法（ GA ）的方式，在一个制造设施规划中，以确定最佳的布局为不同的物料流系统。优化模型被介绍用于研究布置设备的不同形式的物料流的制造环境。举例该方法的利用数值方式对以往流水线作业车间类型是很有效的。另一个实例是 GA 用于多品种产品流水线布置问题的解决。结果表明， GA 提供了一种有效的方法来解决设施布置问题。 2. 建立数学模型该设施布置问题是在一个制造型工厂中如何将 M 个设备安排到 N 个设备布置点。在制造产品过程中，物料流从一台设备向另一台设备流动，直至所有加工工序完成为止。因此解决解决设备布局问题就是降低总的物料搬运系统的成本。定义某一布置方式的物料搬运成本，生产产量、生产路线、成本表、机器 / 位置之间的距离是已知的。定义以下符号是用于确定的目标函数：为设备 i 与设备 j 的物料流量为设备 i 与设备 j 的单位物料流成本为设备 i 与设备 j 的直线距离为物料搬运系统总成本定义物料搬运系统总成本在本论文中提及此函数是最小化物料搬运系统的物料搬运成本，这也是众多研究人员比较倾向的解决设施布置问题的标准方法。此方法也适用于其它的目标函数 3. 遗传算法 (GA) 3.1 背景在早期研究设施布置问题的研究者们认为，来解决设施布置问题最好的方法是通过改进普通二次分配问题（ QAP ）。用 QAP 来解决设施布置问题，采用隐枚举的方法，如求切面，树和约束办法，或其它运筹学技术可以最大限度的解决设备布置最优化问题。只有当问题的规模很小时，在合理的时间内，这才可能是获得精确解最佳方法。结果显示， QAP 解决问题的时间是一个关于布置设备数量呈指数增长函数关系。遗传算法（ GA ）在最近的文献都得到了很大的关注由于它们不依赖于分析的函数而自己又广泛适合于各种优化问题。遗传算法（ GA ）是一种随机搜索技术（ Goldberg,1989;Michalewicz, 1992 ）。它从基因及进化理论（ Kazerooni ,Luonge ＆ Abhary ,1995; Tavakkoli Shayan ,1997; Venugopal ＆ Narendran ,1992 Zhang, Zhu, Luo, 1997 ）发掘可以解空间利用的概念。近年来，遗传算法为解决设施布置问题提出一种创新的方法 ( Al-Hakim, 2000; Gau Meller,1999; Hamamoto, 1999; Islier, 1998; Rajasekharan,Peters, Yang, 1998 ) 。 GA 以一组随机的原始解集合开始，这个集合被称作种群。种群的个体被称作染色体，种群的染色体预先根据物料搬运系统成本确定的函数。染色体形成连续迭代被称为代，在每一代中种群内染色体经过交叉和变异，创造了新的一代。这种经过交叉的染色体形成的新染色体的杂交过程被称为突变，杂交是一个随机的通过染色体的混合和对接过程，从而产生一对新的染色体（后代）。突变是通过重组染色体产生新一代的过程。当新一代产生就需要删除上一代种群里的元素，以腾出空间给新的一代，形成新的种群。这个过程一直迭代直到达到一个标准点而终止。在此论文中的遗传搜索过程概括如下： 1. 随机生成一个初始种群规模为 P 的染色体集合； 2. 根据物料搬运系统的成本方程评估群体的每一个染色体； 3. 确定一个平均合适的种群； 4. 在原种群利用优胜劣汰的法则淘汰最差个体，留住最优染色体复制到下一代的种群中去。为了计算的有效性和经济性，种群中染色体总数保持不变，统计平均染色体的行为包括那些被淘汰那些被复制到下一代作为标准，被删除的染色体的值 P （ k ）基本要大于 1.5 倍的新群体（新染色体和被复制的染色体组成的新种群）的平均值； 5. 运用 Monte Carlo 选择技术从现有群体选择父代染色体，这是用于随机交叉和变异的父代染色体； 6. 统计在原种群基础上运用交叉和变异的操作产生新染色体的的概率（分别为 Pc 和 Pm ），原种群剩下的优质染色体的概率； 7. 检查是否达到与预先设定的停止搜索的准则，满足准则就停止搜索，否则就进行下一次循环，产生新的一代，继续第 2 步。 GA 的寻优流程在图 2 中表示。 3.2 编码制度 GA 技术的需要一个编码制度（染色体），在此论文中，整个生产车间 / 部门被划分成 n 网格，每个网格代表了一台设备的位置。在这项研究中，码被直接表示成某种形式，图 3 所示。表示不同各类型生产车间布局不同的例子，其编码的染色体代表代表所有布置方式里的某一可能的设备布置方式。例：某流水线作业车间包括九台设备 / 部门，生产流线包含五个工作站，多流水线线制造系统包含六个设备布置点，一个环式设备布置方式有 8 台机器，位置符号 e 代表一个空位，表示在这个区域没有已经被布置的设备。 3.3 选择操作选择操作是从种群中选择父代染色体， Monte Carlo 的选择技术被应用其中。父代染色体选择流程如下： 1. 根据公式（ 1 ）计算种群所有元素合理的值； 2. 在 0 和区间内选择任一随机数值为 n ； 3. 返回第一代具有合适值种群元素，增加合适值到第一代种群元素中，使得种群大于或等于 n ； 4. 第二代种群重复第三步并检查新产生的染色体元素是否和第一代种群元素相同。 3.4 杂交操作发生杂交的概率 Pc 是有杂交操作者赋予的值，余下的染色体将产生与父代染色体一致的染色体。否则，被选择用于杂交的染色体将被操作者用于交叉杂交从而产生两个子代染色体。在本论文中一个新的交叉操作建议如下，确定一对父代染色体（ P1 ， P2 ）如下所示： P1 1 4 7 5 2 8 3 6 9 P2 4 1 6 7 5 2 9 3 8 首先，选择两个随机数据给父代染色体，假设在这个例子中的的两个随机数字是 4 和 7 ，该基因具有双内衬边界内切剖面（ Cutting Section ）。即 P1 中的（ 5 ， 2 ， 8 ， 3 ）和 P2 中的（ 7 ， 5 ， 2 ， 9 ），部分的基因编码从 P1 交换到 P2 ，这样新的染色体结构就产生了： P1 1 4 7 7 5 2 9 6 9 P2 4 1 6 5 2 8 3 3 8 在这个阶段，新和成的染色体上存在相同的一些基因，例如 P1 有 7 ， 9 ， P2 有 3 ， 8 。这意味着一台设备在设施布置规划中有多个可能放置点，一种落后的替换程序可以改变在内衬边界内切剖面外相同基因的值，这种在 P1 切剖面外相同的基因用 5 替换原来第三段基因的 7 ，因为 P1 中的基因 5 是由于和 P2 中的基因 7, 然而 P1 内衬边界内切剖面中的基因 5 出现重复 , 此基因再次改变为 2 。在 P1 的基因 9 被基因 3 替换从而产生下一代染色体 c1 ，在 P2 内衬边界内切剖面的重复基因被重组通过基因 8 替换成 7 （ 8 替换成 2 ， 2 替换成 5 ， 5 替换成 7 的综合结果）和基因 3 替换成 9 。下一代染色体 c1,c2 变成为： c1 1 4 8 7 5 2 9 6 3 c2 4 1 6 5 2 8 3 9 7 内衬边界内切剖面的基因被操作者随机选择用于交叉杂交，如果染色体有大量基因信息，基因信息大或小的内衬边界内切剖面是不同的 , 这也是这种方法的柔性。再则，为杂交操作者增加的柔性，在这个方法里空着设备布置点（染色体上的字母 e 表示）被处理为在过程中没有任何改变的布置点。父代染色体交换内衬边界内切剖面的基因 , 此算法表现在第一步检查是否子代染色体是否早熟和空着的基因段与父代染色体一致。 3.5 突变操作突变操作时为了重组染色体的结构。这研究中，基因突变主要是随机选择两个基因交换它们的内容。这种单个基因突变的概率被称为突变率（ Pm ），它一般是一个很小的数值。基因突变增加了寻优的强度，为了解释突变的必要性，主要在于它解决基因杂交和繁殖可能不能够产生问题的最优解。在这个突变创造基因的过程可能会使得群体的大量基因信息丢失，所以检验原群体正确性或早熟的最优解（例：只需要交换一个基因和另一基因）显得非常重要。通过繁殖和杂交产生下一代的染色体有可能不能解决问题，此时，突变显得很重要。 3.6 终止准则此程序将被终止直到达到了最大的结果的一代，或者达到群体收敛点。 4. 例子 4.1 例 1 用数值例子来评估我们的方法 : 第一个例子是比较 C han and Tansri (1994) 和 Mak, Wong, and Chan (1998) 使用相同的方法来评估他们的研究。表 1 设备之间的物料流从 / 至 2 3 4 5 6 7 8 9 1 100 3 0 6 35 190 14 12 2 6 8 109 78 1 1 104 3 0 0 17 100 1 31 4 100 1 247 178 1 5 1 10 1 79 6 0 1 0 7 0 0 8 12 译文原文出处： M. Adel El-Baz. A genetic algorithm for facility layout problems of different manufacturing environments. Computers Industrial Engineering 47 (2004) 233246 图1 图2 相关下载：译文原文

个人分类: 学术评论|4603 次阅读|3 个评论

遗传算法的初步理解

zswm27 2010-5-5 23:43

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。 ga的java算法遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

个人分类: 学习之路|8016 次阅读|3 个评论

[下载,原创]求解旅行商问题的改进遗传算法

热度 5 fswdong 2009-8-27 08:38

附件程序是本人设计的遗传算法程序计算旅行商问题，随包附带了TSPLIB95中较大规模问题数据集，城市数量在1000至10000个城市之间。遗传算法中结合了本人设计的旅行商问题的初始边集化简策略以及选择性交叉、变异算子，是三年前完成的部分工作。使用Lin-kernighan作为局部搜索算法情况雄，试算结果表明，问题规模在小于2000个城市的时候，计算工具可以比同样使用Lin-kernighan的同类进化策略的遗传算法收敛时间得到明显缩短，并以很高高概率收敛于问题的全局最优解，全局最优解源自TSPLIB95。下面是当时试算的统计结果，没有加下划线的数据为30次重复运算的平均计算结果。算法 1 ： GA 使用 3-Opt 局部优化算法；算法 2 ： GA 使用重复 N/2 次且采用 Quadrand 3 近邻域参照优化边集初始化的链式Lin-kernighan 算法；算法 3 ： GA 使用重复 N/2 次且采用初始边集化简的的链式Lin-kernighan 算法；算法 4 ： GA 使用重复 N/2 次且采用初始边集化简的的链式Lin-kernighan 算法，并使用了选择性交叉和变异算子；实验环境为 Intel Core2 E6300 1.86GHz CPU ， 1GB 内存，操作系统为 Windows XP 。该算法很多基础算法源自于Concorde，所以不用作商业用途，可以作为研究者交流，并不提供源代码交流，谢谢合作。到这里点击下载：遗传算法计算工具

个人分类: 试算工具|7299 次阅读|9 个评论

[下载,原创]求解旅行商问题的基本遗传算法

fswdong 2009-8-16 11:20

附件程序是本人设计的常规遗传算法程序计算旅行商问题，随包附带了TSPLIB95中中等规模问题数据集，城市数量在200至1000个城市之间。计算工具中没有使用任何个人创新内容，完全是兴趣所致，希望能在这种方法中寻求一些创新亮点。该算法很多基础算法源自于Concorde，所以不用作商业用途，可以作为研究者交流，并不提供源代码交流，谢谢合作。到这里点击下载：基本遗传算法计算工具

个人分类: 试算工具|5294 次阅读|0 个评论

[下载,原创]使用Grefenstette编码的求解TSP遗传算法

热度 2 fswdong 2009-8-15 20:24

附件程序是本人设计的使用Grefenstette编码方式实现的常规遗传算法计算工具，用于计算旅行商问题，随包附带了TSPLIB95中中等规模问题数据集，城市数量在200至1000个城市之间。Grefenstette编码的优点在于经过交叉、变异等繁殖算子作用后，个体仍然确保为是一条哈密尔顿环路，的确佩服这种编码的创意。试算过程中发现，结合链式Lin-kernighan算法，一般的中等规模问题都能很快收敛于问题的全局最优解，部分大规模问题也能收敛于问题的全局最优解，与常规的全排列编码方式相比，的确有过人之处。计算工具中没有使用任何个人创新内容，完全是兴趣所致，希望能在这种方法中寻求一些创新亮点。该算法很多基础算法源自于Concorde，所以不用作商业用途，可以作为研究者交流，并不提供源代码交流，谢谢合作。到这里点击下载：点击下载

个人分类: 试算工具|6411 次阅读|0 个评论

遗传神经网络

ruanjunhu 2009-3-9 16:14

(河北工程大学管理科学与工程阮俊虎） 1. 神经网络神经网络在神经生理学、神经解剖学的范畴里，指的是生物神经网络 (Biological Neural Networks) ；在信息、计算机科学等领域内，指的则是向生命学习而构造的人工神经网络 (Artificial Neural Networks) 。如同生物学上的基本神经元，人工的神经网络也有基本的神经元。每个神经元有特定数量的输入，也会为每个神经元设定权重（ weight ）。权重是对所输入的资料的重要性的一个指标。然后，神经元会计算出权重合计值（ net value ），而权重合计值就是将所有输入乘以它们的权重的合计。每个神经元都有它们各自的临界值（ threshold ），而当权重合计值大于临界值时，神经元会输出 1 。相反，则输出 0 。最后，输出会被传送给与该神经元连接的其它神经元继续剩余的计算。图 1 给出了单个神经元的基本结构。图 1 神经元结构本文仅以 BP 神经网络为例。 BP 神经网络是一种多层前馈网络，它是利用误差逆传播算法进行误差校正的神经网络，所谓误差逆传播算法 (Error Back-Propagation Training) 是利用实际输出与期望输出之差对网络的各层连接权由后向前逐层进行校正的一种计算方法。图 2 是一个三层 BP 网络模型。这是一个三层 BP 网络，一般来讲， BP 网是一种具有三层或三层以上的多层神经元网络，它的左、右各层之间各个神经元实现全连接，即左层的每一个神经元与右层的每个神经元都有连接，而上下层各神经元之间无连接。在 BP 网络中，当一对学习模式提供给网络后，其神经元的激活值将从输入层经各中间层向输出层传播，在输出层的各神经元输出对应于输入模式的网络响应。然后，按减少希望输出与实际输出误差的原则，从输出层经各中间层，最后回到输入层逐层修正各连接权。随着这种误差逆传播训练的不断进行，网络对输入模式响应的正确率也不断的提高。由于 BP 网络有处于中间位置的隐含层，并有相应的学习规则可循，可训练这种网络，使其具有对非线性模式的识别能力，特别是它的数学意义明确、步骤分明的学习算法，更使其具有广泛的应用前景。 2. 遗传算法遗传算法（ Genetic Algorithm ）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的 J.Holland 教授 1975 年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术之一。遗传算法（ Genetic Algorithm ，简称 GA) 是根据达尔文的自然界生物进化思想，将其灵活运用到优化运算领域而产生的一种寻优算法。遗传算法是从代表问题可能存在解集的一个种群 (population) 开始的，而一个种群则由经过基因 (gene) 编码的一定数目的个体 (individual) 组成的。遗传算法常用来解决最优化问题，首先应对可行域中的点进行编码 ( 一般采用二进制编码 ) ，然后在可行域中随机挑选一些编码组成作为进化起点的第一代编码组，并计算每个解的目标函数值，也就是编码的适应度。接着利用选择机制从编码组中随机挑选编码作为繁殖过程前的编码样本。选择机制应保证适应度较高的解能够保留较多的样本；而适应度较低的解则保留较少的样本，甚至被淘汰。在繁殖过程中，使用交叉和变异两种算子对挑选后的样本进行交换，产生下一代编码组。简单遗传算法可以形式化定义为一个 8 元组： SGA=(C ， E ， Po ， M ，，，， T) ；式中： C 表示个体的编码方法； E 表示个体的适应度函数； Po 表示初始种群； M 表示群体大小；表示选择算子；表示交叉算子；表示变异算子； T 表示遗传运算终止条件。遗传算法的主要计算过程： (1) 对问题的可行解进行染色体编码； (2) 产生初始种群； (3) 对种群内的各个个体进行适应度评价； (4) 根据个体的适应度进行选择操作，然后交叉、变异产生新的群体； (5) 返回到 (3) ，对该组群体解码进行新的评价； (6) 若当前解满足要求或进化过程中达到一定的进化代数，计算结束，否则转 (3) 继续进行。 3. 遗传神经网络 BP 算法具有简单和可塑的优点，但是即算法是基于梯度下降的方法，这种方法的收敛速度慢，且常受局部极小点的困扰。遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，由于其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖梯度信息。该算法从多点出发开始搜索，加上交叉作用，所以该算法不容易陷入局部最小误差。图 3 局部最大和全局最大目前有关遗传算法与神经网络相结合的应用研究工作主要包括三个方面： (l) 利用遗传算法进化神经网络的连接权； (2) 利用遗传算法进化神经网络的结构； (3) 利用遗传算法进化神经网络的学习规则。以利用遗传算法进化神经网络的连接权为例说明利用遗传算法优化神经网络。神经网络的权值训练过程实际是一种复杂函数优化问题，即通过反复调整来寻找最优的连接权值。神经网络权值的整体分布包含着神经系统的全部知识，传统的权值获取方法是采用某种确定的变化规则，在训练中逐步不调整，最终得到一个较好的权值分布。但是目前广泛使用的 BP 网络，是基于梯度下降方法，因而对网络的初始权值异常敏感，不同的初始权值会导致完全不同的结果，而且在训练过程中，有关参数 ( 如学习速率 ) 的选取也没有理论指导，完全凭借经验来确定，一旦取值不当，就会引起网络振荡而不能收敛，即使收敛也会因为收敛速度慢而导致训练时间长，同时又极易陷入局部极值而无法得到最好的权值分布，最终影响网络的泛化能力。用遗传算法进化神经网络的连接权可以有效克服这些问题，进化连接权过程如下： (l) 采用某种编码方案对一权值 ( 阀值 ) 进行编码，随机产生一组分布，它就对应着一组神经网络的连接权 ( 阀值 ) ； (2) 输入训练样本，计算它的误差函数值，以误差平方和倒数作为适应度 ; 若误差越小，适应度越大，反之适应度大。以此来评价连接权 ( 阀值 ) 的优劣； (3) 选择适应度大的个体，直接遗传给下一代； (4) 再利用交叉，变异等操作对当前群体进化，产生下一代群体； (5) 重复 (2)- (4) ，这样初始确定的一组权值 ( 阀值 ) 得到不断进化，直到训练目标满足条件为止。 4. 适用范围神经网络和遗传算法都是人们仿效生物处理模式的方法，并从中获得的用于处理复杂问题的方法。然而，随着神经网络和遗传算法研究的不断深入发现，在许多学科的应用研究中，神经网络技术己渗透到各个领域，在智能控制、模式识别、计算机视觉、非线性优化、连续语音识别、信号处理等方面取得了巨大的成功和进展，但是有关网络模型结构的确定，初始权值的确定以及 BP 算法收敛慢等问题，人工神经网络方法本身还没有很好的理论指导和解决办法，而遗传算法虽然对于寻优问题有很好的自适应优化搜索能力，但是它不具备自适应学习能力，难以单独有效地作为一种控制方法研究，又由于遗传算法能够收敛到全局最优解，且遗传算法的鲁棒性强，将遗传算法与神经网络结合起来是很有意义的。不仅能发挥神经网络的泛化映射能力，而且使神经网络具有很快的收敛性以及较强的学习能力。将它们结合起来，取长补短，寻求更有效的方法，用于解决复杂问题，越来越受到人们的重视。这样可以更好的发挥神经网络的泛化映射能力，并使神经网络具有很快的收敛能力以及较强的学习能力。 5. 推荐学习资源（ 1 ）书籍：神经网络理论与 matlab7 实现初学这入门还是挺不错的，看过了，就对 matlab 神经网络工具箱有教好的了解神经网络设计讲理论不是很多，看过之后就会对神经网络的原理有更好的了解神经网络结构设计的理论与方法对提高网络的泛化能力的一些方法做了讲述，并且书后有程序，对网络结构的设计应该是挺有帮助的。（ 2 ）论文：李晔基于一种改进遗传算法的神经网络太原理工大学硕士论文集（ 2007 ）杨婷基于遗传神经网络的汽车故障率预测上海交通大学硕士论文集（ 2008 ）赵振勇基于遗传 BP 神经网络的股市预测贵州大学硕士论文集（ 2007 ）吴涛用遗传算法优化神经网络权值张庆红基于遗传算法的神经网络性能优化刘勇基于 GA 的神经网络学习规则的发现邱俊基于遗传算法的循环神经网络在销售预测中的应用储诚山基于遗传算法和 BP 神经网络的用水量预测 Nachol Chaiyaratana Time-Optimal Path Planning and Control Using Neural Networks and A Genetic Algorithm S. H. Ling An Improved Genetic Algorithm Based Fuzzy-Tuned Neural Network Gary G. Yen Hierarchical Rank Density Genetic Algorithm for Radial-Basis Function Neural Network Design Gary Yen Hierarchical Genetic Algorithm For Near-Optimal Feedforward Neural Network Design 书籍能帮助你系统、快速地理解基本原理，论文能帮你理清思路，进行创新！（ 3 ）网站资源 http://www.jgchina.com/ednns/ednnsbk/ednns2.htm 数字神经网络系统介绍神经网络的生物原型、系统模型、数学推理等 http://www.ymlib.net/ MATLAB 资源网教程、源码、工具箱程序等 http://www.ilovematlab.cn/ MATLAB 中文论坛 http://bbs.bc-cn.net/forum-216-1.html MATLAB 编程论坛 http://www.matlab-download.cn/default.aspx Matlab 免费源码免费提供各领域的 Matlab 源码

个人分类: 管理科学方法|6871 次阅读|0 个评论

遗传算法：内存中的进化

eloa 2009-3-3 21:35

fwjmath 发表于 2009-03-02 23:09 这是个真实的故事。从前在海岸边有一群扇贝在悠哉游哉地生活繁衍着。它们自然是衣食不愁，连房子也有了着落。它们担忧的只有一件事：每隔一段时间，总有一个人来挖走它们之中的一部分。当然啦，挖回去干什么这大家都知道。但扇贝们不知道的是，这人的家族图腾是Firefox的图标，所以他总是选择那些贝壳花纹长得比较不像Firefox图标的扇贝。这种状况持续了好几十万代。大家应该也猜到扇贝们身上发生什么事情了：它们的贝壳上都印着很像Firefox图标的图案。可能有些读者会说：你这不是糊弄我们么，Firefox才有多少年历史，你就搞了个几十万代的扇贝？确有其事，但是这些扇贝不是真实的，它们在我电脑的内存里边生活。它们是一个遗传算法程序的一部分，这个程序的目的就是用100个半透明三角形把Firefox的图标尽可能像地画出来。什么是遗传算法呢？简单地说，遗传算法是一种解决问题的方法。它模拟大自然中种群在选择压力下的演化，从而得到问题的一个近似解。在二十世纪五十年代，生物学家已经知道基因在自然演化过程中的作用了，而他们也希望能在新出现的计算机上模拟这个过程，用以尝试定量研究基因与进化之间的关系。这就是遗传算法的滥觞。后来，有人将其用于解决优化问题，于是就产生了遗传算法。那么，具体来说，在计算机里边是怎么模拟进化过程的呢？我们还是以开头提到的程序为例。首先，我们知道，生物个体长什么样子很大程度上是由染色体上的基因决定的。同样，如果我们把100个半透明三角形组成的东西看成一个生物个体的话（为了说话方便，称为扇贝吧），我们也可以说它的样子是由这些三角形的具体位置和颜色决定的。所以，我们可以把一个一个的半透明三角形看作是这些扇贝的基因。而组成扇贝的这100个基因就组成了每个扇贝个体的染色体（chromosome）。从下面的图可以大约看出来这些基因是怎么决定扇贝的样子的（为了观看方便，我们只画出其中五个三角形）：然后，扇贝们除了生活，当然还要繁衍后代。生物界中的繁衍无非就是父母的基因组合产生新的个体，而在这个程序里边我们当然也这么办：选择两个原有的扇贝，然后从这两个扇贝的染色体中随机选取一共100个基因组成新个体的染色体。如图所示：（仍然是将扇贝看成是五个三角形组成的）为了产生新的基因，使基因的种类更多样化，在组合的时候，新的扇贝的基因有一定的概率发生变异。也就是说，其中的一个透明三角形的位置或者颜色会随机改变，如图（仍然是五个三角形我偷工减料）：其次，为了使扇贝的样子向Firefox图标靠近，我们要给它们加上一点选择压力，就是文章开头故事中提到的那个人的行动：在每一代把最不像Firefox的扇贝淘汰出去，同时也给新的个体留下生存的空间。怎么评价这个扇贝像不像Firefox呢？最直接的方法就是一个一个像素比较，颜色相差得越多就越不像。这个评价的函数叫做适应函数，它负责评价一个个体到底有多适应我们的要求。在淘汰的过程中，为了便于编程，我们通常会在淘汰旧个体和产生新个体的数目上进行适当的调整，使种群的大小保持不变。淘汰的作用就是使适应我们要求的个体存在的时间更长，从而达到选择的目的。最后，在自然界中，种群的演化是一个无休止的过程，但程序总要停下来给出一个结果。那么，什么时候终止演化输出结果呢？这就要订立一个终止条件，满足这个条件的话程序就输出当前最好的结果并停止。最简单的终止条件就是，如果种群经过了很多代（这里的很多是一个需要设定的参数）之后仍然没有显著改变适应性的变异的话，我们就停止并输出结果。我们就用这个终止条件。好了，现在是万事俱备只欠东风了。定义好基因，写好繁衍、变异、评价适应性、淘汰和终止的代码之后，只需要随机产生一个适当大小的种群，然后让它这样一代代的繁衍、变异和淘汰下去，到最后终止我们就会获得一个惊喜的结果：（这回是完整的了，图片下的数字表示这个扇贝是第几代中最好的）怎么样？虽说细节上很欠缺，但是也算是不错了。要不，你来试试用100个透明三角形画一个更像的？就是这样的看上去很简单的模拟演化过程也能解决一些我们这些有智慧的人类也感到棘手的问题。实际上，在生活和生产中，很多时候并不需要得到一个完美的答案；而很多问题如果要得到完美的答案的话，需要很大量的计算。所以，因为遗传算法能在相对较短的时间内给出一个足够好能凑合的答案，它从问世伊始就越来越受到大家的重视，对它的研究也是方兴未艾。当然，它也有缺点，比如说早期的优势基因可能会很快通过交换基因的途径散播到整个种群中，这样有可能导致早熟（premature），也就是说整个种群的基因过早同一化，得不到足够好的结果。这个问题是难以完全避免的。其实，通过微调参数和繁衍、变异、淘汰、终止的代码，我们有可能得到更有效的算法。遗传算法只是一个框架，里边具体内容可以根据实际问题进行调整，这也是它能在许多问题上派上用场的一个原因。像这样可以适应很多问题的算法还有模拟退火算法、粒子群算法、蚁群算法、禁忌搜索等等，统称为元启发式算法（Meta-heuristic algorithms）。另外，基于自然演化过程的算法除了在这里说到的遗传算法以外，还有更广泛的群体遗传算法和遗传编程等，它们能解决很多棘手的问题。这也从一个侧面说明，我们不一定需要一个智能才能得到一个构造精巧的系统。无论如何，如果我们要将遗传算法的发明归功于一个人的话，我会将它归功于达尔文，进化论的奠基人。如果我们不知道自然演化的过程，我们也不可能在电脑中模拟它，更不用说将它应用于实际了。向达尔文致敬！ Bonus：如果你看明白了这篇文章，而且你懂英语的话，你自然明白下面这个冷笑话：（来自 http://xkcd.com/534/ ） Just to make sure you dont have it maximize instead of minimize.

个人分类: 生物|1791 次阅读|0 个评论

最简单遗传算法的scheme语言实现

xsplendor 2009-1-15 14:54

;徐光华 2009/1/15 ;为了学习遗传算法和scheme编程语言，编写此程序。 ;编写过程中，主要的困难来自于scheme的side-effect （即副作用），一度出些莫名其妙的结果，让我快要崩溃，以下是当时随意写下的一些过程。 ;vector-set!()的使用引入了副作用。 ;快崩溃了，exchange有问题，但不知道是什么问题。难道还是因为side-effect?看来是的，只能不用引起side-effect的东西了。 ;还是不明白到底那里有问题，每个函数看来都没错。 ;每此运行结果后来为什么都是整数的平均适应度？除非每次突变对所有染色体造成同样结果。但为什么会这样呢？ ;select 和exchange或 mutate结合后就造成了这样的问题，他们本身都没有问题。 ;真的不明白是什么问题了，难道还是因为side-effect?也只有这种可能了。 ;2008/11/29, 重新编写exchang()和mutate()，全部去除side-effect，只使用函数返回值，终于成功了！ ;程序如下： ;;初始化一个向量，其值为随机0,1。作为一个染色体的表示。 (define (gen-chromosome n) (cond ((= n 0) '()) (else (cons (random 2) (gen-chromosome (- n 1)))))) ;生成染色体组，以list形式；num为染色体数，leng为每个染色体长度。 (define (gen-chroms num leng) (cond ((= num 0) '()) (else (cons (gen-chromosome leng) (gen-chroms (- num 1) leng))))) ;生成染色体组，共4个染色体，长度为8。 ;(define Chroms (gen-chroms 4 8)) ;计算染色体组的适应度，以和为适应度。 (define (cal-fitness chroms) (map (lambda (x) (apply + x)) chroms)) ;计算染色体组平均适合度 (define (cal-average-fitness chroms) (/ (apply + (cal-fitness chroms)) (length chroms))) ;;子代染色体选择,按概率选择最适应的 ;选择函数,从一组染色体chroms中按照各染色体适应值values的大小，随机选取一个染色体。 (define (comp rand values chroms) (cond ((null? chroms) '()) (( rand (car values)) (car chroms)) (else (comp (- rand (car values)) (cdr values) (cdr chroms))))) ;随机选择函数，从染色体组中选取一次，得到一个子代。 (define (select-once values chroms) (let ((rand (random (apply + values)))) (comp rand values chroms))) ;总的选择函数,选择多次，使子代与父代有同样多的染色体，生成子代染色体,子代染色体独立于父代。 (define (select chroms) (let ((values (cal-fitness chroms)) (leng (length chroms))) (letrec ((sel (lambda (count values_ chroms_) (cond ((= count 0) '()) (else (cons (select-once values_ chroms_) (sel (- count 1) values_ chroms_))))))) (sel leng values chroms))));count的初始值为leng. ;;;; ;;交换,由于之前的选择是随机的，只要相邻的两个染色体交换即可。 ;;但是交换问题有点复杂，包括交换概率，交换位点选择。 ;先写一个函数可以起类似list-tail功能，但提取的是前面部分。其功能与list-tail互补。 (define (list-head lis n) (cond (( n 0) (cond ((pair? lis) (cons (car lis) (list-head (cdr lis) (- n 1)))) (else 'error))) (else '()))) ;list-head 功能演示： ;guile (let ((lis '(1 2 3 4)) ; (n 2)) ; (append (list-head lis n) (list-tail lis n))) ;(1 2 3 4) ;没有副作用的determ-exchange。ch1，ch2表示两个染色体，locus为位点。 (define (determ-exchange ch1 ch2 locus) (cond ((null? ch1) '()) ( (or ( locus 0) ( locus (length ch1))) locus impropor.) (else (list (append (list-head ch1 locus) (list-tail ch2 locus)) (append (list-head ch2 locus) (list-tail ch1 locus)))))) ;给定概率和随机位点的交换,交换概率为p。 (define (rand-exchange p ch1 ch2) (cond (( p (random 1.0)) ;达到交换概率时发生交换 (let ((locus (random (length ch1)))) (determ-exchange ch1 ch2 locus))) (else (list ch1 ch2)))) ;否则不发生交换 ;我们所需要的交换函数,染色体组内的各相邻染色体两两进行rand-exchange,并重新连成一个染色体组list. (define (exchange p chrom) (cond ((null? chrom) '()) ((null? (cdr chrom)) '());防止染色体组含单数个染色体的情况。 (else (append (rand-exchange p (car chrom) (cadr chrom)) (exchange p (cddr chrom)))))) ;; ;;突变,每个染色体都有一个概率在某个位点发生突变。跟交换差不多，但简单些。 ;首先是固定位点的突变，定义一个无副作用的determ-mutate函数。ch表示染色体，locus为位点。 (define (determ-mutate ch locus) (cond ((null? ch) '()) ((or ( locus 0) ( locus (- (length ch) 1))) error) (else (append (list-head ch locus ) (cons (random 2) (list-tail ch (+ 1 locus))))))) ;然后给定概率的随机位点突变 (define (rand-mutate p ch) (cond (( p (random 1.0)) (let ((locus (random (length ch)))) (determ-mutate ch locus))) (else ch))) ;我们所需要的突变函数。 (define (mutate p chroms) (cond ((null? chroms) '()) (else (cons (rand-mutate p (car chroms)) (mutate p (cdr chroms)))))) ;OK,所有准备都完成，写最后的函数。 ;genetic函数表示整个遗传算法，两个参数：n为算法迭代次数，chroms为初始染色体组。 (define (genetic n chroms) (cond (( n 0) (begin (display (cal-average-fitness chroms)) (display ) (genetic (- n 1) (mutate 0.02 (exchange 0.6 (select chroms)))))) (else '()))) ;进行演示。 (let ((K (gen-chroms 20 10))) (genetic 50 K))

个人分类: 计算机|6684 次阅读|0 个评论

遗传算法简介

kinglandom 2008-11-21 19:25

遗传算法是计算数学中用于解决最优化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。遗传算法通常实现为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）的抽象表示（称为染色体）的种群向更好的解进化。传统上，解用二进制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中，整个种群的适应度被评价，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。遗传算法的机理算法种群规模(P,population size)：即种群中染色体个体的数目。字串长度(l, string length) 交叉概率(pc, probability of performing crossover)：控制着交叉算子的使用频率。交叉操作可以加快收敛，使解达到最有希望的最优解区域，因此一般取较大的交叉概率，但交叉概率太高也可能导致过早收敛。变异概率(pm, probability of mutation)：控制着变异算子的使用频率。中止条件(termination criteria) GA参数遗传算法在解决优化问题过程中有如下特点：遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优。对于动态数据，用遗传算法求最优解比较困难，因为染色体种群很可能过早地收敛，而对以后变化了的数据不再产生变化。对于这个问题，研究者提出了一些方法增加基因的多样性，从而防止过早的收敛。其中一种是所谓触发式超级变异，就是当染色体群体的质量下降（彼此的区别减少）时增加变异概率；另一种叫随机外来染色体，是偶尔加入一些全新的随机生成的染色体个体，从而增加染色体多样性。选择过程很重要，但交叉和变异的重要性存在争议。一种观点认为交叉比变异更重要，因为变异仅仅是保证不丢失某些可能的解；而另一种观点则认为交叉过程的作用只不过是在种群中推广变异过程所造成的更新，对于初期的种群来说，交叉几乎等效于一个非常大的变异率，而这么大的变异很可能影响进化过程。遗传算法很快就能找到良好的解，即使是在很复杂的解空间中。遗传算法并不一定总是最好的优化策略，优化问题要具体情况具体分析。所以在使用遗传算法的同时，也可以尝试其他算法，互相补充，甚至根本不用遗传算法。遗传算法不能解决那些大海捞针的问题，所谓大海捞针问题就是没有一个确切的适应度函数表征个体好坏的问题，遗传算法对这类问题无法找到收敛的路。对于任何一个具体的优化问题，调节遗传算法的参数可能会有利于更好的更快的收敛，这些参数包括个体数目、交叉律和变异律。例如太大的变异律会导致丢失最优解，而过小的变异律会导致算法过早的收敛于局部最优点。对于这些参数的选择，现在还没有实用的上下限。适应度函数对于算法的速度和效果也很重要。特点最简单的遗传算法将染色体表示为一个数位串，数值变量也可以表示成整数，或者实数（浮点数）。算法中的杂交和突变都是在字节串上进行的，所以所谓的整数或者实数表示也一定要转化为数位形式。例如一个变量的形式是实数，其范围是0～1，而要求的精度是0.001，那么可以用10个数位表示：0000000000表示0，1111111111表示1。那么0110001110就代表0.389。在遗传算法里，精英选择是一种非常成功的产生新个体的策略，它是把最好的若干个个体作为精英直接带入下一代个体中，而不经过任何改变。通过并行计算实现遗传算法一般有两种，一种是所谓粗糙并行遗传算法，即一个计算单元包含一个种群；而另一种是所谓精细并行遗传算法，每一个计算单元处理一个染色体个体。遗传算法有时候还引入其他变量，例如在实时优化问题中，可以在适应度函数中引入时间相关性和干扰。变量遗传算法擅长解决的问题是全局最优化问题，例如，解决时间表安排问题就是它的一个特长，很多安排时间表的软件都使用遗传算法，遗传算法还经常被用于解决实际工程问题。跟传统的爬山算法相比，遗传算法能够跳出局部最优而找到全局最优点。而且遗传算法允许使用非常复杂的适应度函数（或者叫做目标函数），并对变量的变化范围可以加以限制。而如果是传统的爬山算法，对变量范围进行限制意味着复杂的多的解决过程，这方面的介绍可以参看受限优化问题和非受限优化问题。适用的问题遗传算法由密歇根大学的约翰霍兰德和他的同事于二十世纪六十年代在对细胞自动机（英文：cellular automata）进行研究时率先提出。在二十世纪八十年代中期之前，对于遗传算法的研究还仅仅限于理论方面，直到在伊利诺伊大学召开了第一届世界遗传算法大会。随着计算机计算能力的发展和实际应用需求的增多，遗传算法逐渐进入实际应用阶段。1989年，纽约时报作者约翰马科夫写了一篇文章描述第一个商业用途的遗传算法--进化者（英文：Evolver）。之后，越来越多种类的遗传算法出现并被用于许多领域中，财富杂志500强企业中大多数都用它进行时间表安排、数据分析、未来趋势预测、预算、以及解决很多其他组合优化问题。发展历史工业工程与运作管理物流系统设计生产调度制造系统控制系统优化设计汽车设计，包括材料选择、多目标汽车组件设计、减轻重量等。机电系统设计。分布计算机网络的拓扑结构。电路设计，此类用途的遗传算法叫做进化电路。电子游戏设计，例如计算平衡解决方案。机器智能设计和机器人学习。模糊控制系统的训练。移动通讯优化结构。时间表安排，例如为一个大学安排不冲突的课程时间表。旅行推销员问题. 神经网络的训练，也叫做神经进化。应用领域遗传程序是约翰Koza与遗传算法相关的一个技术，在遗传程序中，并不是参数优化，而是计算机程序优化。遗传程序一般采用树型结构表示计算机程序用于进化，而不是遗传算法中的列表或者数组。一般来说，遗传程序比遗传算法慢，但同时也可以解决一些遗传算法解决不了的问题。交互式遗传算法是利用人工评价进行操作的遗传算法，一般用于适应度函数无法得到的情况，例如，对于图像、音乐、艺术的设计和优化，或者对运动员的训练等。模拟退火是解决全局优化问题的另一个可能选择。它是通过一个解在搜索空间的随机变动寻找最优点的方法：如果某一阶段的随机变动增加适应度，则总是被接受，而降低适应度的随机变动根据一定的概率被有选择的接受。这个概率由当时的退火温度和适应度恶化的程度决定，而退火温度按一定速度降低。从模拟退火算法看，最优化问题的解是通过寻找最小能量点找到的，而不是寻找最佳适应点找到的。模拟退火也可以用于标准遗传算法里，只要把突变率随时间逐渐降低就可以了。

个人分类: 理论探索|6101 次阅读|2 个评论

帐号		自动登录	找回密码
密码			注册

关闭安全验证

标签: 遗传算法

相关帖子

相关日志

关闭 安全验证

标签: 遗传算法

相关帖子

相关日志

关闭安全验证