《遗传单纯形法》由会员分享，可在线阅读，更多相关《遗传单纯形法（38页珍藏版）》请在金锄头文库上搜索。
1、摘要遗传算法是一种借鉴生物选择，染色体交叉与变异等生物进化机制而形成的随机 搜素算法，具有全局搜索和适应能力强等优点。自 70年代问世以来便在数值优化、 系统控制、结构优化设计、参数辨识等诸多领域的应用中展开出其特有的魅力。但 是遗传算法在解决一些复杂优化问题时，算法后期容易出现搜索速度变慢，易陷入 早熟收敛等现象。考虑到传统的单纯形搜索算法局部搜索能力极强的特点，将基本 遗传算法与传统的单纯形搜索算法结合形成了一种混合遗传算法，从而在继承基本 遗传算法极强的全局搜索能力的基础上，克服其局部搜索能力差的缺陷。关键词： 遗传算法 单纯形法 遗传单纯形法 全局最优解ABSTRACTGenetic
2、algorithm is a kind of biological selection, biological evolutionary mechanisms such as chromosomal crossover and mutation to form a random search algorithm, has the advantages of global search and adaptable.Since the 70 s since its launch in numerical optimization, system control, structure optimiz
3、ation design, parameter identification, and many other applications in the field of spread out its unique charm.But the genetic algorithm in solving some complex optimization problems, late algorithm is prone to search speed slow, vulnerable to the phenomenon such as premature convergence.Considerin
4、g the traditional simplex search algorithm local search ability strong characteristic, the basic genetic algorithm with the conventional simplex search algorithm to form a kind of hybrid genetic algorithm, to inherit the basic genetic algorithm on the basis of strong global search ability, and overc
5、ome the defects of poor local search ability.Keywords ：Genetic algorithm Simplex method GASM Global optimal solution目录摘要 引言11. 遗传算法21.1遗传算法简介21.2 遗传算法原理与特点 31.3 遗传算法的实现 41.4 遗传算法的 MATLAB 实现62. 单纯形法162.1单纯形法简介162.2单纯形法的原理162.3单纯形法计算步骤172.4单纯形法表格形式172.5单纯形法MATLAB实现193. 遗传单纯形法243.1 遗传单纯形法简介 243.2 遗传单纯形
6、法的主要步骤263.3 测试方法和结果294. 结语32参考文献32引言遗传算法是自起源到当今已经得到了普遍认可，它为我们解决实际问题提供了 一个很好的方法，但其自身还存在不足，因此许多学者尝试对遗传算法进行改进 以 更好地解决实际问题。遗传算法是由美国的教授于年在他的专著自然界和人工系统的适应性中首 先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。遗传算法是全局优化自适应概率搜索算法，是模拟自然选择和自然遗传过程中 发生的繁殖交叉和基因突变现象。在每次迭代中都保留一组候选解。并按某种指标 从解群中选取较优的个体。利用遗传算子，选择，交叉和变异对这些个体进行组合 产生新一代
7、的候选解群，重复此过程直到满足某种收敛指标为止。遗传算法对一个个体解的好坏用适应度函数值来评价,适应度函数值越大，其解 的质量越好。而适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯 一标准。它的设计应结合求解问题本身的要求而定，遗传算法所使用选择运算来实 现对群体中的个体进行优胜劣汰操作。适应度高的个体被遗传到下一代群体中的概 率大，选择操作就是按某种方法从父代群体中选取一些个体，遗传到下一代群体； 基本遗传算法中采用的选择算子是轮盘赌选择方法，遗传算法要实现全局收敛。首 先要求任意初始种群经有限步都能到达全局最优解，其次算法必须有保优操作来防 止最优解的遗失，与算法收敛性有关的因
8、素主要包括种群规模 选择操作，交叉概率 和变异概率。1 遗传算法1.1 遗传算法简介遗传算法(Gene tic Algori thm)是模拟达尔文的遗传选择和自然淘汰的生物进 化过程的计算模型， 是一种通过模拟自然进化过程搜索最优解的方法，它是有美国 Michigan 大学 J.Holland 教授于 1975 年首先提出来的， 并出版了很有影响的专 著 Adaptation in Natural and Artificial Systems，GA 这个名称才逐渐为人 所知，J.Holland教授所提出的GA通常为简单遗传算法(SGA)。遗传算法是从代 表问题可能潜在的解集的一个种群(popu
9、la-tion)开始的，而一个种群则由经过基 因(gene)编码的一定数目的个体(individual)组成。每个个体实际上是染色体 (chromosome) 带有特征的实体。 染色体作为遗传物质的主要载体， 即多个基因的 集合，其内部表现(即基因型)是某种基因组合，它决定了个体的形状的外部表现。 因此，在一开始需要实现从表现型到基因型的映射即编码工作。 由于仿照基因编码 的工作很复杂，因而需要进行简化，如二进制编码，初代种群产生之后，按照适者 生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解，在每一代，根据问题 域中个体的适应度(fitness)大小选择(selection)个体，并借助
10、于自然遗传学 的遗传算子(gene tic opera tors)进行组合交叉(crossover)和变异(mutati on), 产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比 前代更加适应于环境，末代种群中的最优个体经过解码(decoding),可以作为问 题近似最优解。遗传算法(Genetic Algorithm ,G A)是借鉴生物界自然选择和群体 进化机制形成的一种全局寻优算法。与传统的优化算法相比 ,遗传算法具有如下优 点1:1) 不是从单个点 , 而是从多个点构成的群体开始搜索 ;2) 在搜索最优解过 程中 ,只需要由目标函数值转换得来的适应值信息 ,而
11、不需要导数等其它辅助信 息 ;3) 搜索过程不易陷入局部最优点。目前 ,该算法已渗透到许多领域 ,并成为解 决各领域复杂问题的有力工具2。在遗传算法中 ,将问题空间中的决策变量通过一 定编码方法表示成遗传空间的一个个体 ,它是一个基因型串结构数据 ;同时 ,将目 标函数值转换成适应值 ,它用来评价个体的优劣 ,并作为遗传操作的依据。遗传操 作包括三个算子 :选择、 交叉和变异。选择用来实施适者生存的原则 ,即把当前群 体中的个体按与适应值成比例的概率复制到新的群体中 ,构成交配池（当前代与下 一代之间的中间群体） 。选择算子的作用效果是提高了群体的平均适应值。由于选 择算子没有产生新个体 ,所
12、以群体中最好个体的适应值不会因选择操作而有所改 进。交叉算子可以产生新的个体 ,它首先使从交配池中的个体随机配对 ,然后将两 两配对的个体按某种方式相互交换部分基因。变异是对个体的某一个或某一些基因 值按某一较小概率进行改变。从产生新个体的能力方面来说 ,交叉算子是产生新个 体的主要方法 ,它决定了遗传算法的全局搜索能力 ;而变异算子只是产生新个体的 辅助方法 ,但也必不可少 ,因为它决定了遗传算法的局部搜索能力。交叉和变异相 配合 ,共同完成对搜索空间的全局和局部搜索。1.2 遗传算法原理与特点（1）遗传算法的特点的原理遗传算法（GA）是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应
13、 全局优化概率搜索方法。其采纳了自然进化模型，从代表问题可能潜在解集的一个 种群开始，种群由经过基因编码的一定数目的个体组成，每个个体实际上是染色体 带有特征的实体。初始种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好 的解：在每一代，概据问题域中个体的适应度大小挑选个体；并借助遗传算子进行 组合交叉和主客观变异，产生出代表新的解集的种群。这一过程循环执行，直到满 足优化准则为止。最后，末代个体经解码，生成近似最优解。基于种群进化机制的遗传算法如同自然界进化一样，后生代种群比前生代更加 适应于环境，通过逐代进化，逼近最优解。（2）遗传算法的优点遗传算法利用生物进化和遗传的思想实
14、现优化过程，区别于传统优化算法，它 具有以下特点：通用性强遗传算法只用编码表示问题，以适应度为判断的标准，不要求明确的 解析表达式，可以解决任意高度非线性寻优问题全局性由于交换和变异可以不断在 搜索空间中产生新的个体，扩大搜索范围，尤其是变异算子，可以使得系统从局部 最优附近跳出来，避免陷入局部最优范围，确保群体进化，得到全局最优解。智能 性遗传算法的搜索是以适应度为指导的。各种遗传算子的实施概率基本上是与适应 度相关的，因而遗传算法能自动获得和指导优化的搜索空间。其次 根据具体应用背 景不同，人们还提出了许多种新的遗传算子，这些算子的特征不同程度地体现了智 能寻优的思想方式。鲁棒性遗传算法在
15、解决具体问题时有很强的自适应能力和抗干 扰能力。隐含并行性算法在处理n个编码串时。同时在O (n3)阶次的模式进行处 理。(3) 遗传算法的缺点1) 遗传算法只是对生物进化的简单模拟，对自然界的模仿不够彻底。2) 运行机理还不十分清楚，理论上存在缺陷。3) 运算的参数设定更多依靠经验，缺乏通用性和理论指导。4) 能较快地速度搜索到全局最优解附近 但之后达到最优解速度较慢，有时会 出现过早收敛，即早熟现象。由此，我们有必要对遗传算法进行改进。1.3 遗传算法的实现1. 初始化 定义整数 pop_size 为种群中染色体的个数，种群的大小视实际情 况而定，一般需要 30100 个。 初始种群的每个个体都是在 matlab 中通过随机方 法产生，并把它作为进化的第一代。2. 评价 采用基于序的评价函数,评价个体或解的好坏，并作为以后遗传操作的 依据。如设给定参数a,定义基于序的评价函数为：rangel(i)=a(1-a)i-1,i=1,2,.,pop_size其中 i=1 说明染色体是最好的, i= pop_size 说明是最差的。3. 选择 选择操作是为了决定那些个体可以进入下一代，一般采用赌轮盘选择 法实现，适应性越强的染色体
