当前位置:   article > 正文

遗传算法(GA)学习 || 原理、本质、代码、例题_基因遗传算法怎么学

基因遗传算法怎么学


写在前面:周日和工作任务如期而至,虽然我的研究课题已经离开了水文要素预测,but老板派的活儿还是水位预测,ohnonono真累!

1 一些入门的概念

  1. 计算机上模拟生物的进化过程和基因选择的操作(选择、交叉、变异)。主要的目的就是借助与自然界的适应过程,来更好的进行人工系统的设计。
  2. 基本思想:从初始种群出发,采用优胜劣汰、适者生存的规则选择个体,并通过杂交、变异来产生新一代种群,如此逐渐进化,直到满足目标为止。

1.1 术语介绍

  • 种群(Population):种群是指用遗传算法求解问题时, 初始给定的多个解的集合。遗传算法的求解过程是从这个子集开始的。

  • 个体(Individual):个体是指种群中的单个元素,它通常 由一个用于描述其基本遗传结构的数据结构来表示。例如, 可以用0、1组成的长度为1的串来表示个体。

  • 染色体(Chromosome):染色体是指对个体进行编码后 所得到的编码串。染色体中的每1位称为基因,染色体上由 若干个基因构成的一个有效信息段称为基因组。

  • 适应度函数(Fitness)适应度函数是一种用来对种群中 各个个体的环境适应性进行度量的函数。其函数值是遗传 算法实现优胜劣汰的主要依据。【一般采用适应性函数来度量某个解决方案的优劣】

  • 遗传操作(Genetic Operator):遗传操作是指作用于种群而产生新的种群的操作。标准的遗传操作包括以下3种基本形式:
    – 选择(Selection)
    – 杂交(Crosssover)
    – 变异(Mutation)

2 遗传算法的主要步骤

  1. 编码

将问题的候选解用染色体表示,实现解空间向编码空间的映射过程。遗传算法不直接处理解空间的决策变量,而是将其转换成由基因按一定结构组成的染色体。编码方式有很多,如二进制编码、实数向量编码、整数排列编码、通用数据结构编码等等。本文将采用二进制编码的方式,将十进制的变量转换成二进制,用0和1组成的数字串模拟染色体,可以很方便地实现基因交叉、变异等操作。

  1. 种群初始化

产生代表问题可能潜在解集的一个初始群体(编码集合)。种群规模设定主要有以下方面的考虑:从群体多样性方面考虑,群体越大越好,避免陷入局部最优;从计算效率方面考虑,群体规模越大将导致计算量的增加。应该根据实际问题确定种群的规模。产生初始化种群的方法通常有两种:一是完全随机的方法产生;二是根据先验知识设定一组必须满足的条件,然后根据这些条件生成初始样本。

  1. 计算个体适应度

利用适应度函数计算各个个体的适应度大小。适应度函数(Fitness Function)的选取直接影响到遗传算法的收敛速度以及能否找到最优解,因为在进化搜索中基本不利用外部信息,仅以适应度函数为依据,利用种群每个个体的适应程度来指导搜索。

  1. 进化计算

通过选择、交叉、变异,产生出代表新的解集的群体。选择(selection):根据个体适应度大小,按照优胜劣汰的原则,淘汰不合理的个体;交叉(crossover):编码的交叉重组,类似于染色体的交叉重组;变异(mutation):编码按小概率扰动产生的变化,类似于基因突变。

  1. 解码

末代种群中的最优个体经过解码实现从编码空间向解空间的映射,可以作为问题的近似最优解。这是整个遗传算法的最后一步,经过若干次的进化过程,种群中适应度最高的个体代表问题的最优解,但这个最优解还是一个由0和1组成的数字串,要将它转换成十进制才能供我们理解和使用。

3 遗传的本质

(1)交换染色体信息
(2)染色体信息变异

通俗讲解:

父体提供一条染色体,母体提供一条染色体,然后这两条染色体之间进行部分的信息交换,这样就产生了两条新的个体。

这两条新的个体和原来的父体、母体就构成了新的族群。

当然,在交换的过程中,有可能出现信息变异,也就是信息交换中存在一些未知的可能性,可能会让遗传行为向着更有利的方向推进。

也就是说,遗传的本质就是交换信息和信息变异。

然后,再对族群优胜劣汰,防止族群的数量越来越多。

