遗传算法20080911

第五章 遗传算法在经济活动中，很多实际优化问题涉及到大量参数进行优化，或者寻找问题的全局最优解。这些问题不仅仅涉及大量计算，而且往往难以给出精确的数学模型，或者有了数学模型，也难以解出解析解来。有的搜索问题还面临着组合爆炸，常规算法无法应付。这些困难使得一些学者们寻求一种适于大规模并行且具有某些智能特征如自组织、自适应、自学习等的算法。遗传算法就是一种伴随解决此类复杂的、非线性问题而发展起来的广为应用的、高效的随机全局搜索与优化的自适应智能算法。第一节 引言一、遗传算法生物学意义遗传算法的生物学基础是达尔文进化论和孟德尔的遗传变异理论。根据达尔文进化论，地球上的每一物种从诞生开始就进入了漫长的进化历程。生物种群从低级、简单的类型逐渐发展成为高级、复杂的类型。各种生物要生存下去就必须进行生存斗争，包括同一种群内部的斗争、不同种群之间的斗争，以及生物与自然界无机环境之间的斗争。具有较强生存能力的生物个体容易存活下来，并有较多的机会产生后代；具有较低生存能力的个体则被淘汰，或者产生后代的机会越来越少，直至消亡。达尔文把这一过程和现象叫做“自然选择、适者生存”。按照孟德尔的遗传学理论，遗传物质是作为一种指令密码封装在每个细胞中，并以基因的形式排列在染色体上，每个基因有特殊的位置并控制生物的某些特性。不同的基因组合产生的个体对环境的适应性不一样，通过基因杂交和突变可以产生对环境适应性强的后代。经过优胜劣汰的自然选择，适应值高的基因结构就得以保存下来，从而逐渐形成了经典的遗传学染色体理论，揭示了遗传和变异的基本规律。现代遗传学则对基因的本质、功能、结构、突变和调控进行了深入探讨，开辟了遗传工程研究的新领域。在一定的环境影响下，生物物种通过自然选择、基因交换和变异等过程进行繁殖生长，构成了生物的整个进化过程。生物进化过程的发生需要四个基本条件：(1)存在由多个生物个体组成的种群；(2)生物个体之间存在着差异，或群体具有多样性；(3)生物能够自我繁殖；(4)不同个体具有不同的环境生存能力，具有优良基因结构的个体繁殖能力强，反之则弱。生物进化是一个开放的过程，自然界对进化中的生物群体提供及时地反馈信息，或称为外界对生物的评价。评价反映了生物的存在价值和机会。在基于相同环境下的生存竞争中，生存价值低的个体被淘汰了，生存下来的个体则具有较高的生存价值。由此形成了生物进化的外部动力机制。 大多数高级生物体是以自然选择和有性生殖这两种基本过程实现进化发展的。自然选择决定了生物群体中哪些个体能够存活并繁殖，有性生殖保证了生物体后代基因中的杂交和重组，从而使得群体的进化比其他方式更加快速而有效。自然界的生物进化是一个不断循环的过程 。在这一过程中，生物群体也就不断地完善和发展。可见，生物进化过程本质上是一种优化过程，在计算科学上具有直接的借鉴意义。在计算机技术迅猛发展的时代，生物进化过程不仅可以在计算机上模拟实现，而且还可以模拟进化过程，创立新的优化计算方法，并应用到复杂工程领域之中，这就是遗传算法等一类模拟自然进化的计算方法的思想源泉。以生物进化过程为基础，计算科学学者提出了各种模拟形式的计算方法。二、遗传算法相关术语 由于遗传算法是模拟生物界的进化和遗传的规律的数学模型，用到了大量生物学的术语，因而有必要对这些术语进行了解。 染色体：生物细胞中含有的一种微小的丝状化合物。它是遗传物种的载体，由许多个遗传因子基因组成。 脱氧核糖核酸：决定生物遗传性状的染色体的基本物质，DNA在染色体中有规律的排列，是一种高分子，具有双螺旋的分子结构。它的基本结构单位是核苷酸。基因：DNA长链结构中占有一定位置的基本遗传单位。一个基因或几个基因决定构成生物蛋白质的氨基酸的组成比例及排列顺序，通过这种方式基因确定生物的遗传性状。 基因型、表现型：基因型是指生物的基因组成，由该生物的细胞核中的所有基因决定，基因型的外部性状表现称为表现型。 基因座：遗传基因在染色体中所占据的位置。同一基因座可能有的全部基因称为等位基因。 个体：携带一定性状的遗传信息的单个生物体称为个体。 种群：由同类生物的个体组成的集团是种群。该集团的个体数目称为种群大小，或称为种群规模。 复制：细胞分裂时，DNA通过复制自身而使得新的细胞的DNA与以前的相同，这种情况下，新产生的细胞所携带的遗传性状与原细胞的相同。 交叉：生物在进行有性繁殖时，下一代个体的遗传物质一半来到父本，一半来自母本，新的个体带有两个亲本的遗传信息。这个过程也称为基因重组，或称为交配、杂交等。 变异：在细胞进行复制时有时会因为某些原因发生差错，使得DNA发生变化，产生新的染色体，新的染色体表现出新的外部性状。 进化：生物在其生存繁衍过程中，通过基因的选择复制、交叉、变异使得其性状逐渐适应自然，这种生物性状不断改良的过程称为生物的进化。生物的进化以种群形式进行。 适应度：适应度是指生物适应其生存环境的程度，适应度高的生物更容易生存繁衍下去，相反适应度低的生物生存繁衍概率较低，有可能灭绝。遗传算法在模拟适应度时通常用适应度函数来表示。 编码、解码：遗传信息在DNA长链中以一定的基因模式排列，来表达这种遗传信息，这个过程称为编码。与这一过程相反的是解码，即从生物的基因模式排列中获得其所携带的遗传信息，解码也被称为译码。三、遗传算法特点遗传算法作为一种应用广泛且高效的随机全局搜索与优化的自适应智能算法。它与传统的算法不同，大多数古典的优化算法是基于一个单一的度量函数（评估函数）的梯度或较高次统计，以产生一个确定性的试验解序列；遗传算法不依赖于梯度信息，而是通过模拟自然进化过程来搜索最优解，它利用某种编码技术，作用于称为染色体的数字串，模拟由这些串组成的群体的进化过程。遗传算法通过有组织的、随机的信息交换来重新组合那些适应性好的串，生成新的串的群体。与传统优化算法相比有如下优点：(1)对可行解表示的广泛性。遗传算法的处理对象不是参数本身，而是针对那些通过参数集进行编码得到的基因个体。此编码操作使得遗传算法可以直接对结构对象进行操作。(2)群体搜索特性。许多传统的搜索方法都是单点搜索，这种点对点的搜索方法，对于多峰分布的搜索空间常常会陷于局部的某个单峰的极值点。相反，遗传算法采用的是同时处理群体中多个个体的方法，即同时对搜索空间中的多个解进行评估。这一个特点使遗传算法具有较好的全局搜索性能，也使得遗传算法本身易于并行化。(3)不需要辅助信息。遗传算法仅用适应度函数的数值来评估基因个体，并在此基础上进行遗传操作。更重要的是，遗传算法的适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。对适应度函数的唯一要求是，编码必须与可行解空间对应，不能有死码。由于限制条件的缩小，使得遗传算法的应用范围大大扩展。(4)内在启发式随机搜索特性。遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方向。概率仅仅是作为一种工具来引导其搜索过程朝着搜索空间的更优化的解区域移动的。虽然看起来它是一种盲目搜索方法，实际上它有明确的搜索方向，具有内在的并行搜索机制。(5)遗传算法在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数是不连续的，非规则的或有噪声的情况下，也能以很大的概率找到全局最优解。(6)遗传算法采用自然进化机制来表现复杂的现象，能够快速可靠地解决求解非常困难的问题。(7)遗传算法具有固有的并行性和并行计算的能力。(8)遗传算法具有可扩展性，易于同别的技术混合。同时遗传算法作为一种优化方法，它存在自身的局限性：(1)编码不规范及编码存在表示的不准确性；(2)单一的遗传操作编码不能全面地将优化问题的约束表示出来。考虑约束的一个方法就是对不可行解采用阈值，这样，计算的时间必然增加；(3)遗传算法通常的效率比其他传统的优化方法低；(4)遗传算法容易出现过早收敛；(5)遗传算法对算法的精度可信度计算复杂性等方面，还没有有效的定量分析方法。四、遗传算法发展历史及现状遗传算法作为一种应用广泛且高效的随机全局搜索与优化的自适应智能算法，其研究发展过程大体上可分为以下三个阶段：(1)第一阶段：世纪年代的兴起阶段 世纪年代，美国Michigan大学的Holland教授及其学生受到生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化的自适应概率优化技术遗传算法。年，Holland的学生Bagley在其博士论文中首次提出了“遗传算法”一词，并发展了复制、交叉、差异、显性、倒位等遗传算子，在个体编码上使用双倍体的编码方式。 世纪年代初，Holland教授提出了遗传算法的基本定理模式定理奠定了遗传算法的理论基础。年，Holland出版了第一部系统论述遗传算法和人工自适应系统的专著 Adaptation in Natural and Artificial Systems。(2)第二阶段：世纪年代的发展阶段世纪年代，Holland教授实现了第一个基于遗传算法的机器学习系统分类系统，开创了基于遗传算法的机器学习的新概念，为分类器在构造上提出了一个完整的框架。年，Goldberg出版了专著Genetic Algorithm in Search, Optimization and Machine Learning系统总结了遗传算法的主要成果，对GA的基本原理及应用做了比较详细、全面的论述。奠定了现代遗传算法的理论和应用基础，形成了遗传算法的基本框架。此后，许多学者对原来的遗传算法(或称基本遗传算法)进行了大量改进和发展，提出了许多成功的遗传算法模型，从而使遗传算法应用于更广泛的领域。(3)第三阶段：世纪年代的高潮阶段进入世纪年代后，遗传算法作为一种实用、高效、鲁棒性强的优化技术，发展极为迅速，在各种不同领域(如机器学习、模式识别、神经网络、控制系统优化及社会科学等)中得到广泛应用。年，Davis出版了Handbook of Genetic Algorithms一书，介绍了遗传算法在科学计算、工程技术和社会经济中的大量实例。年，Koza将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程的概念。目前，遗传算法引起包括数学、物理、化学、生物学、计算机科学等领域的科学家的极大兴趣。遗传算法的研究领域和内容十分的广泛，如遗传算法的设计与分析，遗传算法的理论基础及其在各个领域的应用。随着理论的深入研究和应用领域的不断拓展，遗传算法必将取得更大的发展。 五、遗传算法研究方向随着遗传算法应用范围的不断扩展，对其研究也出现了一些引人注目的动向: (1)基于遗传算法的机器学习，它把遗传算法从离散的搜索空间的优化搜索算法扩展到具有规则生成功能的机器学习算法。(2)遗传算法和神经网络、模糊推理以及混沌理论等智能方法互相渗透。(3)遗传算法与人工生命领域结合，在生物的自适应、进化、免疫等方面的研究中将会发挥一定的作用。(4)遗传算法和进化规则以及进化策略等日益结合，模拟从RNA向DNA的进化过程和机制，从而完善和提高遗传算法的性能，通过计算机模拟来再现生命现象是正在兴起的一个新的课题。人工生命研究的重要内容之一就是进化现象。而遗传算法则是研究进化现象的重要方法。在遗传算法的理论研究方面，可以说，目前还没有令人满意的模型与方法可以用来研究一般遗传算法的收敛性。遗传算法不是对单点而是对种群的演化，考虑到其本身的随机性与固有的Markov特性，运用Markov过程及鞍收敛理论有望在统一框架内研究各种形式遗传算法的收敛性，并建立遗传算法的一般收敛性理论。但要从根本上解决遗传算法收敛性所存在的基础问题是相当困难的，目前人们正在从解决以下问题入手开展这方面的研究: (1)非简单遗传算法发展收敛性理论; (2)己有收敛性分析模型的演化研究; (3)遗传算法过早收敛现象的理论分析; (4)关于遗传算法的加速收敛(或效率加速)理论; (5)关于遗传算法的有用性与有效性研究。六、遗传算法应用领域遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面是遗传算法的一些主要应用领域：(1)函数优化。函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。很多人构造出了各种各样的复杂形式的测试函数，用这些几何特性各具特色的函数来评价遗传算法的性能。而对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法已较难求解，而遗传算法却可以方便地得到较好的结果。(2)组合优化。随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题，人们已意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP完全问题非常有效。(3)生产调度问题。生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解，也会因简化得太多而使得求解结果与实际相差甚远。而目前在现实生产中也主要是靠一些经验来进行调度。现在遗传算法己成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。(4)自动控制。在自动控制领域中有很多与优化相关的问题需要求解，遗传算法己在其中得到了初步的应用，并显示出了良好的效果。(5)机器人学。机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人学理所当然地成为遗传算法的一个重要应用领域。(6)图像处理。图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会存在一些误差，这此误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。(7)人工生命。人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大主要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要基础理论。(8)遗传编程。Koza发展了遗传编程的概念，它使用了以LISP语言所表示的编码方法，基于对一种树型结构所进行的遗传操作来自动生成计算机程序。(9)机器学习。学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。七、遗传算法在经济学中的应用传统的经济理论研究是基于经济主体行为的完全理性假设和经济系统的均衡假设。采用的基本途径是基于演绎推理的数学分析。经济学者大都认为这些假设太强，与经济现实不符。应用遗传算法等模拟分析框架，经济学者可以将经济理论建立于有限理性主体及其相互作用基础上，主体主体和主体环境的相互作用导致经济系统协同进化。采用的途径是基于归纳推理的计算模拟。通过仔细的计算实验、测试、求精和扩展传统的经济理论，如经济主体学习、货币生成和社会标准进化等。在此介绍部分基于遗传算法的经济模型：(1)拍卖机制：Edmonds认为要使模型描述地准确，应该充分利用人类实验和认知科学的最新进展。他研究了在拍卖实验中人类的行为。其中，每个对象有一个单位商品要出售，收到一系列对商品的投标，投标是有成本的，对象决定何时停止该过程并接受最后的投标。人工主体模拟停止规则的策略，并通过遗传算法作为进化行为的学习机制。实验结果表明：人工主体在几个方面很接近人类对象，如收入的均值和分布。然而，有些方面却不尽人意，如人工主体的进化策略经常导致主体自动简化其复杂的描述等。(2)进化博弈论：Riechmann认为依据遗传算法的经济学习可以被描述成进化博弈论。他应用了一系列的企业生产定价模型论证了如下的个命题：每个遗传算法是一个动态博弈；每个遗传算法是一个进化博弈；在遗传算法学习中，群体趋向收敛于纳什均衡。Arifovic和Eaton应用遗传算法研究了通过学习进行协作博弈问题。博弈分两个阶段进行：局中人挑选可视商品；局中人随机相遇。偿付取决于局中人的相遇，局中人都不知道对方的类别，并且在商品和类别间没有事先约定。在完全信号均衡中，每一个商品都准确地表示局中人的类别。模型应用符号串表示局中人，并依据选择来进化其行为。实验结果表明：遗传算法在静态环境下是识别全局最优的一个好方法。(3)现实经济中的具体市场是由有限理性主体构成，这些主体能够依据过去的实践经验进行学习。理解具体市场结构、行为和福利产出的因果关系是经济现实研究中的一个重要课题。然而，由于这些关系的复杂性，确定性的结果难以给出。通过应用遗传算法等技术建立经济科学计算实验室，经济学者可以对各种假设进行实验性研究。(4)进化是金融市场研究的一个前沿。Lettau研究了金融市场中有限理性主体资产投资组合决策问题。在其基于主体金融模型中，主体要在风险资产和零利率无风险债券之间进行选择。遗传算法用来模拟投资组合决策，群体由一组候选解组成。依据回报通过保留好的删除坏的规则，以及通过交叉和突变产生新的决策规则，群体得以进化。实验结果表明:遗传算法能学到最好的投资组合权数。(5)劳动力市场的进化是雇员与雇主之间适应市场力的博弈结果。在多主体相互作用市场条件下，关于市场结构、市场行为和市场力的关系是经济学界研究的一个焦点。Tesfatsion应用一个基于主体的劳动力市场计算框架，研究职业容量、职业集中度和市场力之间的关系。工作供给者和雇主应用人工适应主体来描述，他们在不断更新预期效用的基础上寻找合作伙伴，相互作用基于囚徒困境模型，并随时间进化其行为。模型的主要发现是，在用于预测工作者与雇主的相应市场力时，职业容量一贯优于职业集中度。(6)在产品市场中，经济学者主要关注生产者如何确定产品的价格和数量以追求利润最大化，而与此同时消费者追求效用最大化。分析均衡行为的变化的传统途径是比较静态分析，均衡的调整是瞬间的，忽略了均衡调整的过程。Price应用遗传算法模拟了标准的伯川德模型、古诺模型和垄断垂直链模型的价格(或产量)的变化过程，其中字符串用于描述产品价格(或数量)。适应函数通过利润体现。为追求最大利润，企业不断应用基本遗传算子变化产品的价格(或数量)。实验结果表明：遗传算法不仅能给出与经济理论一致的均衡解，并且能给出均衡解的调整过程。(7)宏观经济分析的传统工具是宏观经济计量模型和可计算一般均衡模型。面对复杂的现实经济系统，要建立一个宏观经济模型，必须进行许多简化处理。经济学者的一般方法是：或者完全忽略微观个体的行为分析；或者采用典型个体代替群体，忽略个体间的差异性。这两种方法均会导致宏观经济分析和微观经济分析的相互分离。应用遗传算法等计算技术，模拟微观个体的状态和行为，模拟个体之间相互作用的市场协议，可以自然地累积出宏观经济的动态。微观模拟方法不仅使得宏观经济分析具有坚实的微观基础，而且使得研究经济政策的分配效应成为可能。(8)理性预期假设是一般均衡理论研究的出发点。但经济学者认为该假设太强，应该放松。Bullard和Duffy提供了一个研究一般均衡系统的计算框架，主体关于未来内生变量的值具有不同的信念。主体的信念影响经济的产出，产出反过来又影响主体的信念。他们应用一个两期代际交叠模型作为论述的背景。应用字符串表示主体的信念，并应用遗传算法修正主体的信念。实验结果表明：主体通常能协调他们的信念以达到帕累托有效的理性预期均衡。(9)传统经济理论适用于周期性发生的情景。在转轨经济中，人们要面对全新的机会和全新的规则，要确定如何管理交易和生产的机制。Novkovic应用遗传算法模拟了克罗地亚的转轨过程。模型中的人工主体能决定自己工作时间的长短和每期想卖掉的股票数目。实验结果表明：尽管职工购买企业的股票享受较大的优惠，但他们能否长期持有企业股票取决于他们的偿付能力。第二节遗传算法的基本原理与方法遗传算法是一种基于生物进化原理构想出来的搜索最优解的仿生算法，它模拟基因重组与进化的自然过程，把待解决问题的参数编成二进制码或十进制码（也可编成其他进制码）即基因，若干基因组成一个个体，许多染色体进行类似于自然选择、配对交叉和变异的运算，经过多次重复迭代（即世代遗传）直至得到最后的优化结果。习惯上，适应度值越大，表示解的质量越好。对于求解最小值问题，可通过变换转为求解最大值问题。遗传算法以群体为基础，不是以单点搜索为基础，能同时从不同点获得多个极值，因此不易陷入局部最优；遗传算法是对问题变量的编码集进行操作，而不是变量本身，有效地避免了对变量的微分操作运算；遗传算法只是利用目标函数来区别群体中的个体的好坏而不必对其进行过多的附加操作。本节将讨论遗传算法的实现涉及的主要因素：编码，初始种群的设定，适应度函数，遗传操作，控制参数的设定和终止条件。一、编码编码是遗传算法应用时首要解决的问题，也是设计遗传算法时的关键步骤。编码方法除了决定个体的染色体排列形式之外，还决定了个体从搜索空间的基因型变换到解空间的表现型时的解码方法，并且也影响到交叉、变异等遗传算子的运算方法，由此可见，编码方法在很大程度上决定了群体如何进行遗传、进化运算以及遗传进化运算的效率。针对一个具体应用问题，如何设计一个完美的编码方案一直是遗传算法的应用难点之一，也是遗传算法的一个重要研究方向，可以说目前还没有一套既严密又完整的指导理论及评价准则能够帮助我们设计编码方案。作为参考，问题编码一般应满足以下个原则：(1)完备性：问题空间中的所有点（可行解）都能成为GA编码空间中的点（染色体位串）的表现型。(2)健全性：GA编码空间中的染色体位串必须对应问题空间中的某一可行解。(3)非冗余性：染色体和可行解必须一一对应。在某种情况下，为了提高遗传算法的运行效率，允许生成包含致死基因的编码位串，它们对应于优化问题的非可行解，虽然这会导致冗余或无效的搜索，但可能有助于生成全局最优解所对应的个体，所需要的总计算量可能反而减少。按照遗传算法的模式定理，De Jong进一步提出了较为客观明确的编码评估准则，称之为编码原理，具体可以概括为两条原则：(1)有意义积木块编码原则：应使用能易于产生与所求问题相关的且具有低阶、短定义距模式的编码方案。(2)最小字符集编码原则：应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案。第(1)个编码原则中，模式是指具有某些基因相似性的个体的集合，而具有短定义距、低阶且适应度较高的模式称为构造优良个体的积木块或基因块，这里可以把该编码原则理解成应使用易于生成适应度较高的个体的编码方案。第(2)个编码原则说明了我们为何偏爱于使用二进制编码方法的原因，因为它满足这条编码原则的基本思想。理论分析表明，与其他编码字符集相比，二进制编码方案能包含最大的模式数，从而使得遗传算法在确定规模的群体中能够处理最多的模式。需要说明的是，上述De Jong编码原则仅仅是给出了设计编码方案时的一个指导性大纲，它并不适合于所有问题。所以，对于实际应用问题仍必须对编码方法、交叉运算方法、变异运算方法、解码方法等统一考虑，以寻求到一种对问题的描述最为方便、遗传运算效率最高的编码方案。由于遗传算法应用的广泛性，迄今为止人们已经提出了许多种不同的编码方法。总的来说，这些编码方法可以分为三大类：二进制编码、浮点数编码、符号编码方法。下面从具体实现的角度出发介绍其中的几种主要编码方法：(1)二进制编码二进制编码即是将原问题的解映射成为0，1组成的位串，然后在位串空间上进行遗传操作，结果再通过解码过程还原成其解空间的解，然后再进行适应度的计算。使用二进制编码方法能表达的模式数最多。(2)格雷（Gray）编码格雷码即是将二进制编码通过一个变换而得到的编码，其目的是克服二进制编码中 Hamming 悬崖的缺点。(3)实数编码为了克服二进制编码的缺点，对于问题的变量是实向量的情形，可以直接采用十进制进行编码，这样，便可直接对解进行遗传操作，从而便于引入与问题领域相关的启发式信息以增加遗传算法的搜索能力。对实数编码的情形，通常需要针对十进制编码的特性，引入其他一些遗传算子。实验证明，对于大部分数值优化问题，通过一些专门设计的遗传算子的引入，采用实数编码比采用二进制编码时算法的平均效率要高。(4)有序串编码对于很多组合优化问题，目标函数的值不仅与表示解的字符串中的各字符的值有关，而且与其所在字符串的位置有关，这样的问题称为排序问题。若目标函数的值只与表示解的字符串中各字符的位置有关而与其具体的字符值无关，则称为纯排序问题。如求解旅行商问题就是用的第一种编码方式。用遗传算法求解有序问题时，传统的遗传操作将可能产生非法后代，因此，对这类问题需要针对具体问题专门设计有效且能保证后代合法的遗传算子，这类编码方案在组合优化问题中使用较多。(5)动态编码动态编码是当算法收敛到某局部极值时增加搜索的精度。增加精度的办法是在保持串长不变的前提下减小搜索区域。二、种群初始化产生群体是GA进化过程的基础，从某种程度上来讲，群体的性质变化决定了GA的搜索能力，GA的收敛性取决于群体的收敛性。一般来讲，关于群体的研究包括群体规模设定、群体初始化生成、运行过程中群体规模的控制和多样性变化与控制等，其中，对于遗传算法的实际应用中，最为主要的是群体初始化生成。群体初始化产生一般有两种方法：一种是完全随机的方法产生的，它适合于对问题的解无任何先验知识的情况；另一种方法是某些先验知识可转变为应该满足的一组要求，然后在满足这些要求的解中再随机地选取样本，这样产生的初始种群可使遗传算法更快地达到最优解。在此详细介绍第二种情况的群体初始化产生的方法：初始种群的产生可分为两种情况，第一种情况是求解无约束问题；第二种情况是求解有约束问题。对于第一种情况，当设决策变量个数为，初始种群规模为，和分别为设计变量的取值上限和下限， 为第个初始个体 式中：第个个体第个分量的初始值，。若令为与第个初始个体第个分量相对应的在0，1区间内服从均匀分布的随机数，则初始种群可按下式产生式中， 对于第二种情况，可人为给定一个初始个体，若不是可行域的内点，则先随机产生一个初始可行个体，若为可行域的界点，则重新产生，直至产生的初始可行个体为可行域的内点为止。于是可按下式随机产生一个初始个体其中， ，按上式产生的个体需检验是否满足约束条件，若满足，则产生新的初始个体，若不满足则使其不断地向靠拢，即按下式进行迭代 式中，是一个大于且小于的系数，一般可取。这样经过不断地迭代，总可以使成为可行个体，然后再产生个体，采用与同样的处理方法，可使成为初始可行个体，仿照同样的办法，直至产生出个初始可行个体，此种初始种群生成方式有利于加速遗传算法收敛速度。三、适应度函数在研究自然界中生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某个物种对于其生存环境的适应程度。对生存环境适应程度较高的物种将有更多的繁殖机会；而对生存环境适应程度较低的物种，其繁殖机会就相对较少，甚至会逐渐灭绝。与此相类似，遗传算法中也使用适应度这个概念来度量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率就较大；而适应度较低的个体遗传到下一代的概率就相对小一些。度量个体适应度的函数称为适应度函数。适应度函数也称为评价函数，是根据目标函数确定的，用于区分群体中个体好坏的标准，是算法演化过程的驱动力，也是进行自然选择的唯一根据。适应度函数总是非负，任何情况下都希望其值越大越好，而目标函数可能有正有负，即有时求最大值，有时求最小值，因此需要在目标函数与适应度函数之间进行变换。为了变更选择压力，也需要对适应度函数进行变换。适应度函数设计主要满足以下条件：(1)单值、连续、非负、最大化；这个条件是很容易理解和实现的；(2)合理、一致性；要求适应度值反映对应解的优劣程度，这个条件的达成往往比较难以衡量；(3)计算量小；适应度函数设计应尽可能简单，这样可以减少计算时间和空间上的复杂性，降低计算成本；(4)通用性强;适应度对某类具体问题，应尽可能通用，最好无需使用者改变适应度函数中的参数，从目前而言，这个条件应该是不属于强要求。适应度函数设计基本上有以下三种方法：(1)直接以待解的目标函数转化为适应函数，令目标为最小化问题目标为最大化问题这种适应度函数简单直观，但存在两个问题：一是可能不满足常用的轮盘赌选择中概率非负的要求；二是某些待求解的函数在函数值分布上相差很大，由此得到的平均适应度可能不利于体现种群的平均性能，而影响算法的性能。(2)对于求最小值的问题，作下列转换：其他式中，为一个适当的相对比较大的数，是的最大值估计，可以是一个合适的输入值。对于求最大值的问题，作下列转换：其他式中，为的最小值估计，可以是一个合适的输入值。这种方法是第一种方法的改进，可以称为“界限构造法”，但这种方法有时存在界限值预先估计困难、不可能精确的问题。(3)若目标函数为最小值问题，令： 若目标函数为最大值问题，令， 这种方法与第二种方法类似，为目标函数界限的保守估计值。应用遗传算法时（尤其用它处理小规模群体时）常常会出现一些不利于优化的现象或结果。在进化的初期，通常会出现一些异常的个体，若按照轮盘赌选择策略，这些异常个体有可能在群体中占据很大的比例，这是不希望出现的现象，因此这样可能导致未成熟收敛现象。这是因为，这些异常个体竞争力太突出，因而会控制选择过程，从而影响算法的全局优化性能。对于未成熟收敛现象，设法降低某些异常个体的竞争力，这可以通过缩小相应的适应度函数值来实现。有时也需要扩大相应的适应度函数值，这种适应度的缩放称作适应度调整。目前，调整方式主要有以下几种：(1)线性调整设原适应度函数为，调整后的适应度函数为，则线性调整可采用式中系数和满足原适应度平均值要等于调整后的适应度平均值。调整后适应度函数的最大值要等于原适应度函数平均值的所指定倍数，即其中，是为得到所期待的最优个体的复制数。实验表明，对于一个不太大的群体而言，C 可在范围内取值。(2)幂调整该调整方式可定义为：式中指数与待求解问题有关，而且在算法过程中可按需要做修正。该调整方式由Gillies提出，他曾在机器视觉实验中采用了该方法，实验中。四、选择算子在生物的遗传和自然进化过程中，对生存环境适应度较高的物种将有更多机会遗传到下一代；而对生存环境适应度较低的物种遗传到下一代的机会就相对较少。模仿这个过程，遗传算法使用选择算子(或称复制算子)来对群体中的个体进行优胜劣汰的操作：适应度较高的个体被遗传到下一代群体中概率较大;适应度较低的个体被遗传到下一代群体中的概率较小。遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取哪个个体遗传到下一代群体中的一种遗传运算。 选择操作是建立在对个体的适应度进行评价的基础上，选择操作的主要目的是为了避免有效基因缺失、提高全局收敛性和计算效率。遗传算法中最常使用的选择算子有如下几种：(1)轮盘赌选择轮盘赌选择是目前遗传算法中最基础也是最常用的选择方法。在该方法中，每个个体的选择概率与其适应度值成比例。设群体大小为，其中个体的适应度值为,则被选择的概率为概率反映了个体的适应度在整个的个体适应度总和中所占的比例。当个体的适应度值越大，其概率越大，被选择到的机会也越多，从而，其基因结构被遗传到下一代的可能性也越大。(2)精英保留选择该方法的思想是把群体中适应度最高的个体不进行配对交叉而直接复制到下一代中，采用这种选择方法的优点是，进化过程中某一代的最优解可不被交叉或变异操作破坏。但是，这也隐含了一种危机，即局部最优个体的遗传基因会急速增加而使进化有可能陷于局部最优解。也就是说，该方法的全局搜索能力差。它适合于单峰性质的优化问题的空间搜索，而不适于多峰性质的空间搜索。所以，该方法一般都与其他选择方法结合使用。本文所采用的就是基于精英保留策略的轮盘赌选择。(3)期望值方法在轮盘赌选择方法中，当个体数不太多时，依据产生的随机数有可能会出现不正确地反映个体适应度的选择，即存在统计误差，也就是说，适应度高的个体有可能被淘汰，适应度低的个体也有可能被选择。为了克服这种缺点，期望值方法用了如下思想：计算群体中每个个体在下一代生存的期望数目：；若某个个体被选中并要参与配对和交叉，则它在下一代中的生存的期望数目减去；若不参与配对和交叉，则该个体的期望数目减 。在上述两种情况中，若一个个体的期望值小于零，则该个体不参与选择。(4)排序选择方法排序选择方法在计算每个个体适应度后，根据适应度大小在群体中对个体排序，然后把事先设计好的概率表按序分配给个体，作为各自的选择概率。所有个体按适应度大小排序，因而选择概率和适应度无直接关系而仅与序号有关。这种方法的不足之处在于选择概率和序号的关系需事先确定。此外，它和轮盘赌选择一样都是基于概率的选择，所以仍有统计误差。(5)联赛选择方法类似于体育中的比赛制度，从群体中任意选择一定数目的个体（称为联赛规模），其中适应度最高的个体保存到下一代，这一过程反复执行，直到保存到下一代的个体数达到预先设定的数目为止，联赛规模一般取。在应用GA解决实际问题时，选取一种选择算子，关键要分析其对个体的选择压力，所谓的选择压力是指选择机制给适应值较低的个体造成的“生存压力”。过大的选择压力，使得种群中适应值较低的个体迅速“死亡”，种群的多样性遭到破坏，从而使得算法搜索空间减小，不容易搜索到全局最优解。相反，过小的选择压力，使得种群中具有较高适应值的个体不容易在种群中产生更多的后代，从而使得搜索过程的随机性增强，降低搜索效率，算法的收敛速度变慢。提高选择压力可以加快算法的收敛速度，但是会减小搜索到全局最优解的概率。降低选择压力可以增大算法搜索到全局最优解的概率，但会降低搜索效率，使得算法的收敛速度下降，因此合理地选取选择压力，对遗传算法的进化起到了至关重要的作用。需要对选择压力给出一个合理的定义。Goldberg和Deb给出了“取代时间”概念来作为一种选择压力的度量。所谓“取代时间”就是，在只使用选择算子的情况下，初始种群中唯一的最优个体取代所有其他个体所需要的时间。Goldberg和Deb从理论上推导出了轮盘赌选择的取代时间函数为；排序选择算子和联赛选择算子的取代时间函数均为。对于某些选择算子来说，进行选择压力的理论分析是困难的，而且将理论分析结果应用于实际问题也具有一定的难度，而且在GA的实际应用中，新的选择算子层出不穷，对每一种算子都进行理论分析是不太可能的。五、交叉算子在生物界的自然进化过程中，两个同源染色体通过交配而重组，形成新的染色体，从而产生新的个体或物种。交配重组是生物遗传和进化过程中的一个主要环节。模仿这个环节，遗传算法中使用交叉算子来产生新的个体。交叉算子是遗传算法中最主要的遗传操作，是衡量和评价遗传操作产生新个体能力强弱的一个重要指标。所谓的交叉又称重组是按较大的概率从群体中选择两个个体，交换两个个体的某个或某些位。交叉运算产生子代，子代继承了父代的基本特征。遗传算法的收敛性主要取决于其核心操作交叉算子的收敛性。只在交叉算子的作用下，随着演化代数的增加，模式内部的各基因将趋于独立，并且只要组成模式的各基因都存在，则该模式一定能被搜索到，此时模式的极限概率等于组成该模式各基因的初始概率（也就是基因的极限概率）的乘积，并且与模式的定义距无关，进一步说明了交叉算子能使群体分布扩充的特性。简单介绍一下基于二进制编码的交叉算子：(1)单点交叉单点交叉，又称简单交叉，它是指在个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。单点交叉运算示意图（图）BA单点交叉图 单点交叉示意图(2)多点交叉多点交叉是指在个体编码串中随机设置多个交叉点,然后进行基因交换，多点交叉又称广义交叉,其操作过程与单点交叉类似。多点交叉包括两点交叉,下面以两点交叉为例说明,多点交叉运算示意图（图）。BA两点交叉图 多点交叉示意图(3)均匀交叉均匀交叉，又称一致交叉是指两个配对个体的每个基因座上的基因都以相同的交叉概率进行交换，从而形成两个新的个体。均匀交叉运算示意图（图）A均匀交叉图 均匀交叉示意图六、变异算子在生物的遗传和进化过程中，其细胞分裂复制环节有可能会因为某些偶然因素的影响而产生一些复制差错，这样会导致生物的某些基因发生某种变异，从而产生出新的染色体，表现出新的生物性状。遗传算法模仿生物遗传和进化过程中的变异环节。变异是以较小的概率对个体编码串上的某个或某些位值进行改变，进而生成新个体。在遗传算法中也引入了变异算子来产生新的个体。遗传算法中所谓的变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其它等位基因来替换，从而形成一个新的个体。从遗传运算过程中产生新个体的能力方面来说，变异本身是一种随机算法，但与选择和交叉算子结合后，能够避免由于选择和交叉运算而造成的某些信息丢失，保证遗传算法的有效性。交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力，而变异运算只是产生新个体的辅助方法，但它也是必不可少的一个步骤，因为它决定了遗传算法的局部搜索能力。交叉算子与变异算子相互配合，共同完成对搜索空间的全局搜索和局部搜索，从而使得遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。在遗传算法中使用变异算子主要有以下两个目的：(1)改善遗传算法的局部搜索能力。遗传算法使用交叉算子已经从全局的角度出发找到了一些较好的个体编码结构，它们已接近或有助于接近问题最优解，但仅使用交叉算子无法对搜索空间的细节进行局部搜索，这时若再使用变异算子来调整个体编码串中的部分基因值，就可以从局部的角度出发使个体更加逼近最优解，从而提高了遗传算法的局部搜索能力。(2)维持群体的多样性，防止出现早熟现象。变异算子用新的基因值替换原有基因值从而可以改变个体编码串的结构，维持群体的多样性，这样有利于防止出现早熟现象。变异算子使得遗传算法在接近最优解邻域时加速向最优解收敛，并可以维持群体多样性，避免未成熟收敛。在遗传算法中，传统变异算子通过按变异概率随机反转某位等位基因的二进制字符值来实现。对于给定的染色体位串，具体算法如下：(1)给定变异概率，随机产生，(2)按照以下原则生成新的个体，其中是对应于每一个基因位产生的均匀随机变量七、终止条件遗传算法是一种反复迭代的搜索方法，它通过多次进化逐渐逼近最优解而不恰好等于最优解，因此需要确定终止条件。但是由于遗传算法没有利用目标函数的梯度等信息，所以在进化过程中，无法确定个体在解空间中的位置，从而无法利用传统的方法来判定算法的收敛性以终止算法。通常采用的有以下几种：(1)终止代数T。终止代数T是表示遗传算法运行结束条件的一个参数，它表示遗传算法运行到指定的进化代数之后就停止运行，并将当前群体中的最佳个体作为所求问题的最优解输出。一般建议的取值范围是。(2)当判定出群体已经进化成熟且不再有进化趋势时就可终止算法的运行过程。判定准则有以下两种：连续几代个体平均适应度的差异小于某一个极小的阈值；群体中所有个体适应度的方差小于某一个极小的阈值。(3)根据群体的收敛程度来判断，通过计算种群中的基因多样性测度，即所有基因位的相似性程度来进行控制。利用群体多样性作为算法迭代终止条件，当群体多样性降低到一定程度时，群体稳定，GA达到收敛状态。(4)根据算法的离线性能和在线性能的变化来进行判断；上述两个指标描述了个体的进化能力和GA的搜索能力。(5)采用下列两条准则：在连续代不再出现更优的染色体；优化解的染色体占种群的个数达到以上。当满足以上两准则终止GA运算。八、参数设置遗传算法有4个主要控制参数需要提前设置。主要为：(1)群体规模，即群体中所含个体的数量，一般取为；(2)遗传运算的终止进化代数，一般取为；(3)交叉概率，一般取为；(4)变异概率，一般取为。这四个控制参数对遗传算法的求解质量和求解效率都有一定的影响，但目前尚无合理选择它们的理论依据。在实际应用中，需要经过多次数值实验后确定参数或范围。第三节基本遗传算法一、 基本遗传算法步骤与流程图、开 始产生初始群体计算群体的适应度选择运算交叉运算变异运算终止条件结 束是否图 SGA流程图基本遗传算法的算法步骤及流程图如图：Step1：采用二进制编码对搜索空间进行编码，随机产生个个体组成初始群体；Step2：采用适应度函数评估个体适应度；Step3：采用轮盘赌选择方法选择个个体进行繁殖；Step4：随机配对，按一定交叉概率进行单点交叉操作，生成两个子个体；Step5：按照一定变异概率进行基本位变异，生成子个体；Step6：若不满足终止条件，转到Step，否则，终止运算，输出最优解。二、 简单函数优化算例分析本部分借助基本遗传算法优化一个简单函数实例，分析基本遗传算法的基本特征。考虑下列一元函数求最大值的优化问题： 下面运用遗传算法求解这个问题。1编码(决定初始化种群)其目的是将寻求优化解的参数用若干代码串来表示。编码的基本要求是要为染色体的基因型(代码串)和表现型(参数值)建立对应关系采用二进制代码时，这种对应关系就是二进制数与十进制数的转换关系在本例中值在之间变化，所以有位二进制代码串就可组成所有染色体的基因型，即所有的染色体基因型在之间，接下来是要选择初始染色体种群的个