遗传算法原理和应用（精选6篇）
遗传算法原理和应用 篇1
1 遗传算法的基本原理
遗传算法类似于自然进化,通过作用于染色体上基因寻找最好的染色体来求解问题。与自然界相似,遗传算法对求解问题的本身一无所知,它所需要的仅是对遗传算法所产生的染色体有更多的繁殖机会。在遗传算法中,通过随机方式产生若干个所求解问题的数字编码,即染色体,形成初始种群;通过适应度函数给每个个体一个数值评价,淘汰低适应度的个体,选择高适应度的个体参加遗传操作,经过遗传操作后的个体集合形成下一代新的种群,对这个新种群进行下一轮进化。
2 遗传算法的主要步骤
(1)初始化。选择一个群体,即选择一个串或个体的集合bi,i=1,2……n。这个初始的群体也就是问题假设解的集合。一般取n=30~160。通常以随机方法产生串或个体的集合bi,i=1,2……n。问题的最优解将通过这些初始假设解进化而求出。
(2)选择。根据适者生存原则选择下一代的个体。在选择时,以适应度为选择原则。适应度准则体现了适者生存、不适者淘汰的自然法则。
给出目标函数f,则f(bi)称为个体bi的适应度。以P{选中为选中bi的下一代个体的次数。
显然,从上式可知:(1)适应度较高的个体,繁殖下一代的数目较多;(2)适应较小的个体,繁殖下一代的数目较少,甚至被淘汰。这样,就产生了对环境适应能力较强的后代。对于问题求解角度来讲,就是选择出和最优解较接近的中间解。
(3)交叉。对于选中用于繁殖下一代的个体,随机地选择两个个体的相同位置,按交叉概率P,在选中的位置实行交换。这个过程反映了随机信息交换;目的在于产生新的基因组合,也即产生新的个体。交叉时,可实行单点交叉或多点交叉。
例如有个体
S1=100101
S2=010111
选择左边3位进行交叉操作,则有
S1=010101
S2=100111
一般而言,取值为0.25~0.75。
(4)变异。根据生物遗传中基因变异的原理,以变异概率Pm对某些个体的某些位执行变异。在变异时,对执行变异的串的对应位求反,即把1变为0,把0变为1。变异概率Pm与生物变异极小的情况一致,所以Pm的取值较小,一般取0.01~0.2。
例如有个体S=101011,对其的第1、4位置的基因进行变异,则有S'=001111。
单靠变异不能在求解中得到好处。但是,它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时,交叉是不能产生新的个体的,这时只能靠变异产生新的个体。也就是说,变异增加了全局优化的特质。
(5)全局最优收敛(Convergence to the global optimum)。当最优个体的适应度达到给定的阈值,或者最优个体的适应度和群体适应度不再上升时,则算法的迭代过程收敛、算法结束。否则,用经过选择、交叉、变异所得到的新一代群体取代上一代群体,并返回到第(2)步即选择操作处继续循环执行。
3 遗传算法的应用
3.1 遗传算法的应用关键
遗传算法在应用中最关键的问题有如下3个。
(1)串的编码方式。本质是问题编码。一般把问题的各种参数用二进制编码,构成子串;然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。
(2)适应函数的确定。适应函数(fitness function)也称对象函数(object function),这是问题求解品质的测量函数;往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数;但有时需要另行构造。
(3)遗传算法自身参数设定。遗传算法自身参数有3个,即群体大小n、交叉概率Pc和变异概率Pm。
群体大小n太小时难以求出最优解,太大则增长收敛时间。一般n=30-160。交叉概率Pc太小时难以向前搜索,太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构,太大使遗传算法成了单纯的随机搜索。一般取Pm=0.01-0.2。
3.2 遗传算法的主要应用领域
遗传算法的主要应用领域在于函数优化(非线性、多模型、多目标等),机器人学(移动机器人路径规划、关节机器人运动轨迹规划、细胞机器人的结构优化等),控制(瓦斯管道控制、防避导弹控制、机器人控制等),规划(生产规划、并行机任务分配等),设计(VLSI布局、通信网络设计、喷气发动机设计等),组合优化(TSP问题、背包问题、图分划问题等),图像处理(模式识别、特征提取、图像恢复等),信号处理(滤波器设计等),人工生命(生命的遗传进化等)。
4 遗传算法的研究新动向
4.1 基于遗传算法的机器学习
这一新的研究方向把遗传算法从历史离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。遗传算法作为一种搜索算法从一开始就与机器学习有着密切联系。分类器系统CS-1是GA的创立者Holland教授等实现的第一个基于遗传算法的机器学习系统。分类器系统在很多领域都得到了应用。例如,分类器系统在学习式多机器人路径规划系统中得到了成功应用;Goldberg研究了用分类器系统来学习控制一个煤气管道仿真系统;Wilson研究了一种用于协调可移动式视频摄像机的感知运动的分类器系统等。分类器系统在基于遗传算法的机器学习研究中影响很大,但具体实现方法和要解决的具体问题有关。基于遗传算法的概念学习是近几年来机器学习领域的一个较为引人注目的研究方向。由于概念学习隐含的搜索机制,使得遗传算法在概念学习中有用武之地。目前也有一些嵌入领域知识的基于遗传算法的机器学习的研究,如将概念学习中特有的操作遗传化,并显示出一定的优点。此外,学习分类系统的并行实现在基于遗传算法的机器学习研究中也占有相当的分量。
4.2 遗传算法与其他计算智能方法的相互渗透和结合
遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合,以达到取长补短的作用。近年来在这方面已经取得了不少研究成果,并形成了“计算智能”的研究领域,这对开拓21世纪中新的智能计算技术具有重要意义。GA的出现使神经网络的训练(包括连接权系数的优化、网络空间结构的优化和网络的学习规划优化)有了一个崭新的面貌,目标函数既不要求连续,也不要求可微,仅要求该问题可计算,而且搜索始终遍及整个解空间,因此容易得到全局最优解。GA与神经网络的结合正成功地被用于从时间序列的分析来进行财政预算,在这些系统中,训练信号是模糊的,数据是有噪声的,一般很难正确给出每个执行的定量评价,如采用GA来学习,就能克服这个困难,并显著提高系统的性能。Muhlenbein分析了多层感知机网络的局限性,并猜想下一代神经网络将会是遗传神经网络。遗传算法还可以用于学习模糊控制规划和隶属度函数,从而更好地改善模糊系统的性能。将模糊逻辑、神经网络和遗传算法三者有机地结合起来应用于温室夏季温湿度控制中,实验结果表明得到了良好的控制效果。混沌表现出的随机性是系统内在的随机性,被称为伪随机性,在生物进化中起着重要作用,是系统进化与信息之源。混沌与遗传算法的结合已有人进行过尝试,如吴新余等采用多种混沌模型构造随机开关,以此控制交叉操作以改进GA的性能,采用混沌序列构造变异算子,为遗传算法的实现开辟了新的途径。
4.3 并行处理的遗传算法
并行处理的遗传算法的研究不仅是遗传算法本身的发展,而且对于新一代智能计算机体系结构的研究都是十分重要的。GA在操作上具有高度的并行性,许多研究人员都在探索在并行机上高效执行GA的策略。研究表明,只要通过保持多个群体和恰当地控制群体间的相互作用来模拟并执行过程,即使不使用并行计算机,我们也能提高算法的执行效率。在并GA的研究方面,一些并GA模型已经被人们在具体的并行机上执行了;并行GA可分为两类:一类是粗粒度并行GA,主要开发群体间的并行性,如Cohoon分析了在并计算机上解图划分问题的多群体GA的性能;另一类是细粒GA,主要开发一个群体中的并行性,如Kosak将群体中的每个个体映射到一个连接机的处理单元上,并指出了这种方法对网络衅设计问题的有效性。
4.4 遗传算法与人工生命的渗透
人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统,人工生命与遗传算法有着密切的关系,基于遗传算法的进化模型是研究人工生命现象的重要理论基础。虽然人工生命的研究尚处于启蒙阶段,但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力,并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成,遗传算法为人工生命的研究提供了一个有效的工具,人工生命的研究也必将促进遗传算法的进一步发展。
4.5 遗传算法与进化规则及进化策略的结合
遗传算法、进化规则及进化策略是演化计算的3个主要分支,这3种典型的进化算法都以自然界中生物的进化过程为自适应全局优化搜索过程的借鉴对象,所以三者之间有较大的相似性;另一方面,这3种算法又是从不完全相同的角度出发来模拟生物进化过程,分别是依据不同的生物进化背景、不同的生物进化机制而开发出来的,所以三者之间也有一些差异。随着各种进化计算方法之间相互交流深入,以及对各种进化算法机理研究的进展,要严格地区分它们既不可能、也没有必要。在进化计算领域内更重要的工作是生物进化机制,构造性能更加优良、适应面更加广泛的进化算法。
5 结束语
遗传算法经过几十年的发展,逐渐被人们接受和运用。其应用涉及从工程科学到社会科学的诸多领域。在工程领域特别是人工智能和控制领域中的超大规模、非线性系统优化问题中,遗传算法成为有效求解的得力工具,而这些问题正是传统方法难以解决的。由于遗传算法本身就是一个模拟自然演化的具有自组织、自适应和自学习特征的算法,因此它以独立的或与其它方式相结合的形式被用于机器智能系统设计中。
与此同时,遗传算法作为一种非确定性的拟自然算法,为复杂系统的优化提供了一种新方法,并且经过实践证明效果显著。尽管遗传算法在很多领域具有广泛的应用价值,但仍存在一些问题,例如局部搜索能力差,存在未成熟收敛和随机漫游等现象,从而导致算法的收敛性能差,需要很长时间才能找到最优解,这些不足阻碍了遗传算法的推广应用。如何改善遗传算法的搜索能力和提高算法的收敛速度,使其更好地应用于实际问题的解决中,各国学者一直在探索着。
参考文献
[1]BUCHANAN BG,GLICK J.AI topics,A responsibility to celebrate AI responsibly.AI Magazine,Spring2002.
[2]R J MITCHELL,B CHAMBERS,A P ANDERSON.Array pattern synthesis in the complex plane optimized by a genetic algorithm.Electronics letters,1993(20).
[4]SAVIC D A,EVANS K E,SILBERHORN THORSTEN.A genetic algorithm based system for the optimal design of laminate.Computer Aided Civil and Infrastructure Engineering,1999(14).
[5]PATRICK SIZRRY,FRANCOIS GUELY.A Genetic Algorithm for Optimizing Takagi-Sugeror Fuzzy Rule Bases.Fuzzy Sets and Sys-tem,1998(99).
[6]张文修,梁怡.遗传算法的教学基础[M].西安:西安交通大学出版社,2000.
[7]蒋腾旭.智能优化算法概述[J].电脑知识与技术,2007(8).
[8]任庆生,叶中行.遗传算法中常用算子的分析[J].电子学报,2005(5).
[9]余建坤,张文彬,陆玉昌.遗传算法及其应用[J].云南民族学院学报,2002(4).
[10]蔡自兴,徐光祐.人工智能及应用[M].北京:清华大学出版社,2003.
遗传算法在入侵检测中的应用 篇2
关键词：遗传算法；入侵检测；神经网络；人工免疫；数据挖掘
中图分类号：TP393文献标识码：A文章编号：1009-3044(2007)15-30826-02
The Survey of Intrusion Detection System Based on Genetic Algorithms
WANG Xiu-ying
(Xinqiao Vocational College, Shanghai 200237, China)
Abstracts:The basic concept and mechanism of IDS and GA was presented. GA's application and Fusion with other method in IDS was reviewed in this paper.
Key words:GA; IDS; neural networks; artificial immune; data mining
1 引言
近年来，随着Internet的蓬勃发展，网络本身的安全性问题显得尤为重要。网络安全的主要威胁是通过网络对信息系统的入侵，常见的网络攻击有：口令攻击、缓冲区溢出攻击、利用程序攻击、网络监听、拒绝服务等[1]。为了实现计算机和Internet的安全，在计算机网络中引入了防火墙技术，作为一种静态防护技术。作为对防火墙技术的补充，入侵检测以其以其动态防护特点，成为实现网络安全的新的解决策略。
2 入侵检测技术
入侵检测技术在1980年由James Anderson提出[2]，他将入侵尝试或威胁定义为：潜在的、有预谋的、未经授权的访问信息、操作信息，致使系统不可靠或无法使用的企图。他提出审计追踪可应用于监视入侵威胁。
入侵检测技术主要有两种分类[3]，异常检测方法（anomaly detection）和误用检测技术（abuse detection）。根据检测和推理方法的不同可将系统分为基于统计 (statistical profile-based) 和基于规则(rule-based)的异常检测两种方法。根据攻击签名的表示方法以及攻击时间的检测方法，又可以分为基于专家系统知识的（if－then－else）推理、状态转移分析、模式匹配的误用检测方法。
1995年以后出现了很多不同的新的研究方法特别是智能检测：包括神经网络、遗传算法、模糊识别、免疫系统、数据挖掘等。
3 遗传算法
3.1 遗传算法原理
遗传算法（Genetic Algorithm, GA）是近年来迅速发展起来的一种全新的随机搜索与优化算法，其基本思想是基于Darwin的进化论和Mendel的遗传学说。该算法由密执安大学教授Holland及其学生于1975年创建[4]。遗传算法是一种模拟生命进化机制的搜索优化方法，它模拟了自然选择和遗传中发生的繁殖、交配和突变现象，从初始种群出发，通过随机选择、交又和变异操作，产生新的更适应环境的个体，使群体进化到搜索空间中越来越好的区域．这样一代一代不断繁殖进化，最后收敛到一群最适应环境的个体上，求得问题的最优解。图1[5]给出了一个简单的遗传算法的结构图。
在将遗传算法应用于入侵检测规则学习的过程中，需要考虑3个主要问题：(1)对染色体的编码；(2)确定一个能够有效评价染色体性能的适应度函数；(3)遗传算子的选择。
3.2 遗传算法在入侵检测中的应用
由于遗传算法利用了生物进化和遗传的思想，所以将它应用于入侵检测规则发现中与传统方法具有不同的特征：首先，它的处理对象是问题参数的编码集，而不是参数本身；其次，遗传算法在搜索空间中同时对很多点进行求解，这样就减小了收敛于局部最小的可能，增强了鲁棒性，同时也增加了处理的并行性。
图1 简单的遗传算法的结构
遗传算法在入侵检测中的应用大致可以分为以下三类：用于误用检测模型、用于异常检测模型、和其他技术结合应用于入侵检测中。本文重点介绍GA和其他技术结合在入侵检测中的应用。
3.2.1 基于遗传的误用检测模型
基于误用的入侵检测系统如RIPPER（二十世纪八十年代后期一种基于规则的专家系统）由于需要不断地更新规则，需要大量的维护代价，所以还有待改进。关健[6]提出了一种基于遗传算法的入侵检测规则自动学习方法，主要利用遗传算法的启发式搜索能力，在网络连接数据空间中搜索最优的攻击归纳规则，优于RIPPER算法。
3.2.2 基于遗传算法在异常检测中的应用
考虑到基于误用的IDS不能有效检测未知入侵行为，而基于统计的异常检测法在建模时忽略了多变量在一段时间内的关系，张凤斌等[7]提出了一种异常检测算法．用滑动窗口将系统各属性表示为特征向量，从而将系统正常状态分布在n维空间中，并使用遗传算法进化检测规则集来覆盖异常空间，降低了漏报率、误报率。
3.2.3 其他技术和GA相结合在入侵检测中的应用
(1) GA算法和支持向量机(SVM)相结合
在文献[8]中提到了利用支持向量机和GA相结合的办法，SVM技术是一种新的分类技术它比传统的在生物信息和模式识别中。在所有的特征中选择优良的特征就显得尤其重要，SVM不仅可以提高检测率，还可以提高检测的稳定性。而GA算法可以提供快速和良好的优化效果。
(2) GA算法和数据挖掘技术相结合
基于经典集合的数据挖掘会产生所谓的“边界锐化”问题，变量值的微小变化就可能导致分类结果的变化。将遗传算法和模糊逻辑引入到入侵检测中，一方面通过对网络流量数据和主机审计数据进行模糊数据挖掘，产生更高抽象层次上的检测规则来对异常行为进行检测；另一方面采用遗传算法优化模糊集合隶属函数，从而达到提高入侵检测系统性能的目的。文献[9]给出一个包含遗传算法的模糊数据挖掘框架，见图2。
图2 自适应的入侵检测模型
(3) GA算法和神经网络相结合
常规的神经网络如BP网有时不收敛、或收敛速度太慢或有时陷入局部最小或产生振荡。而进化方法将网络的连接及其权值都用二进制串进行编码，通过不断的进化、杂交和变异，获得全局意义上的最优的网络结构和模型。文献[10]将神经网络与遗传算法结合，提出了入侵检测的进化神经网络方法，是个高效并行非线性动态处理系统，可以满足实时处理要求。用进化神经网络方法不断演化，寻找最优的网络结构自动搜索。
(4) GA和人工免疫理论结合在入侵检测中应用
为了实现入侵检测的自动化、高效性，S.Forrest第一个提出将免疫原理运用于计算机安全[11]，并提出了用于检测器（Detector）生成的否定选择（Negative Selection Algorithm）。否定选择算法有三个阶段组成：首先，建立被监控系统的正常行为描述，即“自我”特征模式集;接着随机生成大量的特征模式，并将这些生成的模式与“自我”的模式进行匹配比较，如匹配就将该模式删除，而剩下的所有的模式构成“检测器”模式集;最后监控新出现的模式，并与“检测器”模式集相比较，如匹配，则说明当前存在“非我”的特征模式，是不安全的。很显然通过这种方式可以容易地检测未知的入侵模式。但利用该方法进行网络检测时存在问题，主要原因是其“检测器”模式集是随机生成的，存在的问题包括：完备性问题、有效性问题和“自我”的描述模式应随着时间的推移重新学习，这也将导致“检测器”模式集的全部更新，如何提高学习与更新的效率也是一个问题。
基于遗传算法的检测器模式集生成与优化过程如图3所示，[6]其中用G来代表进化的代(Generation)，整个优化过程在经过MAX_GEN代遗传后结束，而每一代的优化通过多次的遗传操作迭代来完成，并要经过否定选择算法去除与“自我”匹配的模式。
4 结束语
基于遗传算法的入侵检测规则自动学习方法，主要利用遗传算法的启发式搜索能力，在网络连接数据空间中搜索最优的攻击归纳规则，具有较优的性能。入侵检测系统中把遗传算法和SOM、数据挖掘技术，人工神经网络、SVM等技术相结合，都有较好的研究和应用前景。
图3 基于遗传算法的检测模式集优化过程
参考文献：
[1]张小斌, 严望佳. 黑客分析与防范技术[M]. 北京：清华大学出版社,1999.
[2] Anderson J P. Computer security threat monitoring and surveillance[P]. PA 19034, USA,1980.4.
[3] Helman, P., Liepins, G., and Richards, Foundations of Intrusion Detection. Proceedings of the Fifth Computer Security Foundations Workshop. pp.114-120 Franconia, 1992.
[4] Holand J H. Adaptation in natural and artificial systems. M: University of v Michigan Press. 1975.
[5] Pohlheim, H. Competition and Cooperation in Extended Evolutionary Algorithms. in Spector, L. (ed.): GECCO'2001 - Proceedings of the Genetic and Evolutionary Computation Conference-Late Breaking Papers. San Francisco, CA: Morgan Kaufmann Publishers, 2001.
[6] 关健，刘大昕. 一种基于遗传算法的误用检测模型自适应建立算法[J]. 哈尔滨工程大学学报,Vol.25 No.1 Feb.2004.
[7] 张凤斌，杨永田，江子扬. 遗传算法在基于网络异常的入侵检测中的应用[J]. 电子学报,Vol.32 No.5 May 2004.
[8] Dong Seong Kim, Ha-Nam Nguyen, Syng-Yup Ohn, and Jong Sou Park. Fusions of GA and SVM for Anomaly Detection in Intrusion Detection System ISNN 2005, LNCS 3498, pp. 415.420, 2005. Springer-Verlag Berlin Heidelberg 2005.
[9] Hossain, Mahmood and Susan M. Bridges. 2001. A framework for an adaptive intrusion detection system with data mining[C]. In Proceedings of the 13th Annual Canadian Information Technology Security Symposium, Ottawa, Canada, June, 2001.
[10] 王丽娜，董晓梅，于戈，王东. 基于进化神经网络的入侵检测方法[J]. 东北大学, 2002,23(2):107-110.
[11] S. Forrest, A.S. Perelson, L. Allen, R. and Cherukuri．Self-nonself discrimination in a computer. In Proceedings of the 1994 IEEE Symposium on Research in Security and Privacy, Los Alamitos, CA: IEEE Computer Society Press(1994).
遗传算法的原理及组成浅析 篇3
1 遗传算法的主要步骤及
遗传算法操作的是一群编码化的可行解, 称作种群p (t) 。它通过种群的更新与迭代来搜索全局最优解。种群的迭代是通过选择、杂交和变异等具有生物意义的遗传算子来实现的。在算法中, 进化过程是通过一代群体p (t) 向下一代群体p (t+1) 的演化完成的, 每一代群体由若干个个体组成, 每个个体称为一个染色体, 而每个染色体是一系基因组成的基因串。每个染色体由于其中所含基因排列方式的不同而表现出不同的性能[1]。
算法在整个优化过程中的遗传操作是随机的, 但它所呈现出的特性并不是完全随机的搜索, 它能有效的利用历史信息来推测下一代的期望性能有所提高的寻优点集, 这样反复进行, 最后收敛到一个最优解。
2 遗传算法的组成
遗传算法主要由几个部分组成:编码方式、适应度函数、遗传操作、算法终止条件。要利用遗传算法成功的解决优化问题, 每个部分的设计都非常关键。
2.1 编码
编码原理遗传算法不是对所求问题的实际优化变量直接操作, 而是对表示可行解的遗传编码 (即个体) 作遗传操作。因此遗传算法中在进行搜索之前需要把解空间的可行解转换为搜索空间的基因型结构, 这些串结构数据的不同组合便构成了不同的点。编码问题实际上是问题空间到表示空间的映射问题。
一个好的编码方法, 有可能会使得交叉运算、变异运算等遗传操作可以简单地实现和执行[2]。
通常的编码方法包括: (1) 二进制编码方法; (2) 格雷码编码方法; (3) 浮点数编码方法。
符号编码方法: (1) 多参数级联编码方法; (2) 多参数交叉编码方法。
2.2 适应度函数的设计
从数学角度看, 遗传算法实质上是一种溉率性捜索算法。但它也具有一定的智能特怔。遗传算法是在适应度函数的指导下进行搜索。而不是穷举式的全面搜索。适应度函数评估是选择操作的依据。各个体适应度函数值的大小决定了它们是继续繁衍还是消亡。相当于是自然界中各生物对环境的适应能力的大小。通常, 适应度大的个体具有更适应环境的基因结构。再通过基因重组和基因突变等遗传操作, 就可能产生更适应环境的后代。改变种群内部结构的操怍皆通过适应度加以控制。适应度函数的选取直接影响到遗传的收敛性及收敛速度。
2.2 遗传操作
基本遗传搡作包括:选择、交叉、变异。
1) 选择。选择操作决定如何从当前种群中选取个体作为产生下一代种群的父代个体。不同的选择策略将导致不同的选择压力, 即最佳个体选中的概率与平均中概率的比值。但也较容易出现过早收敛现象;较小的选择压力能使种群保持足够的多样性。从而增大算法收敛到全局最优的概率, 但算法收敛速度一般较慢。
常用的选择方法有:
(1) 基于比例的适应度分配 (proportional fitness assignment) 方法
基干适应度比例的选择方法利用比例于各个体适应的概率决定其子孙的遗留可能性。包括繁殖池选择 (breeding pool selection) 、轮盘赌选择 (roulette wheel selection) 等方法。
(2) 基于排名的适应度分配 (rank-based fitness assignment) 方法
基于排名的选择方法包括线性排名选择和非线性排名选择等方法, 是将种群中的个体按目标值进行排序。适应度仅仅取决于个体在种群中的序位, 而不是实际的目标值。
常用选择方法还包括局部选择、截断选择、锦标赛选择、稳态繁殖等。
2) 交叉
在生物的自然进化过程中, 两个同源染色体通过交叉而重组形成新的染色体, 从而产生出新的个体或物种。交配重组是生物遗传和进化过程中的一个主要坏节。模仿这个环节, 在遗传算法中也使用交叉算子来产生新的个体。
常用的几种交叉算子有:
(1) 实值重组;离散重组;中间重组;线性重组;扩展线性重组。
(2) 二进制交叉;单点交叉;多点交叉;均匀交叉;洗牌交叉;缩小代理交叉。
3) 变异
变异是遗传算法中保持生物多样性的一个重要途径。它以一定概率选择某一基因座, 通过改变该基因座的基因值来获取新个体。
算法中的适应值函数要求是非负的, 而一般优化问题的目标函数并不满足这个条件。常用的实现变异的适应度变换有以下三种[3]:
(2) 乘幕尺度变换。变换公式为:J′=a J (A) +β, 坌A∈HL
即新的适应度是原适应度的某个指定乘幕。幕指数K与变换目的及所求解的问题有关。
(3) 指数尺度变换換公式为:J′=a J (A) +β, 坌A∈HL
指数比例既可以让非常好的个体保持较多的复制机会, 同时又限制了其复制数目以免它很快的控制整个群体。
3 遗传算法的不足及改进
通过分析, 可以看出在用遗传算法进行路径规划时, 随机产生初始种群, 为了避免陷人局部极值点, 种群数量要达到一定的规模。但种群规模大会导致搜索空间较大, 删除冗余个体的能力较差, 大大影响路径规划的速度。特别在环境较为复杂的情形下, 这种缺点就更加明显。
为了更好地发挥遗传算法的作用, 众多学者从各方面对算法进行深人研究和讨论, 目前的改进策略大致可以分为以下两方面[4]:
(1) 改进遗传算法的各组成部分。如:设计新的编码方式、动态的、自适应的参数操作、新奇的遗传操作等, 来进一步改善算法的性能 (如:收敛速度慢、早熟、易陷入局部最优解等) 。
(2) 由于遗传算法的操作简单, 较容易与其他方法结合, 实验研究表明这种改进相对是比较有效的。如:为克服早熟等缺陷, 提出与禁搜索 (Tabu search) 结合, poths提出基于迁移和人工选择的遗传算法;为解决局部优的问题, 遗传算法分别与模糊集 (Fuzzy set) 、与混沌 (Chaos结合、与单纯形、与爬出法、神经网络、正交设计、免疫等结合来不断优化算法。
在问题越来越复杂化的今天, 遗传算法也应与时倶进, 只有通过不同的方式来对算法的结构、参数、操作不断改进和提高, 才能设计高效的遗传算法, 满足现代社会的需要。
摘要：本文简单讨论了遗传算法的特点、组成, 即介绍了算法的交叉及常用的交叉算子、变异, 其中进一步说明算法的编码原理、适应度函数设计, 最后提出该算法的不足之处和改进。
关键词：遗传算法,参数,适应度函数
参考文献
[1]张文修, 梁怡.遗传算法的数学基础[M].西安:西安交通大学出版社, 2000.
[2]张晓绩, 方浩, 戴冠中.遗传算法的编码机制研究[J].信息与控制, 1997, 26 (2) :134-139.
[3]周浦城, 洪炳镇, 杨敬辉.基于遗传算法的移动机器人路径规划方法[J].哈尔滨工业大学学报, 2004, 36 (7) :880-883.
遗传算法在大学排课问题中的应用 篇4
关键词：排课遗传算法最优解冲突检测
中图分类号：O24文献标识码：A文章编号：1007-3973(2010)09-167-02
当今时代，伴随着计算机技术的快速发展，许多繁琐的人工操作已经被计算机系统所取代。排课系统作为高校教务管理系统中最重要也最复杂的部分之一，已经成为国内外众多高校以及软件公司的研究课题，在这方面也取得了许多的理论成果和实现方法。因此，研究开发一个实用的排课系统具有十分重要的现实意义。
1、研究背景
随着我国教育体制改革的不断深入和发展，高校的办学规模逐年扩大，因此，编排一张适用的、科学的课表已经成为每一所高校在新学期开始之前必须进行的一项极其重要工作。简而言之，它具体的工作内容就是将课程、教师、教室和学生四者之间进行合理的调度分配，从而达到四者之间的完美结合，从而使整个教学活动能够正常、有序地顺利进行。
大学课表的编排不但数量多、规模大、涉及的因素多、限制条件多，而且结构复杂，要想编排出合理、科学的课表必然要消耗大量的时间与精力，它复杂性的原因在于排课中资源约束条件与特殊要求对有限时空目标的限制。由于近几年各个高校连年扩招，使得课程安排的工作量逐年增大，学校自身问题的逐步暴露，这也给课程安排增加了许多的难度，这些问题主要包括：教室资源的不足、师资力量的不足、多媒体教学设备的不足等，这些问题的出现对排课工作提出更高的要求。
伴随着科学技术的不断发展和提高，计算机具有的强大功能已经被人们所深刻地认识，计算机应用技术也已经逐渐进入人类社会的各个领域，同时在各个领域都发挥着非常重要的作用。作为计算机应用技术的一部分，通过计算机进行排课，具有手工排课无法比拟的优点，包括：排课速度快、省时省力、查找方便、检索迅速、可靠性较高、保密性较好、存储量较大、人工成本较低、使用寿命较长等。这些优点可以极大地提高排课管理工作的效率。排课系统是对一个教育单位而言是不可缺少的重要组成部分，排课效果的好坏直接影响到教学工作能否有序地、正常地开展，对于学校的领导来说也是一项至关重要的工作，因此排课系统必须为用户提供充足的信息以及快捷的查询手段。利用计算机进行排课操作，任何具有使用者都能够清晰的看到教学中的各种信息，可以高效、快速的工作，这不但减轻了教务人员手工排课的工作，而且极大提高了管理工作的效率，可以合理高效地分配、利用教学资源，间接地提高了教学质量，推进了教学活动的良性循环。因此，研究并改进一个排课系统具有十分重要的实际意义。
2、排课原则
排课问题实质上一种资源竞争问题。在排课过程中要全面考虑教师、课程、教室、时间、学生人数等多方面因素，做到统筹兼顾，才能排出即符合教学规律，又满足各方面要求的课程表。一个好的课表应该既能符合学校的管理要求，又能满足所有参与者的基本要求，尽量使绝大多数课程的安排能够令学校师生满意。为了达到这样的目的，在排课中必须遵守以下六个基本原则：
(1)在同一时间段内，一位教师只能安排一门课程。
(2)在同一时间段内，一个班级只能安排一门课程。
(3)在同一时间段内，一间教室只能安排一门课程。
(4)根据能提供的教室总数安排同一时间段内安排的课程总数，二者要相适应。
(5)每门课程的学生人数不应大于所安排教室的座位数，二者也要相适应。
(6)多媒体教室应合理安排，因为有的科目用多媒体设备教学的效果比较好，但是有的科目并不需要多媒体教室，如果安排了多媒体，就造成了教学资源的浪费。
同时，为了使排出的课表更具人性化、更合理、更科学，排课还需要考虑以下五个因素：
(1)尽可能保证同一个班级连续的两门课之间更换教室的机率最小，或就近安排。
(2)每门课程在一周内的上课时间尽可能合理分布。
(3)同一门课程的不同上课时间应尽可能安排在同一间教室，同时要隔一天以上再安排，以给任课教师留出充足的备课和批改作业的时间，使学生也有足够的时间复习和消化所学的内容，并有时间预习下次课的内容。
(4)学生每天必修课的安排尽可能趋于合理、平衡，应尽量避免出现全天有课，而第二天一天没课的情况。
(5)满足个别教师(如外聘教师)的特殊上课时间要求。
3、遗传算法在排课问题中的应用
遗传算法应用类似基因演化的循环过程，它的演算过程如下：
(1)根据排课的因素产生相关基因编码和染色体，并随机产生一定数目的初始种群，即一定数目的班级课程表。
(2)对个体，即班级课程表适应度进行评估，如果个体的适应度与优化准则相符，则输出最佳个体和它所代表的最优解，并结束计算，否则进入第(3)步。
(3)依据适应度情况选择再生个体。
(4)按照一定的交叉概率及交叉方法生成新个体。
(5)按照一定的变异概率及变异方法生成新个体。
(6)由交叉和变异产生新一代种群，之后返回第(2)步，最后进行冲突检测与消除。
通常可利用编码技术对变量进行编码，将变量转化成适合群体进化的表达形式。对目标函数进行处理操作，使其能够蕴含遗传算法的适应度函数。这样，在群体进化的过程之中，适应度就能够反映模型的目标函数。当群体进化结束的时候，适应度值最大的那个个体对应的目标函数值最小，这个个体即为最优解。最佳个体的产生过程是这样的：首先产生一个初始化种群，然后对初始化种群中的每一个个体进行适应度的计算，得出个体对环境的适应程度。计算后的这个个体能否满足准则判定，如果能够满足，那么算法就找到了这个个体并停止计算，如果不满足准则判定，那么算法将会对这个种群进行选择、交叉、变异等相关操作。遗传操作的目的是从初始化种群中筛选出较优的个体，之后进行演变，对演变后的子代群体，再重新进行优化准则的判定，如此循环下去，直到找到一个最优的个体，或者不满足其它循环条件为止。
约束条件和优化的目标有轻重缓急的分别，约束条件必须满足，优先级别必须最高，同时，各种优化目标之间也有优先级的分别，应尽量满足级别较高的优化目标。将它们都转化成罚值，而其罚值权则是不同的，高一级的罚值权比所有低级的罚值的和值还要大。由此可以得出，采用静态定标罚值权的方法是不可取的，因此我们采用动态罚值权的定标方法。遗传进化在进行选择的操作过程中，我们着眼于目标函数或者适应度函数的相对值而并不关心它的绝对值，确定这个个体目标函数的真正目的在于确定该个体在群体中的优劣，因此我们可以根据整个群体情况进行罚值权的统一定标，把各级的罚值用向量进行表示，此时，目标函数就是各级罚值的带权和。
如果想终止可以采用以下方法：
(1)给定一个迭代步数；
(2)当设定与估计的最优解的距离小于某个范围时，就终止搜索：
(3)当与最优解的距离连续若干步保持不变时，就终止搜索。
排课问题同样是一个N-P问题，无论应用哪种方法冲突问题的出现都不可能避免。但是，解决冲突问题的方法有很多种，这里采用一种利用二进制0、1矩阵检测冲突的方法。在冲突检测过程中其基本的约束条件为：
(1)任何教师在同一时间最多只能安排一门课。
(2)任何班级在同一时间最多只能安排一门课。
(3)任何教室在同一时间最多只能有一门课程被安排。
为了避免冲突的出现，在本系统的设计、实现过程中引进了冲突检测函数，保证当排完一位教师的所有相关课程后，系统就会通过该冲突检测函数对这位教师课程安排的冲突情况进行检测并做出相应的修正。
参考文献：
[1]毕晓君，信息智能处理技术[M]，北京：电子工业出版社，2010
[2]陈强，通用高校排课算法研究[J]，科技广场，2006年第07期
[3]张文修，粱怡，遗传算法的数学基础(第2版)[M]，西安：西 安交通大学出版社，2003
遗传算法原理和应用 篇5
关键词：元件贴装顺序优化,贴片机,遗传算法,交叉算子
0引言
随着电子产品装配技术日新月异的发展, 表面组装技术 (SMT) , 这一集电子元器件、组装装备和焊接技术为一体的综合性技术得到了越来越广泛的应用[1]。表面组装生产线的使用, 加快了电子产品的生产效益, 增强了产品的可靠性, 与此同时大大降低了生产成本, 使得电子产品装配较之手工装配发生了质的飞跃。为进一步地提高贴片机的性能, 其关键因素之一就是提高贴片机的效率:即贴片机送料器的位置分配优化和元器件的贴装优化。
这里假设送料器位置固定, 来解决元器件的贴装优化问题。对于单台贴片机而言, 这个问题都属于NP Hard问题, 一般被规划为旅行商问题 ( Traveling Sales man Problem, TSP) [2], 已有一些学者成功地用传统的遗传算法 (GA) 解决。但是, 由于贴片机的发展, 它的结构已经变得更为复杂, 其头数已多达12头, 甚至更多, 解决贴装顺序优化问题的方法近年来主要有:遗传算法、蚁群算法、伞布搜索法以及差分算法。遗传算法是进化算法, 主要通过选择变异和交叉算子完成;蚁群算法是基于图论的算法, 通过信息素选择交换信息;伞布搜索法属于比较新的应用于贴装顺序优化的算法, 目前国内的研究报道少之又少, 国外尚未有关此算法在贴装优化方面的研究应用;差分算法是在遗传算法的基础上增加了迁徙进化过程, 使算法拥有更好的全局性, 但较之遗传算法编程思想比较麻烦。所以本文只讨论遗传算法的应用, 并对其进行改进, 使贴装优化不仅编程简便且拥有较好的全局性和收敛性。
1遗传算法的基本原理
20世纪50—60年代, 一些科学家独立开展了旨在可以成为工程问题优化工具的进化系统的研究。80年代以后, 经过相关领域专家学者的交流和共同努力, 遗传算法、ES、EP走向融合, 构成了进化计算的思想和主要算法形式[3]。由于其不受搜索空间的限制性假设的约束, 不必要求诸如连续性、倒数存在和单峰等假设, 以及其固有的并行性, 遗传算法在最优化、机器学习和并行处理领域得到了越来越广泛的应用。遗传算法GA把问题的解表示成“染色体”, 在执行遗传算法之前, 给出一群“染色体”, 即假设解。然后把这些假设解放置于问题的“环境”中, 按照适者生存的原则, 较适应环境的“染色体”被挑选出来进行复制, 再通过交叉, 变异过程产生更适应环境的新一代“染色体”群。这样, 一代一代地进化, 最后就会收敛到最适应环境的一个“染色体”上, 它就是问题的最优解。
2贴片机的工作过程及数学模型
无论是全自动贴片机还是手动贴片机, 无论是高速贴片机还是中低速贴片机, 它的总体结构均有类似之处。图1是一种通用贴片机的内部结构示意图, 所示为12个吸嘴, 其工作过程:PCB由传送带入口送入, 传送带将PCB送到工作位置停板, 定位针进行夹紧, 通过相机识别MARK点对PCB板完成定位后, PCB板固定, 贴装头吸取元件通过x/y轴及R轴和Z轴的移动以一定的压力把元件贴装在有粘性的已经印刷焊锡的焊盘上, 即吸取-位移-定位-放置功能[4], 贴装头不断地重复这样的贴装循环, 直到所有元件贴装完毕即完成贴装。贴片机贴装路径优化问题描述如下:已知印制板上各个元器件的装配位置, 寻求一个贴片机头遍历这些装配位置的路径, 寻求开销最小。
该问题与经典的TSP问题有相似之处, 即都是遍历整个集合, 求最小值问题。不同的是, 贴片机贴装要分批进行, 如一个4吸嘴的贴片头一个贴装循环内只能贴装4个元器件, 一次循环结束后贴片头要返回工料站进行取料再开始下一个循环。所以整体来说, 贴片机的贴装优化并不属于TSP问题。贴片机贴装时间需包括:取料时间、贴装时间、循环间吸取原料的时间及弃料抛料时间等。整个贴片机的贴装过程是一个比较复杂的过程, 为使模型的建立稍微简单些, 必须牺牲掉一些不必要的环节, 故参照文献[5]做以下假设:
(1) 假设供料器位置为原点;
(2) 将整个贴装过程中只做一次的动作例如PCB MARK点的定位省略;
(3) 假设每次贴片式贴装头在x, y方向运动的时间均大于其贴装头的旋转对中时间;
(4) 假设吸嘴吸片时间固定, 为90 ms;贴片时间固定, 为90 ms;
故类似文献[6], 一个完整的贴装时间可以表示为:
式中:T1i表示第i个循环内总共的贴片头移动时间;T2i表示贴片头从第i个循环的最后一个元件贴装完毕移动到下一个循环的第一个元件的贴装位置所需要的时间; ti表示第i个元件的贴片时间, 如上文所假设, 一般每个元件的贴片时间一定;s表示总循环次数;n表示总元件个数。按距离远近x, y方向的运动有加速-减速 (短距离) 、加速-恒速-减速 (长距离) 两种形式。按给定运动距离S、加速度a、恒速度v可得到对应的运动时间t的计算公式:
短距离:t =4aS ;长距离:t =vS+av
式中v, a都是设定值。故求上式的最小值可简化为的最小值, d1表示贴装循环内贴片头要移动的距离, d2表示循环间贴片头要移动的距离。
3算法
3.1遗传算法
遗传算法在群体进化过程中发生繁殖、杂交和突变现象, 不断发现重要基因[7]。寻找较好模式的过程中, 高适应度的个体被选择的概率大于低适应度的个体, 则好的基因得以遗传下来, 不好的基因被剔除, 随着迭代次数的增加逐渐创造出更好的个体, 同时也渐渐趋近于全局最优解。
主要包括3部分:多样性初始解集的产生;解集的改良更新, 其中的算子包括复制算子、交叉算子和变异算子;最优解的出现。
3.2初始解集的产生
初始解集的特性对计算结果和计算效率有重要的影响, 要实现全局最优, 初始解集在解空间上应尽量分散, 若按照随机方法产生一组原始解集, 可能会导致初始解集在解空间的分布不均进而影响算法的性能。在遗传算法中初始种群的各个个体间应保持一定的距离, 这样的分布能使解在解空间上含有较丰富的模式, 进而增加搜索收敛全局最优的可能性[8]。
3.3复制算子
遗传算法中通过个体的适应值反映群体中个体的好坏程度, 复制算子把当前群体中的个体按照与适应值成比例的概率复制到新的群体中。一般选用赌盘选择的方法完成复制。
3.4交叉算子
交叉算子是对整个染色体操作的, 所以在遗传算法中起核心作用, 遗传算法的收敛性主要取决于交叉算子的收敛性[9]。经典的交叉算子包括:单点交叉、两点交叉、多点交叉、融合交叉、均匀交叉等。
3.5变异算子
按概率对染色体的某一基因位 (自变量的某一维) 进行一个微扰动或是取反。
4算法的比较和改进
以一个PCB板子上的20个元器件为例, 其各个元件坐标如下表所示, 假设贴片头上有4个吸嘴。这里初始染色体中有10个体, 迭代次数为200, 交叉概率为定值0.8, 变异概率为定值0.2, 采用多种遗传算法的贴装距离分别如表1所示。
mm
如图2所示, 其中 (a) 结果收敛性和全局优化性都差; (b) 虽然收敛速度快, 但全局性不好; (c) 虽然获得了好的全局性, 但收敛速度慢;相比之下 (d) 的收敛速度和全局性都比较优秀。
图2 (d) 是在前3种遗传算法上的改进, 算法步骤为:
(1) 初始化染色体, 这里取染色体的个体为10;2
(2) 按照赌盘选择和适应值的大小进行复制。即将染色体中前5个适应值高的个体直接复制给新的群体, 剩下的5个解则按照赌盘选择的方法进行选择, 这样不仅提高了群体的平均适应值, 也加快了算法的整体收敛速度;
(3) 对染色体按适应度大小进行排列, 适应度大的排在前面, 小的排在后面;
(4) 从第一个染色体开始选取概率为Pc个染色体, 每两个进行组合形成一对父代双亲, 随机产生一个交叉点k, 并随机产生一个小于从交叉点到最后节点个数的随机数r, 进行交叉。
如假设P1=[1, 4, 3, 7, 2, 5, 6], P2=[2, 4, 7, 3, 6, 5, 1];
若随机产生k=2, r=3;则P1′=[7, 3, 6, 1, 4, 3, 7, 2, 5, 6], P2′=[3, 7, 2, 2, 4, 7, 3, 6, 5, 1];依次删去重复的数得到新的子代个体:p1=[7, 3, 6, 1, 4, 2, 5], p2=[3, 7, 2, 4, 6, 5, 1];
(5) 分别比较2个父代和子代的适应值, 选择适应值最大的遗传下来, 作为最终的子代个体。这样保证了每次都遗传最好的基因, 加快了最优解出现的速度。
5结论
本文提出的遗传算法, 是在传统遗传算法基础上的完善, 通过改善复制算子和交叉算子并加入最后选择算子, 使新的交叉算子有更大的全局优化性和更快的收敛性。相比于文献[2], 文献[2]是改进过交叉算子的应用, 但迭代结果仍然上下波动, 收敛效果不好;相比于文献[10]虽然效果相似, 但却比其有着更简便的编程思想。 该方法得到最优解更具有全局性, 且速度也比较快。
参考文献
[1]SRIHARI K, RAGHAVAN Sundarraman.A process planning system for PCB assembly using TAB and SMT[J].Advanced Manufacturing Technology, 1994, 9:311-318.
[2]曾又姣, 金烨.基于遗传算法的贴片机贴装顺序优化[J].计算机集成制造系统, 2004, 10 (2) :205-208.
[3]韩瑞锋.遗传算法原理与应用实例[M].北京:兵器工业出版社, 2009.
[4]王燕.水平旋转式贴片机贴装过程优化研究[D].西安:西安电子科技大学, 2010.
[5]袁鹏, 刘海明, 胡跃明.高速高精度多功能贴片机及产业化关键技术研究[D].广州:华南理工大学, 2005.
[6]朱光宇, 罗哲, 陈志锦.基于差分算法的贴装顺序优化问题求解[J].中国工程机械学报, 2012, 10 (4) :391-397.
[7]俞国燕, 郑时雄, 刘桂雄, 等.复杂工程问题全局优化算法研究[J].华南理工大学学报, 2000, 28 (8) :104-110.
[8]袁鹏, 刘海明, 胡跃明.基于伞布搜索法的贴片机贴装顺序优化算法[J].电子工艺技术, 2007, 28 (6) :316-320.
[9]翟梅梅.基于交叉算子改进的遗传算法求解TSP问题[J].淮南师范学院学报, 2009, 11 (5) :114-119.
遗传算法原理和应用 篇6
关键词：遗传算法网架结构配电网优化
1 问题的提出
配电系统中的网架结构优化问题主要有两个特点：非线性和整数性，这也正是解决问题的困难所在。用非线性规划方法解题常常会遇到搜索方向错误，迭代不收敛，逼近速度慢等问题。当变量和约束条件数目较多时，这些问题更加突出。另外，线路都是按整回和确定的电压等级来架设的，若变量取线路的某电气量，则变量应是整数值或某种离散值。对于这样的非线性整数规划问题，目前还没有理想的优化算法。若试图严格地解决这种问题，将会遇到一个典型的组合数目以指数形式增长，即所谓“组合爆炸”问题。综观以前的各种传统优化方法，各有优势，要么容易偏离最优解陷入局部最优，要么受到维数的限制而难以达到实用的目的。为了解决这两个方面的问题，下面把遗传算法引入城市电力网网架结构的优化中来，以欺得到一个较满意的解决问题的办法。
2 遗传算法介绍
遗传算法是一种搜索算法，是通过模拟自然进化过程来搜索最优解的方法。其目的是解释自然界的自适应过程而设计的一个体现自然界进化机理的软件系统。大多数生物体是通过自然选择和有性生殖这两种基本过程进行演化的。自然选择决定了群体中哪些个体能够存活并繁殖，即适者生存，不适者淘汰；有性生殖保证了后代基因中的混合与重组，加快了进化过程。由于该方法隐含并行性和全局信息的有效利用能力，尤其适合于处理传统搜索方法解决不了的复杂问题，近十多年來在各领域得到广泛应用。
遗传算子：一个简单的遗传算法由复制、杂交和变异三个遗传算子组成。其中复制算子是把当前群体中的个体按与适应值成正比的概率复制到新群体中去。这样，低适应值的个体趋向于被淘汰，高适应值的个体趋向于被复制，复制算子的作用效果提高了群体的平均适应值，也充分体现了“优胜劣汰”这种自然进化机制；杂交算子是模拟生物界的有性繁殖，可以产生新的个体，使其比它的两个父代有更高的适应值。杂交算子是遗传算法的重要组成部分；变异算子是用一个很小的概率随机地改变染色体串上的位置，其效果是增加群体的多样性，扩大搜索空间。
主要特点：遗传算法与传统的优化算法相比，主要体现在它不是直接作用参变量集上，而是利用参变量集的某种编码；不是从单个点，而是从一个点的群体开始搜索，因而能够快速全局收敛；它还利用了概率转移规则，而非确定性规则，因而能够搜索离散的有噪声的多峰值复杂空间；以及利用适应值信息，无须导数或辅助信息，具有广泛的适应性；在解空间内进行充分的搜索，但并不是盲目地穷举或瞎碰，因此在其搜索时间和效率上往往优于其他优化方法。首先，它在搜索过程中不容易陷入局部最优，即使在所定义的适应函数是不连续的、非规则的或有噪声情况下，它也能以很大的概率找到整体最优解。为了寻找最优解，传统方法是用启发式策略，在单个猜测解的领域寻找，即使算法中允许偶尔地跳到解空间中更远的部分，这些启发式算法也往往趋于局部最优。理论上遗传算法像撒网一样，通过保持在参变量的解空间区域中的多个点的搜索可以以很大的概率找到全局最优解。其次，由于它固有的并行性，遗传算法非常适用于大规模并行计算机。由于遗传算法的操作主要是在单个位串上，至多是一对位串之间的杂交，所以可让每个处理机负责处理单个位串，从而可以并行处理整个群体。
计算步骤：在进行个体遗传算法之前，需要作好如下准备工作。首先是选择编码；一般编码选择由多个二进制串（0，1）构成，其中“0”、“1”分别表示支路不连通和连通。应注意的是编码不局限于二进制，根据对象不同也可选其他的数来编码。其次是确定适应值函数；相当于确定数学规划中的目标函数。然后在选择控制算法的参数；最后确定停止运行的准则。
3 网架结构优化的遗传算法
网络结构优化的目标函数：网络结构优化问题是基于现有网架结构，在已知水平年电源及负荷需求下，并假定变电站的扩建或新建的时间、地点和容量都已确定，决定在规划期内何时何地架设多少回输电线路，以使得线路年费用最小。这里采用考虑了贴现的线路建设投资费用和运行费用的最小年费用法，即。其中Z为方案总的线路建设投资费用，为方案第年的运行费用。
编码的选择：遗传算法是一个搜索特征串空间的过程，其目的是找到具有相对高适应值的串。在应用遗传算法求解特殊问题之前，第一步就要确定用类似于染色体的串来表示问题的办法，即染色体的编码形式。这里采用二进制编码形式，直接对待选线路进行编码，反映其是否架设，以及选用多大截面等。这种编码形式非常直观，便于规划方案和染色体之间的编码和解码。若只考虑线路架设与否，则可将各待选线路排序，然后按此顺序将每条待选线路作为染色体串中的一个基因，每个基因是一个一位的二进制数。当基因值为1时，表示其对应的待选线路被选中加入系统，当基因值为0时，则相反。但考虑到对方案进行评估时需对方案所表示的网络进行潮流分析，这样的染色体解码成规划方案时应能得到线路参数，所以需在基因中加入线路截面的信息。
城网优化遗传算法的计算过程：首先输入原始数据；其中包括网络拓扑，即节点数、已有和待架线路数、各线路的首末节点号和线路的有关参数。节点的发电出力及负荷，遗传算数本身所需参数，即群体大小、基因位数、最大遗传代数、变异率和计算适应函数时用到的有关参数等。然后形成初始方案，接着计算适应值，进行遗传操作，最后输出计算结果。
适应函数的建立：在编码方案选定以后，接着就是要确定适应函数以检测由特定位串所表示的规划方案的好坏程度，从而指引遗传操作的正常进行。适应函数应该反映电网规划的目的和要求，即要使规划方案在满足正常运行要求和安全运行要求的情况下，使电网的建设和运行费用最小。建设费用和运行费用最小的目标函数，在考虑约束条件后的增广函数数学模型为。其中为方案的年费用，为惩罚因子，为方案的约束条件。电网规划的目的是希望电网的建设和运行费用最小，为符合遗传算法最大值的特点，适应函数可表示为。其中的选取以保证为非负数为准。由的表达式可知适应函数是一个非线性的、不连续和非凸的，这对于严格的数学规划方法是难以求解的，而遗传算法则是在解码得到一个解之后才对适应函数进行计算评估的，因此对适应函数形式无任何限制，这充分显示了遗传算法的优越性。
参考文献：
[1]孙杰.基于单亲遗传算法的配电网络优化规划[D].华北电力大学（河北）.2005年.
[2]闫大威.基于遗传算法的城市中压配电网规划自动布线[D].天津大学；2005年.