基于遗传算法的课程安排优化设计

南京师范大学

毕业设计（论文）

（届）

题目：基于遗传算法的课程安排优化设计

学院：

专业：

姓名：

学号：

指导教师：

南京师范大学教务处制

摘要

课程表规划问题是一个NP 完全问题，其规划策略可以通过多种方法实现，一般启发式搜索算法是通过在全局区间找到可行结果，通常适合于简单的例子，对于多参数输入和结果要求，寻找一个相当好的解决方案可能需要耗费很多时间，甚至是不可能的。遗传算法(GAs) 是基于启发式方法的种群，该方法已经成功应用于人工智能、搜索和优化的各个领域，遗传算法的原理是由Holland设计并进行开发的，遗传算法具有以下特性：（1）从种群中选择个体的机制;（2）创造新个体的运算;（3）通过将以前的单个方案随机打乱，生成新解决方案的过程（4）更新个体的规则，这些特性分别被称为选择，杂交，变异，更新。本论文拟将遗传算法应用于课程表的多参数优化，寻找满足约束条件的课程规划。

关键字：课程表规划，遗传算法，选择，杂交，变异，更新

Abstract

Making a class schedule is one of those NP-complete problems which can be solved by many methods. The normal heuristic search algorithm finds the optimal solution based local search procedure, but it only works for simple cases. For more complex inputs and requirements, finding a considerably good solution can take a while, or it may be impossible. Genetic algorithms (GAs) are population based heuristic approaches. They have been applied successfully in various domains of artificial intelligence, search, and optimization. The promising results were obtained for many difficult optimization problems. The principles of GAs were developed by Holland .Very briefly, GAs can be characterized by the following features: (1) a mechanism for selecting individuals from the population; (2) an operator for creating new individuals; (3) a procedure for generating new solution by random perturbations of the single previous solutions; (4) a rule for updating the population. These features are referred to as selection, crossover, mutation, and updating. In this paper, GAs will be applied to optimizing the multi-parameter of schedule and searching the schedule which satisfies the requirements .

Key words: class schedule planning，genetic algorithms，selection，crossover，mutation，updating.

目录

摘要 (1)

Abstract (2)

第一章绪论 (4)

1.1研究目的及意义 (4)

1.2研究现状 (4)

1.3研究内容 (4)

第二章排课问题研究的概述 (5)

2.1课程表问题的描述 (5)

2.1.1 时间表问题概述 (5)

2.1.2 课程表问题概述 (5)

2.2大学课程表问题的研究情况 (6)

2.2.1 大学课程表问题的理论研究 (6)

2.2.2 大学课程表问题解决方法 (6)

2.3排课的各种算法的比较 (7)

第三章课程表的类对象 (9)

3.1课程表的类对象 (9)

3.2Chromosome 染色体 (9)

3.2.1 Representation 表示 (9)

3.2.2 Fitness 适应度 (10)

3.2.3 Crossover 杂交 (11)

3.2.4 Mutation 突变 (12)

第四章基于遗传算法的课程规划 (12)

4.1遗传算法的来源和研究发展 (12)

4.2具体操作 (13)

4.3课表观察员 (15)

4.4配置 (16)

4.4.1 配置文件 (16)

4.4.2 配置文件的例子 (17)

4.4.3 解析一个配置文件 (18)

4.5程序运行示意图 (19)

第五章结论 (21)

致谢 (22)

参考文献 (23)

第一章绪论

1.1研究目的及意义

排课问题的本质是将课程、教师和学生在合适的时间段内分配到合适的教室中，涉及到的因素较多，是一个多目标的调度问题，即NP（Nondeterministic Polynomial，非确定的多项式）完全问题。NP-完全问题的简单与否，取决于问题的难易程度，只能用启发式算法找出最优解。然而这种算法太慢了，根本无法在计算机上实现。因此众多研究者提出了多种其他排课算法，如模拟退火、禁忌搜索、进化算法等。其中，遗传算法(Genetic Algorithm, 简称GA)是很有效的求最优解的算法。

本课题的主要目的是通过综合研究、分析现有的排课优化的解决方法，实现基于遗传算法的自动排课优化。

本课题的研究意义在于，实现基于遗传算法的排课优化问题，可以提高优化的满意度和灵活度。实践证明，这种算法设计得出的课程安排可以达到了师生的高度满意。

1.2研究现状

大学课程表问题（University Timetable Problem-UTP）或者时间表问题（Time Table Problem-TTP）是一个一直困扰各个学校的令人头疼问题，它是运筹学典型的组合优化问题之一。教师，教室，时间，课程和班级是五个制约该问题解决的重要因素。

19世纪60年代，开始有学者从事计算机辅助排课的研究，Appleby等人开始使用简单的经验法，来解决小规模的排课问题。

遗传算法是由美国芝加哥大学Holland教授于1975年所提出。其基本观念源自于达尔文的进化论（Darwin's Theory of Evolution）中适者生存的理论，是一种通过模拟自然界生物进化过程求解极值的自适应人工智能技术。遗传算法借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制来提高各个个体的适应性，体现了自然界中“物竞天择、适者生存”的进化过程。

1975年，经过对该问题进行证明，S.Even提出它是一个NP完全问题。这意味着普通的方法比如图着色，整数规划，对复杂的学校排课问题并不能进行良好的解决。

从70年代到90年代，有些学者开始了利用矩阵向量方法来对排课问题进行研究，能够解决规模稍大的问题，但是仍然存在缺陷。

到了90年代后，国内外很多学者转而采用遗传算法对排课问题进行了研究，随着遗传算法的发展，有了一定的结果，但是仍然未能解决满意度的问题。

1.3研究内容

第一步：了解遗传算法的概念及其对于排课优化的重要意义。

第二步：研究现有的排课优化方案及存在问题。

第三步：利用遗传算法建立数学模型，定义染色体编码方案和适应度函数。

第四步：通过初始化种群、选择、交叉、变异等过程不断进化，最后得到最优解。

第五步：结果分析及其优化。

第二章排课问题研究的概述

2.1课程表问题的描述

2.1.1 时间表问题概述

时间表问题（Time Table Problem）既是一个理论方面的问题也是一个来源于实践的问题，它是实际生活中人们可以遇到的问题，甚至对于我们来说很常见。比如说交通时间表问题[11][12]（transportation Timetabling)，这个问题是如何设计城市中公交车或者有轨电车的时间表问题,使其能够良好的运行，减缓城市交通的压力；比赛时间表问题[13](employee timetabling)是如何设计一项大型赛事的时间表，来保证大型赛事能够良好的进行；还有雇员工作时间表问题(employee timetabling)，研究得是如何来安排雇员的工作，使其工作能够达到最高的效率；当然还有我们要研究的大学课程表问题，这个问题研究的主要目的是提出一种优秀的算法最大程度上使学校课程安排人性化、合理化。

时间表问题是一类具有多约束的将有限时间资源分配给多个事件组合优化问题。通常，一个时间表问题会有一系列事件(event)和一组有限的时空单元(time-space slot)和一组具体地点，并且还要受到一系列约束的限制，这些约束又分为硬约束和软约束。硬约束就是我们在进行时间表安排的情况下必须无条件满足的一系列限制，不能有任何违反，而软约束也是一系列的限制，但是我们不一定要全部满足，但是这些软约束的满足情况却决定了我们时间表安排的合理情况。

当你排一个课程表时，你必须考虑很多要求（教授、学生、班级和教室的数目，教室的大小，教室里的实验器材等等）。这些需求可通过其重要性被分成若干组。

硬约束（如果你不能解决其中一个，这个排课计划就是不可行的）：

●一个班级只能放在一个空教室里

●没有教授和学生可以在同一时间上一门以上的课

●一个教室要有足够的位子安排所有的学生

●如果要在一个教室排课，此教室要有这门课程所需要的设备（例如电脑）

软约束（即使不能解决，计划仍是可行的）

●一些教授对上课时间的偏好

●一些教授对上课地点的偏好

●学生或教授的在时间和地点上的班级分配

