必威体育Betway必威体育官网
当前位置:首页 > IT技术

遗传算法(GA)

时间:2019-10-15 13:42:14来源:IT技术作者:seo实验室小编阅读:78次「手机版」
 

遗传算法

遗传算法(Genetic Algorithm)

一个讲得很清楚的博客:非常好理解的遗传算法的例子

简单理解:

计算机模拟人类进化,适应环境(符合条件)的继续繁衍后代,不适应环境(不符合条件)的淘汰,从而逐步找到最优解。

整体思路:

随机挑选初始种群,根据适应度函数给初始种群中的个体“打分”,通过定义的规则进行选择,将选择出来的个体两两配对进行交叉,并在生成的对象中挑选变异点,将0变1,1变0,生成后代种群,如此循环找到最优个体即为最优解。

初始种群是啥:

利用二进制(一般)表示最终解

例如:需要求解z=x^2+y^2的最大值,x={1,5,3,8},y={5,4,0,6}

用六位二进制数表示由x,y组成的解,例如:001100 表示x=1,y=4

001100 称为一条基因序列,表示的是该问题的一种解决方案

种群是包含多个基因序列(解决方案/个体)的集合

适应度函数是啥,有什么作用:

适应度函数可以理解成“游戏规则”,如果问题较为复杂,需要自定义适应度函数,说明如何区分优秀与不优秀的个体; 如果问题比较简单,例如上述求最大值的问题,则直接用此函数式作为适应度函数即可。作用:评定个体的优劣程度,从而决定其遗传机会的大小。

怎么选择:

定义“适者生存不适者淘汰”的规则,例如:定义适应度高的被选择的概率更大

怎么交叉:

利用循环,遍历种群中的每个个体,挑选另一个体进行交叉。例如,通过遍历为基因序列A挑选出B配对,则取A的前半部分,B的后半部分,组合成新的个体(基因序列)C

如何变异:

随机挑选基因序列上的某一位置,进行0-1互换

Python实现

这里写图片描述

在此附上莫烦的python实现代码(解决在多峰曲线函数中寻找最大值的问题,如图所示):

莫烦关于此部分的详细讲解视频/代码:遗传算法 莫烦源码

import numpy as np
import matplotlib.pyplot as plt

DNA_SIZE = 10           #序列长度
POP_SIZE = 100          #种群的个体数目
CROSS_RATE = 0.8        #选择多少个体进行交叉配对
MUTATION_RATE = 0.003   #变异的概率/强度
N_GENERATIONS = 100     #有多少代(主循环的迭代次数)
X_BOUND = [0,5]         #输入数据的范围

#需要要找到哪个函数的最大值
def F(x): return np.sin(10*x)*x + np.cos(2*x)*x  #返回y值(此例中为高度)

#用0-1按照定义的规模表示一代种群
pop = np.random.randint(1, size=(POP_SIZE, DNA_SIZE))  #默认从0开始,随机(提供选择的数值个数,重复次数(纵向,横向))
#print(pop)

#适应度函数(在本例中直接使用F函数就好,但是要处理返回值为负数的情况)
def get_fitness(pred):
    return pred + 1e-3 - np.min(pred)

#DNA的翻译规则
def translateDNA(pop):
    #把二进制翻译成十进制,并将其归一化至一个范围(0,5)
    return pop.dot(2 ** np.arange(DNA_SIZE)[::-1]) / float(2**DNA_SIZE-1) * X_BOUND[1]


#适者生存不适者淘汰
#idx:种群中个体的编号
#p参数定义:按什么规格来选择(此例中按照比例来选择,适应度得分高的p越大)
def select(pop,fitness_score):
    idx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True,
                           p=fitness_score/fitness_score.sum())
    return pop[idx]


#繁衍
#父母的DNA交叉配对(定义到底怎么个交叉法)
def crosscover(parent,pop):
    if np.random.rand() < CROSS_RATE:
        i_ = np.random.randint(0,POP_SIZE,size = 1)
        cross_points = np.random.randint(0,2,size = DNA_SIZE).astype(np.bool)
        parent[cross_points] = pop[i_,cross_points]
    return parent

#变异(定义如何随机挑选0-1互换的位置)
def mutate(child):
    for point in range(DNA_SIZE):
        if np.random.rand() < MUTATION_RATE:
            child[point] = 1 if child[point] == 0 else 0
    return child


#画图
#plt.ion()       # something about plotting
#x = np.linspace(*X_BOUND, 200)
#plt.plot(x, F(x))

for _ in range(N_GENERATIONS):
    F_values = F(translateDNA(pop))
    print(translateDNA(pop))
    #print(F_values)

    #计算适应度得分,适应度越高的越好(本例中,适应度就用y轴-高度,也就是F_value体现)
    fitness_score = get_fitness(F_values)  

    #print("Most fitted DNA: ", pop[np.argmax(fitness_score), :])

    #进行适者生存的选择(把种群和得分传入)
    pop = select(pop,fitness_score)
    #print(pop)

    pop_copy = pop.copy()
    #对于种群中所有个体,在种群中挑选另一个体进行配对:
    for parent in pop:
        child = crosscover(parent,pop_copy)        
        child = mutate(child)
        parent[:] = child

#plt.ioff();plt.show()

微生物遗传算法(Microbial GA)

为“升级版GA”,由Inman Harvey于2009年提出,原文:《The Microbial Genetic Algorithm》

解决了什么问题:

主要解决遗传算法中,无法有效保留“好父母”的问题(Elitism):分析GA可是无论父母多么优秀,都不会被保留,只能将各自基因的一部分进行重组,但是重组后的子代并不会一定优于父母。

改进做法:

