下载文档原格式
遗传算法遗传算法（Genetic Algorithm, GA）是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，借鉴了达尔文的进化论和孟德尔的遗传学说。
其本质是一种高效、并行、全局搜索的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最佳解。
遗传算法中每一条染色体，对应着遗传算法的一个解决方案，一般我们用适应性函数来衡量这个解决方案的优劣。
所以从一个基因组到其解的适应度形成一个映射。
可以把遗传算法的过程看作是一个在多元函数里面求最优解的过程。
可以这样想象，这个多维曲面里面有数不清的“山峰”，而这些山峰所对应的就是局部最优解。
而其中也会有一个“山峰”的海拔最高的，那么这个就是全局最优解。
而遗传算法的任务就是尽量爬到最高峰，而不是陷落在一些小山峰。
3. 遗传算法：模拟物竞天择的生物进化过程，通过维护一个潜在解的群体执行了多方向的搜索，并支持这些方向上的信息构成和交换。
是以面为单位的搜索，比以点为单位的搜索，更能发现全局最优解。
（在遗传算法中，有很多袋鼠，它们降落到喜玛拉雅山脉的任意地方。
这些袋鼠并不知道它们的任务是寻找珠穆朗玛峰。
但每过几年，就在一些海拔高度较低的地方射杀一些袋鼠，并希望存活下来的袋鼠是多产的，在它们所处的地方生儿育女。
）（或者换个说法。
从前，有一大群袋鼠，它们被莫名其妙的零散地遗弃于喜马拉雅山脉。
于是只好在那里艰苦的生活。
海拔低的地方弥漫着一种无色无味的毒气，海拔越高毒气越稀薄。
可是可怜的袋鼠们对此全然不觉，还是习惯于活蹦乱跳。
于是，不断有袋鼠死于海拔较低的地方，而越是在海拔高的袋鼠越是能活得更久，也越有机会生儿育女。
就这样经过许多年，这些袋鼠们竟然都不自觉地聚拢到了一个个的山峰上，可是在所有的袋鼠中，只有聚拢到珠穆朗玛峰的袋鼠被带回了美丽的澳洲。
）例如我们用GA算法在既定的区间找到以下函数的最大值。
(1)个体编码将x表达为基因的过程，称之为编码，常见的编码格式有二进制编码和浮点编码。
遗传算法总结遗传算法概念遗传算法是模仿⾃然界⽣物进化机制发展起来的随机全局搜索和优化⽅法，它借鉴了达尔⽂的进化论和孟德尔的遗传学说。
其本质是⼀种⾼效、并⾏、全局搜索的⽅法，它既能在搜索中⾃动获取和积累有关空间知识，并⾃适应地控制搜索过程以求得最优解遗传算法操作使⽤适者⽣存的原则，在潜在的解决⽅案种群中逐次产⽣⼀个近视最优⽅案。
在遗传算法的每⼀代中，根据个体在问题域中的适应度值和从⾃然遗传学中借鉴来的再造⽅法进⾏个体选择，产⽣⼀个新的近视解。
这个过程导致种群中个体的进化，得到的新个体⽐原个体更适应环境，就像⾃然界中的改造⼀样。
应⽤遗传算法在⼈⼯智能的众多领域具有⼴泛应⽤。
例如，机器学习、聚类、控制（如煤⽓管道控制）、规划（如⽣产任务规划）、设计（如通信⽹络设计、布局设计）、调度（如作业车间调度、机器调度、运输问题）、配置（机器配置、分配问题）、组合优化（如TSP、背包问题）、函数的最⼤值以及图像处理和信号处理等等。
遗传算法多⽤应与复杂函数的优化问题中。
原理遗传算法模拟了⾃然选择和遗传中发⽣的复制、交叉、和变异等现象，从任⼀初始种群出发，通过随机选择、交叉、变异操作，产⽣⼀群更适合环境的个体，使群体进⾏到搜索空间中越来越好的区域，这样⼀代⼀代地不断繁衍进化，最后收敛到⼀群最适合环境的个体求得问题的最优解。
算法流程1.编码：解空间中的解数据x，作为作为遗传算法的表现型形式。
从表现型到基本型的映射称为编码。
遗传算法在进⾏搜索之前先将解空间的解数据表⽰成遗传空间的基本型串结构数据，这些串结构数据的不同的组合就构成了不同的点。
2.初始种群的形成：随机产⽣N个初始串数据，每个串数据称为⼀个个体，N个串数据构成了⼀个群体。
遗传算法以这N个串结构作为初始点开始迭代。
设置进化代数计数器t 0;设置最⼤进⾏代数T；随机⽣成M个个体作为初始群体P(0)。
3.适应度检测：适应度就是借鉴⽣物个体对环境的适应程度,适应度函数就是对问题中的个体对象所设计的表征其优劣的⼀种测度。
算法】超详细的遗传算法（GeneticAlgorithm）解析01 什么是遗传算法？1.1 遗传算法的科学定义遗传算法（Genetic Algorithm, GA）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。
其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，不需要确定的规则就能自动获取和指导优化的搜索空间，自适应地调整搜索方向。
遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。
其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。
1.2 遗传算法的执行过程(参照百度百科)遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。
每个个体实际上是染色体(chromosome)带有特征的实体。
染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。
因此，在一开始需要实现从表现型到基因型的映射即编码工作。
由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码。
初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。
遗传算法（GA）学习笔记⼀、步骤：⼆、重点：1、编码由于遗传算法不能直接处理问题空间的数据，所以我们必须将问题空间的数据映射成遗传空间的基因型串结构数据，⽽算法程序是可以处理遗传空间的基因型串结构数据的。
⽐如现在要计算北京、天津、⼴东、新疆这四个城市的⼀条最优路径，但算法程序不能够直接处理北京、天津、⼴东、新疆这些数据，所以我们得给它们编上号，北京（0）、天津（1）、⼴东（2）、新疆（3），路径（天津->新疆->北京->⼴东）可以表⽰成基因型串结构数据（1302），这样算法程序只要直接处理它们的编号就⾏了。
（1）⼆进制编码，基因⽤0或1表⽰（常⽤于解决01背包问题）如：基因A：00100011010 (代表⼀个个体的染⾊体)（2）互换编码（⽤于解决排序问题，如旅⾏商问题和调度问题）如旅⾏商问题中，⼀串基因编码⽤来表⽰遍历的城市顺序，如：234517986，表⽰九个城市中，先经过城市2，再经过城市3，依此类推。
（3）树形编码（⽤于遗传规划中的演化编程或者表⽰）如问题：给定了很多组输⼊和输出。
请你为这些输⼊输出选择⼀个函数，使得这个函数把每个输⼊尽可能近地映射为输出。
编码⽅法：基因就是树形结构中的⼀些函数。
（4）值编码（⼆进制编码不好⽤时，解决复杂的数值问题）（源代码中使⽤类似此⽅法）在值编码中，每个基因就是⼀串取值。
这些取值可以是与问题有关任何值：整数，实数，字符或者其他⼀些更复杂的东西。
2、适应度函数遗传算法对⼀个个体（解）的好坏⽤适应度函数值来评价，适应度函数值越⼤，解的质量越好。
适应度函数是遗传算法进化过程的驱动⼒，也是进⾏⾃然选择的唯⼀标准，它的设计应结合求解问题本⾝的要求⽽定。
如TSP问题，遍历各城市路径之和越⼩越好，这样可以⽤可能的最⼤路径长度减去实际经过的路径长度，作为该问题的适应度函数。
3、选择在进化中，适者⽣存，所以在遗传算法运⾏过程中，会不断地选择优者保留下来，同时也不断地选择劣者淘汰下去。
遗传算法的基本原理与方法一一笔记遗传算法的实现有6个主要因素：参数的编码、初始种群的设定、适应度函数的设计、遗传操作、算法掌握参数的设定、约束条件的处理。
基因gene染色体chromosome群体population复制reproduction交叉crossover变异mutation 适应性fitnessSGA基本遗传算法(SimpleGenelicAlgorilhm)遗传算子GeneticOperatorSGA基本步骤1.染色体编码与解码2.个体适应度的检测评估3.遗传算子(选择运算使用比例选择算子、交叉运算使用单点交叉算子、变异运算使用基本位变异算子或者匀称变异算子)4.运行的主要参数：M群体规模T终止条件PC交叉概率Pm变异概率。
优化问题的基本遗传算法构造过程：1.确定决策变量和约束条件2.建立优化模型3.确定编码方法4.确定解码方法5.确定个体评价方法6.设计遗传算子和确定遗传算法的运行参数。
一、编码(CodingandDecoding)编码：把一个问题的可行解从其解空间转换到遗传算法所能处理的搜寻空间的转换方法。
解码：由遗传算法解空间向问题空间的转换。
二进制编码的缺点之一是HammingCliff海明悬崖：某些相邻整数的二进制代码间有很大的海明距离，使得交叉和突变都难以跨越。
DeJOng依据模式定理，提出的编码准则：1、积木块规章：编码应易于生成与所求问题相关的短距和低阶的积木块。
2、最小字符集规章：编码应采纳最小字符集以使问题得到自然的表示和描述。
主要的编码方法有：二进制编码、格雷码、浮点数编码、多参数级联编码、多参数交叉编码。
编码的评估策略：完备性、健全性、非冗余性二、选择选择是在群体中选择生命力强的个体产生新的群体的过程。
依据每个个体的适应度值大小选择，适应度较高的个体被遗传到下一代群体的概率较大。
这样使得群体中个体的适应度值接近最优解。
常用的选择算子：轮盘赌选择（RoUletteWheelSelection）＞随机竞争选择（StOChaStiCTournament）,最佳保留选择、无回放随机选择、确定式选择、无回放余数随机选择、匀称选择、最优保存策略、随机联赛选择、排挤选择（小生境常用）。
第七章遗传算法的应用
7．1 数值函数优化计算
7．1．1 遗传算法与纯数值函数优化计算
首先．对很多实际问题进行数学建棋后，可将其抽象为一个数信函数的优化问题。
除了在函数是连续、可求导、低阶的简单情况下可解析地求出其最优解外，大部分情况下需要通过数值计算的方法来进行近似优化计算。
尽管人们对这个问题进行了多年的研究，而至今仍尚无一种既能处理各种不同的复杂函数，又具有良好求解结果的数值计算方法。
持别是当问题的规模比较大时，优化计算时的搜索空间也急剧扩大，人们逐渐意识到要严格地求出其最优解既不可能、也不现实。
所以需要研究出一种能够在可接受的时间和可接受的精度范围内求出数值函数近似最优解的方法或通用算法。
遗传算法提供了一种求解这种优化问题的通用框架。
其次，如何评价一个遗传算法的性能优劣程度一直是一个比较难的问题，这主要是因为现实问题种类繁多，影响因素复杂，若对各种情况都加以考虑进行试算，其计算工作量势必太大。
利用遗传算法进行数值函数优化计算时，若精度要求不是太高，自变量的个数不是太多时，可以采用二进制编码来表示个体；若精度要求较高，自变量的个数较多时．可以来用浮点数编码来表示个体。
7．1．2 评价遇传算法性能的常用测试函数
数学待性主要包括
1.连续函数或离散函数；
2.凹函数或众函数：
3.二次函数或非二次函数；
4.低维函数或高维函数；
5.确定性函数或随机性函数；
6.单峰值函数或多峰值函数.
7．1．3 De Jong的研究结论
De Jong提出的两个评价遗传算法性能的指标是：在线性能指标和离线性能指标。
由定义7．1可知，算法的在线性能指标表示了算法从开始运行一直到当前为止的时间段内性能值的平均值．它反映了算法的动态性能。
由定义7．2可知，算法的离线性能表示了算法运行过程中各进化代的最佳性能值的累积平均，它反映了算法的收敛性能。
经过仔细分析和计算，De Jong得到了下述几条重要的结论：
结论1：群体的规模越大，遗传算法的离线性能越好，越容易收敛。
结论2：规模较大的群体，遗传算法的初始在线性能较差；而规模较小的群体，遗传算法的初始在线性能较好。
结论3：虽然变异概率的增大也会增加群体的多样性，但它却降低了遗传算法的离线性能和在线性能、并且随着变异概率的增大，遗传算法的性能越来越接近厂随机搜索算法的性能。
结论4：使用保留最佳个体模型或期望值模型的遗传算法比基本遗传算法的性能有明显的改进。
结论5：对于广义交叉算子，随着交叉点数的增加会降低遗传算法的在线性能和离线性能。
7.2 多目标优化
7．2．1 多目标优化的基本概念
7．2．2 多目标优化与遗传算法
7．2．3 求解多目标优化问题的遗传算法
7．2．3 求解多目标优化问题的遗传算法
对于如何求多目标优化问题的Pareto最优解，目前已经提出了多种基于遗传算法的求解方法。
下面介绍其中几种主要的方法。
1．权重系数变化法
2．并列选择法
并列选择法的基本思想是：先将群体中的全部个体按子目标函数的数目均等地划分为一些子群体，对每个子群体分配一个子目标函数，各个子目标函数在其相应的子群体中独立地进行选择运算．各自选择出一些适应度较高的个体组成一个新的子群体、然后再将所有这些新生成的子群体合并为一个完整的群体，在这个完整的群体中进行交叉运算和变异运算，从而生成下一代的完整群体，如此这样不断地进行“分割——并列选择——合并”过程，最终可求出多目标优化问题的Pareto最优解。
这种方法很容易产生个别子目标函数的极端最优解，而要找到所有目标函数在某种程度上较好的协调最优解却比较闲难。
3．排序选择法
排序选择法的基本思想是：基于“Pareto最优个体”的概念来对群体中的各个个体进行排序，依据这个排列次序来进行进化过程中的选择运算，从而使得排在前面的Pareto最优个体将有更多的机会遗传到下—代群体中。
如此这样经过一定代数的循之后，最终就可求出多目标优化问题的Pareto最优解。
这里所谓的Pareto最优个体，是指群体中的这洋一个或一些个体，群体中的其他个体都不比它或它们更优越。
需要说明的是，在群体进化过程中所产生的Pareto最优个体并不一定就对应于多目标优化问题的Pareto最优解。
当然，当遗传算法运行结束时、我们需要取排在前面的几个Pareto最优个体，以它们所对应的解来作为多目标优化问题的Pareto最优解。
对群体中的所有个体进行Pareto最优个体排序的算法是：
由上述Pareto最优个体排序算法可知．排序选择法仅仅度量了各个个体之间的优越次序，而未度量各个个体的分散程度，所以它易于生很多个相似的Pareto最优解，而难于生成分布较广的Pareto最优解。
4．共享函数法
为达到这个要求，可以利用小生境遗传算法的技术来求解多目标优化问题，这种求解多目标优化问题的方法称为共享函数法，它将共享函数的概念引入求解多目标优化问题的遗传算法中。
在利用通常的遗传算法求解最优化问题时，算法并未限制相同个体或类似个体的数量。
但当在遗传算法中引入小生境技术之后，算法对它们的数量就要加以限制，以便能够产生出种类较多的不同的最优解。
对于某一个个体X而言，在它的附近还存在有多少种、多大程度相似的个体．这是可以度量的，这种度量值称之为小生境数。
式中，d(x，y)是两个个体x、y之间的海明距离，δ＞0是预先指定的一个表示小生境范围的参数。
在计算出各个个体的小生境数之后．可以使小生境数较小的个体能够有更多的机会被选中遗传到下一代群体中，即相似个体较少的个体能够有更多的机会被遗传到下一代群体中．这样也就增加了群体的多样性，相应地也会增加解的多样性。
使用这个选择操作方法的遗传算法可用于求解多目标优化问题的Pareto最优解。
该方法的优点是它能够得到多种不同的Pareto最优解，但另一方面，由于每次进行选择操作时都需要进行大量的个体之间优越关系的评价相比较运算，所以使得算法的搜索效率较低。
5．混合法
下面介绍—种使用遗传算法求解多目标优化问题的混合方法。
该方法的主要思想是；选择算子的主体使用并列选择法，然后通过引入保留最佳个体和共享函数的思想来弥补仅仅只使用并列选择法的不足之处。
算法的主要过程是：
7.3．1 装箱问题的描述。