在这里插入图片描述

  • 所以说,需要根据解的情况,来对解进行等长度的表示。对于集合、数组、列表这种解无需变化,但是对于十进制的数,我们可以先转换为二进制的数,方便我们进行染色体的信息变异。
    在这里插入图片描述

4 题目

**加粗样式**

4.1 创建随机解集

(1)创建包含100个解的初始解集
在这里插入图片描述


import random


def create_answer(number_set, n):
    # 创建随机解集,包含n个解,每个解的长度都为10
    result = []
    for i in range(n):
        result.append(random.sample(number_set, 10))
    return result


numbers_set = random.sample(range(0, 1000), 50)  # 从0-1000内随机抽取50个元素
print(numbers_set)
middle_answer = create_answer(numbers_set, 100)
print(middle_answer)

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

4.2 两个解交换信息

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

  • 上面讲到的两种思路,代码实现时采用的是思路2,因为在交换时已经考虑到了优胜劣汰问题。

  • 先写一个计算误差的函数

4.3 代码

import random

def create_answer(numbers_set, n):
    # 创建随机解集,包含n个解,每个解的长度都为10
    result = []
    for i in range(n):
        result.append(random.sample(numbers_set, 10))
    return result


def error_level(new_answer, numbers_set):
    # new_answer 是什么
    error = []
    right_answer = sum(numbers_set)/10  # 表示原数组的十分之一
    for item in new_answer:
        value = abs(right_answer-sum(item))
        if value == 0:
            error.append(10)
        else:
            error.append(1/value)

    return error


def choice_selected(old_answer, numbers_set):
    result = []
    error = error_level(old_answer, numbers_set)
    error_one = [item/sum(error) for item in error]  # 归一化
    for i in range(1, len(error_one)):
        error_one[i] += error_one[i-1]  # 累积求和
    for i in range(len(old_answer)//2):
        temp = []
        for j in range(2):
            rand = random.uniform(0, 1)
            for k in range(len(error_one)):
                if k == 0:
                    if rand < error_one[k]:
                        temp.append(old_answer[k])
                else:
                    if rand >= error_one[k-1] and rand < error_one[k]:
                        temp.append(old_answer[k])
        rand = random.randint(0, 6)
        temp_1 = temp[0][:rand] + temp[1][rand:rand+3] + temp[0][rand+3:]
        temp_2 = temp[1][:rand] + temp[0][rand:rand+3] + temp[1][rand+3:]  # 至此产生了新的两个个体
        result.append(temp_1)
        result.append(temp_2)
    return result


def variation(old_answer, numbers_set, pro):
    for i in range(len(old_answer)):
        rand = random.uniform(0, 1)
        if rand < pro:
            rand_num = random.randint(0, 9)
            old_answer[i] = old_answer[i][:rand_num] + random.sample(numbers_set, 1) + old_answer[i][rand_num+1:]
    return old_answer


numbers_set = random.sample(range(0, 1000), 50)  # 从0-1000内随机抽取50个元素
print(numbers_set)
middle_answer = create_answer(numbers_set, 100)
print(middle_answer)
first_answer = middle_answer[0]
great_answer = []

for i in range(1000):
    middle_answer = choice_selected(middle_answer, numbers_set)
    middle_answer = variation(middle_answer, numbers_set, 0.1)
    error = error_level(middle_answer, numbers_set)
    index = error.index(max(error))  # 选择误差最小的
    great_answer.append([middle_answer[index], error[index]])
great_answer.sort(key=lambda x:x[1], reverse=True)
print("正确答案为", sum(numbers_set)/10)
print("给出的最优解为", great_answer[0][0])
print("该和为", sum(great_answer[0][0]))
print("选择系数为", great_answer[0][1 ])
print("最初解的和为", sum(first_answer))
# print(middle_answer)

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79

4.4 结果

[489, 295, 150, 490, 914, 227, 829, 678, 462, 445, 
268, 260, 590, 542, 877, 980, 200, 267, 969, 161, 
594, 598, 775, 587, 614, 736, 939, 439, 2, 891, 
108, 238, 55, 764, 288, 947, 564, 996, 669, 254, 
738, 588, 578, 817, 116, 525, 790, 153, 782, 977]

原数组的和为:27215,也就是说要找到10个数无限接近2721.5
正确答案为 2721.5
给出的最优解为 [227, 55, 598, 260, 490, 55, 238, 445, 200, 153]
该和为 2721
选择系数为 2.0
最初解的和为 5651
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/683996
推荐阅读
相关标签
  

闽ICP备14008679号