当然，硬的和软的约束取决于有关情况。在这个程序中，只有硬约束落到了实处。2.1.2 课程表问题概述

本文主要研究的是时间表问题中的课程表问题。这个问题是来源于学校日常生活，和学生的日常生活息息相关。随着学校规模扩大，学生的数量急剧增加，学校的教育资源显得越来越有限，这个问题就显得越发突出。所以对这个问题的研究具有现实意义，但是它又不缺乏理论性，1975年，S.Even对该问题进行了研究，并指出大学课程表问题是一个NP完全问题，这就说明了该问题没有真正意义上的最优解，人们的求解只有

可能是相似最优解，也就是说求解获得的答案只可能不断接近最优解，但是不可能是最优解。于是人们就尝试用各种方法去解决这个问题，如图着色、分支定界、整数规划等，经过实践证明，遗传算法和模拟退火算法是两种解决该问题比较理想的方法。本文在后面主要介绍了遗传算法。

那什么是课程表问题？虽然已经从感性上已经了解了这个问题，但是下面将给出一个较为严格的定义方便深入理性的理解这个问题。Carter和Laporte这样定义：“课程表问题是一个多元分配问题，它研究的就是如何把学生和老师分配给课程，课程单元或者班级，如何把事件（上课事件）分配给教室和时间”。

简单一些的说大学课程表问题研究的就是如何把一系列的课程分给有限的教室和

一周内有限的上课时间单元，如何把学生和老师分配给课程。当然实际研究的时候并没有理论上说得这么简单，它会受到多种约束的影响，有硬约束也有软约束，这我们在上一小节已经提到了。

2.2大学课程表问题的研究情况

2.2.1 大学课程表问题的理论研究

大学课程表问题在20世纪50年代末就已经开始被人们所重视，将它作为一个科学问题来研究，但是一直到1963年才由Gotlieb提出了该问题的数学模型和形式化描述，这标志着排课问题正式被作为科学问题来被人们所研究，到了1975年S. Even在他的论文中提出并证明大学课程表问题是一个NP完全问题，把该问题理论化，同时也说明该问题有解，并能够找到解。但是根据计算和难解性理论，目前还没有解决NP完全问题的多项式算法。到1979年，Schmidt和Stroheim在文献中就列出了300多篇有关大学课程表问题的已发表文献。现在每年外国的关于运筹学的杂志上依然总会出现一些关于该问题的论文。

2.2.2 大学课程表问题解决方法

