遗传算法实例解析(python)

一.简介

遗传算法(Genetic Algorithm, GA)是模拟达尔文生物进化论的自然选择和遗传机理的生物学进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。

遗传算法以一种群体中的所有个体为对象,并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中,选择、交叉和变异构成了遗传算法的遗传操作;参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。

初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代(generation)演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度(fitness)大小选择(selection)个体,并借助于自然遗传学的遗传算子(genetic operators)进行组合交叉(crossover)和变异(mutation),产生出代表新的解集的种群。

二.遗传算法图解过程


图1 遗传算法流程图

三.程序实例

(一)题目简介

最大化目标函数Y。

其中(x1,x2,x3,x4,x5,x6)=(4,-2,3.5,5,-11,-4.7),求w1,w2,w3,w4,w5,w6。

图2 目标函数

(二)分步程序

1. 初始种群:随机生成8个solution,即生成8组w1,w2,w3,w4,w5,w6。

# Inputs of the equation.

equation_inputs = [4,-2,3.5,5,-11,-4.7]

# Number of the weights we are looking to optimize.

num_weights =len(equation_inputs)  # num_weight=6

sol_per_pop =8

num_parents_mating =4

# Defining the population size:shape(8,6).

pop_size = (sol_per_pop, num_weights)

# Creating the initial population.

new_population = numpy.random.uniform(low=-4.0, high=4.0, size=pop_size)

print(new_population)  # 输出随机生成的(8,6) population矩阵

2.计算适应度:计算每个solution的fitness,即带入公式计算出Y的值。

# 计算fitness

def cal_pop_fitness(equation_inputs, pop):

# Calculating the fitness value of each solution in the current population.

# The fitness function calculates the sum of products between each input and its corresponding weight.

    fitness = numpy.sum(pop * equation_inputs, axis=1)  # 每一行6位对应相乘相加得出和,一共计算出8个和值

    return fitness

a = cal_pop_fitness(equation_inputs, new_population)

print(a)  # 输出计算出的8个solution的fitness值

3.根据fitness值从大到小,选择最大的4个作为parent,以便后续交叉、变异生成子代。

# 选择parents:

def select_mating_pool(pop, fitness, num_parents):

# Selecting the best individuals in the current generation as parents for producing the offspring of the next generation.

    parents = numpy.empty((num_parents, pop.shape[1]))# parents用来存放被选择的parent,shape:(4,6)

    for parent_numin range(num_parents):

max_fitness_idx = numpy.where(fitness == numpy.max(fitness))

# print(max_fitness_idx)  存的是array([3],),所以需要下一步取出具体的值3

        max_fitness_idx = max_fitness_idx[0][0]

# print(max_fitness_idx)

        parents[parent_num, :] = pop[max_fitness_idx, :]# 将fitness值大的solution放入parent

        fitness[max_fitness_idx] = -99999999999  # 将已选的solution的fitness值赋为很小,以免再被选到

    return parents

b = select_mating_pool(new_population, a, num_parents_mating)

print('\n',b)

4.交叉:随机生成一个数作为交叉点开始位置,从交叉点起始后的片段进行交叉。parent1与parent2交叉,把交叉第一个结果作为子代offspring1,同样,parent2与parent3交叉得到offspring2,parent3与parent4交叉得到offspring3,parent4与parent1交叉得到offspring4.

# 单点交叉crossover

def crossover(parents, offspring_size):

offspring = numpy.empty(offspring_size)

# The point at which crossover takes place between two parents. Usually, it is at the center.

    crossover_point = numpy.uint8(offspring_size[1] /2)# 6/2=3

    print('\n crossover point: ',crossover_point)

for kin range(offspring_size[0]):

# Index of the first parent to mate.

        parent1_idx = k % parents.shape[0]

# Index of the second parent to mate.

        parent2_idx = (k +1) % parents.shape[0]

# The new offspring will have its first half of its genes taken from the first parent.

        offspring[k,0:crossover_point] = parents[parent1_idx,0:crossover_point]

# The new offspring will have its second half of its genes taken from the second parent.

        offspring[k, crossover_point:] = parents[parent2_idx, crossover_point:]

return offspring

offspring_size = (pop_size[0]-b.shape[0],num_weights)# 8-4=4

c = crossover(b, offspring_size)

print(c)

5.变异:随机生成一个数,作为变异数。假定变异位为4,将交叉后生成的offspring每个位置4上的值都加上变异数,形成新的4个子代。

# 随机变异mutation

def mutation(offspring_crossover):

# Mutation changes a single gene in each offspring randomly.

    for idxin range(offspring_crossover.shape[0]):

