摘 要
本次毕业设计的题目是应用遗传算法设计出一种解决师生双向选择问题的方法，自20世纪为提高毕业设计质量，培养合格的高素质人才，加强毕业设计的指导和管理工作，严格按照一名学生只能选择一位指导老师，每个学生可以根据自己所学的专业知识、感兴趣的学习研究方向、对老师教学方式的偏爱去选择自己的指导老师。老师可以根据平时对该生的了解、课余时间的交流、学生自荐选择所想要指导的学生。这一举措受到了老师和学生的普遍欢迎，增强了学生与老师之间的互相促进，给了同学们和老师充分的选择空间。本程序为学生提供了三个自愿，学生可以根据自己的条件初选三位老师，而且是按照满意度的大小排序选择三位老师。每位老师同样可以按照满意度的大小排序为自己初选几位同学，为了防止一位老师带众多学生的情况出现，我们可以适当的对老师所带学生的个数进行约束。然后我们可以根据遗传算法初始师生互选搭配组合种群，评估适应度函数，并对老师和学生互相选择问题进行选择、交叉、变异等基本操作运算，最终得到师生互选组合的近似最优组合。本文结合惩罚函数，提出了一种改进的遗传算法，并可应用于相当一类的约束优化问题，寻找师生双向选择问题中的最优组合。
关键词：遗传算法，惩罚函数，适应度函数，约束优化问题
Based on genetic algorithm teachers and students two-way job choice question research
Abstract
This graduation project's topic is designs one kind using the genetic algorithm to solve the teachers and students two-way job choice question method, from the 20th century for the enhancement graduation project quality, trained the qualified high quality talented person, strengthened the graduation project the instruction and the supervisory work, only could choose one strictly according to a student to instruct teacher, each student might act according to the specialized knowledge which one studied, be interested the study research direction, to teacher the teaching way to be partial chooses own instructs teacher.Teacher may act according to usually to the understanding which, after school exchange, the student should live offers to volunteer the student who the choice wants the instruction. This action has received teacher and student's general reception, strengthened between the student and teacher's mutual promotion, has given schoolmates and teacher the full choice space. This procedure provided three voluntary for the student, the student has been possible to act according to own condition primary election three teachers, moreover was defers to the degree of satisfaction size sorting to choose three teachers.Each teacher may defer to the degree of satisfaction similarly size sorting for own primary election several schoolmates, to prevent a teacher to have the numerous student's situations to appear, we may suitable have student's integer to teacher to carry on the restraint. Then we may choose the matching combination population mutually according to the genetic algorithm initial teachers and students, the appraisal sufficiency function, and chooses the question to teacher and the student to carry on the choice mutually, overlapping, the variation and so on elementary operation eo operation, obtains the teachers and students to choose the combination mutually finally the shortsighted most superior combination.This article unifies the penalty function, proposed one kind of improvement's genetic algorithm, and may apply in quite a kind of restraint optimization question, seeks for in the teachers and students two-way job choice question the most superior combination.
Key words: genetic algorithm, penalty function, the fitness function, constrained optimization proble
遗传算法的基本步骤
编码：GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合便构成了不同的点。
初始群体的生成：随机产生N个初始串结构数据，每个串结构数据称为一个个体， N个个体构成了一个群体。GA以这N个串结构数据作为初始点开始迭代。
适应性值评估检测：适应性函数表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。
选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则
是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。
交换：交换操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新一代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。
变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，GA中变异发生的概率很低，通常取值在0.001~0.01之间。变异为新个体的产生提供了机会。
将遗传算法用于解决师生互选组合问题后，会由于参数配置不当过早向目标函数的局部最优解收敛，从而很难找到全局最优解。其中也可能是由于目标函数的特性造成的，例如函数具有欺骗性，不满足构造模块假说等等；另外一些则是由于算法设计不当。为此，我们就要不断的试探参数的配置并改进方案。例如：针对随机的选择机制，提出了按比例选择、竞争选择、按续挑选等改进方案；针对原先的单点交叉算子，提出了两点交叉、多点交叉、均匀交叉等算子；针对原先遗传算法各控制参数在进化过程中不变的情况，提出了自适应遗传算法等。
本次设计利用遗传算法的全局寻优和收敛速度快的特点，结合随机选取法和适应度排序法的优点，设计了一种用于老师与学生互选配对组合的算法，使老师与学生互选配对组合的成功率和速度都得到了明显的提高，可以根据不同的需要设置遗传代数，100代和150代的组合结果会有不同，还要看交叉、变异算子，接近最优的组合有可能在遗传的过程中产生。要使师生互选组合达到相对来说更加满意的方案和收敛速度进一步得到改进，还需要做出更深的研究
目 录 12000字
任务书 I
摘 要 II
ABSTRACT III
第1章 绪 论 1
1.1选题背景和意义 1
1.2遗传算法的特点 1
1.3遗传算法的基本步骤 1
第2章 师生互选的编码 3
2.1编码的定义 3
2.1编码的原则 3
2.3师生互选的编码方法 3
第3章 师生互选适应度函数的设定 4
3.1评价每个组合的适应度 4
3.2适应度函数的作用 4
第4章 师生互选的一般操作 6
4.1师生互选的选择操作(selection) 6
4.1.1初始师生互选组合的种群 6
4.1.2计算Uk的适应度值 7
4.1.3计算组合方案群体适应度值的总和 7
4.1.4计算每个组合的选择概率 7
4.1.5计算每个组合的累计概率: 8
4.1.6产生新的师生组合种群 8
4.2师生互选交叉操作 (crossover) 9
4.2.1随机选择一组交叉对象 9
4.2.2定义交叉概率 10
4.2.3产生交叉后的组合方案 10
4.3师生互选组合变异操作(mutation) 11
4.3.1遗传算法中使用变异操作主要有两个目的 11
4.3.2选择变异算子 12
4.3.3定义变异概率 12
4.3.4生成变异后师生组合种群 13
第5章 师生互选过程的说明 15
5.1输入满意度数据库 15
5.2设置遗传参数配置 15
5.3定义满意度权重 15
5.4执行遗传算法操作 16
5.5运行结果 17
5.6遗传算法的终止 17
第6章 结论 18
参考文献 19
致 谢 20 |
