遗传算法

根据问题的目标函数构造一个适值函数，对一个由多个解（每个解对应一个染色体）构成的种群进行评估、遗传、选择，经多代繁殖，获得适应值最好的个体作为问题的最优解。

1，产生一个初始种群

2，根据问题的目标函数构造适值函数

3，根据适应值的好坏不断选择和繁殖

4，若干代后得到适应值最好的个体即为最优解

1种群和种群大小

一般越大越好，但是规模越大运算时间越大，一般设为100~1000

2 编码方法 （基因表达方法

3 遗传算子

包括交叉和变异，模拟了每一代中创造后代的繁殖过程。是遗传算法的精髓

交叉：性能在很大程度上取决于交叉运算的性能，交叉率Pc：各代中交叉产生的后与代数与种群中的个体数的比。Pc越高，解空间就越大，越耗时/

变异:Pm:种群中变异基因数在总基因数中的百分比。它控制着新基因导入种群的比例。太低，一些有用的基因就难以进入选择；太高，后代就可能失去从双亲继承下来的良好特性，也就失去了从过去中搜索的能力。

4选择策略

适者生存，优胜劣汰

5停止准则

最大迭代数

初始种群的产生：随机产生，具体依赖于编码方法

编码方法 ：二进制编码法、浮点编码法、符号编码法。顺序编码，实数编码，整数编码。

适值函数 ：根据目标函数设计

遗传运算 ： 交叉 ：单切点交叉，双切点交叉，均匀交叉，算术交叉

变异 ：基本位变异（Simple Mutation）：对个体编码串中以变异概率、随机指定的某一位或某几位仅因座上的值做变异运算。

均匀变异（Uniform Mutation）：分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。（特别适用于在算法的初级运行阶段）

边界变异（Boundary Mutation）：随机的取基因座上的两个对应边界基因值之一去替代原有基因值。特别适用于最优点位于或接近于可行解的边界时的一类问题。

非均匀变异：对原有的基因值做一随机扰动，以扰动后的结果作为变异后的新基因值。对每个基因座都以相同的概率进行变异运算之后，相当于整个解向量在解空间中作了一次轻微的变动。

高斯近似变异：进行变异 *** 作时用符号均值为P的平均值，方差为P2的正态分布的一个随机数来替换原有的基因值。

选择策略 ：1轮盘赌选择（Roulette Wheel Selection）：是一种回放式随机采样方法。每个个体进入下一代的概率等于它的适应度值与整个种群中个体适应度值和的比例。选择误差较大。

2随机竞争选择（Stochastic Tournament）：每次按轮盘赌选择一对个体，然后让这两个个体进行竞争，适应度高的被选中，如此反复，直到选满为止。

3最佳保留选择：首先按轮盘赌选择方法执行遗传算法的选择 *** 作，然后将当前群体中适应度最高的个体结构完整地复制到下一代群体中。

4无回放随机选择（也叫期望值选择Excepted Value Selection）：根据每个个体在下一代群体中的生存期望来进行随机选择运算。方法如下:

（1） 计算群体中每个个体在下一代群体中的生存期望数目N。

（2） 若某一个体被选中参与交叉运算，则它在下一代中的生存期望数目减去05，若某一个体未 被选中参与交叉运算，则它在下一代中的生存期望数目减去10。

（3） 随着选择过程的进行，若某一个体的生存期望数目小于0时，则该个体就不再有机会被选中。

5确定式选择：按照一种确定的方式来进行选择 *** 作。具体 *** 作过程如下：

（1） 计算群体中各个个体在下一代群体中的期望生存数目N。

（2） 用N的整数部分确定各个对应个体在下一代群体中的生存数目。

（3） 用N的小数部分对个体进行降序排列，顺序取前M个个体加入到下一代群体中。至此可完全确定出下一代群体中M个个体。

6无回放余数随机选择：可确保适应度比平均适应度大的一些个体能够被遗传到下一代群体中，因而选择误差比较小。

7均匀排序：对群体中的所有个体按期适应度大小进行排序，基于这个排序来分配各个个体被选中的概率。

8最佳保存策略：当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来代替掉本代群体中经过交叉、变异等 *** 作后所产生的适应度最低的个体。