# The random value to be added to the gene.

        random_value = numpy.random.uniform(-1.0,1.0,1)

# print(random_value) 随机生成突变数

        offspring_crossover[idx,4] = offspring_crossover[idx,4] + random_value

return offspring_crossover

d = mutation(c)

print('\n',d)

6.新种群:将4个新生成的offspring加入原有的parents,形成新的种群。

# 新种群:4 parents+4 offsprings

new_population[0:b.shape[0], :] = b

new_population[b.shape[0]:, :] = d

print("\n new population:\n",new_population)

7.计算新种群fitness

# 计算新种群fitness

e = cal_pop_fitness(equation_inputs, new_population)

print("\n new population fitness:\n",e)

#一次迭代过程结束


(三)完整一次迭代程序

import numpy

'''

一次迭代遗传算法实例

-----------------------------------------

The y=target is to maximize this equation:

y = w1x1+w2x2+w3x3+w4x4+w5x5+6wx6

where (x1,x2,x3,x4,x5,x6)=(4,-2,3.5,5,-11,-4.7)

What are the best values for the 6 weights w1 to w6?

------------------------------------------

原种群:随机生成8个solution

计算fitness:计算8个solution的fitness值

选择parent:fitness较高的其中4个solution

生成offspring:parent交叉、变异生成4个新的solution

新种群:4个parent + 4个offspring

计算新种群的fitness,观察是否有改进

------------------------------------------

'''

# Inputs of the equation.

equation_inputs = [4,-2,3.5,5,-11,-4.7]

# Number of the weights we are looking to optimize.

num_weights =len(equation_inputs)# 6

sol_per_pop =8

num_parents_mating =4

# Defining the population size:shape(8,6).

pop_size = (sol_per_pop,num_weights)

# The population will have sol_per_pop chromosome where each chromosome has num_weights genes.

# Creating the initial population.

new_population = numpy.random.uniform(low=-4.0,high=4.0,size=pop_size)

print(new_population)# 输出随机生成的(8,6)population矩阵


# 计算fitness

def cal_pop_fitness(equation_inputs, pop):

# Calculating the fitness value of each solution in the current population.

# The fitness function calculates the sum of products between each input and its corresponding weight.

    fitness = numpy.sum(pop * equation_inputs,axis=1)# 每一行6位对应相乘相加得出和,一共计算出8个和值

    return fitness

a = cal_pop_fitness(equation_inputs,new_population)

print(a)

# 输出计算出的8个solution的fitness值: (8,6)*(6,1)=(8,1)


# 选择parents

def select_mating_pool(pop, fitness, num_parents):

# Selecting the best individuals in the current generation as parents for producing the offspring of the next generation.

    parents = numpy.empty((num_parents, pop.shape[1]))# parents用来存放被选择的parent,shape:(4,6)

    for parent_numin range(num_parents):

max_fitness_idx = numpy.where(fitness == numpy.max(fitness))

# print(max_fitness_idx)  存的是array([3],),所以需要下一步取出具体的值3

        max_fitness_idx = max_fitness_idx[0][0]

# print(max_fitness_idx)

        parents[parent_num, :] = pop[max_fitness_idx, :]# 将fitness值大的solution放入parent

        fitness[max_fitness_idx] = -99999999999  # 将已选的solution的fitness值赋为很小,以免再被选到

    return parents

b = select_mating_pool(new_population,a,num_parents_mating)

print('\n',b)

# 单点交叉crossover

def crossover(parents, offspring_size):

offspring = numpy.empty(offspring_size)

# The point at which crossover takes place between two parents. Usually, it is at the center.

    crossover_point = numpy.uint8(offspring_size[1] /2)# 6/2=3

    print('\ncrossover point: ',crossover_point)

for kin range(offspring_size[0]):

# Index of the first parent to mate.

        parent1_idx = k % parents.shape[0]

# Index of the second parent to mate.

        parent2_idx = (k +1) % parents.shape[0]

# The new offspring will have its first half of its genes taken from the first parent.

        offspring[k,0:crossover_point] = parents[parent1_idx,0:crossover_point]

# The new offspring will have its second half of its genes taken from the second parent.

        offspring[k, crossover_point:] = parents[parent2_idx, crossover_point:]

return offspring

offspring_size = (pop_size[0]-b.shape[0],num_weights)# 8-4=4

c = crossover(b,offspring_size)

print(c)

# 随机变异mutation

def mutation(offspring_crossover):

# Mutation changes a single gene in each offspring randomly.

    for idxin range(offspring_crossover.shape[0]):

# The random value to be added to the gene.

        random_value = numpy.random.uniform(-1.0,1.0,1)

# print(random_value) 随机生成突变数

        offspring_crossover[idx,4] = offspring_crossover[idx,4] + random_value