至今已经有很多算法被拿来研究用于尝试解决该问题。起初，图论是研究大学课程表问题的一个主要武器，图着色技术被广泛的用来尝试解决该问题。举个例子，1994年，Burke, Elliman 和Weare[6]就研究出一种启发式的图着色方法，该方法把考试进程分成若干组，然后把它们放在一起安排，以求找到一种能够解决考试时间表问题的方法。但是图着色技术本身就是一个NP完全问题，所以对解决该问题帮助不大。后来CARTER, M.W. 和 LAPORTE[15]尝试采用按序分派的方法解决该问题，这种方法需要按启发顺序把事件分出先后顺序，然后再尝试寻找一个可行的解决方案。Ferland 等人[18]和吴金荣[17]把排课问题转化成整数规划问题来解决，但计算量很大，只适合一些理论中的简单情况对于解决复杂问题是不可行的。许多文章[11][12[13][14]试图利用启发式函数来解决排课问题，但是大多数启发方法都是模拟手工排课的过程来实现的。但是由于实际的排课问题存在各种各样的限制条件与特殊要求，处理不好这些限制和要求就无法找到理想的排课方案。

最后，启发式算法被引入大学课程表问题，而且在一定程度上获得成功，在解决大学课程表问题上取得了不错的成绩。启发式算法主要包括三种：禁忌搜索(Tabu Search)，模拟退火算法(Simulated Annealing)和进化算法(Evolutionary Algorithms)。

1.禁忌搜索( Tabu Search)

禁忌搜索是一种主要研究研究具有各种特殊要求的真实世界时间表问题的算法。它由Glover在1986年提出，进而慢慢形成一种独特而又完整的算法。经过研究表明这种算法如果能够正确恰当选择参数（禁忌列表，初始化解决方案和目标函数）那么它在解决大学课程表问题上将有很出色的表现。1998年，Nonobe和Ibaraki[13]开发出一种基于禁忌搜索的处理一般问题的解决系统，这种系统对于满足约束问题特别是高中课程表问题有着出人意料的良好效果。后来在2002年，Alvarez.Valdes, Crespo和Tamarit [14]研制出了一种基于禁忌搜索的具有友好界面的系统，这个系统经过一系列实验也取得不错成绩。现在关于这项技术的研究还在继续，我们这里就不再赘述了。

2.模拟退火算法(Simulated Annealing)

模拟退火算法是一种被广泛研究的算法，它也经常被用来解决时间表问题和大学课程表问题。它是一种模拟固体退火过程的算法。它由Kirkpatrick等人于1982年提出，后来就专门用来解决大规模组合优化问题，它是一种解决NP完全组合优化问题的有效的近似算法。现在一些研究表明，模拟退火算法在课程表问题[15]和考试时间表问题[6]上的实现是高度依赖于各种设定与参数（解决方案空间，降温时间表，邻居产生和评估函数）。因此使用这种算法的时候需要谨慎的选择参数。

3.进化算法(Evolutionary Algorithms)

进化算法和遗传算法现在已经被广泛用来研究时间表问题和大学课程表问题。遗传算法最早是由Colorni[7]等人在90年代初期引入用来解决课程表问题的，一开始他们引进了矩阵表示方案和交叉、变异算子。后来Colorni[8]又把遗传算法成功应用到米兰一所较大的学校的课程排布问题中。Paechter[9]等人对TTP问题进行了研究，提出了时域置换法和放置查找法，并针对较大规模的实际TTP问题比较了这二种算法的性能。Burke[3]对将进化算法分阶段的用于UTP问题做了初步的研究，得到一些颇有价值的成果。遗传算法是本文研究的重点，后面第四章我们将更加详细的讲解遗传算法。

另外基于知识学习的技术也渐渐的参与到对于时间表问题和课程表问题的求解上来。基于知识学习的技术是一种模仿人类思维过程的技术，人类在解决问题的时候总是先在大脑中寻找一个相似的问题，然后对这个相似问题进行分析学习，然后对这个相似问题进行改进以求获得当前新问题的解决方案。这种技术有一个很至关的重要问题，就是如何能清晰地表示经验和知识，并将其存入知识库以便后来之用。这种技术主要包括两种：一种是基于规则的系统，另一种是基于案例推理的系统(Case-Based Reasoning，CBR)。现在大多数用来解决时间表问题的基于知识学习的系统都是基于规则的，很少有基于案例推理的系统。本文主要讲述的是前一种基于规则的系统。

2.3排课的各种算法的比较

至今为止有很多的方法技术和算法都已经被用来尝试解决时间表问题或者大学课程表问题，他们效果各异，有的完成很出色，有的则只在某些特定情况下才能有不错的效果。传统的算法比如说图论和整数规划在应付简单时间表问题和课程表问题时可以较容易的编码，通常情况下可以圆满地完成任务。但是他们通常对于大型的复杂约束时间表或者课程表问题显得束手无策。人工智能领域的全局搜索技术（包括遗传算法，禁忌

搜索，还有模拟退火算法）在各个问题领域都取得了很不错的效果。他们都能够处理各个级别的问题，既可以是简单的问题，也可以是复杂的大型问题。但是他们也有自己的问题需要注意，在使用他们的时候不同场合参数的初始化往往不同，这是一个既重要又难以处理的问题。研究表明基于启发方式的混合算法，在处理问题时候往往会比单独一种算法有更好的更出色的效果。

可以看出启发式算法是解决时间表问题和大学课程表问题各种算法中的翘楚。但是当他们之间作比较的时候，一些研究表明，当算法使用的环境不同，表示的方法不同和选择的算子不同的时候他们往往会有完全不同的表现。1995年，Ross和Corne在解决一个时间表问题时，对遗传算法、模拟退火算法和随机爬山算法进行比较，得出结论随机爬山算法在解决问题的质量上略胜一筹[3]。Colorni、Dorigo和Maniezzo在1998年，对遗传算法、模拟退火算法、禁忌搜索和辅以局部搜索的遗传算法进行比较，得出结论禁忌搜索的效果更佳，但是辅以局部搜索的遗传算法给出了一系列的高质量解决方案，给用户更多的灵活性，以满足各种不同的要求。虽然在不同的环境下，各种启发算法会有不同的表现。但是大家都一致认为遗传算法在解决现实生活中问题的时候具有足够的灵活性，可以给出一系列的较优解以满足人们各种方面不同的需要。本文将着重研究的就是遗传算法，一种改进的混合算法，希望能够对解决时间表问题有较好的作用。

大学课程表问题作为一个典型时间安排问题已经成为了一个具有丰富知识和经验的应用领域。现在几乎所有的用来解决时间表问题的基于知识学习系统都是基于规则的。本文试图讲述一个使用基于规则进行初始化，并用该技术用来指导算法进行改进的遗传算法。

第三章课程表的类对象

3.1课程表的类对象

Professor教授

教授类有ID和name（教授的名字）。还包括一个教授所教课的链表

Students Group 学生组

学生组类有ID和name（学生组的名字），及这个学生组的学生数目。还包括这个学生组要参加的课的链表。

Classroom 教室

教室类有ID和name（教室的名字），也有座位的数目、有关设备（电脑）的信息。如果教室有电脑，预计为每个座位都有电脑。ID是内部自动生成的。

Course 课程

课程类有ID和name（课程的名字）。

Course Class 课（单门课的信息）

课类包含哪位教授教的这节课，这节课上的什么课程，参加这节课的学生组列表。还有教室需要的座位数（即学生组的学生数目之和），是否需要电脑，这节课持续的小时数。

3.2Chromosome 染色体

首先我们应该考虑，当我们处理遗传算法时如何以遗传运算可行的方式来表达我们的解法，例如杂交和突变。此外，我们应该知道如何判断我们的解法有多好。换句话说，我们应该能够计算出我们解法的适应度

3.2.1 Representation 表示

怎么来用染色体表示一个课程表呢？好，我们需要一个存储槽（时空槽）对应每个小时，每个教室，每一天。还有，我们假设只能在周一到周五（总共5天的早上9点到晚上9点之间上课（总共12个小时）。我们可以使用一个12*5*number_of_rooms大小的向量组。每一个槽都应该是一个链表，因为在该算法运行时，我们允许多个课在同一个时空槽里。我们使用一个辅助的hash图用来获取一节课开始时的地址。一门课的

每个小时都在向量中有一个单独的表目，但在hash图中每门课只有一个表目。例如，假如一节课从下午1点开始并持续3小时，它必须进入1点、2点、3点的槽。

每一条染色体表示一种可能的排课结果，至于排课结果的优劣，则由适应度函数评估染色体的适应值来决定。

染色体代表课程表类，它存储课程表的两个属性：

// 时空槽的项代表一个教室的一小时

vector> _slots;

// 课程表染色体，存储class占用的第一个时空槽地址

hash_map _classes;

此外，染色体应该存储它的适应度和遗传操作要使用的参数。

// 染色体的适应度

float _fitness;

// 课需求满意度的标准

vector _criteria;

3.2.2 Fitness 适应度

遗传算法在进化中是以每个个体的适应度值为依据来选取下一代种群的。适应度函数设定的好坏直接影响到遗传算法的收敛速度和能否找到最优解。在本系统中，适应度值的设计只与硬约束有关：

●每门课有0到5分

●如果一门课用了一个空教室，我们就增加它的分数

●如果一门课需要电脑而它所在的教室有电脑或者不需要电脑，我们就增加它的

分数

●如果一门课被安排在有足够椅子的教室里，我们就增加它的分数

●如果一位教授没有其他课，我们就增加这门课的分数

●如果要上课的学生组里的任何一个人在同一时间没有其它课，就加一分

●一个课程表的总分是所有门课分数的总和

●适应度= schedule_score/maximum_score，

maximum_score = number_of_classes*5

适应度由单精度浮点数表示（float），值在0到1之间。

3.2.3 Crossover 杂交

一个杂交操作结合了hash图中双亲的数据，并根据新hash图的内容创造出一个向量槽。杂交操作以随机的一些部分来分割hash图中的双亲。部分数由染色体参数里的杂交数决定。它交替复制双亲的一些部分给新的染色体，形成新的向量槽。

// 执行杂交操作并且返回后代的指针

Schedule* Crossover(const Schedule& parent2) const

3.2.4 Mutation 突变

突变操作非常简单。它只须随便移一门课到另外一个随机选择的槽里。在一个简单操作里，要被移动的课的数目由染色体参数里的突变大小决定。

// 执行突变操作

void Mutation();

第四章基于遗传算法的课程规划

4.1遗传算法的来源和研究发展

19世纪达尔文通过艰辛的考察多年的研究，最终提出了一个具有划时代意义的理论－进化论。按照进化论，地球上的每一物种从诞生开始就开始了漫长的进化。生物种群总是从低级，简单的类型逐步发展到高级，复杂的类型，从简单单细胞生物逐步发展成为高级多细胞生物。每种生物为了生存需要不停的斗争，包括同一种群内部的斗争，不同种群之间的斗争，和自然无机环境进行斗争。有些生物生存了下来，并繁衍壮大，因为它具有与众不同但是能够适应环境适合生存的特点；有的生物消亡了，不再存在于地球，留给我们只是化石和无边的猜测，这是因为它不能够适应环境，不能在生物竞争中取胜。达尔文通过研究考察发现了这一过程，并将它称为“物竞天择，适者生存”。

生物学家通过研究发现有的生物之所以繁衍壮大，有的生物之所以消亡，就是因为他们具有了一些别的种群没有的特点，而这些特点又是遗传基因决定的，遗传基因上有大量的遗传信息，这些遗传信息就是决定生物身上各种性征，而这些性征有一部分又能够决定生物在自然界的竞争中胜败，而竞争的胜败直接决定了某一种生物的生存和发展。但是一种生物的壮大就需要生物能够把自己的性征传给下一代，而这一过程是通过遗传基因来做到的。

遗传基因是有一定组合规律的，这些组合的特异性决定了生物体的多样性，基因结构的稳定性保证了生物物种的稳定性，而基因的杂交和变异是生物产生了进化的可能。生物的遗传是通过父代向子代传递基因来实现的，而这种遗传信息的改变决定了生物体的变异。

遗传算法采用类似基因演化的循环过程，其演算过程如下：

1）随机产生一定数目的初始种群

2）对个体适应度进行评估，如果个体的适应度符合优化准则，则输出最佳个体及其代表的最优解，并结束计算，否则转向第3步。

3）依据适应度选择再生个体

4）按照一定的交叉概率和交叉方法生成新的个体

5）按照一定的变异概率和变异方法生成新的个体

6）由交叉和变异产生新一代的种群，然后返回第2步。如图1所示：

4.2 具体操作

遗传算法相当简单。对于每一代，它执行两个基本操作：

1、从当前种群里随机选择n 对父母，并且通过在每对父母里执行杂交操作产出n 个新的染色体

2、从当前种群里随机选择n 对父母，并且用新的代替他们。如果它是种群里最优的染色体之一，算法就不选择新的染色体

这两个操作会一直重复直到最优的染色体的适应度达到1（意味着课表里的所有课程都达到要求）。正如之前提到的，遗传算法一直追踪种群里的m 个最优染色体，同时当他们属于最优染色体时保证它们不会被代替。

// 遗传算法

class Algorithm

{

private :

// 染色体的种群

vector _chromosomes;

// 表明染色体是否属于最优染色体群

vector _bestFlags;

// 最优染色体

vector

> _bestChromosomes;

// 当前存储的最优染色体数目

int _currentBestSize;

// 在每一代人被后代所取代的染色体数目

int _replaceByGeneration;

// 指向算法观察员

ScheduleObserver* _observer;

// 种群里的染色体原型

Schedule* _prototype;

// 当前的一代

int _currentGeneration;

// 算法的执行状态

AlgorithmState _state;

// 算法状态的同步

CCriticalSection _stateSect;

// 指向算法的全局实例

static Algorithm* _instance;

// 全局实例创建和毁灭的同步化

static CCriticalSection _instanceSect;

public:

// 返回算法全局实例的引用

static Algorithm& GetInstance();

static void FreeInstance();

// 初始化遗传算法

Algorithm(int numberOfChromosomes, int replaceByGeneration, int trackBest, Schedule* prototype, ScheduleObserver* observer);

~Algorithm();

// 开始执行

void Start();

// 停止执行

void Stop();

// 返回种群里最优染色体的指针

Schedule* GetBestChromosome() const;

// 返回当前这一代

inline int GetCurrentGeneration() const { return _currentGeneration; }

// 返回算法观察员的指针

inline ScheduleObserver* GetObserver() const { return _observer; }

private:

// 增加染色体进最优染色体群

void AddToBest(int chromosomeIndex);

// 如果染色体属于最优染色体则返回TRUE

bool IsInBest(int chromosomeIndex);

// 清空最优染色体群

void ClearBest();

};

4.3课表观察员

ScheduleObserver类处理由遗传算法触发的事件。这个类给应用程序的视图窗口发送消息。当算法的执行没有结束或者中断了，可以通过调用WaitEvent()阻塞呼叫方的线程。

// 当算法找到新的最优染色体时启动的句柄事件

void NewBestChromosome(const Schedule& newChromosome);

// 当算法执行状态发生变化时启动的句柄事件

void EvolutionStateChanged(AlgorithmState newState);

// 阻塞调用者进程直到算法执行结束

inline void WaitEvent() { WaitForSingleObject( _event, INFINITE ); }

如果你计划改变NewBestChromosome方法，记住如果要显示最优染色体，必须作一个硬件拷贝（通过使用Schedule类里的MakeCopy方法）因为算法会在下一代里删除染色体。

4.4配置

4.4.1 配置文件

对象的标识符：

1. professor ( #prof tag) –教授

2. course ( #course tag) –课程

3. room ( #room tag)–教室

4. group ( #group tag)–学生组

5. course class ( #class tag) –绑定了教授、课程、学生组的课

每个对象以自己的标记符开始以#end结束，所有的标记必须在单独的行里。在对象的主题里，每行只包含一个键和值对（属性）以=分开。每个属性被一次性指定，除了#group对象里的group属性，它可以有多个group属性。以下是对象属性的列表：

1. #prof

●id (number, required)–教授的编号

●name (string, required) - 教授的名字

2. #course

●id (number, required) –课程的编号

●name (string, required) - 课程的名字

3. #room

●name (string, required) –教室的名字

●size (number, required) –教室的座位数

●lab (boolean, optional) –教室是否有电脑，默认值为false

4. #group

●id (number, required) –学生组的编号

●name (string, required) - 学生组的名称

●size (number, required) - 学生人数

5. #class

●professor (number, required) –绑定的教授编号

●course (number, required) –绑定的课程编号

●group (number, required) –绑定的学生组编号，每门课都绑定多个学生组

●duration (number, optional) –课的持续时间（单位小时），默认值为1

●lab (boolean, optional) –这门可是否需要教室里有电脑，默认值为false

值得注意的是professor、students group、course在绑定到class前都必须先定义。

4.4.2 配置文件的例子

#prof

id = 1

name = 刘备

#end

#course

id = 1

name = C++

#end

#room

name = S3-402

lab = true

size = 24

#end

#group

id = 1

name = 1O1

size = 19

#end

#class

professor = 1

course = 1

duration = 2

group = 1

group = 2

#end

#class

professor = 1

course = 1

duration = 2

group = 3

group = 4

#end

#class

professor = 9

course = 1

duration = 3

group = 1

lab = true

#end

4.4.3 解析一个配置文件

由Configuration类来解析一个配置文件。ParseFile打开并分析一个配置文件。它寻找对象标识符并且调用合适的方法来分析对象。ParseFile清空之前解析了的对象。public:

void ParseFile(char* fileName);

private:

Professor* ParseProfessor(ifstream& file);

StudentsGroup* ParseStudentsGroup(ifstream& file)

Course* ParseCourse(ifstream& file);

Room* ParseRoom(ifstream& file);

CourseClass* ParseCourseClass(ifstream& file);

解析一个文件：

Configuration::GetInstance().ParseFile( "GaSchedule.cfg" )

除了课程类，解析的对象都被放在一个hash图里，所以他们可以被快速轻易的访问private:

hash_map _professors;

hash_map _studentGroups

hash_map _courses

hash_map _rooms;

list _courseClasses;

Configuration类也包含检索已经解析了的信息和对象的方法

public:

inline Professor* GetProfessorById(int id) //...

inline int GetNumberOfProfessors() const//...

inline StudentsGroup* GetStudentsGroupById(int id) //...

inline int GetNumberOfStudentGroups() const//...

inline Course* GetCourseById(int id) //...

inline int GetNumberOfCourses() const//...

inline Room* GetRoomById(int id) //...

inline int GetNumberOfRooms() const//...

inline const list& GetCourseClasses() const//...

inline int GetNumberOfCourseClasses() const//...

4.5程序运行示意图

遗传算法的c语言程序

一需求分析 1．本程序演示的是用简单遗传算法随机一个种群，然后根据所给的交叉率，变异率，世代数计算最大适应度所在的代数 2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的命令；相应的输入数据和运算结果显示在其后。3．测试数据 输入初始变量后用y=100*(x1*x1-x2)*(x1*x2-x2)+(1-x1)*(1-x1)其中-2.048<=x1,x2<=2.048作适应度函数求最大适应度即为函数的最大值 二概要设计 1．程序流程图 2．类型定义 int popsize; //种群大小 int maxgeneration; //最大世代数 double pc; //交叉率 double pm; //变异率 struct individual

{ char chrom[chromlength+1]; double value; double fitness; //适应度 }; int generation; //世代数 int best_index; int worst_index; struct individual bestindividual; //最佳个体 struct individual worstindividual; //最差个体 struct individual currentbest; struct individual population[POPSIZE]; 3．函数声明 void generateinitialpopulation(); void generatenextpopulation(); void evaluatepopulation(); long decodechromosome(char *,int,int); void calculateobjectvalue(); void calculatefitnessvalue(); void findbestandworstindividual(); void performevolution(); void selectoperator(); void crossoveroperator(); void mutationoperator(); void input(); void outputtextreport(); 4．程序的各函数的简单算法说明如下： （1）．void generateinitialpopulation ()和void input ()初始化种群和遗传算法参数。 input() 函数输入种群大小，染色体长度，最大世代数，交叉率，变异率等参数。 （2）void calculateobjectvalue();计算适应度函数值。 根据给定的变量用适应度函数计算然后返回适度值。 （3）选择函数selectoperator() 在函数selectoperator()中首先用rand ()函数产生0～1间的选择算子，当适度累计值不为零时，比较各个体所占总的适应度百分比的累计和与选择算子，直到达到选择算子的值那个个体就被选出，即适应度为fi的个体以fi/∑fk的概率继续存在； 显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可能被选中，以便增加下一代群体的多样性。 （4）染色体交叉函数crossoveroperator() 这是遗传算法中的最重要的函数之一，它是对个体两个变量所合成的染色体进行交叉，而不是变量染色体的交叉，这要搞清楚。首先用rand ()函数产生随机概率，若小于交叉概率，则进行染色体交叉，同时交叉次数加1。这时又要用rand()函数随机产生一位交叉位，把染色

MATLAB实验遗传算法和优化设计

实验六 遗传算法与优化设计 一、实验目的 1. 了解遗传算法的基本原理和基本操作（选择、交叉、变异）； 2. 学习使用Matlab 中的遗传算法工具箱(gatool)来解决优化设计问题； 二、实验原理及遗传算法工具箱介绍 1. 一个优化设计例子 图1所示是用于传输微波信号的微带线(电极)的横截面结构示意图，上下两根黑条分别代表上电极和下电极，一般下电极接地，上电极接输入信号，电极之间是介质(如空气，陶瓷等)。微带电极的结构参数如图所示，W 、t 分别是上电极的宽度和厚度，D 是上下电极间距。当微波信号在微带线中传输时，由于趋肤效应，微带线中的电流集中在电极的表面，会产生较大的欧姆损耗。根据微带传输线理论，高频工作状态下（假定信号频率1GHz ），电极的欧姆损耗可以写成（简单起见，不考虑电极厚度造成电极宽度的增加）： 图1 微带线横截面结构以及场分布示意图 {} 28.6821ln 5020.942ln 20.942S W R W D D D t D W D D W W t D W W D e D D παπππ=+++-+++?????? ? ??? ??????????? ??????? (1) 其中πρμ0=S R 为金属的表面电阻率， ρ为电阻率。可见电极的结构参数影响着电极损耗，通过合理设计这些参数可以使电极的欧姆损耗做到最小，这就是所谓的最优化问题或者称为规划设计问题。此处设计变量有3个：W 、D 、t ，它们组成决策向量[W, D ,t ] T ，待优化函数(,,)W D t α称为目标函数。 上述优化设计问题可以抽象为数学描述： ()()min .. 0,1,2,...,j f X s t g X j p ????≤=? (2)

遗传算法与组合优化.

第四章 遗传算法与组合优化 4.1 背包问题（knapsack problem ） 4.1.1 问题描述 0/1背包问题：给出几个尺寸为S 1，S 2，…，S n 的物体和容量为C 的背包，此处S 1，S 2，…，S n 和C 都是正整数；要求找出n 个物件的一个子集使其尽可能多地填满容量为C 的背包。 数学形式： 最大化 ∑=n i i i X S 1 满足 ,1C X S n i i i ≤∑= n i X i ≤≤∈1},1,0{ 广义背包问题：输入由C 和两个向量C ＝(S 1，S 2，…，S n )和P ＝(P 1，P 2，…，P n )组成。设X 为一整数集合，即X ＝1，2，3，…，n ，T 为X 的子集，则问题就是找出满足约束条件∑∈≤T i i C X ，而使∑∈T i i P 获得最大的子集T ，即求S i 和P i 的下标子集。 在应用问题中，设S 的元素是n 项经营活动各自所需的资源消耗，C 是所能提供的资源总量，P 的元素是人们从每项经营活动中得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。 广义背包问题可以数学形式更精确地描述如下： 最大化 ∑=n i i i X P 1 满足 ,1C X S n i i i ≤∑= n i X i ≤≤∈1},1,0{ 背包问题在计算理论中属于NP —完全问题，其计算复杂度为O (2n )，若允许物件可以部分地装入背包，即允许X ，可取从0.00到1.00闭区间上的实数，则背包问题就简化为极简单的P 类问题，此时计算复杂度为O (n )。

4.1.2 遗传编码 采用下标子集T 的二进制编码方案是常用的遗传编码方法。串T 的长度等于n(问题规模)，T i (1≤i ≤n )＝1表示该物件装入背包，T i ＝0表示不装入背包。基于背包问题有近似求解知识，以及考虑到遗传算法的特点（适合短定义距的、低阶的、高适应度的模式构成的积木块结构类问题），通常将P i ，S i 按P i /S i 值的大小依次排列，即P 1/S 1≥P 2/S 2≥…≥P n /S n 。 4.1.3 适应度函数 在上述编码情况下，背包问题的目标函数和约束条件可表示如下。 目标函数：∑==n i i i P T T J 1 )( 约束条件：C S T n i i i ≤∑=1 按照利用惩罚函数处理约束条件的方法，我们可构造背包问题的适应度函数f (T )如下式： f (T ) = J (T ) + g (T ) 式中g (T )为对T 超越约束条件的惩罚函数，惩罚函数可构造如下: 式中E m 为P i /S (1≤i ≤n )i 的最大值，β为合适的惩罚系数。 4.2 货郎担问题（Traveling Salesman Problem ——TSP ） 在遗传其法研究中，TSP 问题已被广泛地用于评价不同的遗传操作及选择机制的性能。之所以如此，主要有以下几个方面的原因： (1) TSP 问题是一个典型的、易于描述却难以处理的NP 完全（NP-complete ）问题。有效地 解决TSP 问题在可计算理论上有着重要的理论价值。 (2) TSP 问题是诸多领域内出现的多种复杂问题的集中概括和简化形式。因此，快速、有效 地解决TSP 问题有着极高的实际应用价值。 (3) TSP 问题因其典型性已成为各种启发式的搜索、优化算法的间接比较标准，而遗传算法 就其本质来说，主要是处理复杂问题的一种鲁棒性强的启发式随机搜索算法。因此遗传算法在TSP 问题求解方面的应用研究，对于构造合适的遗传算法框架、建立有效的遗传操作以及有效地解决TSP 问题等有着多方面的重要意义。

遗传算法应用论文

论文 题目：遗传应用算法 院系：计算机工程系 专业：网络工程 班级学号： 学生姓名： 2014年10月23日

摘要: 遗传算法是基于自然界生物进化基本法则而发展起来的一类新算法。本文在简要介绍遗传算法的起源与发展、算法原理的基础上,对算法在优化、拟合与校正、结构分析与图谱解析、变量选择、与其他算法的联用等方面的应用进行了综述。该算法由于无需体系的先验知识,是一种全局最优化方法,能有效地处理复杂的非线性问题,因此有着广阔的应用前景。 关键词: 遗传算法; 化学计量学; 优化 THEORY AND APPL ICATION OF GENETIC AL GORITHM ABSTRACT: Genetic Algo rithm( GA) is a kind of recursive computational procedure based on the simulation of principle principles of evaluati on of living organisms in nature1Based on brief int roduction of the principle ,the beginning and development of the algorithms ,the pape r reviewed its applications in the fields of optimization ,fitting an d calibration,structure analysis and spectra interpretation variable selection ,and it s usage in combination with othersThe application o f GA needs no initiating knowledge of the system ,and therefore is a comprehensive optimization method with extensive application in terms of processing complex nonlinear problems。 KEY WORDS : Genetic Algorithm( GA) Chemometrics Optimization 遗传算法是在模拟自然界生物遗传进化过程中形成的一种自适应优化的概率搜索算法，它于1962年被提出，直到1989年才最终形成基本框架。遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机化搜索算法, 由美国J. H. Ho llad教授提出, 其主要特点是群体搜索策略和群体中个体之间的信息交换。该算法尤其适用于处理传统搜索方法难以解决的复杂和非线性问题, 可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。 顾名思义,遗传算法(Genetic Algorithm ,GA)是模拟自然界生物进化机制的一种算法 ,即遵循适者生存、优胜劣汰的法则 ,也就是寻优过程中有用的保留 ,无用的则去除。在科学和生产实践中表现为 ,在所有可能的解决方法中找出最符合该问题所要求的条件的解决方法 ,即找出一个最优解。这种算法是 1960 年由

基本遗传算法的C源程序。doc【精品毕业设计】(完整版)

/********************************************************** ********/ /* 基于基本遗传算法的函数最优化SGA.C */ /* A Function Optimizer using Simple Genetic Algorithm */ /* developed from the Pascal SGA code presented by David E.Goldberg */ //********************************************************** ********/ #include #include #include #include "graph.c" /* 全局变量*/ struct individual /* 个体*/ { unsigned *chrom; /* 染色体*/ double fitness; /* 个体适应度*/ double varible; /* 个体对应的变量值*/ int xsite; /* 交叉位置*/ int parent[2]; /* 父个体*/ int *utility; /* 特定数据指针变量*/ };

struct bestever /* 最佳个体*/ { unsigned *chrom; /* 最佳个体染色体*/ double fitness; /* 最佳个体适应度*/ double varible; /* 最佳个体对应的变量值*/ int generation; /* 最佳个体生成代*/ }; struct individual *oldpop; /* 当前代种群*/ struct individual *newpop; /* 新一代种群*/ struct bestever bestfit; /* 最佳个体*/ double sumfitness; /* 种群中个体适应度累计*/ double max; /* 种群中个体最大适应度*/ double avg; /* 种群中个体平均适应度*/ double min; /* 种群中个体最小适应度*/ float pcross; /* 交叉概率*/ float pmutation; /* 变异概率*/ int popsize; /* 种群大小*/ int lchrom; /* 染色体长度*/ int chromsize; /* 存储一染色体所需字节数*/ int gen; /* 当前世代数*/ int maxgen; /* 最大世代数*/ int run; /* 当前运行次数*/

遗传算法与优化问题(重要,有代码)

实验十遗传算法与优化问题 一、问题背景与实验目的 遗传算法（Genetic Algorithm—GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975年首先提出的．遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位． 本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题，使读者能够学会利用遗传算法进行初步的优化计算．1．遗传算法的基本原理 遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程．它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体．这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代．后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程．群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解．值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要（目前生物界对此学说尚有争议）． （1）遗传算法中的生物遗传学概念 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念． 首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系．这些概念如下： 序号遗传学概念遗传算法概念数学概念 1 个体要处理的基本对象、结构也就是可行解 2 群体个体的集合被选定的一组可行解 3 染色体个体的表现形式可行解的编码 4 基因染色体中的元素编码中的元素 5 基因位某一基因在染色体中的位置元素在编码中的位置 6 适应值个体对于环境的适应程度， 或在环境压力下的生存能力可行解所对应的适应函数值 7 种群被选定的一组染色体或个体根据入选概率定出的一组 可行解 8 选择从群体中选择优胜的个体， 淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解 9 交叉一组染色体上对应基因段的 交换根据交叉原则产生的一组新解 10 交叉概率染色体对应基因段交换的概 率（可能性大小）闭区间[0,1]上的一个值，一般为0.65~0.90 11 变异染色体水平上基因变化编码的某些元素被改变

基于遗传算法的多式联运组合优化

第四章基于遗传算法的集装箱多式联运运输组合优化模型 的求解 4.1 遗传算法简介 4.1.1 遗传算法 遗传算法(Genetic Algorithm,GA)是在20世纪六七十年代由美国密歇根大学的Holland J.H.教授及其学生和同事在研究人工自适应系统中发展起来的一种随机搜索方法,通过进一步的研究逐渐形成了一个完整的理论和方法体系取名为基本遗传算法(Simple Genetic Algorithm)。在接下来几年的研究过程中Holland在研究自然和人工系统的自适应行为的过程中采用了这个算法，并在他的著作《自然系统和人工系统的适配》中对基本遗传算法的理论和方法进行了系统的阐述与描写，同时提出了在遗传算法的理论研究和发展中具有极为重要的作用的模式理论，它的编码技术和遗传操作成为了遗传算法被广泛并成功的应用的基础，经过许多学者多年来的研究，遗传算法逐渐成熟起来，到现在已经成为了一个非常大的体系，广泛的应用于组合优化、系统优化、过程控制、经济预测、模式识别以及智能控制等多个领域。De Jong于1975年在他的博士论文中设计了一系列针对于各种函数优化问题的遗传算法的执行策略，详细分析了各项性能的评价指标。在此基础上，美国伊利诺大学的Goldberg于1989年系统全面的阐述了遗传算法理论，并通过例证对遗传算法的多领域应用进行了分析，为现代遗传算法的研究和发展奠定了基础。 遗传算法是一种模仿基于自然选择的生物进化过程的随机方法，它以类似于基因的编码作为种群的个体，首先，随机的产生初始种群的个体，从这个群体开始进行搜索，根据类似于生物适应能力的适应度函数值的大小，按照不同问题各自的特点，在当前的种群中运用适当的选择策略选择适应能力大的个体，其中所选择出来的个体经过遗传操作、交叉操作以及变异操作产生下一代种群个体。如此反复，像生物的进化过程一样逐代进化，直到满足期望的终止条件为止。

论文-遗传算法的基本步骤

遗传算法 遗传算法（Genetic Algorithm）是基于进化论的原理发展起来的一种广为应用，高效的随机搜索与优化的方法。它从一组随机产生的初始解称为“种群”，开始搜索过程。种群中的每个个体是问题的一个解，成为“染色体”是一串符号。这些染色体在每一代中用“适应度”来测量染色体的好坏, 通过选择、交叉、变异运算形成下一代。选择的原则是适应度越高,被选中的概率越大。适应度越低，被淘汰的概率越大。每一代都保持种群大小是常数。经过若干代之后，算法收敛于最好的染色体，它很可能是问题的最优解或次优解。这一系列过程正好体现了生物界优胜劣汰的自然规律。 比如有编号为1到10的特征，现在要选取其中的5个，基于遗传算法的特征选择可以如下这样直观的理解： 下续（表格） 下续……

即设有4个不同的初始特征组合，分别计算判别值，然后取最大的2个组合（[1,2,3,4,9]和[1,3,5,7,8]）进行杂交，即互换部分相异的特征（4和7），得到新的两个特征组合（[1,2,3,7,9]和[1,3,4,5,8]）,然后再计算这两个新的组合的判别值，和原来的放在一起，再从中选择2个具有最大判别值的组合进行杂交。如此循环下去，在某一代的时候就得到了一个最好的特征组合（比如第2代的[1,3,5,7,9]的特征组合）。当然，在实际中每代的个体和杂交的数量是比较大的。 遗传算法的具体的步骤如下：

1.编码：把所需要选择的特征进行编号，每一个特征就是一个基因，一个解就是一串基因的组合。为了减少组合数量，在图像中进行分块（比如5*5大小的块），然后再把每一块看成一个基因进行组合优化的计算。每个解的基因数量是要通过实验确定的。 2.初始群体（population）的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体。N个个体，构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。这个参数N需要根据问题的规模而确定。 3.交换(crossover)：交换（也叫杂交）操作是遗传算法中最主要的遗传操作。由交换概率( P)挑选的每两个父代 c 通过将相异的部分基因进行交换（如果交换全部相异的就变成了对方而没什么意义），从而产生新的个体。可以得到新一代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。 4.适应度值(fitness)评估检测：计算交换产生的新个体的适应度。适应度用来度量种群中个体优劣（符合条件的程度）的指标值，这里的适应度就是特征组合的判据的值。这个判据的选取是GA的关键所在。

MATLAB课程遗传算法实验报告及源代码

硕士生考查课程考试试卷 考试科目： 考生姓名：考生学号： 学院：专业： 考生成绩： 任课老师(签名) 考试日期：年月日午时至时

《MATLAB 教程》试题： A 、利用MATLA B 设计遗传算法程序，寻找下图11个端点最短路径，其中没有连接端点表示没有路径。要求设计遗传算法对该问题求解。 a e h k B 、设计遗传算法求解f (x)极小值，具体表达式如下： 321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =?=???-≤≤=? ∑ 要求必须使用m 函数方式设计程序。 C 、利用MATLAB 编程实现：三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行，随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货，但是如何乘船渡河的大权掌握在商人手中，商人们怎样才能安全渡河？ D 、结合自己的研究方向选择合适的问题，利用MATLAB 进行实验。 以上四题任选一题进行实验，并写出实验报告。

选择题目： B 、设计遗传算法求解f (x)极小值，具体表达式如下： 321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =?=???-≤≤=? ∑ 要求必须使用m 函数方式设计程序。 一、问题分析（10分） 这是一个简单的三元函数求最小值的函数优化问题，可以利用遗传算法来指导性搜索最小值。实验要求必须以matlab 为工具，利用遗传算法对问题进行求解。 在本实验中，要求我们用M 函数自行设计遗传算法，通过遗传算法基本原理，选择、交叉、变异等操作进行指导性邻域搜索，得到最优解。 二、实验原理与数学模型（20分） （1）试验原理： 用遗传算法求解函数优化问题，遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。其采纳了自然进化模型，从代表问题可能潜在解集的一个种群开始，种群由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体；初始种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的解：在每一代，概据问题域中个体的适应度大小挑选个体；并借助遗传算子进行组合交叉和主客观变异，产生出代表新的解集的种群。这一过程循环执行，直到满足优化准则为止。最后，末代个体经解码，生成近似最优解。基于种群进化机制的遗传算法如同自然界进化一样，后生代种群比前生代更加适应于环境，通过逐代进化，逼近最优解。 遗传算法是一种现代智能算法，实际上它的功能十分强大，能够用于求解一些难以用常规数学手段进行求解的问题，尤其适用于求解多目标、多约束，且目标函数形式非常复杂的优化问题。但是遗传算法也有一些缺点，最为关键的一点，即没有任何理论能够证明遗传算法一定能够找到最优解，算法主要是根据概率论的思想来寻找最优解。因此，遗传算法所得到的解只是一个近似解，而不一定是最优解。 （2）数学模型 对于求解该问题遗传算法的构造过程： （1）确定决策变量和约束条件；

TSP问题的遗传算法求解 优化设计小论文

TSP问题的遗传算法求解 摘要：遗传算法是模拟生物进化过程的一种新的全局优化搜索算法，本文简单介绍了遗传算法，并应用标准遗传算法对旅行包问题进行求解。 关键词：遗传算法、旅行包问题 一、旅行包问题描述： 旅行商问题，即TSP问题（Traveling Saleman Problem）是数学领域的一个著名问题，也称作货郎担问题，简单描述为：一个旅行商需要拜访n个城市（1，2，…，n），他必须选择所走的路径，每个城市只能拜访一次，最后回到原来出发的城市，使得所走的路径最短。其最早的描述是1759年欧拉研究的骑士周游问题，对于国际象棋棋盘中的64个方格，走访64个方格一次且最终返回起始点。 用图论解释为有一个图G=（V,E），其中V是顶点集，E是边集，设D=（d ij）是有顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只能通过一次的具有最短距离的回路。若对于城市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-1）！，随着城市数目的增加，路径数急剧增加，对与小规模的旅行商问题，可以采取穷举法得到最优路径，但对于大型旅行商问题，则很难采用穷举法进行计算。 在生活中TSP有着广泛的应用，在交通方面，如何规划合理高效的道路交通，以减少拥堵；在物流方面，更好的规划物流，减少运营成本；在互联网中，如何设置节点，更好的让信息流动。许多实际工程问题属于大规模TSP，Korte于1988年提出的VLSI芯片加工问题可以对应于1.2e6的城市TSP，Bland于1989年提出X-ray衍射问题对应于14000城市TSP，Litke于1984年提出电路板设计中钻孔问题对应于17000城市TSP，以及Grotschel1991年提出的对应于442城市TSP的PCB442问题。

一个简单实用的遗传算法c程序完整版

一个简单实用的遗传算 法c程序 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】

一个简单实用的遗传算法c程序（转载） 2009-07-28 23:09:03 阅读418 评论0 字号：大中小 这是一个非常简单的遗传算法源代码，是由Denis Cormier (North Carolina State University)开发的，Sita (University of North Carolina at Charlotte)修正。代码保证尽可能少，实际上也不必查错。对一特定的应用修正此代码，用户只需改变常数的定义并且定义“评价函数”即可。注意代码的设计是求最大值，其中的目标函数只能取正值；且函数值和个体的适应值之间没有区别。该系统使用比率选择、精华模型、单点杂交和均匀变异。如果用Gaussian变异替换均匀变异，可能得到更好的效果。代码没有任何图形，甚至也没有屏幕输出，主要是保证在平台之间的高可移植性。读者可以从,目录 coe/evol中的文件中获得。要求输入的文件应该命名为‘’；系统产生的输出文件为‘’。输入的文件由几行组成：数目对应于变量数。且每一行提供次序——对应于变量的上下界。如第一行为第一个变量提供上下界，第二行为第二个变量提供上下界，等等。 /**************************************************************************/ /* This is a simple genetic algorithm implementation where the */ /* evaluation function takes positive values only and the */ /* fitness of an individual is the same as the value of the */ /* objective function */ /**************************************************************************/ #include <> #include <> #include <> /* Change any of these parameters to match your needs */ #define POPSIZE 50 /* population size */

基于遗传算法的齿轮减速器优化设计

煤矿机械Coal Mine Machinery Vol.30No.12 Dec.2009 第30卷第12期2009年12月 0引言 工程机械中所用电动机的转速较高，为了满足工作机低转速的需要，一般在电动机和工作机之间安装减速器，用来降低电机的转速或增大转矩，减速器是一种机械传动装置，广泛地应用于运输机械、矿山机械和建筑机械等重型机械中。因此，减速器的设计非常重要。 遗传算法（GA）是模拟生物在自然界中优胜劣汰的自然进化过程而形成的一种具有全局范围内优化的启发式搜索算法。这种方法已在很多学科得到广泛的应用，为减速器的优化设计提供有力的保证。因此，本文采用遗传算法对两级齿轮减速器进行优化设计，并通过与惩罚函数法和模拟退火算法等优化方法计算结果进行比较，来探讨适合于减速器的优化设计方法。 1建立数学模型 两级齿轮传动减速器结构如图1所示。该减速器的总中心距 a∑＝［m n1z1（1＋i1）+m n2z3（1＋i2）］/2cosβ（1）式中m n1、m n2—— —高速级与低速级的齿轮法面模 数； i1、i2—— —高速级与低速级传动比； z1、z3—— —高速级与低速级的小齿轮齿数： β—— —2组齿轮组的螺旋角。 1.1设计变量的确定 在进行两级齿轮传动减速器设计时，一般选择齿轮传动独立的基本参数或性能参数，如齿轮的齿数、模数、传动比、螺旋角等为设计变量。两级齿轮传动由4个齿轮组成，分别用z1、z2、z3、z4表示，高速级的传动比由i1表示，低速级传动比由i2表示，两组齿轮组的法面模数分别由m n1和m n2表示，2组齿轮的螺旋角用β表示，由于两级齿轮传动减速器的总传动比i0，在设计时会给出具体数据，并且满足i0＝i1i2，可以得出i2＝i0/i1，可以确定独立的参数有z1、z3、m n1、m n2、i1和β。因此，可以确定该设计变量X＝［z1，z3，m n1，m n2，i1，β］T=［x1，x2，x3，x4，x5，x6］T。 图1减速器结构简图 1.2目标函数的建立 在对减速器进行优化设计时，首先要确定目标函数。确定目标函数的原则是在满足各种性能要求的前提下，使减速器的体积最小，这样设计的减速器既经济又实用，从而达到了优化的目的。要使减速器的体积最小，必须使减速器的总中心距最小。因此，以减速器的中心距最小建立目标函数为 a∑＝［x3x1（1＋x5）+x4x2(1+i0/x5)］ 6 （2）1.3约束条件的确定 为使两级齿轮传动减速器满足强度、设计变量 基于遗传算法的齿轮减速器优化设计* 吴婷，张礼兵，黄磊 （安徽建筑工业学院机电学院，合肥230601） 摘要：对两级齿轮减速器优化设计进行了分析，建立了其优化设计的数学模型，确定了优化设计的约束条件，采用遗传算法对两级齿轮减速器进行优化设计，并通过实例说明，采用遗传算法对减速器进行优化，可以得到更加优化的设计结果。 关键词：减速器；遗传算法；优化设计 中图分类号：TH132文献标志码：A文章编号：1003－0794（2009）12－0009－03 Gear Reducer Optimal Design Based on Genetic Algorithm WU Ting，ZHANG Li-bing，HUANG Lei （School of Mechanical and Electrical Engineering,Anhui University of Architecture,Hefei230601,China）Abstract:T he optimal design of a gear reducer was analyzed,the mathematic model was established, and the restriction condition was confirmed.Design of the gear reducer was optimized with genetic algorithm and the examples showed that design of the gear reducer based on genetic algorithm can gain more optimized result. Key words:reducer；genetic algorithm；optimal design *安徽省教育厅自然基金项目（2006KJ015C） 轴1轴2轴3 z1z2 z3z4 9

人工智能遗传算法新论文

论文 题目：遗传算法应用 院系：计算机工程系 专业：网络工程 班级学号：112055126 学生姓名：崔小杰 2014年10月23日

内容摘要 图像分割就是指把图像分成各具特性的区域并提取出感兴趣目标的技术和过程。图像的分割是以灰度值作为分割的依据,通过各个像素的灰度值和事先确定的阈值的比较来分割图像。如何确定最合适的阈值是处理好图像分割的关键,这自然成为一直以来分割算法研究的焦点。 遗传算法是对生物进化论中自然选择和遗传学机理中生物进化过程的模拟来计算最优解的方法。遗传算法具有众多的优点,如鲁棒性、并行性、自适应性和快速收敛,可以应用在图像处理技术领域中图像分割技术来确定分割阈值。 本文主要介绍基于遗传算法的最小误差阈值法、最大类间方差法（Otsu法）以及最佳直方图熵法(KSW熵法)等三种方法分割图像。 关键词：图像分割，遗传算法，阈值分割

目录 第一章绪论 .................................................. - 1 - 第二章遗传算法概述 ........................................ . - 1 - 2.1遗传算法的研究历史....................................... - 1 - 2.2生物背景................................................. - 2 - 2.3遗传算法的基本思想....................................... - 2 - 2.4遗传算法的几个概念....................................... - 2 - 2.4.1适应度函数......................................... - 2 - 2.4.2遗传算法最常用的算子............................... - 3 - 2.5遗传算法运算的基本流程 (4) 第三章图像分割的现状 ........................................ - 4 - 3.1图像分割简介............................................. - 4 - 3.2图像分割方法............................................. - 5 - 3.2.1基于边缘检测的分割 (6) 3.2.2基于区域的分割..................................... - 5 - 3.2.3边缘与区域相结合的分割............................. - 5 - 3.3阈值选取................................................. - 6 - 第四章基于新的遗传算法的图像分割 ............................ - 6 - 4.1混沌遗传算法............................................. - 6 - 4.2量子遗传算法............................................. - 6 - 4.3免疫遗传算法............................................. - 6 - 结论 ........................................................... - 7 - 参考文献: ...................................................... - 7 -

遗传算法的特点及其应用

遗传算法的特点及其应用 上海复旦大学附属中学张宁 目录 【关键词】 【摘要】 【正文】 §1遗传算法的基本概念 §2简单的遗传算法 1．选择 2．交换 3．变异 §3简单的遗传算法运算示例 1．计算机公司的经营策略优化问题 2．函数优化问题 §4遗传算法应用举例 1．子集和问题 2．TSP（旅行商）问题 §5结束语 【附录】 1．子集和问题源程序 2．TSP（旅行商）问题源程序 【参考文献】

【关键词】 遗传算法遗传变异染色体基因群体 【摘要】 遗传算法是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它根据适者生存，优胜劣汰等自然进化规则来进行搜索计算和问题求解。 文章的第一部分介绍了遗传算法的基本概念。第二部分介绍了遗传算法的原理以及三种运算：选择、交换、变异。第三部分着重介绍三种运算的具体实现，以及简单实例，主要体现遗传算法的实现过程。第四部分介绍了两个具体问题，都是属于NP-完全问题，如何用遗传算法来解决，以及实现时的一些基本问题。 文章在介绍遗传算法的原理以及各种运算的同时，还分析了一些应用中出现的基本问题，对于我们的解题实践有一定的指导意义。 【正文】 遗传算法作为一门新兴学科，在信息学竞赛中还未普及，但由于遗传算法对许多用传统数学难以解决或明显失效的复杂问题，特别是优化问题，提供了一个行之有效的新途径，且能够较好地解决信息学竞赛中的NP难题，因此值得我们进行深入的讨论。 要掌握遗传算法的应用技巧，就要了解它的各方面的特点。首先，让我们来了解一下什么是遗传算法。 §1遗传算法的基本概念 遗传算法（Genetic Algorithms，简称GA）是人工智能的重要新分支，是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它

遗传算法电机优化设计简介

收稿日期:20001225 综 述 遗传算法电机优化设计简介 李鲲鹏,胡虔生 (东南大学,南京210096) B rief I ntroduction of Motor Optimizing Design B ased on G enetic Algorithms L I Kun -peng ,HU Qian -sheng (S outheast University ,Nanjing 210096,China ) 摘　要:介绍了遗传算法的基本思想及其特点,实现了基于遗传算法的电机优化设计,讨论了保证其全局收敛性的方法,最后给出了基于遗传算法的电机优化设计实例。 关键词:电机优化设计;遗传算法;全局收敛性中图分类号:T M302 文献标识码:A 文章编号:1004-7018(2001)04-0032-02 Abstract :In this paper ,the essence and a pplications of genetic alg orithms are friendly introduced.Based on com paris ons between ge 2netic alg orithms and conventional methods ,the a pplication of genetic alg orithm to motor design is im plemented.In this process ,the meth 2ods to improve the global convergence of genetic alg orithm are dis 2cussed.Finally ,the results of the optimization of three -phase electri 2cal machine design based on genetic alg orithms are presented. K eyw ords :motor optimal design ;genetic alg orithms (G A );glob 2al convergence 1遗传算法的基本思想及其特点 遗传算法是模拟生物进化机制的一种现代优化计算方法。其基本思想是:首先通过编码操作将问题空间映射到编码空间(如[0,1]L ),然后在编码空间内进行选择、交叉、变异三种遗传操作及其循环迭代操作,模拟生物遗传进化机制,搜索编码空间的最优解,最后逆映射到原问题空间,从而得到原问题的最优解。选择操作模拟了个体之间和个体与环境之间的生存竞争,优良个体有更多的生存繁殖机会。在这种选择压力作用下,个体之间通过交叉、变异遗传操作进行基因重组,期望得到更优秀的后代个体,在这场竞争中胜出。选择、交叉、变异遗传操作都是以概率值进行的。这些概率值与当时生存环境和个体适应能力密切相关。从这里可以看出遗传算法是一种随机性搜索算法,但是它不同于传统的随机搜索算法。遗传算法通过交叉算子(Cross over operator )和变异算子(Mutation Operator )的协同作用确保状态空间([0,1]L )各点的概 率可达性,在选择算子(Selection Operator )的作用下保证迭代进程的方向性。 2电机优化设计的数学模型和一般优化方法 电机优化设计的一般数学模型: min/max :f (x ) g i (X )≤0,i =1,2,3,…,m X j ∈[a j ,b j ],j =1,2,3,…,n (1) 其中:X =[x 1,x 2,x 3,…,x n ]为设计参量即电磁系统的参数,如冲片尺寸、绕组参量等。g i (X )(i =1,2,3,…,m )为约束条件,如性能约束和一般约束。由于目标函数f (X )和约束条件g i (X )都是X 的高度非线性函数,因此电机优化设计问题是求解约束非线性最优化问题。 由于电机设计的目标函数f (X )不是一个单纯的数学表达式,而是一段电机设计分析计算程序,在计算目标函数值的同时还计算各个性能指标值,即约束条件函数值,因此利用目标函数的梯度确定搜索方向的优化方法在电机优化设计中是相当繁琐,直接利用目标函数值的优化方法在电机优化设计中具有优势,遗传算法通过选择、交叉、变异算子的协同作用,既保证了搜索的方向性,又满足了状态空间各点的概率可达性,具有概率意义下的全局收敛性。遗传算法继承了传统确定性算法和一般随机算法的优点,是一种新的启发式随机搜索算法。 遗传算法对约束的处理有两种思路:增加修正算子将约束条件反映在遗传算子的设计中;利用惩罚函数法将有约束优化问题转化为无约束优化问题。在电机优化设计中常采取后者。基于遗传算法的惩罚函数主要分为静态惩罚函数、动态惩罚函数和自适应惩罚函数三种[4]。自适应惩罚函数法效果较好,但较复杂; 静态、动态惩罚函数相对较简单,经常使用。约束条件 23 微特电机　2001年第4期