英式风情茶
共3条回答285浏览
-
-
遗传算法GA 遗传算法： 旅行商问题(traveling saleman problem,简称tsp)：已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？用图论的术语来说，假设有一个图 g=(v,e)，其中v是顶点集，e是边集，设d=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。这个问题可分为对称旅行商问题(dij=dji,,任意i,j=1,2,3，…,n)和非对称旅行商问题(dij≠dji,,任意i,j=1,2,3，…,n)。若对于城市v={v1,v2,v3,…,vn}的一个访问顺序为t=(t1,t2,t3,…,ti,…,tn),其中ti∈v(i=1,2,3,…,n)，且记tn+1= t1，则旅行商问题的数学模型为：min l=σd(t(i),t(i+1)) （i=1,…,n）旅行商问题是一个典型的组合优化问题，并且是一个np难问题，其可能的路径数目与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法求其近似解。遗传算法：初始化过程：用v1,v2,v3,…,vn代表所选n个城市。定义整数pop-size作为染色体的个数，并且随机产生pop-size个初始染色体，每个染色体为1到18的整数组成的随机序列。适应度f的计算：对种群中的每个染色体vi，计算其适应度，f=σd(t(i),t(i+1)).评价函数eval(vi)：用来对种群中的每个染色体vi设定一个概率，以使该染色体被选中的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被选择产生后台的机会要大，设alpha∈(0,1)，本文定义基于序的评价函数为eval(vi)=alpha*(1-alpha).^(i-1) 。[随机规划与模糊规划]选择过程：选择过程是以旋转赌轮pop-size次为基础，每次旋转都为新的种群选择一个染色体。赌轮是按每个染色体的适应度进行选择染色体的。step1 、对每个染色体vi,计算累计概率qi，q0=0;qi=σeval(vj) j=1,…,i;i=1,…、从区间(0,pop-size)中产生一个随机数r；step3、若qi-1
class Graph{ public: Graph(int vertices=10) { n=vertices; e=0; } ~Graph(){} virtual bool Add(int u,int v,const T& w)=0; virtual bool Delete(int u,int v)=0; virtual bool Exist(int u,int v)const=0; int Vertices()const{return n;} int Edges()const{return e;} protected: int n; int e;};template class MGraph:public Graph { public: MGraph(int Vertices=10,T noEdge=0); ~MGraph(); bool Add(int u,int v,const T& w); bool Delete(int u,int v); bool Exist(int u,int v)const; void Floyd(T**& d,int**& path); void print(int Vertices); private: T NoEdge; T** a;};template MGraph ::MGraph(int Vertices,T noEdge){ n=Vertices; NoEdge=noEdge; a=new T* [n]; for(int i=0;i ::~MGraph(){ for(int i=0;i ::Exist(int u,int v)const{ if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==NoEdge)return false; return true;}template bool MGraph ::Add(int u,int v,const T& w){ if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]!=NoEdge){ cerr<<"BadInput!"< :delete(int u,int v){ if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==NoEdge){ cerr<<"BadInput!"< ::Floyd(T**& d,int**& path){ d=new T* [n]; path=new int* [n]; for(int i=0;i ::print(int Vertices){ for(int i=0;i b(vertices,noEdge); cout<<"请输入u,v,w:"<
-
-
-
目录摘要IAbstractII引言1第一章基本遗传算法遗传算法的产生及发展基本原理遗传算法的特点基本遗传算法描述遗传算法构造流程6第二章遗传算法的实现技术编码方法二进制编码格雷码编码符点数编码参数编码适应度函数选择算子交叉算子单点交叉算子双点交叉算子均匀交叉算子部分映射交叉顺序交叉变异算子运行参数约束条件的处理方法遗传算法流程图14第三章遗传算法在TSP上的应用问题的建模与描述对TSP的遗传基因编码方法针对TSP的遗传操作算子选择算子轮盘赌选择最优保存策略选择交叉算子单点交叉部分映射交叉变异算子的混和遗传算法26第四章实例分析测试数据测试结果结果分析27摘要TSP(TravelingSalesmanProblem)旅行商问题是一类典型的NP完全问题，遗传算法是解决NP问题的一种较理想的方法。文章首先介绍了基本遗传算法的基本原理、特点及其基本实现技术；接着针对TSP问题，论述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子变异算子这三种算子）等方面的应用情况，分别指出几种常用的编码方法的优点和缺点，并且结合TSP的运行实例详细分析了基本遗传算法的4个运行参数群体大小、遗传算法的终止进化代数、交叉概率、变异概率，对遗传算法的求解结果和求解效率的影响，经过多次的测试设定出了它们一组比较合理的取值。最后，简单说明了混合遗传算法在求解TSP问题中的应用并对遗传算法解决TSP问题的前景提出了展望。关键词：TSP遗传算法遗传算子编码@@@需要的话按我的名字找我吧
-
-
-
寂寞开无主，零落碾作尘——孟德尔和他的遗传理论1965年夏天的一个傍晚，在捷克布尔诺的摩拉维亚镇的一座教堂里，曾举行过一次盛大的纪念会。参加这次纪念会的大部分人并非教徒，而是应捷克科学院邀请而来的各国遗传学家。他们怀着崇敬而又惋惜的心情来纪念一位为遗传学奠定了基础，而其成果又被埋没35年之久的伟大生物学家。他就是格里戈．孟德尔神父。1965年是他的研究成果发表一百周年。 孟德尔其人 孟德尔（G．J．Mendel，1822－1884）出生于奥地利摩亚维亚的海因申多夫村。现今这个地方是捷克境内的海因西斯村。孟德尔的父亲是个农民，素性酷爱养花。因此，孟德尔自幼养成了养花弄草的兴趣。这也许是这位科学家后来在豌豆实验上成名的一个最初的契机吧。 孟德尔的童年不但平常，且有些寒苦。整个小学可以说是在半饥半饱中念完的。中学毕业后，主要靠妹妹准备作嫁妆的钱，读了欧缪兹学院的哲学系。大学毕业后，21岁的孟德尔在老师的建议下，进了设在鄂尔特伯伦的奥古斯丁派的修道院当了一名修士，取了一个教名叫格里戈。25年后被选为该修道院院长。 如果说童年的孟德尔是在贫寒中度过的，那么青年的孟德尔则饱历了生活道路的坎坷。孟德尔不满意于修道院的单调、古板的修士生活，兼任了布尔诺一所实验学校代课教师的职务。他曾两次申请转为正式教师，但经考试的均名落孙山。特别令人气愤的是，在第二次考试中，主考官竟这样来评论他的考卷说：“这次的考卷使我们认为，该生连作为初等学校的老师也不够格”。在这期间他还到维也纳大学旁听了植物生理学、数学和物理学等课程。 好学勤奋和充满进取的孟德尔，考试落榜后，便在修道院的花园里从事植物杂交的研究工作。他的成果只发表了很小一部分。除了死后使他成名的《植物杂交实验》（1865）外，还有《人工授粉得到的山柳菊属的杂种》（1870）和《1870年10月13日的旋风》（1871）。 孟德尔的晚年，可说是在愁云惨雾中度过的。他孑身一个，无妻无子，孤苦令仃。又因拒绝缴纳当局对修道院征收的一笔税金，而遭受着与当局僵持之苦。学志未酬而又愤懑填膺的孟德尔，终于于1884年1月6日因患肾炎不治而与世长辞，享年只有62岁。当人们吊唁这位少年清贫，中年研究成果遭冷遇，晚年孤独悲惨的老人时，谁也未想到他是一位在科学史上留下峥嵘篇章的伟大科学家。 孟德尔的业绩 孟德尔开始研究植物杂交工作，所用的实验材料是豌豆。他选用了22个豌豆品种，按种子的外形是圆的还是皱的，子叶是黄的还是绿的……等特征。把豌豆分成了7对相对的性状。然后，按一对相对性状和两对相对性状，分别进行了杂交实验，得到了如下的一些结果。 一对相对性状的杂交实验孟德尔通过人工授粉使高茎豌豆跟矮茎豌豆互相杂交。第一代杂种（子1代）全是高茎的。他又通过自花授粉（自交）使子1代杂种产生后代，结果子2代的豌豆有3／4是高茎的，1／4是矮茎的，比例为3：1。孟德尔对所选的其它6对相对性状，也一一地进行了上述的实验，结果子2代都得到了性状分离3：1的比例。 两对相对性状的杂交实验孟德尔又用具有两对相对性状的豌豆作了杂交实验。结果发现，黄圆种子的豌豆同绿皱种子的豌豆杂交后，子1代都是黄圆种子；子1代自花授粉所生的子2代，出现4种类型种子。在556粒种子里，黄圆、绿圆、黄皱、绿皱种子之间的比例是9：3：3：1。 通过上述实验材料，孟德尔天才地推出了如下的遗传原理。 1．分离定律。孟德尔假定，高茎豌豆的茎所以是高的，是因为受一种高茎的遗传因子（DD）来控制。同样，矮茎豌豆的矮茎受一种矮茎遗传因子(dd)来控制。杂交后，子1代的因子是Dd。因为D为为性因子，d为隐性因子，故子1代都表现为高茎。子1代自交后，雌雄配子的D，d是随机组合的，因此子1代在理论上应有大体相同数量的4种结合类型：DD，Dd，dD，dd。由于显性隐性关系，于是形成了高、矮3：1的比例。孟德尔根据这些事实得出结论：不同遗传因子虽然在细胞里是互相结合的，但并不互相掺混，是各自独立可以互相分离的。后人把这一发现，称为分离定律。 2．自由组合定律。对于具有两种相对性状的豌豆之间的杂交，也可以用上述原则来解释。如设黄圆种子的因子为YY和RR，绿皱种子的因子为yy和rr。两种配子杂交后，子1代为YyRr，因Y，R为显性，y，r为隐性，故子1代都表现为黄圆的。自交后它们的子2代就将有16个个体，9种因子类型。因有显性、隐性关系，外表上看有4种类型：黄圆、绿圆、黄皱、绿皱，其比例为9：3：3；1。根此孟德尔发现，植物在杂交中不同遗传因子的组合，遵从排列组合定律，后人把这一规律称为自由组合定律。 孟德尔的发现被埋没 孟德尔从1856年开始，经过8个的专心研究，得出了上述两上定律并写成一篇题为《植物杂交实验》的论文。在好友耐塞尔（一个气象学家）的鼓励的支持下，他于1865年2月8日和3月8日举行的布尔诺学会自然科学研究会上，报告了这一论文。与会者很有兴致地听取了他的报告，但大概并不理解其中的内容。因为既没有人提问题，也没有人进行讨论。不过该会还是于1866年在自己的刊物《布尔诺自然科学研究会会报》上全文发表了这篇论文。 曾一个时期，人们以为孟德尔的工作被埋没，是由于当时学术情报囿闭不通，交流不广，人们不知道他的工作造成的。后经调查，才知情况并非如此。原来该学会至少同120个协会或学会研究会有交流资料关系。刊载孟文的杂志，共寄出115本。其中，当地有关单位12本，柏林8本，维也纳6本，美国4本，英国2本（英国皇家学会和林耐学会）。孟德尔本人还往外寄送过该论文的抽印本。迄今有据可查的至少有5个人了解他的工作。第一个是耐格里。他是19世纪著名的植物学家。他的研究对解剖学、生理学、分类学和进化论的发展，有一定的推动作用。在植物学方面，他是心柳菊属方面的权威。孟德尔不仅把自己的论文寄给了他，且还给他写过进一步说明论文的长信。第二个是A．凯尔纳。他曾在因斯布罗克任教授，在维也纳植物园当主任。第三个是H．霍夫曼，一位植物学教授。第四个是威廉．奥尔勃斯．福克，他是植物杂交方面的权威。第五个是俄国的施马尔豪森。但是，刊物也好，论文也好，都如石沉大海，没有得到明显的反响。这样，孟德尔的为遗传学奠定了基础的、具有划时代意义的发现，竟被当代人们所忽视和遗忘，被埋没达35年之久。 1900年，对孟德尔盖棺后成名具有重要意义。这一年，有三人几乎同时重新作出了孟德尔那样的发现。第一个是德弗里期，他于1900年3月26日发表了同孟德尔的发现相的的论文；第二个人是科仑斯，收到他论文的时间是1900年4月24日；第三个人是丘歇马克，收到他论文的时间为1900胪6月20日。也就是在这一年里，他们也都发现了孟德尔的论文。这时，他们才清楚，原来自己的工作，早在35年前就由孟德尔做过了。 对孟德尔发现被埋没的原因分析 有不少生物史学家。对这一问题很感兴趣，也曾进行了一些调查。但因事情发生已年深日久，有确凿证据的材料所得无几，尤其关系到人们心理方面的活材料更难以到手。现据已有材料作如下分析： 历史的局限性 1866年孟德尔发表自己的论文时，正值达尔文的《物种起源》发表的第七个年头。这期间各国的生物学家，特别是著名生物学家都把兴趣转到了生物进化问题上，而物种杂交问题自然就不是人们瞩目的中心问题了。“这一事实也许对孟德尔的工作所遭到的命运，起到了更为决定性的作用”。其次，由于历史条件的限制，当时学术资料不能广泛地交流也是一个原因。如，对杂交问题搜集资料较多的达尔文，就没有看到过孟德尔的论文。虽然也有人说，即使达尔文看到了这一成果，也不一定能充分地认识到它的意义。但，这样推论是没有多大根据的。又如，了解孟德尔工作的俄国的施马尔豪森，他本来在自己学位论文的历史部分加了一个附注，正确地评价了孟德尔的工作。但遗憾的是，当1875年《植物区系》杂志发表他的论文译本时，删去了加有评价孟德尔工作的附注。这样，就又减少了后人了解孟德尔工作的机会。 怀疑以至完全不相信这是一项新发现孟德尔发表他的新发现时，当时只是一名普普通通的修士。至于他从事植物杂交的研究，只被人们看作“不过是为了消遣，他的理论不过是一个有魅力的懒汉的唠叨罢了”。的确，在一个专业学者的眼里，他还够不上一名地道的生物学家。因为他既没有生物学专业的学历，也没有博士、教授的头衔。因此，他的具有挑战性的发现，自然不易被人们所相信。从已知的少数几个看过他论文的人的反映和态度看，怀疑以至不相信孟德尔这个小人物能有什么新发现，乃是忽视他成果的一个和重要原因。当时了解孟德尔最多的是生物学家耐格里。孟德尔跟他素来关系甚密，相互交往达七年之久，孟德尔常同他交换种子。他也是读过孟文的第一个人。然而，正是由于他不仅没有正确地认识孟德尔的工作，而且还提出种种怀疑和责难，从而成为这桩遗憾后世的科学蒙难案的重要原因。现已查到，他看过孟德尔论文后，于1866年12月31日给孟德尔的复信。从中可以确凿地看到他是怎样地怀疑、责难以至忽视了孟的工作。他在信中说：“我认为，你用豌豆属作的实验还远远没有完成，其实还只是个开端。……能为最重要的结论提出无可争辩的证明的这样一套试验，决不是已在着手进行了。……你打算在你的试验中包括其他植物，这是很好的，我相信，从其他品种中会得到完全不同的结果（就遗传性而言）”。他还怀疑孟德尔得出的3：1的规律。如他说：“你应当把数量的表现看作仅仅是经验的理象，因为它们还不能被证明是合理的”。在耐格里看来，“只有那些在最模糊的专业领域能够作出正确判断的人，才能探究这个问题”。另一个了解孟德尔工作的A．凯尔纳，接到孟德尔寄送的论文后，曾给孟德尔写过复信。但据凯尔纳的助手说，孟德尔的论文在凯尔纳的图书室中压根就没有拆过封。人们是否可以推论：在凯尔纳的眼中，像孟德尔这样的小人物的文章，简直是不屑一顾的。 不理解其成果的重要意义 孟德尔的发现本身，在一定程度上超出了当时的流行观念。在当时，传统的遗传学观点是融合遗传理论，而孟德尔的思想则是粒子遗传；其次，当时在生物学领域主要的研究方法是定性的观察和实验，而孟德尔用的是定量的数学统计分析。所以，即使是认真地看过他的文章，如果跳不出传统框框，也不一定能理解其重要意义。如H．霍夫曼不仅看过他的文章，而且在自己的著作中，五处引用了孟德尔的文章，但现在看来，不是没有引到重要的地方，就是有所误解，总之，没有真正理解孟德尔工作的意义。所以，在霍夫曼的书中完全忽视了孟德尔的贡献。福克也曾多次提到孟德尔的成果，但他说：“孟德尔所作的很多次杂交的结果，十分类似于奈特的结果，但孟德尔自以为发现了各种杂种类型之间稳定的数量关系”。他所否定的正是孟德尔的成功之处，说明他根本不理解孟德尔发现的意义。他的提到孟德尔，不过是因为孟德尔培育成了植物杂种，不得不得一下而已。 教训和启示 埋没孟德尔发现一案，已经过去一百多年了。今天，孟德尔在科学史上的地位及其光辉业绩已被充分肯定，以他的成果为基础的遗传学也已取得辉煌胜利。然而，我们不应忘记，忽视孟德尔发现的代价是沉重的，它也许使生物学的发展延缓了几十年。难道我们不应从中悟出应有的教训，找出以古鉴今的富有启发性的道理，以便今后不犯或少犯同类错误吗？ 警惕传统观念的束缚 有些人认为孟德尔的发现是早产儿，它超越了时代的认识水平，因此被埋没是必然的。然而，我们却认为，孟德尔的发现不被理解从而导致被埋没，主要应归咎于传统观念的束缚。理由是，孟德尔的课题当时已经摆到了人拉的面前。至少有向个人的工作接近于孟德尔的结论（参阅斯多倍《遗传学史》，第126－138页，第189页），其中甚至包括人所共知的达尔文，他关于金鱼草的杂交实验距离孟德尔的结论只差一小步。这充分说明，孟德尔的发现决非偶然的早产儿，而是具备成熟的历史条件的。上述几个人和看过孟德尔论文的人，之所以没有作出孟德尔那样的结论和没有认识到其意义，主要因为他们没有冲破传统观念的束缚和跳出传统的定性方法的局面。而孟德尔的成功，正由于他的老框框少些，所以才有可能冲破当时的研究方法和流行的
-