return offspring_crossover

d = mutation(c)

print('\n',d)

# 新种群:4 parents+4 offsprings

new_population[0:b.shape[0], :] = b

new_population[b.shape[0]:, :] = d

print("\nnew population:\n",new_population)

# 计算新种群fitness

e = cal_pop_fitness(equation_inputs,new_population)

print("\nnew population fitness:\n",e)


(四)程序输出结果

initial population:

[[ 1.49671815  0.93113301  1.52468311  2.1008358  0.52596433  1.98108016]

[ 0.02967332  3.04681893  1.97656438  2.7959895  3.15241166  3.91648211]

[-1.31178987 -1.27418233 -1.00478326 -1.29114282  1.8485721  3.13817543]

[ 2.65273704  1.00240443  3.92621841  1.7364455  1.46130962 -3.52271109]

[ 1.51475644 -2.1725475  1.47089756 -3.69968089  2.24351239  2.65613884]

[-2.54748948  1.26403815 -0.09425664  3.68666271 -1.41268268 -3.59376827]

[ 0.58807659 -0.57318307 -2.12536315 -1.06865911  3.62827415 -0.47741893]

[ 0.72622601  1.08531417 -1.14659535 -0.95386063 -1.96272369 -0.51242958]]

initial fitness:

[  4.86849204 -38.16101585 -47.75496796  31.51246754 -40.10863106

  37.81560145 -46.95054081  15.95026854]

parents:

[[-2.54748948  1.26403815 -0.09425664  3.68666271 -1.41268268 -3.59376827]

[ 2.65273704  1.00240443  3.92621841  1.7364455  1.46130962 -3.52271109]

[ 0.72622601  1.08531417 -1.14659535 -0.95386063 -1.96272369 -0.51242958]

[ 1.49671815  0.93113301  1.52468311  2.1008358  0.52596433  1.98108016]]

crossover point:  3

crossover offspring:

[[-2.54748948  1.26403815 -0.09425664  1.7364455  1.46130962 -3.52271109]

[ 2.65273704  1.00240443  3.92621841 -0.95386063 -1.96272369 -0.51242958]

[ 0.72622601  1.08531417 -1.14659535  2.1008358  0.52596433  1.98108016]

[ 1.49671815  0.93113301  1.52468311  3.68666271 -1.41268268 -3.59376827]]

mutation offspring:

[[-2.54748948  1.26403815 -0.09425664  1.7364455  2.1462265  -3.52271109]

[ 2.65273704  1.00240443  3.92621841 -0.95386063 -2.7350463  -0.51242958]

[ 0.72622601  1.08531417 -1.14659535  2.1008358  0.21911624  1.98108016]

[ 1.49671815  0.93113301  1.52468311  3.68666271 -2.21451672 -3.59376827]]

new population:

[[-2.54748948  1.26403815 -0.09425664  3.68666271 -1.41268268 -3.59376827]

[ 2.65273704  1.00240443  3.92621841  1.7364455  1.46130962 -3.52271109]

[ 0.72622601  1.08531417 -1.14659535 -0.95386063 -1.96272369 -0.51242958]

[ 1.49671815  0.93113301  1.52468311  2.1008358  0.52596433  1.98108016]

[-2.54748948  1.26403815 -0.09425664  1.7364455  2.1462265  -3.52271109]

[ 2.65273704  1.00240443  3.92621841 -0.95386063 -2.7350463  -0.51242958]

[ 0.72622601  1.08531417 -1.14659535  2.1008358  0.21911624  1.98108016]

[ 1.49671815  0.93113301  1.52468311  3.68666271 -2.21451672 -3.59376827]]

new population fitness:

[ 37.81560145  31.51246754  15.95026854  4.86849204 -11.41745433

  50.07252895  -4.4959844  69.14470585]


对比new population fitness 和 initial fitness,结果有了很大改善。初始解中最大值是37.81560145,经过遗传算法一次选择交叉变异后,最大值变为了69.14470585,效果显著。迭代次数增加,越接近最优解。

简书代码不美观,同时在CSDN发布:https://mp.csdn.net/postedit/102652596


参考资料:

https://www.jianshu.com/p/ae5157c26af9

https://towardsdatascience.com/genetic-algorithm-implementation-in-python-5ab67bb124a6

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 201,681评论 5 474
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,710评论 2 377
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 148,623评论 0 334
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,202评论 1 272
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,232评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,368评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,795评论 3 393
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,461评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,647评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,476评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,525评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,226评论 3 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,785评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,857评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,090评论 1 258
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,647评论 2 348
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,215评论 2 341

推荐阅读更多精彩内容