遗传算法 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()
领取专属 10元无门槛券
私享最新 技术干货