9随机联赛选择：每次选取几个个体中适应度最高的一个个体遗传到下一代群体中。

10排挤选择：新生成的子代将代替或排挤相似的旧父代个体，提高群体的多样性。

之前在网上看到的一个比方，觉得很有趣：

{

既然我们把函数曲线理解成一个一个山峰和山谷组成的山脉。那么我们可以设想所得到的每一个解就是一只袋鼠，我们希望它们不断的向着更高处跳去，直到跳到最高的山峰。所以求最大值的过程就转化成一个“袋鼠跳”的过程。

下面介绍介绍“袋鼠跳”的几种方式。

爬山算法：一只袋鼠朝着比现在高的地方跳去。它找到了不远处的最高的山峰。但是这座山不一定是最高峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。

模拟退火：袋鼠喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高峰跳去。这就是模拟退火算法。

遗传算法：有很多袋鼠，它们降落到喜玛拉雅山脉的任意地方。这些袋鼠并不知道它们的任务是寻找珠穆朗玛峰。但每过几年，就在一些海拔高度较低的地方射杀一些袋鼠。于是，不断有袋鼠死于海拔较低的地方，而越是在海拔高的袋鼠越是能活得更久，也越有机会生儿育女。就这样经过许多年，这些袋鼠们竟然都不自觉地聚拢到了一个个的山峰上，可是在所有的袋鼠中，只有聚拢到珠穆朗玛峰的袋鼠被带回了美丽的澳洲。

}

（把那些总是爱走下坡路的袋鼠射杀，这就是遗传算法的精粹！）

遗传算法并不保证你能获得问题的最优解，但是使用遗传算法的最大优点在于你不必去了解和 *** 心如何去“找”最优解。（你不必去指导袋鼠向那边跳，跳多远。）而只要简单的“否定”一些表现不好的个体就行了。（把那些总是爱走下坡路的袋鼠射杀，这就是遗传算法的精粹！）

改进与变形

编码方法：

优点：

1、遗传算法是以决策变量的编码作为运算对象，可以直接对集合、序列、矩阵、树、图等结构对象进行 *** 作。这样的方式一方面有助于模拟生物的基因、染色体和遗传进化的过程，方便遗传 *** 作算子的运用。

另一方面也使得遗传算法具有广泛的应用领域，如函数优化、生产调度、自动控制、图像处理、机器学习、数据挖掘等领域。

2、遗传算法直接以目标函数值作为搜索信息。它仅仅使用适应度函数值来度量个体的优良程度，不涉及目标函数值求导求微分的过程。因为在现实中很多目标函数是很难求导的，甚至是不存在导数的，所以这一点也使得遗传算法显示出高度的优越性。

3、遗传算法具有群体搜索的特性。它的搜索过程是从一个具有多个个体的初始群体P(0)开始的，一方面可以有效地避免搜索一些不必搜索的点。

另一方面由于传统的单点搜索方法在对多峰分布的搜索空间进行搜索时很容易陷入局部某个单峰的极值点，而遗传算法的群体搜索特性却可以避免这样的问题，因而可以体现出遗传算法的并行化和较好的全局搜索性。

4、遗传算法基于概率规则，而不是确定性规则。这使得搜索更为灵活，参数对其搜索效果的影响也尽可能的小。

5、遗传算法具有可扩展性，易于与其他技术混合使用。以上几点便是遗传算法作为优化算法所具备的优点。

缺点：

1、遗传算法在进行编码时容易出现不规范不准确的问题。

2、由于单一的遗传算法编码不能全面将优化问题的约束表示出来，因此需要考虑对不可行解采用阈值，进而增加了工作量和求解时间。

3、遗传算法效率通常低于其他传统的优化方法。

4、遗传算法容易出现过早收敛的问题。

扩展资料

遗传算法的机理相对复杂，在Matlab中已经由封装好的工具箱命令，通过调用就能够十分方便的使用遗传算法。

函数ga：[x, fval,reason]= ga(@fitnessfun, nvars, options)x是最优解，fval是最优值，@fitnessness是目标函数，nvars是自变量个数，options是其他属性设置。系统默认求最小值，所以在求最大值时应在写函数文档时加负号。

