精华内容
下载资源
问答
  • 遗传算法python库Genetic algorithms (GA) are an optimization and search technique based on the principles of genetics and natural selection, in essence mimicking the natural evolution process that we ...

    遗传算法python库

    Genetic algorithms (GA) are an optimization and search technique based on the principles of genetics and natural selection, in essence mimicking the natural evolution process that we observe in life. Their general principle is based on the concept of having an initial population composed of several individuals — with each representing a particular solution to the problem — and allow it to evolve to a state that maximizes its overall fitness, using three main operators: selection, crossover and mutation. We’ll look into these aspects a bit more in detail below.

    遗传算法(GA)是一种基于遗传和自然选择原理的优化和搜索技术,实质上模仿了我们在生活中观察到的自然进化过程。 他们的一般原则基于以下概念: 初始人口由几个人组成,每个人代表一个特定的问题解决方案,并使用三个主要运算符将其发展为最大化整体适应性的状态: 选择交叉突变 。 我们将在下面更加详细地研究这些方面。

    Genetic Algorithms are nothing short of fantastic, as they can be applied to many kinds of optimization problems and find solutions to complex functions for which we do not have a mathematical expression. This comes at a cost of computational complexity though, as, for large populations, we’ll have to evaluate the fitness of all individuals at every generation. If the fitness function is expensive, the algorithm run will be slow.

    遗传算法简直就是太神奇了,因为它们可以应用于多种优化问题并找到我们没有数学表达式的复杂函数的解。 但是,这是以计算复杂性为代价的,因为对于大量人口,我们必须评估每一代所有个体的适应性。 如果适应度函数昂贵,则算法运行会很慢。

    GA’s can be divided into Binary and Continuous, depending on the type of problem we’re optimizing for. Potentially all problems could be broken down as having their variables (genes) represented by binary strings, but in general, if the input space is real-valued, it makes more sense to use a continuous GA.

    GA可以分为BinaryContinuous ,具体取决于我们要优化的问题类型。 可能所有问题都可以通过用二进制字符串表示其变量( 基因)来分解,但是总的来说,如果输入空间是实值,则使用连续 GA更有意义。

    As there are fewer examples for continuous GA out there, the examples shown here will be for that version of GA.

    由于那里连续GA的示例较少,因此此处显示的示例适用于该版本的GA。

    Initialization

    初始化

    The search starts with a random population of N individuals. Each of those individuals corresponds to a chromosome, which encodes a sequence of genes representing a particular solution to the problem we’re trying to optimize for. Depending on the problem at hand, the genes representing the solution could be bits (0’s and 1’s) or continuous (real valued). An example of a real-valued chromosome representing a solution to a given problem with 9 variables (genes) is shown below.

    搜索从N个个体的随机种群开始。 这些个体中的每一个都对应一条染色体 ,该染色体编码表示代表我们要优化的问题的特定解决方案的一系列基因。 根据当前的问题,代表解决方案的基因可以是位(0和1)或连续(实值)。 下面显示了一个实值染色体的示例,该染色体代表具有9个变量( 基因 )的给定问题的解决方案。

    Image for post
    Example of an individual’s chromosome
    个人染色体的例子

    Fitness

    适合度

    The fitness of each individual is what defines what we are optimizing for, so that, given a chromosome encoding a specific solution to a problem, its fitness will correspond to how well that particular individual fares as a solution to the problem. Therefore, the higher its fitness value, the more optimal that solution is.

    每个人的健康状况 是什么定义了我们要优化的内容,因此,给定染色体编码的问题的特定解决方案,其适应性将对应于特定个体解决问题的能力。 因此,其适用性值越高,该解决方案越理想。

    After all, individuals have their fitness score calculated, they are sorted, so that the fittest individuals can be selected for crossover.

    毕竟,已经计算了个人的健身得分,并对他们进行了排序,以便可以选择最适合的个人进行交叉。

    Selection

    选拔

    Selection is the process by which a certain proportion of individuals are selected for mating between each other and create new offsprings. Just like in real-life natural selection, individuals that are fitter have higher chances of surviving, and therefore, of passing on their genes to the next generation. Though versions with more individuals exist, usually the selection process matches two individuals, creating pairs of individuals. There are four main strategies:

    选择是选择特定比例的个体以使其彼此交配并产生新后代的过程。 就像现实中的自然选择一样,更健康的个体有更高的生存机会,因此可以将其基因传给下一代。 尽管存在更多个人的版本,但通常选择过程会匹配两个个人,从而创建成对的个人。 有四种主要策略:

    pairing: This is perhaps the most straightforward strategy, as it simply consists of pairing the top fittest chromosomes two-by-two (pairing odd rows with even ones).

    配对 :这可能是最直接的策略,因为它仅包括将最合适的染色体两两配对(将奇数行与偶数行配对)。

    random: This strategy consists of randomly selecting individuals from the mating pool.

    随机 :此策略包括从交配池中随机选择个体。

    roulette wheel: This strategy also follows a random principle, but fitter individuals have higher probabilities of being selected.

    轮盘赌 :这种策略也遵循随机原则,但是更健康的人被选中的可能性更高。

    tournament: With this strategy, the algorithm first selects a few individuals as candidates (usually 3), and then selects the fittest individual. This option has the advantage that it does not require the individuals to be sorted by fitness first.

    比赛 :采用这种策略时,算法首先选择一些个人作为候选者(通常为3个人),然后选择最适合的个人。 该选项的优点是它不需要先按适合度对个人进行分类。

    A python implementation for the roulette wheel strategy is shown on the snippet below.

    下面的代码段显示了轮盘策略的python实现。

    Crossover

    交叉

    This is the step where new offsprings are generated, which will then replace the least fit individuals in the population. The idea behind crossing over individuals is that, by combining different genes, we might produce even fitter individuals, which will be better solutions to our problem. Or not, and in that case, those solutions won’t survive to the next generations.

    这是生成新后代的步骤,然后将替换种群中最不适合的个体。 跨越个体​​背后的想法是,通过组合不同的基因,我们甚至可以生产出更健康的个体,这将是解决我们问题的更好方法。 不管是不是,在那种情况下,这些解决方案都无法延续到下一代。

    In order to perform the actual crossover, each of the pairs coming from the selection step are combined to produce two new individuals each, which will both have genetic material from each of the parents. There are several different strategies for performing the crossover, so for brevity, we’ll only discuss one of them.

    为了进行实际的杂交,将来自选择步骤的每对配对以产生两个新个体,每个个体都具有来自每个亲本的遗传物质。 执行交叉有几种不同的策略,为简便起见,我们仅讨论其中一种。

    Supposing we have a problem defined by 9 variables, if we have 2 parents and we choose randomly the crossover gene as index 3, then each of the offsprings will be a combination of each parent, as shown in the diagram below.

    假设我们有一个由9个变量定义的问题,如果我们有2个父母,并且我们随机选择交叉基因作为索引3,那么每个后代将是每个父母的组合,如下图所示。

    Image for post
    Diagram showing how parents are crossed over to generate new offspring
    该图显示了父母如何过渡以产生新的后代

    The crossover gene of each offspring is calculated according to the rule given by:

    每个后代的交叉基因根据以下规则计算:

    Image for post
    Equation for calculating new crossover genes
    计算新交叉基因的方程式

    Where β will be a random number between 0 and 1. The python code for the crossover is given below.

    其中β是0到1之间的随机数。下面给出了交叉的python代码。

    Mutation

    突变

    Mutation is the process by which we introduce new genetic material in the population, allowing the algorithm to search a larger space. If it were not for mutation, the existing genetic material diversity in a population would not increase, and, due to some individuals “dying” between generations, would actually be reduced, with individuals tending to become very similar quite fast.

    突变是我们在种群中引入新遗传物质的过程,从而使算法可以搜索更大的空间。 如果不是为了突变,则种群中现有的遗传物质多样性将不会增加,而且由于某些个体在世代之间“垂死”,实际上会减少,而个体趋于变得非常相似。

    In terms of the optimization problem, this means that without new genetic material the algorithm can converge to local optima before it explores an enough large size of the input space to make sure that we can reach the global optimum. Therefore, mutation plays a big role in maintaining diversity in the population and allowing it to evolve to fitter solutions to the problem.

    就优化问题而言,这意味着在没有新的遗传材料的情况下,该算法可以先收敛到局部最优,然后再探索足够大的输入空间,以确保我们可以达到全局最优。 因此,突变在维持种群多样性并使其进化以适应问题的解决方案中起着重要作用。

    The most simple way we can do this is, given a certain mutation rate, to randomly choose some individuals and some genes and assign a new random number to those positions. This is exemplified in the diagram and code snippet below.

    我们可以执行此操作的最简单方法是,在确定突变率的情况下 ,随机选择一些个体和某些基因,并为这些位置分配一个新的随机数。 下面的图和代码段中对此进行了举例说明。

    Image for post
    Mutation of two genes in an individual
    个体中两个基因的突变

    Solver

    解算器

    Now it’s time to tie it all together. Using the operators that we defined above, the algorithm can now solve the problem, with the actual main cycle of the algorithm being implemented in just a few lines of code. The flowchart of the algorithm, as well as an example implementation in python are shown below.

    现在是时候将它们捆绑在一起了。 使用上面定义的运算符,该算法现在可以解决问题,该算法的实际主循环仅用几行代码即可实现。 该算法的流程图以及python中的示例实现如下所示。

    Image for post
    Flowchart of the Genetic Algorithm
    遗传算法流程图

    介绍GeneAl (Introducing GeneAl)

    GeneAl is a python library implementing Genetic Algorithms, which can be used and adapted to solve many optimization problems. One can use the provided out-of-the-box solver classes — BinaryGenAlgSolver and ContinuousGenAlgSolver — , or create a custom class which inherits from one of these, and implements methods that override the built-in ones. It also has support for solving the (in)famous Travelling Salesman Problem.

    GeneAl是实现遗传算法的python库,可用于解决许多优化问题。 可以使用提供的现成的求解器类BinaryGenAlgSolverContinuousGenAlgSolver ,或者创建一个自定义类继承自其中的类,并实现覆盖内置方法的方法。 它还支持解决著名的旅行推销员问题

    For brevity, we’ll only see how to use the continuous version — keeping in line with this post — , but for more details, check out the README of this project.

    为简便起见,我们只会看到如何使用连续版本-与本文保持一致-,但是要了解更多详细信息,请查看该项目的自述文件。

    The first thing would be to install the package, which can be made through pip, as such:

    首先是要安装软件包,可以通过pip进行安装,如下所示:

    pip install geneal 

    After the installation completes, one is ready to use it. So let’s see how we can use the ContinuousGenAlgSolver class.

    安装完成后,就可以使用了。 因此,让我们看看如何使用ContinuousGenAlgSolver类。

    As a bare minimum, the class requires the user to provide the number of genes present in the problem, as well as to provide the custom defined fitness function. For convenience, the library provides some default fitness functions that can be used for testing.

    至少,该类别要求用户提供问题中存在的基因数量,并提供自定义的适应度函数。 为了方便起见,该库提供了一些可用于测试的默认适应性函数。

    With the initialization done above, the class will solve the problem using default values for all the parameters. If we wish to have more control over the algorithm run, we will want to adjust these, and that can be done as shown below:

    通过上面的初始化,该类将使用所有参数的默认值解决问题。 如果我们希望对算法的运行有更多的控制,我们将希望对其进行调整,如下所示:

    Finally, this class allows the user to specify the type of problem — if the possible values are integers or floats — , as well as the variables’ limits, in order to limit the search space.

    最后,该类允许用户指定问题的类型(如果可能的值是整数或浮点数)以及变量的限制,以限制搜索空间。

    This completes this short introduction to the library. If you want to know more, check out the GitHub repository, which has more information :)

    这样就完成了对库的简短介绍。 如果您想了解更多信息,请查看GitHub存储库 ,其中包含更多信息:)

    Thanks for reading!

    谢谢阅读!

    翻译自: https://towardsdatascience.com/introducing-geneal-a-genetic-algorithm-python-library-db69abfc212c

    遗传算法python库

    展开全文
  • 遗传算法python

    2020-12-24 13:19:36
    本文实例为大家分享了python遗传算法的具体代码,供大家参考,具体内容如下 1、基本概念 遗传算法(GA)是最早由美国Holland教授提出的一种基于自然界的“适者生存,优胜劣汰”基本法则的智能搜索算法。该法则很好...
  • 遗传算法python代码

    2019-04-01 15:34:50
    解决的例子y=10*sin(5x)+7*cos(4x) 代码用python3.6可以运行
  • 遗传算法Python 教程(1) 遗传算法简介 遗传算法是一种通过种群演化得到最优解的搜索算法。遗传算法受启发与生物演化过程中的一些现象,这些现象包括自然选择,交配,突变,遗传等。本教程将通过Python来展示遗传...

    遗传算法Python 教程(1)

    遗传算法简介

    遗传算法是一种通过种群演化得到最优解的搜索算法。遗传算法受启发与生物演化过程中的一些现象,这些现象包括自然选择,交配,突变,遗传等。本教程将通过Python来展示遗传算法的本质和如何使用遗传算法去解决问题。

    遗传算法的一般概念

    遗传算法是通过一代一代种群 population 演化来寻找对问题最优解的个体 individual。其中种群中包含了 N 个个体,而每一个个体是问题的可能解。每一次迭代,fitness 函数会计算每一个个体对目标问题解的合适成都然后选择最适合的k个个体为下一代演化的后代。演化过程中会有一定概率的个体相互交配,互换染色体,和突变行为,这一过程可以防止种群在演化过程中的适应度被困在局部最优解。 遗传算法的过程可以被一下步骤描述。

    1. 一个随机生成的种群 population
    2. 通过fitness 函数选择种群的后代;
    3. 后代 offerspring 在一定概率下交配
    4. 后代 offerspring 在一定概率下 变异
    5. 将后代赋值给种群 population, 重复步骤 (2) 至 (4) 直到迭代次数超过设定值;

    第一个遗传算法的实现

    首先我们实现一个简单的遗传算法。我们期望通过遗传算法演化出一个长度为10 且所有元素都为 1list [1111111111]。在这个简单例子中将只会用到 变异,因为这里我们主要希望展现遗传算法的迭代过程,所以关于交配的方法和更高级的fitness函数的构建将在后续的教程中介绍。

    import numpy as np
    import copy
    
    # -- 定义参数 --
    populationSize = 50
    numGenerations = 100
    # ***
    genomeLength = 10
    population = []
    
    # -- 遗传算法需要用到的方法 --
    
    # 变异
    def mutate(Wgenome, mutationRate=0.1):
    	for i in range(len(Wgenome)):
    		if np.random.random() < mutationRate:
       			Wgenome[i] = np.random.randint(2)
    
    # 选择
    def topNSelectFull(topn=10, maximize=True):
        global population, populationSize
        population.sort(key=lambda x: x.fitness, reverse=maximize)
        selected = copy.deepcopy(population[:topn])
        counter = 0
        for i in range(populationSize):
            population[i] = copy.deepcopy(selected[counter])
            counter += 1
            if counter == topn:
                counter = 0
    

    接着我们定义一个个体

    class individual:
        def __init__(self):
            self.fitness = 0 #个体的适应度
            self.genome = [] #个体是一个list
        def setGenome(self, newGenome):
            self.genome = newGenome
        def getGenome(self):
            return self.genome
    

    因为我们期望从随机生成的个体中演化出一个全为1的list, 所以我们的fitness 函数就会是这个list的求和 sum(p.getGenome())。然后我们选择演化过程中最大化个体的适应度,所以让 topNSelectFull 去选择适应度最高的5个个体。最后演化完成后我们把最后一代的所有个体打出来。

    if __name__ == "__main__":
        for i in range(populationSize):
            indiv = individual()
            # ***
            #indiv.setGenome( np.random.choice(2,genomeLength) )
            indiv.setGenome( np.zeros(genomeLength, dtype=int) )
    
            population.append( indiv )
    
        for generation in range(numGenerations):
            for p in population:
                #计算每个个体的适应度
                p.fitness = sum(p.getGenome())
    
            if generation % 1 == 0:
                print( "Gen", generation, "Fitness: ", np.max( [p.fitness for p in population] ) )
    
            topNSelectFull(topn=5, maximize=True)
            # 选择适应度最高的五个个体
    
            for i in range(populationSize):
            # 使 10 % 的个体变异
                newGenome = mutate(population[i].getGenome(), mutationRate=0.1)
    
    # ***
    for p in population:
        print ( p.getGenome() )
    

    一个简单的遗传算法就完成了。

    展开全文
  • 遗遗传传算算法法python版版 这篇文章主要为大家详细介绍了python实现遗传算法具有一定的参考价值感兴趣的小伙伴们可以参考一下 本文实例为大家分 了python遗传算法的具体代码供大家参考具体内容如下 1基基本本概...
  • 柔性作业车间调度问题中,以完工时间作为优化目标,编写的遗传算法代码,python语言。代码中套用了一个自己随机生成的实例进行运行验证,仅供参考学习。
  • 遗传算法python(含例程代码与详解)

    千次阅读 多人点赞 2020-10-24 11:00:57
    遗传算法1.算法简介2.算法流程3.算法示例4.算法实现5.算法应用


    遗传算法简称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,表明这一代的个体已全部处理完毕,需要转入下一代群体。
    交叉率 PcP_c 就是参加交叉运算的染色体个数占全体染色体总数的比例,记为Pc,取值范围一般为0.4~0.99。
    变异率 PmP_m 是指发生变异的基因位数所占全体染色体的基因总位数的比例,记为Pm,取值范围一般为0.0001~0.1。
    复制概率 PtP_t 用于控制复制与淘汰的个体数目。

    遗传算法主要执行以下四步:
    (1)随机地建立由字符串组成的初始群体;
    (2)计算各个体的适应度;
    (3)根据遗传概率,利用下述操作产生新群体:

    a. 复制。将已有的优良个体复制后添入新群体中,删除劣质个体;
    b. 交换。将选出的两个个体进行交换,所产生的新个体添入新群体中。
    c.突变。随机地改变某一个体的某个字符后添入新群体中。

    (4)反复执行(2)、(3)后,一旦达到终止条件,选择最佳个体作为遗传算法的结果。

    3.算法示例

    求f(x) = x2x^2 极大值问题,设自变量 x 介于0~31,求其二次函数的最大值,即:max f(x) = x2x^2, x∈ [0, 31]

    (1)编码
    遗传算法首先要对实际问题进行编码,用字符串表达问题。这种字符串相当于遗传学中的染色体。每一代所产生的字符串个体总和称为群体。为了实现的方便,通常字符串长度固定,字符选0或1。
    本例中,利用5位二进制数表示x值,采用随机产生的方法,假设得出拥有四个个体的初始群体,即:01101,11000,01000,10011。x值相应为13,24,8,19。
    在这里插入图片描述
    (2)计算适应度
    衡量字符串(染色体)好坏的指标是适应度,它也就是遗传算法的目标函数。本例中用x2x^2计算。
    在这里插入图片描述
    表中还列出了当前适应度的总和f(xi)∑f(x_i)及平均值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]这个区间

    1. 首先将二进制数按权展开:029+028+027+126+025+024+023+022+021+120=650* 2^9+0*2^8+0*2^7+1*2^6+0*2^5+0*2^4+0*2^3+0*2^2+0*2^1+1*2^0=65
    2. 然后将其压缩到区间[0,1]:65/(2101)0.063538665/(2^{10} - 1) \approx0.0635386
    3. 最后将[0,1]区间的数映射到我们想要的区间[1,3]:0.063538631+11.127077220.0635386*(3-1)+ 1\approx1.12707722,可以看出规律为:num * (high-low)+low 其中num为[0,1]之间的数对应此处的0.0635386,high和low表示我们想要映射的区间的上边界和下边界,分别对应此处的3和1。

    现在再来看看编码过程。不难看出上面我们的DNA(二进制串)长为10,10位二进制可以表示2102^{10}种不同的状态,可以看成是将最后要转化为的十进制区间 [ 1 , 3 ] 切分成2102^{10}份。可看出,如果我们增加二进制串的长度,那么我们对区间的切分可以更加精细,转化后的十进制解也更加精确。所以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]
    
    
    def F(x, y):
        return 100.0 * (y - x ** 2.0) ** 2.0 + (1 - x) ** 2.0  # 以香蕉函数为例
    
    
    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, cmap=cm.coolwarm)
        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)  # 随机产生一个实数,代表要变异基因的位置
            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.remove()
            sca = ax.scatter(x, y, F(x, y), c='black', marker='o')
            plt.show()
            plt.pause(0.1)
            pop = np.array(crossover_and_mutation(pop, CROSSOVER_RATE))
            fitness = get_fitness(pop)
            pop = select(pop, fitness)  # 选择生成新的种群
    
        print_info(pop)
        plt.ioff()
        plot_3d(ax)
    
    

    在这里插入图片描述
    在这里插入图片描述

    该部分参考链接:
    https://blog.csdn.net/ha_ha_ha233/article/details/91364937

    5.算法应用

    1.若只有选择和交叉,而没有变异,则无法在初始基因组合以外的空间进行搜索,使进化过程在早期就陷入局部解而进入终止过程,从而影响解的质量。为了在尽可能大的空间中获得质量较高的优化解,必须采用变异操作。

    2.交叉率的取值范围:一般为0.4~0.99,变异率的取值范围:一般为0.0001~0.1

    3.终止条件
    第一种:迭代次数
    第二种:当目标函数是方差这一类有最优目标值的问题时,可采用控制偏差的方法实现终止。一旦遗传算法得出的目标函数值(适应度)与实际目标值之差小于允许值后,算法终止。
    第三种:检查适应度的变化。在遗传算法后期,一旦最优个体的适应度没有变化或变化很小时,即令计算终止。

    4.遗传算法的另一个重要参数是每代群体中的个体数。很明显,个体数目越多,搜索范围越广,容易获取全局最优解。然而个体数目太多,每次迭代时间也长。通常,个体数目可取100-1000之间。

    5.应用领域
    (1)函数优化
    函数优化是遗传算法的经典应用领域,也是遗传算法进行性能评价的常用算例。尤其是对非线性、多模型、多目标的函数优化问题,采用其他优化方法较难求解,而遗传算法却可以得到较好的结果。
    (2)组合优化。
    随着问题的增大,组合优化问题的搜索空间也急剧扩大,采用传统的优化方法很难得到最优解。遗传算法是寻求这种满意解的最佳工具。例如,遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用.
    (3)生产调度问题
    在很多情况下,采用建立数学模型的方法难以对生产调度问题进行精确求解。在现实生产中多采用一些经验进行调度。遗传算法是解决复杂调度问题的有效工具,在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。
    (4)自动控制。
    在自动控制领域中有很多与优化相关的问题需要求解,遗传算法已经在其中得到了初步的应用。例如,利用遗传算法进行控制器参数的优化、基于遗传算法的模糊控制规则的学习、基于遗传算法的参数辨识、基于遗传算法的神经网络结构的优化和权值学习等。
    (5)机器人
    例如,遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人结构优化和行为协调等方面得到研究和应用。
    (6)图像处理
    遗传算法可用于图像处理过程中的扫描、特征提取、图像分割等的优化计算。目前遗传算法已经在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。

    .6.遗传算法的基本特征
    (1)智能式搜索
    遗传算法的搜索策略,既不是盲目式的乱搜索,也不是穷举式的全面搜索,它是有指导的搜索。指导遗传算法执行搜索的依据是适应度,也就是它的目标函数。利用适应度,使遗传算法逐步逼近目标值。
    (2)渐进式优化
    遗传算法利用复制、交换、突变等操作,使新一代的结果优越于旧一代,通过不断迭代,逐渐得出最优的结果,它是一种反复迭代的过程。
    (3)全局最优解
    遗传算法由于采用交换、突变等操作,产生新的个体,扩大了搜索范围,使得搜索得到的优化结果是全局最优解而不是局部最优解。
    (4)黑箱式结构
    遗传算法根据所解决问题的特性,进行编码和选择适应度。一旦完成字符串和适应度的表达,其余的复制、交换、突变等操作都可按常规手续执行。个体的编码如同输入,适应度如同输出。因此遗传算法从某种意义上讲是一种只考虑输入与输出关系的黑箱问题。
    (5)通用性强
    传统的优化算法,需要将所解决的问题用数学式子表示,常常要求解该数学函数的一阶导数或二阶导数。采用遗传算法,只用编码及适应度表示问题,并不要求明确的数学方程及导数表达式。因此,遗传算法通用性强,可应用于离散问题及函数关系不明确的复杂问题,有人称遗传算法是一种框架型算法,它只有一些简单的原则要求,在实施过程中可以赋予更多的含义。
    (6)并行式算法
    遗传算法是从初始群体出发,经过复制、交换、突变等操作,产生一组新的群体。每次迭代计算,都是针对一组个体同时进行,而不是针对某个个体进行。因此,尽管遗传算法是一种搜索算法,但是由于采用这种并行机理,搜索速度很高。这种并行式计算是遗传算法的一个重要特征。

    展开全文
  • python实现的遗传算法的一个实例 求函数f x 10 sin 5x + 7 cos 4x 0 < x < 10的最大值
  • 遗传算法详解 附python代码实现

    万次阅读 多人点赞 2019-06-10 11:14:59
    遗传算法 遗传算法是用于解决最优化问题的一种搜索算法。从名字来看,遗传算法借用了生物学里达尔文的进化理论:”适者生存,不适者淘汰“,将该理论以算法的形式表现出来就是遗传算法的过程。 问题引入 上面提到...

    遗传算法

    遗传算法是用于解决最优化问题的一种搜索算法。从名字来看,遗传算法借用了生物学里达尔文的进化理论:”适者生存,不适者淘汰“,将该理论以算法的形式表现出来就是遗传算法的过程。

    问题引入

    上面提到遗传算法是用来解决最优化问题的,下面我将以求二元函数:

    def F(x, y):
    	return 3*(1-x)**2*np.exp(-(x**2)-(y+1)**2)- 10*(x/5 - x**3 - y**5)*np.exp(-x**2-y**2)- 1/3**np.exp(-(x+1)**2 - y**2)
    

    x[3,3],y[3,3]x\in[-3, 3], y\in[-3, 3]范围里的最大值为例子来详细讲解遗传算法的每一步。该函数的图像如下图:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    通过旋转视角可以发现,函数在这个局部的最大值大概在当x0,y1.5x \approx 0,y\approx1.5时,函数值取得最大值,这里的x,yx,y的取值就是我们最后要得到的结果。

    算法详解

    先直观看一下算法过程:

    寻找最小值:

    在这里插入图片描述

    寻找最大值
    在这里插入图片描述

    首先我们生成了200个随机的(x,y)对,将(x, y)坐标对带入要求解的函数F(x,y)中,根据适者生存,我们定义使得函数值F(x,y)越大的(x,y)对越适合环境,从而这些适应环境的(x,y)对更有可能被保留下来,而那些不适应该环境的(x,y)则有很大几率被淘汰,保留下来的点经过繁殖产生新的点,如此进化下去最后留下的大部分点都是试应环境的点,即在最高点附近。下图为算法执行结果,和上面的分析x0,y1.5x \approx 0,y\approx1.5相近。

    在这里插入图片描述

    种群和个体的概念

    遗传算法启发自进化理论,而我们知道进化是由种群为单位的,种群是什么呢?维基百科上解释为:在生物学上,是在一定空间范围内同时生活着的同种生物的全部个体。显然要想理解种群的概念,又先得理解个体的概念,在遗传算法里,个体通常为某个问题的一个解,并且该解在计算机中被编码为一个向量表示! 我们的例子中要求最大值,所以该问题的解为一组可能的(x,y)(x, y)的取值。比如(x=2.1,y=0.8),(x=1.5,y=2.3)...(x=2.1,y=0.8), (x=-1.5, y=2.3)...就是求最大值问题的一个可能解,也就是遗传算法里的个体,把这样的一组一组的可能解的集合就叫做种群 ,比如在这个问题中设置100个这样的x,yx,y的可能的取值对,这100个个体就构成了种群。

    编码、解码与染色体的概念

    在上面个体概念里提到个体(也就是一组可能解)在计算机程序中被编码为一个向量表示,而在我们这个问题中,个体是x,yx,y的取值,是两个实数,所以问题就可以转化为如何将实数编码为一个向量表示,可能有些朋友有疑惑,实数在计算机里不是可以直接存储吗,为什么需要编码呢?这里编码是为了后续操作(交叉和变异)的方便。实数如何编码为向量这个问题找了很多博客,写的都是很不清楚,看了莫烦python的教学代码,终于明白了一种实数编码、解码的方式。


    生物的DNA有四种碱基对,分别是ACGT,DNA的编码可以看作是DNA上碱基对的不同排列,不同的排列使得基因的表现出来的性状也不同(如单眼皮双眼皮)。在计算机中,我们可以模仿这种编码,但是碱基对的种类只有两种,分别是0,1。只要我们能够将不同的实数表示成不同的0,1二进制串表示就完成了编码,也就是说其实我们并不需要去了解一个实数对应的二进制具体是多少,我们只需要保证有一个映射
    y=f(x),x is decimal system,y is binary system y=f(x), x \ is\ decimal \ system, y \ is \ binary\ system
    能够将十进制的数编码为二进制即可,至于这个映射是什么,其实可以不必关心。将个体(可能解)编码后的二进制串叫做染色体染色体(或者有人叫DNA)就是个体(可能解)的二进制编码表示。为什么可以不必关心映射f(x)f(x)呢?因为其实我们在程序中操纵的都是二进制串,而二进制串生成时可以随机生成,如:

    #pop表示种群矩阵,一行表示一个二进制编码表示的DNA,矩阵的行数为种群数目,DNA_SIZE为编码长度,不理解乘2的看后文
    pop = np.random.randint(2, size=(POP_SIZE, DNA_SIZE*2)) #matrix (POP_SIZE, DNA_SIZE*2)
    

    实际上是没有需求需要将一个十进制数转化为一个二进制数,而在最后我们肯定要将编码后的二进制串转换为我们理解的十进制串,所以我们需要的是y=f(x)y=f(x)逆映射,也就是将二进制转化为十进制,这个过程叫做解码(很重要,感觉初学者不容易理解),理解了解码编码还难吗?先看具体的解码过程如下。

    首先我们限制二进制串的长度为10(长度自己指定即可,越长精度越高),例如我们有一个二进制串(在程序中用数组存储即可)
    [0,1,0,1,1,1,0,1,0,1] [0,1,0,1,1,1,0,1,0,1]
    ,这个二进制串如何转化为实数呢?不要忘记我们的x,y[3,3]x,y\in[-3,3]这个限制,我们目标是求一个逆映射将这个二进制串映射到x,y[3,3]x,y\in[-3,3]即可,为了更一般化我们将x,yx,y的取值范围用一个变量表示,在程序中可以用python语言写到:

    X_BOUND = [-3, 3] #x取值范围
    Y_BOUND = [-3, 3] #y取值范围
    

    为将二进制串映射到指定范围,首先先将二进制串按权展开,将二进制数转化为十进制数,我们有029+128+027+...+020+120=3730*2^9+1*2^8+0*2^7+...+0*2^0+1*2^0=373,然后将转换后的实数压缩到[0,1][0,1]之间的一个小数373/21010.36461388074373 / (2^{10}-1) \approx 0.36461388074,通过以上这些步骤所有二进制串表示都可以转换为[0,1][0,1]之间的小数,现在只需要将[0,1][0,1] 区间内的数映射到我们要的区间即可。假设区间[0,1][0,1]内的数称为num,转换在python语言中可以写成:

    #X_BOUND,Y_BOUND是x,y的取值范围 X_BOUND = [-3, 3], Y_BOUND = [-3, 3],
    x_ = num * (X_BOUND[1] - X_BOUND[0]) + X_BOUND[0] #映射为x范围内的数
    y_ = num * (Y_BOUND[1] - Y_BOUND[0]) + Y_BOUND[0] #映射为y范围内的数
    

    通过以上这些标记为蓝色的步骤我们完成了将一个二进制串映射到指定范围内的任务(解码)。

    现在再来看看编码过程。不难看出上面我们的DNA(二进制串)长为10,10位二进制可以表示2102^{10}种不同的状态,可以看成是将最后要转化为的十进制区间x,y[3,3]x,y\in[-3,3](下面讨论都时转化到这个区间)切分成2102^{10},显而易见,如果我们增加二进制串的长度,那么我们对区间的切分可以更加精细,转化后的十进制解也更加精确。例如,十位二进制全1按权展开为1023,最后映射到[-3, 3]区间时为3,而1111111110(前面9个1)按权展开为1022,1022/(2101)0.9990221022/(2^{10}-1) \approx 0.9990220.999022(3(3))+(3)2.9941340.999022*(3 - (-3)) + (-3)\approx2.994134;如果我们将实数编码为12位二进制,111111111111(12个1)最后转化为3,而111111111110(前面11个1)按权展开为4094,4094/(2121=4095)0.9997564094/(2^{12}-1=4095)\approx0.9997560.999755(3(3))+(3)2.9985340.999755*(3-(-3))+(-3)\approx2.998534;而32.994134=0.0058663-2.994134=0.00586632.998534=0.0014663-2.998534=0.001466,可以看出用10位二进制编码划分区间后,每个二进制状态改变对应的实数大约改变0.005866,而用12位二进制编码这个数字下降到0.001466,所以DNA长度越长,解码为10进制的实数越精确。

    以下为解码过程的python代码:

    这里我设置DNA_SIZE=24(一个实数DNA长度),两个实数x,yx,y一共用48位二进制编码,我同时将x和y编码到同一个48位的二进制串里,每一个变量用24位表示,奇数24列为x的编码表示,偶数24列为y的编码表示。

    def translateDNA(pop):#pop表示种群矩阵,一行表示一个二进制编码表示的DNA,矩阵的行数为种群数目
    	x_pop = pop[:,1::2]#奇数列表示X
    	y_pop = pop[:,::2] #偶数列表示y
        #pop:(POP_SIZE,DNA_SIZE)*(DNA_SIZE,1) --> (POP_SIZE,1)完成解码
        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
    

    适应度和选择

    我们已经得到了一个种群,现在要根据适者生存规则把优秀的个体保存下来,同时淘汰掉那些不适应环境的个体。现在摆在我们面前的问题是如何评价一个个体对环境的适应度?在我们的求最大值的问题中可以直接用可能解(个体)对应的函数的函数值的大小来评估,这样可能解对应的函数值越大越有可能被保留下来,以求解上面定义的函数F的最大值为例,python代码如下:

    def get_fitness(pop): 
        x,y = translateDNA(pop)
    	pred = F(x, y)
    	return (pred - np.min(pred)) + 1e-3 #减去最小的适应度是为了防止适应度出现负数,通过这一步fitness的范围为[0, np.max(pred)-np.min(pred)],最后在加上一个很小的数防止出现为0的适应度
    

    pred是将可能解带入函数F中得到的预测值,因为后面的选择过程需要根据个体适应度确定每个个体被保留下来的概率,而概率不能是负值,所以减去预测中的最小值把适应度值的最小区间提升到从0开始,但是如果适应度为0,其对应的概率也为0,表示该个体不可能在选择中保留下来,这不符合算法思想,遗传算法不绝对否定谁也不绝对肯定谁,所以最后加上了一个很小的正数。

    有了求最大值的适应度函数求最小值适应度函数也就容易了,python代码如下:

    def get_fitness(pop): 
    	x,y = translateDNA(pop)
    	pred = F(x, y)
    	return -(pred - np.max(pred)) + 1e-3
    

    因为根据适者生存规则在求最小值问题上,函数值越小的可能解对应的适应度应该越大,同时适应度也不能为负值,先将适应度减去最大预测值,将适应度可能取值区间压缩为[np.min(pred)np.max(pred),0][np.min(pred)-np.max(pred), 0],然后添加个负号将适应度变为正数,同理为了不出现0,最后在加上一个很小的正数。

    有了评估的适应度函数,下面可以根据适者生存法则将优秀者保留下来了。选择则是根据新个体的适应度进行,但同时不意味着完全以适应度高低为导向(选择top k个适应度最高的个体,容易陷入局部最优解),因为单纯选择适应度高的个体将可能导致算法快速收敛到局部最优解而非全局最优解,我们称之为早熟。作为折中,遗传算法依据原则:适应度越高,被选择的机会越高,而适应度低的,被选择的机会就低。 在python中可以写做:

    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]
    

    不熟悉numpy的朋友可以查阅一下这个函数,主要是使用了choice里的最后一个参数p,参数p描述了从np.arange(POP_SIZE)里选择每一个元素的概率,概率越高约有可能被选中,最后返回被选中的个体即可。

    交叉、变异

    通过选择我们得到了当前看来“还不错的基因”,但是这并不是最好的基因,我们需要通过繁殖后代(包含有交叉+变异过程)来产生比当前更好的基因,但是繁殖后代并不能保证每个后代个体的基因都比上一代优秀,这时需要继续通过选择过程来让试应环境的个体保留下来,从而完成进化,不断迭代上面这个过程种群中的个体就会一步一步地进化。

    具体地繁殖后代过程包括交叉和变异两步。交叉是指每一个个体是由父亲和母亲两个个体繁殖产生,子代个体的DNA(二进制串)获得了一半父亲的DNA,一半母亲的DNA,但是这里的一半并不是真正的一半,这个位置叫做交配点,是随机产生的,可以是染色体的任意位置。通过交叉子代获得了一半来自父亲一半来自母亲的DNA,但是子代自身可能发生变异,使得其DNA即不来自父亲,也不来自母亲,在某个位置上发生随机改变,通常就是改变DNA的一个二进制位(0变到1,或者1变到0)。

    需要说明的是交叉和变异不是必然发生,而是有一定概率发生。先考虑交叉,最坏情况,交叉产生的子代的DNA都比父代要差(这样算法有可能朝着优化的反方向进行,不收敛),如果交叉是有一定概率不发生,那么就能保证子代有一部分基因和当前这一代基因水平一样;而变异本质上是让算法跳出局部最优解,如果变异时常发生,或发生概率太大,那么算法到了最优解时还会不稳定。交叉概率,范围一般是0.6~1,突变常数(又称为变异概率),通常是0.1或者更小。

    python实现如下:

    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)	#随机产生一个实数,代表要变异基因的位置
    		child[mutate_point] = child[mutate_point]^1 	#将变异点的二进制为反转
    

    上面这些步骤即为遗传算法的核心模块,将这些模块在主函数中迭代起来,让种群去进化

    	pop = np.random.randint(2, size=(POP_SIZE, DNA_SIZE*2)) #生成种群 matrix (POP_SIZE, DNA_SIZE)
    	for _ in range(N_GENERATIONS):	#种群迭代进化N_GENERATIONS代
    		crossover_and_mutation(pop, CROSSOVER_RATE)	#种群通过交叉变异产生后代
    		fitness = get_fitness(pop)	#对种群中的每个个体进行评估
    		pop = select(pop, fitness) 	#选择生成新的种群
    

    附录

    完整代码

    
    import numpy as np
    import matplotlib.pyplot as plt
    from matplotlib import cm
    from mpl_toolkits.mplot3d import Axes3D
    
    DNA_SIZE = 24
    POP_SIZE = 200
    CROSSOVER_RATE = 0.8
    MUTATION_RATE = 0.005
    N_GENERATIONS = 50
    X_BOUND = [-3, 3]
    Y_BOUND = [-3, 3]
    
    
    def F(x, y):
    	return 3*(1-x)**2*np.exp(-(x**2)-(y+1)**2)- 10*(x/5 - x**3 - y**5)*np.exp(-x**2-y**2)- 1/3**np.exp(-(x+1)**2 - y**2)
    
    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,cmap=cm.coolwarm)
    	ax.set_zlim(-10,10)
    	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 - np.min(pred)) + 1e-3 #减去最小的适应度是为了防止适应度出现负数,通过这一步fitness的范围为[0, np.max(pred)-np.min(pred)],最后在加上一个很小的数防止出现为0的适应度
    
    
    def translateDNA(pop): #pop表示种群矩阵,一行表示一个二进制编码表示的DNA,矩阵的行数为种群数目
    	x_pop = pop[:,1::2]#奇数列表示X
    	y_pop = pop[:,::2] #偶数列表示y
    	
    	#pop:(POP_SIZE,DNA_SIZE)*(DNA_SIZE,1) --> (POP_SIZE,1)
    	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]))
    
    
    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.remove()
    		sca = ax.scatter(x, y, F(x,y), c='black', marker='o');plt.show();plt.pause(0.1)
    		pop = np.array(crossover_and_mutation(pop, CROSSOVER_RATE))
    		#F_values = F(translateDNA(pop)[0], translateDNA(pop)[1])#x, y --> Z matrix
    		fitness = get_fitness(pop)
    		pop = select(pop, fitness) #选择生成新的种群
    	
    	print_info(pop)
    	plt.ioff()
    	plot_3d(ax)
    
    展开全文
  • 遗传算法劫介绍和遗传算法python实现文章目录: Reference: 1、https://morvanzhou.github.io/tutorials/machine-learning/evolutionary-algorithm/2-01-genetic-algorithm/ 2、...
  • python使用遗传算法 遗传算法概述: (Outline of a Genetic Algorithm:) A genetic algorithm is: 遗传算法是: “A technique in artificial intelligence that uses the ideas of genetic mutation, ...
  • 遗传算法Python实现

    2018-05-10 16:24:39
    自己对遗传算法的理解以及【Python】的实现,希望对你们有所帮助
  • 简介遗传算法(Genetic Algorithm)顾名思义,是一种基于自然选择原理和自然遗传机制的启发式搜索算法。该算法通过模拟自然界中生物遗传进化的自然机制(选择、交叉和变异操作),将好的遗传基因(最优目标)不断...
  • 遗传算法实例解析(python

    千次阅读 2019-10-20 19:43:52
    遗传算法(Genetic Algorithm, GA)是模拟达尔文生物进化论的自然选择和遗传机理的生物学进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。 遗传算法以一种群体中的所有个体为对象,并利用随机化...
  • Python遗传算法代码实例讲解

    千次阅读 2018-12-18 14:54:36
    求解函数的最大值y=xsin(10x)+xsin(2x),自变量取值:0--5,用Python画出的图像如下 (注:此代码好像有一些感觉不对的地方,首先:没有保留那些适应度低的个体 pop = select(pop, fitness) '''这一行代码,压根...
  • 2.4 算法验证采用 Matlab 2010b编写求解 TSP 问题的遗传算法,并选用 TSPLIB测试库实例dantzig42进行测试,该实例中的城市数量为42个,要求规划旅行商的城市路线,最后回到出发城市,使旅行商行驶路程最短。...
  • 遗传算法——Python

    2018-10-30 15:44:00
    遗传算法 遗传算法 ( GA , Genetic Algorithm ) ,也称进化算法 。 遗传算法是受达尔文的进化论的启发,借鉴生物进化过程而提出的一种启发式搜索算法。因此在介绍遗传算法前有必要简单的介绍生物进化知识。 一....
  • 本文章用Python实现了基本的优化遗传算法并用类进行了封装一、遗传算法概述遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索...
  • 睿智的智能优化算法2——遗传算法python实现什么是遗传算法求解过程整体代码分解1、编码解码部分2、求取适应度部分3、自然选择部分4、组合交叉5、基因突变实现代码GITHUB下载连接 睿智的智能优化算法小课堂再次...
  • 用于遗传算法python 3库 例子 寻找世界 import string import random import genetics letters = string . ascii_uppercase + string . ascii_lowercase + string . punctuation + ' ' solution = 'Hello World!' ...
  • 遗传算法(Python) #4 DEAP框架入门 1. DEAP框架简介 DEAP(Distributed Evolutionary Algorithms in Python)是一个热门的Python进化算法框架,我们可以用这个框架在Python内实现遗传算法的应用,本文将介绍DEAP中主要...
  • 遗传算法Python版,可外部注册适应度函数(通过@装饰器)
  • 前言最近需要用到遗传算法来优化一些东西,最初是打算直接基于某些算法实现一个简单的函数来优化,但是感觉单纯写个非通用的函数运行后期改进算子或者别人使用起来都会带来困难,同时遗传算法基本概念和运行流程相对...
  • 遗传算法-原理+实例+Python实现

    千次阅读 2019-10-07 21:06:30
    遗传算法求解最优化问题。
  • 基于遗传算法的图像分割python实现,包含例子和源代码
  • 吉吉:(I)实现功能求解函数 f(x) = x + 10*sin(5*x) + 7*cos(4*x) 在区间[0, 9] 的最大值;(II)代码:#求解函数 f(x) = x + 10*sin(5*x) + 7*cos(4*x) 在区间[0,9]的最大值。import mathimport randomclass GA()...
  • python实现遗传算法

    2020-10-26 22:49:01
    最近事情比较多,一个月没有写公众号了,但也积累了些不错的内容可以分享,今天就给大家介绍的是遗传算法,并用python加以实现。 在遗传算法的学习过程中,在CSDN上看到一篇已有人分享的python代码,因此直接借鉴...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,076
精华内容 1,230
关键字:

遗传算法python实例

python 订阅