下载文档原格式
20世纪50年代末，国外就有人开始进行课程编排问题研究，Judit Csima & C.C. Gotlieb[16]曾形象化描述并提出一个求解课表问题的数学模型，上世纪70年代，Even和Cooper[17]等人证明了排课问题就是一个NP-Hard问题。
而NP 问题除了穷举法没有绝对的求解方法，这有效地回答了排课在应用中遇到困难的原因，同时认识到了课表编排的复杂性，从理论上证明了要解决大规模的排课问题单纯依靠数学方法是行不通的。
印度Vastapur 大学管理学院的Arabinda Tripathy 在1992年进行了课表编排研究，他在进行课表编制过程中，充分地考“人”的因素，并以“人”为单位进行课表编排，但是效果却差强人意[18]。
有学者指出，可以通过适当地减少变量的个数，从而使得在排课时，最大程度地减少计算量，但是，这种思想无疑是不可取的，因为排课属于一个多目标的优化问题，减少变量的个数，人为地造成课程之间的矛盾[19]。
有学者设计了多重课组进行排课，具体是根据学生自主选课的冲突情况，如果选课学生人数过多，教学与教室之间冲突情况严重，则可以在一周内开设一定数量的重复课程，来解决选课学生人数多的矛盾，但是这种方法的随机性较大，无法从根本上解决排课过程中多目标问题。
加拿大Montreal 大学的Jacques A．Ferland 等人通过研究，认为可以将排课问题分解成两个关联程度较高的子问题：即分成时间表和课程分组，并构造相应的启发函数和惩罚因子，来试图解决排课问题[20]。
在排课过程中，Jacques A．Ferland 等人将SAPHIR 课程调度决策支持系统分成多个功能模块，如数据处理、自动优化、交互优化等模块，利用多重课组来协调解决排课过程中出现的主要矛盾[21]。
Colomi 等人将具有自适应寻优能力的遗传算法用于课程编排问题求解，首先与高校教学过程相关的因素进行编码，然后采用遗传算法模拟自然界的选择、交叉、变异算子寻找最优排课方案，并应用到当前一所高中的排课系统中。
遗传算法综述王宏杰魏先峰薛周建彭丹(贵州大学电子科学与信息技术学院，贵州贵阳550025)摘要：近年来遗传算法越来越广泛地受到世界各国学者的关注，本文简述了遗传算法的发展、特点及其应用。
关键词：遗传；搜索；遗传算法1引言遗传算法(G enet i c A l gori t hm，缩写为G A)，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
它是由美国的J．H ol l and 教授1975年首先提出来的，近年来，由于遗传算法求解复杂优化问题的巨大潜力和工程等领域的成功应用，受到了国内外学者的广发关注。
2遗传算法的发展早在上个世纪40年代，就有学者开始研究如何利用计算机进行生物模拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作。
进入60年代后，美国密执安大学的H oll and教授及其学生们受到这种模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术…遗传算法。
进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。
尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。
此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑都给遗传算法增添了新的活力。
遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。
3遗传算法的特点G A是一种利用自然选择和进化思想在高维空间中寻优的方法，它不一定能寻得最优点，但是它可以找到更优点。
因此G A 可能会暂时停留在某些非最优点上，直到变异发生使它跃居到另一个更优点上。
G A寻优过程的一个重要特点是它始终保持整个种群的进化，这样即使某个体在某时刻丧失了有用的特征，这种特征也会被其他个体所保留并延续发展下去。
3D S可以方便灵活地实现对动画帧中的节点、平面、边界、颜色和轨迹的控制,同时对于物体变形测试,轴心点设置以及段信息的获取和设置也能方便准确地进行。
而keyscri p t语言的优点体现在于其精确的数值计算,它可以对大量的复杂无序的动作进行随机计算,节省了制作时间。
利用keyscri p t编辑器还能方便地进行语法检查并能直接执行无语法错误的keyscri p t程序。
3 内存管理方式3D S使用了独特的Pharlap的虚拟内存管理技术(VMM 386),该技术使3D—Studi o能使用比物理内存RAM更大的空间。
这种内存管理方式与W indow2 s T M的内存管理方式不同,因此一般不在W indow s T M中使用3D S,若要在W indow s T M中使用,则必须在W in2 dow s T M的system1in i中的[386Enh]段加入device= Pharlap1386,使W indow s T M可以使用Pharlap的内存管理方式。
这种内存管理方式也有一些不足,如内存一旦被3D S使用将不被释放。
4 硬件环境使用3D—Studi o410的最低配制要求是386(带协处理器)的主机,至少8兆的内存,20兆以上的硬盘空间,DO S313以上的操作系统。
由于3D S中的许多图形渲染时都必须使用256色,且观看3D S自带的一些图片也必须在256色的模式下进行,所以需要SV GA或TV GA的显示器。
输入系统除了键盘外还必须配有鼠标,也可选配数字化仪。
由于3D S在进行图形渲染需要大容量的内存,同时还需要CPU进行大量的浮点运算,因此当CPU为Pen tium T M、内存为16兆以上,并使用高性能的显示卡时,3D S的动画制作功能才能得到完美体现。
由于ln tel公司生产的CPU兼容的Cyrix、AM D等公司生产的CPU浮点运算能力较差,因此CPU首选还是ln tel公司的产品。
遗传算法综述摘要遗传算法（Genetic Algorithm，GA）是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。
它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。
本文从遗传算法的起源谈起，论述了遗传算法的基本思想和基本原理，并对其性能和收敛性进行了分析，最后还介绍了几种改进的遗传算法及其在求解旅行商问题（TSP）方面的应用。
Genetic algorithm ( Genetic, Algorithm, GA ) is a kind of biological natural selection and genetic mechanism of the random search algorithm, its main characteristic is the group searching strategy and individual in the colony between the exchange of information, search does not rely on gradient information. It is especially suitable for the processing of traditional search method to solve the complex and nonlinear problems, can be widely used in combinatorial optimization, machine learning, adaptive control, planning design and artificial life etc.. This article from the origin of the genetic algorithm, the genetic algorithm basic thought and basic principle, and its performance and convergence are analyzed, finally introduces several improved genetic algorithm for solving the traveling salesman problem ( TSP ) with respect to the application.关键词：遗传算法；搜索算法；TSP；遗传算法收敛性Key words: genetic algorithm; search algorithm; TSP; genetic algorithm convergence1 引言在自然界中，生物要生存下去，就必须进行生存斗争。
遗传算法优化问题研究综述遗传算法是一种基于进化论和遗传学原理的优化算法，被广泛应用于求解复杂问题。
遗传算法具有通用性、自适应性、并行性等优点，因此被应用于各个领域。
本文将综述遗传算法在优化问题中的研究进展和应用情况。
一、遗传算法的基本原理遗传算法是一种群体智能算法，其基本原理来自于进化论和遗传学原理。
整个算法过程可以分为个体编码、适应度评估、选择、交叉和变异五个环节。
个体编码将问题转化为适应度评估可以处理的数值表示形式；适应度评估是对各代种群中每一个个体的适应度进行评估的过程，适应度越好，则个体越可能被选择进行操作；选择是根据个体适应度大小对个体进行筛选，保留好个体进行进化操作；交叉是在选择个体之间进行部分信息交换，产生新的后代；变异是对新后代进行一些可控的随机操作，使其具备某些新性质。
通过这些进化操作，种群可以逐渐进化出适应度更高的个体。
二、遗传算法的改进算法进化策略算法是遗传算法的一种改进算法，其特点在于选择和变异操作。
进化策略算法不对个体进行选择操作，而是将个体分为若干互不干扰的子群。
在每个子群中，个体根据策略进行迭代式改变，直到达到一定停止标准。
与此不同的是，遗传算法的选择和变异操作是在整个种群中进行的。
差分进化算法是遗传算法的另一种改进算法，其特点在于采用差分变异操作。
在差分进化算法中，交叉操作是基于差分变异操作的。
通过选择两个个体以及进行差分，得到新的候选解向量。
由于差分运算减少了变异产生的随机性，提高了算法的收敛速度和效率。
三、遗传算法在优化问题中的应用1.组合优化问题组合优化问题是指通过组合若干元素来构造一个最优解的问题。
遗传算法结合带约束的排序方法可以高效地求解组合优化问题。
具体实现中，可以对候选解按照适应度进行排序，并将排序结果与已知的约束进行比对，从而有效地求出最优解。
2.数值优化问题数值优化问题是指寻找函数或者变量最小或者最大值的问题。
遗传算法可以有效地求解数值优化问题，且相比传统的优化方法有着更快的求解速度和更高的求解精度。
遗传算法简述及代码详解声明：本文内容整理自网络，认为原作者同意转载，如有冒犯请联系我。
遗传算法基本内容遗传算法为群体优化算法，也就是从多个初始解开始进行优化，每个解称为一个染色体，各染色体之间通过竞争、合作、单独变异，不断进化。
遗传学与遗传算法中的基础术语比较染色体：又可以叫做基因型个体(individuals)群体/种群(population)：一定数量的个体组成，及一定数量的染色体组成，群体中个体的数量叫做群体大小。
初始群体：若干染色体的集合，即解的规模，如30，50等，认为是随机选取的数据集合。
适应度(fitness)：各个个体对环境的适应程度优化时先要将实际问题转换到遗传空间，就是把实际问题的解用染色体表示，称为编码，反过程为解码/译码，因为优化后要进行评价（此时得到的解是否较之前解优越），所以要返回问题空间，故要进行解码。
SGA采用二进制编码，染色体就是二进制位串，每一位可称为一个基因；如果直接生成二进制初始种群，则不必有编码过程，但要求解码时将染色体解码到问题可行域内。
遗传算法的准备工作:1) 数据转换操作，包括表现型到基因型的转换和基因型到表现型的转换。
前者是把求解空间中的参数转化成遗传空间中的染色体或者个体(encoding)，后者是它的逆操作(decoding)2) 确定适应度计算函数，可以将个体值经过该函数转换为该个体的适应度，该适应度的高低要能充分反映该个体对于解得优秀程度。
非常重要的过程。
遗传算法基本过程为:1) 编码，创建初始群体2) 群体中个体适应度计算3) 评估适应度4) 根据适应度选择个体5) 被选择个体进行交叉繁殖6) 在繁殖的过程中引入变异机制7) 繁殖出新的群体，回到第二步实例一：（建议先看实例二）求 []30,0∈x 范围内的()210-=x y 的最小值1) 编码算法选择为"将x 转化为2进制的串"，串的长度为5位（串的长度根据解的精度设 定，串长度越长解得精度越高）。
遗传算法综述摘要：遗传算法(genetic algorithms，GA)是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法，适用于处理传统搜索方法难以解决的复杂和非线性优化问题。
遗传算法可广泛应用于组合优化、机器学习、自适应控制、设计和人工生命等领域，是21世纪有关智能计算中的重要技术之一。
本文通过对相关论文的查阅和整理，对遗传算法的研究现状和发展趋势进行了综述并谈论了一些自己的看法。
关键词：遗传算法研究现状发展趋势引言：遗传算法是模拟遗传选择和自然淘汰的生物进化过程的计算模型，由美国Michigan大学的Holland教授于1969年提出，后经DeJong、Goldberg 等人归纳总结，形成一种新的全局优化搜索算法[1]。
遗传算法以其简单通用、鲁棒性强、适于并行处理以及高效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能算法之一。
1、遗传算法的基本原理与传统搜索算法不同, 遗传算法从一组随机产生的初始解,称为群体, 开始搜索过程。
群体中的每个个体是问题的一个解,称为染色体。
这些染色体在后续迭代中不断进化, 称为遗传。
遗传算法主要通过交叉、变异、选择运算实现。
交叉或变异运算生成下一代染色体, 称为后代。
染色体的好坏用适应度来衡量。
根据适应度的大小从上一代和后代中选择一定数量的个体, 作为下一代群体, 再继续进化, 这样经过若干代之后, 算法收敛于最好的染色体, 它很可能就是问题的最优解或次优解。
“遗传算法中使用适应度这个概念来度量群体中的各个个体的在优化计算中有可能到达最优解的优良程度。
度量个体适应度的函数称为适应度函数。
适应度函数的定义一般与具体求解问题有关”[2]。
遗传算法包含两个数据转换操作，一个是从表现型到基因型的转换，将搜索空间的参数或解转换成遗传空间中的染色体或个体，这个过程称为编码（coding）。
另一个是从基因型到表现型的转换，即将个体转化成搜索空间中的参数，这个过程称为译码（decode）。
遗传算法综述
太原理工大学刘晶学号：s2*******
摘要：遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，它借鉴了达尔文的进化论和孟德尔的遗传学说。
其本质是一种高效、并行、全局搜索的方法，它能在搜索过程中自动获得和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优的方案。
遗传算法作为一种实用、高效、鲁棒性强的优化技术，有着广泛的应用前景。
关键词：遗传算法数学模型优点流程
一，概述。
遗传算法（Genetic Algorithm，简称GA）起源于对生物系统所进行的计算机模拟研究。
美国Michigan 大学的Holland 教授及其学生受到生物模拟技术的启发，创造了一种基于生物遗传和进化机制的适应于复杂系统优化的自适应概率优化技术———遗传算法。
二，基本遗传算法的数学模型。
基本遗传算法可表示为：SGA=（C，E，P0，M，Φ，Γ，Ψ，T）式中，C为个体的编码方法；E 为个体适应度评价函数；P0 为初始种群；M为种群大小；Φ为选择算子；Γ为交叉算子；Ψ为变异算子；T为遗传运算终止条件。
三，遗传算法的优点。
3.1 对可行解的广泛性表示。
遗传算法的处理对象不是参数本身，而是针对那些通过参数集进行编码得到的基因个体。
次编码操作
使得遗传算法可以直接对结构对象进行操作。
（1）通过对连接矩阵的操作，遗传算法可用来对神经网络或自动机的结构或参数加以优化。
（2）通过对集合的操作，遗传算法可实现对规则集合和知识库的精炼而达到高质量的机器学习目的。
（3）通过对树结构的操作，用遗传算法可得到用于分类的最佳决策树。
（4）通过对任务序列的操作，遗传算法可用于任务规划，而通过对操作序列的处理，可自动构造的顺序控制系统。
3.2 群体搜索特性。
许多传统的搜索方法都是单点搜索，这种点对点的搜索方法，对于多峰分布的搜索空间常常会陷于局部的某个单峰的极值点，相反，遗传算法采用的是同时处理群体中多个个体的方法。
3.3 不需要辅助信息。
遗传算法仅用适应度函数的数值来评估基因个体，并在此基础上进行遗传操作。
更重要的是，遗传算法的适应度函数不仅不受连续可微的约束，而且某定义域可以任意设定。
对适应度函数的唯一要求是，编码必须与可行解空间对应，不能有死码。
由于限制条件的缩小，使得遗传算法的应用范围大大扩展。
3.4 内在启发式随机搜索特性。
遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方向。
概率仅仅是作为一种工具来引导其搜索过程朝着搜索空间的更优化的解区域移动的。
虽然看起来它是一种盲目搜索方法，实际上它有明确的搜索方向，具有内
在并行搜索机制。
3.5 遗传算法在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数是不连续的、非规则的或有噪声的情况下，也能以很大的概率找到全局最优解。
3.6 遗传算法采用自然进化机制来表现复杂的现象，能够快速可靠的解决求解非常困难的问题。
3.7 遗传算法具有固有的并行性和并行计算的能力。
3.8 遗传算法具有可扩展性，易于同别的技术混合使用。
四，遗传算法流程。
遗传算法的主要运算过程如下：
4.1 编码：解空间的解数据，作为遗传算法的表现型形式，从表现型到基因型的映射称为编码。
遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，这些串结构的数据的不同组合就构成了不同的点。
4.2 初始群体的生成：随即产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。
遗传算法以这N个串结构作为初始点开始迭代。
设置进化代数计数器t←0；设置最大进化代数T；随机生成M个个体作为初始群体P(0)。
4.3 适应度值评价检测：适应度函数表明个体的优劣性。
对于不同的问题，适应度函数的定义方式不同。
根据具体问题，计算群体P(t)中各个个体的适应度。
4.4 选择：将选择算子作用于群体。
4.5 交叉：将交叉算子作用于群体。
4.6 变异：将变异算子作用于群体。
群体P(t)经过选择、交叉、变异运算后得到下一代群体P(t+1)。
4.7 终止条件判断：若t≤T，则t=t＋1，转到步骤4.2；若t>T，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止运算。
五，遗传算法的发展方向
5.1 遗传算法自身的优化
算法在各种问题中得到广泛的应用以来，遗传算法的优化问题就成了人们研究的焦点。
专家学者们从各个方面，在各种细节上采用各种方法试图来改进遗传算法。
从编码方法，控制种群，控制交叉，控制变异等来改进遗传算法。
根据不同问题的需要来选择编码方案，是改进遗传算法最初的手段。
随着编码方案的不断完善，现在从编码方案上来改进遗传算法的意义已经很小。
目前对遗传算法的优化主要有两大手段。
一是利用对种群的控制，在选取种群的时候，在种群的规模，种群的多样性上下功夫。
有的是利用加入种间竞争的手段。
另一种是通过控制交叉方法和变异的概率，根据问题的实际情况来设定一个线性或非线性的函数来控制变异的概率，使得遗传算法在执行的时候能够在加快收敛效率的时候同时保持个体的多样性，有利于找出全局最优解。
这两种优化算法在不同问题的应用中都成功的优化了遗传算法的效率。
5.2 遗传算法与其他计算智能方法的相互渗透和结合
遗传算法是一种通用而有效的求解最优化问题的方法，然而，单用简单的遗传算法在许多情况下不是十分有效，容易产生早熟现象以及局部寻优能力较差等问题，于是提出了多种混合算法。
遗传算法在日益和神经网络、模糊推理以及混沌理论等其他智能计算方法相互渗透和结合，必能达到取长补短的作用，近年来在这方面已取得了不少研究成果，并形成了“计算智能”的研究领域，这对开拓21 世纪新的智能计算技术具有重要的意义。
例如Ackley 推荐的遗传爬山法；Mathefoud 提出的遗传模拟退火算法；Miller 等提出的对于NP 难问题的优化问题，采用遗传算法中增加局部改善运算等等。
混合遗传算法的基本思想是：对于每个新产生的后代在其进入下一代群体之前应用局部优化技术，使之移动到最近的局部最优点。
在混合遗传操作中，运用启发式方法作局部优化，采用遗传算法作全局最优点的探索。
由于遗传算法与传统优化方法的互补性，混合遗传算法通常比单一算法优越。
六，结论
遗传算法作为一种非确定性的拟自然算法，为复杂系统的优化提供了一种解决方法，并且经过实践证明效果显著。
遗传算法是一种全局最优化方法，在优化过程中，它无需体系的先验只是，能在许多局部较优中找到全局最优点，能有效的处理复杂的非线性问题。
遗传算法的理论研究需要进一步深入，应用领域有待进一步开拓。
但可以相信，遗传算法必将在以后得到更为广泛的应用。
参考文献：
[1]陈文伟.智能决策支持技术[M].北京:电子工业出版社，1998，6.
[2]雷英杰，张善文.MATLAB 遗传算法工具箱及应用[M].西安:西安电子科技大学出版社，2006，4
[3]吴家英，郑金华.遗传算法的研究与发展动向[J].横阳师范学院学报, 2003.
[4]李华昌，谢淑兰，易忠胜.遗传算法的原理与应用[J].矿冶,2005，3.
[5]张玲，张钹. 遗传算法机理的研究[J]. 软件学报, 2000,11.
[6]吉根林. 遗传算法研究综述[J]. 计算机应用与软件, 2004,2.
[7]张丽萍，柴跃进.遗传算法的现状及发展动向[J].信息与控制,2001,30.
[8]丁承民，张传生，刘辉.遗传算法纵横谈[J].信息与控制, 1997,26。
