遗传算法：基本概念与Python演示

遗传算法 Genetic algorithm

优化问题

目标函数：max，min

决策变量

约束函数

遗传算法：通过模拟自然进化过程搜索最优解的方法

擅长：

全局搜索，

鲁棒性搜索，

不规则搜索空间，

不依赖于优化问题的性质

载体：染色体

染色体是一个串（数组），作为优化问题的解的代码，本身不一定是解

遗传算法的过程

首先，随机产生一定数目（种群的规模）的初始染色体，构成一个种群

然后，用评价函数评价每一个染色体的优劣，即染色体对环境的适应度，用于后续遗传操作的依据

接着，进行选择，选择过程的目的是从当前种群中选出优良的染色体，使之成为新一代的染色体

判断染色体优良与否的准则就是适应度

通过选择过程产生，产生一个新的种群

对新的种群进行交叉操作，相当于生物的杂交

然后进行变异操作，目的是挖掘种群中个体的多样性，克服可能陷入局部的弊病

经过上述运算产生的染色体称为后代

接下来，对新的种群（后代）重复进行选择、交叉、变异操作

经过给定次数的迭代处理后，把最好的染色体作为优化问题的解

表示结构

GA的关键：如何将问题的解转化为编码表示的染色体

GA的显著特点：交替的在编码空间和解空间工作

编码空间：遗传运算（交叉、变异）

解空间：评估、选择

自然选择连接了染色体和它所表达的解的性能

处理约束条件

处理约束条件的关键

将约束条件的符合程度转化为适应度

设计恰当的遗传操作保证所有新的染色体都是合法的

尽量减少在不可行解上的处理时间

初始化过程

初始化

随机产生可行解

难度：可行！？

设计处理不可行染色体的策略

设计生成可行染色体的方法

进化算子

选择过程

交叉算子

变异算子

遗传算法的过程

步骤1：初始产生pop_size个染色体

步骤2：对染色体进行交叉和变异操作

步骤3：计算所有染色体的函数值

步骤4：根据目标函数值，计算每个染色体的适应度

步骤5：通过旋转赌轮，选择染色体

步骤6：重复2-5，直到满足终止条件

步骤7：最好的染色体作为最优解

讨论

为什么遗传算法是有效的，可以作为优化算法？

在遗传算法的执行过程中，哪个操作是影响算法性能的关键？

采用遗传算法求解优化问题的步骤是？

编码、选择、交叉、变异，在优化的过程中各有什么作用？如果提高优化的速度?如何提高解的质量？

遗传算法有哪些可以改进的机会？

Python代码演示：

importrandom

importnumpyasnp

classHandByHandGA:

def__init__(self):

print('Hello, this is HandByHandGA!')

defmain(self):

X =list()

Y =list()

N =10

foriinrange(N):

X.append(random.randint(1,500))

Y.append(random.randint(1,500))

D = {(i,j): np.sqrt(X[i]**2+ Y[j]**2)foriinrange(N)forjinrange(N)}

P = {'iVar': N,'iPop':20,'iGen':10000,'x_over':0.9,'mut':0.01,'D': D}

POP =self.init_population(P)

POP,Elite =self.fitness(P,POP)

v_objective =list()

forginrange(P['iGen']):

POP =self.x_over(P,POP)

POP =self.mutate(P,POP)

POP,Elitec =self.fitness(P,POP)

ifElitec['fitness']

printg,Elitec['fitness'],Elite['fitness']

Elite = Elitec.copy()

v_objective.append(Elite['Obj'])

print'v_objective =',v_objective

print'finnal elite: ','decoded =',Elite['decoded']

print'final objective: ',v_objective[-1]

definit_population(self,P):

POP =list()

foriinrange(P['iPop']):

x =list()

forkinrange(P['iVar']):

x.append(random.random())

POP.append({'x': x,'decoded':list(),'Obj': np.inf,'fitness': np.inf})

returnPOP

deffitness(self,P,POP):

lv_fitness =list()

foriinrange(len(POP)):

obj =

x = POP[i]['x']

lv_d =

lv_d =sorted(lv_d.items(),key=lambdad: d[1])

lv_k = [kfork,vinlv_d]

forkinrange(P['iVar'] -1):

obj += P['D'][lv_k[k],lv_k[k+1]]

obj += P['D'][lv_k[P['iVar'] -1],lv_k[]]

POP[i]['Obj'] = obj

POP[i]['fitness'] = obj

POP[i]['decoded'] = lv_k

lv_fitness.append(obj)

Elite = POP[np.argmin(lv_fitness)]

returnPOP,Elite

defmutate(self,P,POP):

foriinrange(len(POP)):

forcinrange(P['iVar']):

ifrandom.random()

POP[i]['x'][c] = random.random()

returnPOP

defx_over(self,P,POP):

foriinrange(P['iPop']):

ifrandom.random() > P['x_over']:

continue

i1 = random.randint(,P['iPop']-1)

i2 = random.randint(,P['iPop']-1)

i3 = random.randint(,P['iPop']-1)

i4 = random.randint(,P['iPop']-1)

ia,iat,ib,ibt = i2,i1,i4,i3

ifPOP[i1]['fitness']

ia,iat = i1,i2

ifPOP[i3]['fitness']

ib,ibt = i3,i4

forcinrange(P['iVar']):

d = random.random()

POP[iat]['x'][c] = d * POP[ia]['x'][c] + (1- d) * POP[ib]['x'][c]

POP[ibt]['x'][c] = (1- d) * POP[ia]['x'][c] + d * POP[ib]['x'][c]

returnPOP

ga= HandByHandGA()

ga.main()