1.把种群中表现好的基因不做任何改变放入子代中

2.只对表现较差的基因序列进行交叉/变异处理

3.交叉方法:表现较差的在表现较好的基因序列中抽取一部分替换进来

4.变异方法:只在表现较差的基因序列中挑选变异点

注:表现好坏由fitness的得分决定

这里写图片描述

具体做法:

1.生成初始种群

2.在初始种群中随机抽取两个基因序列A/B,对比fitness(假定A的fitness值高)

3.从A中截取部分基因序列替换掉B中对应位置

4.随机在B中抽取位置,进行变异

5.将A与处理后的B‘放回种群中

6.自定义每一代进行多少次抽取/放回操作

Python实现

对于前文提到的在多峰曲线函数中寻找最大值的问题,此处使用MGA解决:

来源:莫烦源码

import numpy as np
import matplotlib.pyplot as plt

DNA_SIZE = 10            # DNA length
POP_SIZE = 20            # population size
CROSS_RATE = 0.6         # mating probability (DNA crossover)
MUTATION_RATE = 0.01     # mutation probability
N_GENERATIONS = 200
X_BOUND = [0, 5]         # x upper and lower bounds


def F(x): return np.sin(10*x)*x + np.cos(2*x)*x     # to find the maximum of this function


class MGA(object):
    def __init__(self, DNA_size, DNA_bound, cross_rate, mutation_rate, pop_size):
        self.DNA_size = DNA_size
        DNA_bound[1] += 1
        self.DNA_bound = DNA_bound
        self.cross_rate = cross_rate
        self.mutate_rate = mutation_rate
        self.pop_size = pop_size

        # initial DNAs for winner and loser
        self.pop = np.random.randint(*DNA_bound, size=(1, self.DNA_size)).repeat(pop_size, axis=0)

    def translateDNA(self, pop):
        # convert binary DNA to decimal and normalize it to a range(0, 5)
        return pop.dot(2 ** np.arange(self.DNA_size)[::-1]) / float(2 ** self.DNA_size - 1) * X_BOUND[1]

    def get_fitness(self, product):
        return product      # it is OK to use product value as fitness in here

    def crossover(self, loser_winner):      # crossover for loser
        cross_idx = np.empty((self.DNA_size,)).astype(np.bool)
        for i in range(self.DNA_size):
            cross_idx[i] = True if np.random.rand() < self.cross_rate else False  # crossover index
        loser_winner[0, cross_idx] = loser_winner[1, cross_idx]  # assign winners genes to loser
        return loser_winner

    def mutate(self, loser_winner):         # mutation for loser
        mutation_idx = np.empty((self.DNA_size,)).astype(np.bool)
        for i in range(self.DNA_size):
            mutation_idx[i] = True if np.random.rand() < self.mutate_rate else False  # mutation index
        # flip values in mutation points
        loser_winner[0, mutation_idx] = ~loser_winner[0, mutation_idx].astype(np.bool)
        return loser_winner

    def evolve(self, n):    # nature selection wrt pop's fitness
        for _ in range(n):  # random pick and compare n times
            sub_pop_idx = np.random.choice(np.arange(0, self.pop_size), size=2, replace=False)
            sub_pop = self.pop[sub_pop_idx]             # pick 2 from pop
            product = F(self.translateDNA(sub_pop))
            fitness = self.get_fitness(product)
            loser_winner_idx = np.argsort(fitness)
            loser_winner = sub_pop[loser_winner_idx]    # the first is loser and second is winner
            loser_winner = self.crossover(loser_winner)
            loser_winner = self.mutate(loser_winner)
            self.pop[sub_pop_idx] = loser_winner

        DNA_prod = self.translateDNA(self.pop)
        pred = F(DNA_prod)
        return DNA_prod, pred


plt.ion()       # something about plotting
x = np.linspace(*X_BOUND, 200)
plt.plot(x, F(x))

ga = MGA(DNA_size=DNA_SIZE, DNA_bound=[0, 1], cross_rate=CROSS_RATE, mutation_rate=MUTATION_RATE, pop_size=POP_SIZE)

for _ in range(N_GENERATIONS):                    # 100 generations
    DNA_prod, pred = ga.evolve(5)          # natural selection, crossover and mutation

    # something about plotting
    if 'sca' in globals(): sca.remove()
    sca = plt.scatter(DNA_prod, pred, s=200, lw=0, c='red', alpha=0.5); plt.pause(0.05)

plt.ioff();plt.show()

参考:莫烦关于进化算法的视频教程

相关阅读

Gamma校正

1. Gamma 值 2. Gamma校正 2.1 使用OpenGL内建的sRGB帧缓存 2.2 在片元着色器中自己应用gamma校正 3. sRGB纹理 3.1 使用 与 实

Ubautu下安装pygame

1.在linux系统中检查是否安装了pippip --version出现所示信息:  pip 8.1.1 from /usr/lib/python2.7/dist-packages (python 2.7)

事件冒泡之cancelBubble和stoppropagation的区别

事实上stoppropagation和cancelBubble的作用是一样的,都是用来阻止浏览器默认的事件冒泡行为。不同之处在于stoppropagation属于W3

安路科技邀您参加第三届全国大学生FPGA创新设计竞赛

由教育部电子信息类专业教学指导委员会及国家级实验教学示范中心联席会联合组织,面向全国大学本科学生及研究生的第三届全国大学

如何评价GAN网络的好坏?IS(inception score)和FID(Fréche

值得一看,总结了IS和FID的历史发展原文地址在对抗生成网络中,判别器和生成器的目标函数通常都是用来衡量它们各自做的怎么样的。例

分享到:

栏目导航

推荐阅读

热门阅读