为了设置options，需要用到下面这个函数：options= gaoptimset ('PropertyName1', 'PropertyValue1', 'PropertyName2', 'PropertyValue2','PropertyName3', 'PropertyValue3', )通过这个函数就能够实现对部分遗传算法的参数的设置。

-遗传算法

用ga函数，ga函数就是遗传算法的函数，它的调用格式为：

x

=

ga(fitnessfcn,nvars,a,b,aeq,beq,lb,ub,nonlcon,options)

fitnessfcn就是待优化函数，nvars为变量个数，然后后面的lb是下界，ub是上界，你这个问题就需要这4个位置的参数，其他位置的参数用[]代替就行，由于ga函数默认是求待优化函数的最小值，所以要想求最大值需要把待优化函数取负，即编写为

function

y=myfun(x)

y=-xsin(10pix)-2;

把这个函数存为myfunm，然后在命令行里敲

x=ga(@myfun,1,[],[],[],[],[1],[2])

会返回

optimization

terminated:

average

change

in

the

fitness

value

less

than

optionstolfun

x

=

18506

由于遗传算法的原理其实是在取值范围内随机选择初值然后进行遗传，所以可能每次运行给出的值都不一样，比如再运行一次会返回

optimization

terminated:

average

change

in

the

fitness

value

less

than

optionstolfun

x

=

16507

这个具体原因需要参考遗传算法的有关资料

最近在做遗传算法的项目，简单记录一下。

遗传算法是模拟自然界生物进化机制的一种算法，在寻优过程中有用的保留无用的去除。包括3个基本的遗传算子：选择（selection）、交叉（crossover）和变异（mutation）。遗传 *** 作的效果与上述3个遗传算子所取的 *** 作概率、编码方法、群体大小、初始群体，以及适应度函数的设定密切相关。

1、种群初始化

popsize 种群大小，一般为20-100，太小会降低群体的多样性，导致早熟；较大会影响运行效率；迭代次数一般100-500；交叉概率：04-099，太小会破坏群体的优良模式；变异概率：0001-01，太大搜索趋于随机。编码包括实数编码和二进制编码，可以参考遗传算法的几个经典问题，TSP、背包问题、车间调度问题。

2、选择

目的是把优化个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代，我大部分采用了轮盘赌的方法。具体可参考 http://myoschinanet/u/1412321/blog/192454 轮盘赌方法各个个体的选择概率和其适应值成比例，个体适应值越大，被选择的概率也越高，反之亦然。在实际问题中，经常需要最小值作为最优解，有以下几种方法进行转换

a、0-1之间的数据，可以用1-该数值，则最小值与最大值互换；

b、 求倒数；

c、求相反数；

以上几种方法均可以将最大值变为最小值，最小值变为最大值，便于利用轮盘赌选择最优个体，根据实际情况来确定。

3、交叉

交叉即将两个父代个体的部分结构加以替换重组而生成新个体的 *** 作，通过交叉，遗传算法的搜索能力得以飞跃提高。根据编码方法的不同，可以有以下的算法：

a、实值重组

离散重组、中间重组、线性重组、扩展线性重组

b、二进制交叉

单点交叉、多点交叉、均匀交叉、洗牌交叉、缩小代理交叉

4、变异

基本步骤：对群中所有个体以事先设定的变异概率判断是否进行变异；对进行变异的个体随机选择变异位进行变异。根据编码表示方法的不同，有实值变异和二进制变异

变异的目的：

a、使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部搜索能力可以加速向最优解收敛。显然该情况下变异概率应取较小值，否则接近最优解的积木块会因为变异遭到破坏。

b、使遗传算法可维持多样性，以防止未成熟收敛现象。此时收敛概率应取较大值。

变异概率一般取0001-01。

5、终止条件

当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时，或者迭代次数达到预设的代数时，算法终止。预设代数一般为100-500。

6、其它

多变量：将多个变量依次连接

多目标：一种方法是转化为单目标，例如按大小进行排序，根据排序和进行选择，可以参考 https://blogcsdnnet/paulfeng20171114/article/details/82454310