下载文档原格式
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寻优过程的一个重要特点是它始终保持整个种群的进化，这样即使某个体在某时刻丧失了有用的特征，这种特征也会被其他个体所保留并延续发展下去。
遗传算法综述摘要遗传算法（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.数值优化问题数值优化问题是指寻找函数或者变量最小或者最大值的问题。
遗传算法可以有效地求解数值优化问题，且相比传统的优化方法有着更快的求解速度和更高的求解精度。
遗传算法综述作者：常洪江来源：《电脑学习》2010年第03期摘要：本文主要回顾了遗传算法的发展历程，并对遗传算法的基本原理及特点作了简要阐述。
进一步指出了遗传算法存在的问题及相应的改进措施，讨论了遗传算法在实际中的应用。
关键词：遗传算法选择交叉变异适应度函数中图分类号：TF273文献标识码：A文章编号：1002-2422(2010)03-0115-02遗传算法广泛应用于自动控制、计算科学、模式识别、工程设计、智能故障诊断管理科学和社会科学领域，适用于解决复杂的非线性和多维空间寻优问题。
1遗传算法的特点遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。
遗传算法具有进化计算的所有特征，同时又具有自身的特点：(1)搜索过程既不受优化函数的连续性约束，也没有优化函数导数必须存在的要求。
(2)遗传算法采用多点搜索或者说是群体搜索，具有很高的隐含并行性，因而可以提高计算速度。
(3)遗传算法是一种自适应搜索技术，其选择、交叉、变异等运算都是以一种概率方式来进行，从而增加了搜索过程的灵活性，具有较好的全局优化求解能力。
(4)遗传算法直接以目标函数值为搜索信息，对函数的性态无要求。
具有较好的普适性和易扩充性。
(5)遗传算法更适合大规模复杂问题的优化。
2遗传算法的基本原理GA研究的问题是搜索候选假设空间并确定“最佳假设”。
在GA中，“最佳假设”被定义为是使适应度最优的假设，适应度是为当前问题预先定义的数字度量。
2，1遗传算法的原型John Holland教授通过模拟生物进化过程设计了最初的遗传算法，称之为标准遗传算法。
标准遗传算法给出了遗传算法的基本框架，以后对于遗传算法的改进，都是基于此种算法。
尽管遗传算法的实现在细节上有所不同，但都具有以下的共同结构：算法迭代更新一个假设池，这个假设池称为群体。
在每一次的迭代中，根据适应度函数评估群体中的所有成员，然后从当前群体中用概率方法选取适应度最高的个体产生新一代群体。
遗传算法综述遗传算法是计算数学中用于解决最优化的搜索算法，是进化算法的一种。
进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。
在阅读了一些相关资料后，我整理出这篇综述，将通过五个部分来介绍遗传算法以及其在计算机科学领域的相关应用、一、起源和发展分支尝试性地将生物进化过程在计算机中模拟并用于优化问题求解开始于20世纪50年代末，其目的是将生物进化的思想引入许多工程问题中而成为一种优化工具，这些开拓性的研究工作形成了遗传算法的雏形。
但当时的研究进展缓慢，收效甚微。
原因是由于缺少一种通用的编码方式，人们只有通过变异才能改变基因结构，而无法使用交叉，因而增加了迭代次数。
同时算法本身需要较大的计算量，当时的计算机速度便无法满足要求，因而限制了这一仿生过程技术的迅速发展。
20世纪60年代中期，Holland在Fraser和Bremermann等人研究成果的基础上提出了位串编码技术，这种编码技术同时适用于变异操作和交叉操作。
遗传算法的真正产生源于20世纪60年代末到70年代初，美国Michigan大学的Holland教授在设计人工适应系统中开创性地使用了一种基于自然演化原理的搜索机制，并于1975年出版了著名的专著“Adaptation in Natural andArtificial Systems”，这些有关遗传算法的基础理论为遗传算法的发展和完善奠定了的基础。
同时，Holland教授的学生De Jong首次将遗传算法应用于函数优化中，设计了遗传算法执行策略和性能评价指标，他挑选的5个专门用于遗传算法数值实验的函数至今仍被频繁使用，而他提出的在线(on-line)和离线(off-line)指标则仍是目前衡量遗传算法优化性能的主要手段。
在Holland教授和他的学生与同事De Jong进行大量有关遗传算法的开创性工作的同时，德国柏林工业大学的Rechenberg和Schwefel等在进行风洞实验时，为了对描述物体形状的参数进行优化以获得更好的实验数据，将变异操作引入计算模型中，获得了意外的优良效果。
遗传算法与智能算法综述(doc 18页)智能算法综述摘要：随着计算机技术的飞速发展，智能计算方法的应用领域也越来越广泛，本文介绍了当前存在的一些智能计算方法，阐述了其工作原理和特点，同时对智能计算方法的发展进行了展望。
关键词：人工神经网络遗传算法模拟退火算法群集智能蚁群算法粒子群算1 什么是智能算法智能计算也有人称之为“软计算”，是们受自然（生物界）规律的启迪，根据其原理，模仿求解问题的算法。
从自然界得到启迪，模仿其结构进行发明创造，这就是仿生学。
这是我们向自然界学习的一个方面。
另一方面，我们还可以利用仿生原理进行设计(包括设计算法)，这就是智能计算的思想。
这方面的内容很多，如人工神经网络技术、遗传算法、模拟退火算法、模拟退火技术和群集智能技术等。
2 人工神经网络算法“人工神经网络”(ARTIFICIAL NEURAL NETWORK，简称ANN)是在对人脑组织结构和运行机制的认识理解基础之这一结构特点决定着人工神经网络具有高速信息处理的能力。
人脑的每个神经元大约有103～104个树突及相应的突触，一个人的大脑总计约形成1014～1015个突触。
用神经网络的术语来说，即是人脑具有1014～1015个互相连接的存储潜力。
虽然每个神经元的运算功能十分简单，且信号传输速率也较低(大约100次/秒)，但由于各神经元之间的极度并行互连功能，最终使得一个普通人的大脑在约1秒内就能完成现行计算机至少需要数10亿次处理步骤才能完成的任务。
人工神经网络的知识存储容量很大。
在神经网络中，知识与信息的存储表现为神经元之间分布式的物理联系。
它分散地表示和存储于整个网络内的各神经元及其连线上。
每个神经元及其连线只表示一部分信息，而不是一个完整具体概念。
只有通过各神经元的分布式综合效果才能表达出特定的概念和知识。
由于人工神经网络中神经元个数众多以及整个网络存储信息容量的巨大，使得它具有很强的不确定性信息处理能力。
即使输入信息不完全、不准确或模糊不清，神经网络仍然能够联想思维存在于记忆中的事物的完整图象。
遗传算法综述摘要：遗传算法(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
（注：本资料素材和资料部分来自网络，仅供参考。
请预览后才下载，期待您
的好评与关注！）。
