遗传算法python （含例程代码与详解）
遗传算法
遗传算法简称GA（Genetic Algorithms）模拟⾃然界⽣物遗传学（孟德尔）和⽣物进化论（达尔⽂）通过⼈⼯⽅式所构造的⼀类 并⾏随机搜索最优化⽅法，是对⽣物进化过程**“优胜劣汰，适者⽣存”**这⼀过程进⾏的⼀种数学仿真。
1.算法简介
该部分主要讲解遗传算法的基础知识，如果已了解的可以直接看下⾯的实现部分
该算法特点
(1)直接对结构对象进⾏操作，不存在求导和函数连续性的限定；
(2)具有内在的隐含并⾏性和更好的全局寻优能⼒；
(3)采⽤概率化的寻优⽅法，能⾃动获取和指导优化的搜索空间，⾃适应地调整搜索⽅向，不需要确定的规则。
遗传算法将“优胜劣汰，适者⽣存”的⽣物进化原理引⼊优化参数形成的编码串体中，按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进⾏筛选，适应度⾼的个体被保留下来，组成新的体，新的体既继承了上⼀代的信息，⼜优于上⼀代。这样周⽽复始，体中个体适应度不断提⾼，直到满⾜⼀定的条件。遗传算法的算法简单，可并⾏处理，并能到全局最优解。
遗传算法主要包括以下三个⽅⾯：
（1）遗传：这是⽣物的普遍特征，亲代把⽣物信息交给⼦代，⼦代总是和亲代具有相同或相似的性状。⽣物有了这个特征，物种才能稳定存在。
（2）变异：亲代和⼦代之间以及⼦代的不同个体之间的差异，称为变异。变异是随机发⽣的，变异的选择和积累是⽣命多样性的根源。
（3）⽣存⽃争和适者⽣存：具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过⼀代代的⽣存环境的选择作⽤，性状逐渐逐渐与祖先有所不同，演变为新的物种。基本操作
1.复制：复制是从⼀个旧种中选择⽣命⼒强的个体位串产⽣新种的过程。具有⾼适应度的位串更有可能在下⼀代中产⽣⼀个或多个⼦孙。（从旧种中选择出优秀者，但不能创造新的染⾊体）复制操作可以通过随机⽅法来实现。⾸先产⽣0-1之间均匀分布的随机数，若某串的复制概率为40%，则当产⽣的随机数在0~0.40之间时，该串被复制，否则被淘汰。
2.交叉：交叉模拟了⽣物进化过程中的繁殖现象，通过两个染⾊体的交换组合，来产⽣新的优良品种。交叉体现了⾃然界中信息交换的思想。交叉有单点交叉、两点交叉、还有⼀致交叉、顺序交叉和周期交叉。单点交叉是最基本的⽅法，应⽤较⼴。它是指在匹配池中任选两个
染⾊体，随机选择⼀个交换点位置，交换双亲染⾊体交换点右边的部分，即可得到两个新的染⾊体，例：3.变异：变异运算⽤来模拟⽣物在⾃然的遗传环境中由于各种偶然因素引起的基因突变，它以很⼩的概率随机地改变遗传基因（表⽰染⾊体的符号串的某⼀位）的值。在染⾊体以⼆进制编码的系统中，变异表现为随机地将染⾊体的某⼀个基因由1变为0，或由0变为1。
2.
算法流程
注：
Gen：遗传（迭代）的代次。表明遗传算法反复执⾏的次数，即已产⽣体的代次数⽬。
M：体中拥有的个体数⽬。
i：已处理个体的累计数，当i等于M，表明这⼀代的个体已全部处理完毕，需要转⼊下⼀代体。
交叉率  就是参加交叉运算的染⾊体个数占全体染⾊体总数的⽐例，记为Pc，取值范围⼀般为0.4～0.99。
变异率  是指发⽣变异的基因位数所占全体染⾊体的基因总位数的⽐例，记为Pm，取值范围⼀般为0.0001～0.1。
复制概率  ⽤于控制复制与淘汰的个体数⽬。
遗传算法主要执⾏以下四步：
（1）随机地建⽴由字符串组成的初始体；
（2）计算各个体的适应度；
（3）根据遗传概率，利⽤下述操作产⽣新体：
P c P m P t
a. 复制。将已有的优良个体复制后添⼊新体中，删除劣质个体；
b. 交换。将选出的两个个体进⾏交换，所产⽣的新个体添⼊新体中。
c.突变。随机地改变某⼀个体的某个字符后添⼊新体中。
（4）反复执⾏（2）、（3）后，⼀旦达到终⽌条件，选择最佳个体作为遗传算法的结果。
3.算法⽰例
求f(x) =  极⼤值问题，设⾃变量 x 介于0～31，求其⼆次函数的最⼤值，即：max f(x) = , x∈ [0, 31]
（1）编码
遗传算法⾸先要对实际问题进⾏编码，⽤字符串表达问题。这种字符串相当于遗传学中的染⾊体。每⼀代所产⽣的字符串个体总和称为体。为了实现的⽅便，通常字符串长度固定，字符选0或1。
本例中，利⽤5位⼆进制数表⽰x值，采⽤随机产⽣的⽅法，假设得出拥有四个个体的初始体，即：
01101，11000，01000，10011。x值相应为13，24，8，19。
（2）计算适应度
衡量字符串（染⾊体）好坏的指标是适应度，它也就是遗传算法的⽬标函数。本例中⽤
计算。
表中还列出了当前适应度的总和及平均值f
表中第6列的 f(xi)/f 表⽰每个个体的相对适应度，它反映了个体之间的相对优劣性。如2号个体的 f(xi)/f 值最⾼（1.97），为优良个体，3号个体最低（0.22），为不良个体。
（3）复制
根据相对适应度的⼤⼩对个体进⾏取舍，2号个体性能最优，予以复制繁殖。3号个体性能最差，将它删除，使之死亡，表中的M表⽰传递
给下⼀代的个体数⽬，其中2号个体占2个，3号个体为0，1号、4号个体保持为1个。这样，就产⽣了下⼀代体
复制后产⽣的新⼀代体的平均适应度明显增加，由原来的293增加到421
（4）交换
利⽤随机配对的⽅法，决定1号和2号个体、3号和4号个体分别交换，如表中第5列。再利⽤随机定位的⽅法，确定这两对母体交叉换位的
位置分别从字符长度的第4位及第3位开始。如：3号、4号个体从字符长度第3位开始交换。交换开始的位置称交换点
（5）突变
将个体字符串某位符号进⾏逆变，即由1变为0或由0变为1。例如，下式左侧的个体于第3位突变，得到新个体如右侧所⽰。
遗传算法中，个体是否进⾏突变以及在哪个部位突变，都由事先给定的概率决定。通常，突变概率很⼩，本例的第⼀代中就没有发⽣突变。上述（2）～（5）反复执⾏，直⾄得出满意的最优解。
综上可以看出，遗传算法参考⽣物中有关进化与遗传的过程，利⽤复制、交换、突变等操作，不断循环执⾏，逐渐逼近全局最优解。
4.算法实现
（1）编码与解码
将不同的实数表⽰成不同的0，1⼆进制串表⽰就完成了编码，因此我们并不需要去了解⼀个实数对应的⼆进制具体是多少，我们只需要保证有⼀个映射能够将⼗进制的数编码为⼆进制即可。⽽在最后我们肯定要将编码后的⼆进制串转换为我们理解的⼗进制串，所以我们需要的是y = f ( x )的逆映射，也就是将⼆进制转化为⼗进制，也就是解码，⼗进制与⼆进制相互映射的关系以下为例进⾏说明：
例如 ：对于⼀个长度为10的⼆进制串，如[0,0,0,1,0,0,0,0,0,1]，将其映射到[1,3]这个区间
x 2x 2x 2f (x )∑i
接口测试的流程和步骤实例1. ⾸先将⼆进制数按权展开：
2. 然后将其压缩到区间[0,1]：
3. 最后将[0,1]区间的数映射到我们想要的区间[1,3]：，可以看出规律为：num *
(high-low)+low 其中num为[0,1]之间的数对应此处的0.0635386，high和low表⽰我们想要映射的区间的上边界和下边界，分别对应此处的3和1。
现在再来看看编码过程。不难看出上⾯我们的DNA（⼆进制串）长为10，10位⼆进制可以表⽰种不同的状态，可以看成是将最后要转化为的⼗进制区间 [ 1 , 3 ] 切分成份。可看出，如果我们增加⼆进制串的长度，那么我们对区间的切分可以更加精细，转化后的⼗进制解也更加精确。所以DNA长度越长，解码为10进制的实数越精确
另外需要注意的是⼀个基因可能存储了多个数据的信息，在进⾏解码时注意将其分开，如⼀个基因含有x,y两个数据，该基因型的长度为20，可以⽤前10位表⽰x，后10位表⽰y，解码时分开进⾏解码。
（2）适应度
在实际问题中，有时希望适应度越⼤越好（如赢利、劳动⽣产率），有时要求适应度越⼩越好（费⽤、⽅差）。为了使遗传算法有通⽤性，这种最⼤、最⼩值问题宜统⼀表达。通常都统⼀按最⼤值问题处理，⽽且不允许适应度⼩于0。
对于最⼩值问题，其适应度按下式转换：
为了保证适应度不出现负值，对于有可能产⽣负值的最⼤值问题，可以采⽤下式进⾏变换：
(3)选择
有了适度函数，然后就可以根据某个基因的适应度函数的值与所有基因适应度的总和的⽐值作为选择的依据，该值⼤的个体更易被选择，可以通过有放回的随机采样来模拟选择的过程，有放回的随机采样的⽅式可以参考我的这篇博客:
(4)交叉和变异
交叉和 变异都是随机发⽣的，对于交叉⽽⾔，随机选择其双亲，并随机选择交叉点位，按照⼀定的概率进⾏交叉操作。可以通过以下⽅式实现：⾸先选择种中的每个基因作为⽗亲，然后通过产⽣⼀个[0,1]随机数，将其与定义的交叉概率⽐较，如果⼩于该数，则在种中随机选择另外的母亲，随机选择交叉点位进⾏交叉。
（5）举例
利⽤遗传算法求Rosenbrock函数的极⼤值
由于该函数的值⾮负就使⽤该函数的值作为适应度值。
算法源码：
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import cm
from mpl_toolkits.mplot3d import Axes3D
DNA_SIZE = 24
POP_SIZE = 80
CROSSOVER_RATE = 0.6
MUTATION_RATE = 0.01
N_GENERATIONS = 100
X_BOUND = [-2.048, 2.048]
Y_BOUND = [-2.048, 2.048]
access短语搭配def F(x, y):
return 100.0 * (y - x ** 2.0) ** 2.0 + (1 - x) ** 2.0  # 以⾹蕉函数为例
0∗2+90∗2+80∗2+71∗2+60∗2+50∗2+40∗2+30∗2+20∗2+11∗2=065
65/(2−101)≈0.0635386
0.0635386∗（3−1）+1≈1.12707722210210
def plot_3d(ax):
X = np.linspace(*X_BOUND, 100)
Y = np.linspace(*Y_BOUND, 100)
X, Y = np.meshgrid(X, Y)
Z = F(X, Y)
ax.plot_surface(X, Y, Z, rstride=1, cstride=1, lwarm)
ax.set_xlabel('x')
ax.set_ylabel('y')
ax.set_zlabel('z')
plt.pause(3)
plt.show()
def get_fitness(pop):
x, y = translateDNA(pop)
pred = F(x, y)
return pred
# return pred - np.min(pred)+1e-3  # 求最⼤值时的适应度
# return np.max(pred) - pred + 1e-3  # 求最⼩值时的适应度，通过这⼀步fitness的范围为[0, np.max(pred)-np.min(pred)]
def translateDNA(pop):  # pop表⽰种矩阵，⼀⾏表⽰⼀个⼆进制编码表⽰的DNA，矩阵的⾏数为种数⽬
x_pop = pop[:, 0:DNA_SIZE]  # 前DNA_SIZE位表⽰X
y_pop = pop[:, DNA_SIZE:]  # 后DNA_SIZE位表⽰Y
x = x_pop.dot(2 ** np.arange(DNA_SIZE)[::-1]) / float(2 ** DNA_SIZE - 1) * (X_BOUND[1] - X_BOUND[0]) + X_BOUND[0]    y = y_pop.dot(2 ** np.arange(DNA_SIZE)[::-1]) / float(2 ** DNA_SIZE - 1) * (Y_BOUND[1] - Y_BOUND[0]) + Y_BOUND[0]    return x, y
def crossover_and_mutation(pop, CROSSOVER_RATE=0.8):
new_pop = []
for father in pop:  # 遍历种中的每⼀个个体，将该个体作为⽗亲
child = father  # 孩⼦先得到⽗亲的全部基因（这⾥我把⼀串⼆进制串的那些0，1称为基因）
if np.random.rand() < CROSSOVER_RATE:  # 产⽣⼦代时不是必然发⽣交叉，⽽是以⼀定的概率发⽣交叉
mother = pop[np.random.randint(POP_SIZE)]  # 再种中选择另⼀个个体，并将该个体作为母亲
cross_points = np.random.randint(low=0, high=DNA_SIZE * 2)  # 随机产⽣交叉的点
child[cross_points:] = mother[cross_points:]  # 孩⼦得到位于交叉点后的母亲的基因
mutation(child)  # 每个后代有⼀定的机率发⽣变异
new_pop.append(child)
return new_pop
def mutation(child, MUTATION_RATE=0.003):
if np.random.rand() < MUTATION_RATE:  # 以MUTATION_RATE的概率进⾏变异
mutate_point = np.random.randint(0, DNA_SIZE*2)  # 随机产⽣⼀个实数，代表要变异基因的位置
child[mutate_point] = child[mutate_point] ^ 1  # 将变异点的⼆进制为反转
def select(pop, fitness):  # nature selection wrt pop's fitness
idx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True,
p=(fitness) / (fitness.sum()))
return pop[idx]
def print_info(pop):
fitness = get_fitness(pop)
max_fitness_index = np.argmax(fitness)
print("max_fitness:", fitness[max_fitness_index])
x, y = translateDNA(pop)
print("最优的基因型：", pop[max_fitness_index])
print("(x, y):", (x[max_fitness_index], y[max_fitness_index]))
print(F(x[max_fitness_index], y[max_fitness_index]))
if __name__ == "__main__":
fig = plt.figure()
ax = Axes3D(fig)数字生成器小程序
plt.ion()  # 将画图模式改为交互模式，程序遇到plt.show不会暂停，⽽是继续执⾏
plot_3d(ax)
pop = np.random.randint(2, size=(POP_SIZE, DNA_SIZE * 2))  # matrix (POP_SIZE, DNA_SIZE)
for _ in range(N_GENERATIONS):  # 迭代N代
x, y = translateDNA(pop)
if 'sca' in locals():
sca = ax.scatter(x, y, F(x, y), c='black', marker='o')
plt.show()
plt.pause(0.1)
web安全攻防电子书pop = np.array(crossover_and_mutation(pop, CROSSOVER_RATE))
python基础代码100例fitness = get_fitness(pop)
pop = select(pop, fitness)  # 选择⽣成新的种oracle vm virtualbox鼠标怎么释放
print_info(pop)
plt.ioff()
plot_3d(ax)
该部分参考链接：
blog.csdn/ha_ha_ha233/article/details/91364937
5.算法应⽤
1.若只有选择和交叉，⽽没有变异，则⽆法在初始基因组合以外的空间进⾏搜索，使进化过程在早期就陷⼊局部解⽽进⼊终⽌过程，从⽽影响解的质量。为了在尽可能⼤的空间中获得质量较⾼的优化解，必须采⽤变异操作。
2.交叉率的取值范围：⼀般为0.4～0.99，变异率的取值范围：⼀般为0.0001～0.1
3.终⽌条件
第⼀种：迭代次数
第⼆种：当⽬标函数是⽅差这⼀类有最优⽬标值的问题时，可采⽤控制偏差的⽅法实现终⽌。⼀旦遗传算法得出的⽬标函数值（适应度）与实际⽬标值之差⼩于允许值后，算法终⽌。
第三种：检查适应度的变化。在遗传算法后期，⼀旦最优个体的适应度没有变化或变化很⼩时，即令计算终⽌。
4.遗传算法的另⼀个重要参数是每代体中的个体数。很明显，个体数⽬越多，搜索范围越⼴，容易获取全局最优解。然⽽个体数⽬太多，每次迭代时间也长。通常，个体数⽬可取100-1000之间。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。