利用 Python 实现 遗传算法（GeneticAlgorithm）

悠扬的幻想天空 - 博客

December 10, 2018 日常 • 作者：悠扬

要求：

题目

核心代码：

1、生成初代

我采用的是2进制来表示染色体，先随机出一堆0和1的列表

def getFisrtGroup(group_size, chrom_length):
    group = []
    for i in range(group_size):
        temp = []
        for j in range(chrom_length):
            temp.append(random.randint(0, 1))
        group.append(temp)
    return group

2、GA循环

for i in range(generation):
    obj_value = calobjValue(group, chrom_length, max_value, min_value, divid)   # 个体评价
    fit_value = calfitValue(obj_value)  # 获取群体适应值
    best_individual, best_fit = best(group, fit_value)  # 返回最优基因, 最优适应值
    if( abs(f(xx)+186.730909) < 0.000001):#找到最优解
    
    crossover(group, fit_value, pc) # 交配
    mutation(group, pm) # 变异

3、解码

div代表每个参数的开始位置和末尾位置，方便分隔参数。这个函数会返回一个包含参数的列表。

'''
b 染色体
chrom_length 染色体长度
max_value，min_value 最大最小值
div 分割
'''
def b2d(b, chrom_length, max_value, min_value, div):
    rwno = []
    for i in range(len(div)):
        。。。
        for j in range(star, end):
            t += b[j] * (math.pow(2, j - star))
        t = t * max_value / (math.pow(2, end - star + 1) - 1) - min_value
        rwno.append(t)
    return rwno

5、获取适应值

因为都是求函数最小值，所以我用的是e^(-x)这个函数来表示适应值，当计算结果减去预估的最小值，结果越逼近1就代表计算结果离最小值越近。

e^-x

#适应函数
def s(x):
    return math.exp(-abs(x-1))

6、选择交叉方案

我用的是轮盘选择，先求出每个子代的适应值的占比，然后把它们按它的占比分在[0, 1]的区间上面，随机出0到1的随机数，看看这个随机数落在谁的上面。

# 转轮盘选择法
def selection(group, fit_value):
    newfit_value = [] #[ [[染色体], [锚点]],... ]
    newgroup = [] #[ [父], [母], [父], [母],....]
    # 适应度总和
    total_fit = sum_fit(fit_value)
    # 设置各个的锚点
    t = 0
    for i in range(len(group)):
        t += fit_value[i]/total_fit
        newfit_value.append([group[i], t])
    # 转轮盘选择法
    for i in range(len(newfit_value)):
        parents = len(newfit_value) # 初始化指针
        r = random.random() #指针
        for j in range(len(newfit_value)):#看看指针指到睡了
            if newfit_value[j][1] > r:
                parents = j
                break
        newgroup.append(newfit_value[parents][0])
        
    return newgroup

7、交配

先用上面的轮盘选出一堆父代母代，然后开始交叉。

def crossover(group, fit_value, pc):
    parents_group = selection(group, fit_value) #[ [[父], [母]],....]
    group_len = len(parents_group)
    for i in range(0, group_len, 2):
        if(random.random() < pc): # 看看是否要交配
            cpoint = random.randint(0, len(parents_group[0])) # 随机交叉点
            。。。

∞、繁衍

继续重复计算适应值→选择→交配的过程模拟物竞天择适者生存的遗传算法，直到推衍出想要的结果。

计算结果：

generation = 1000    # 繁衍代数
group_size = 2000     # 染色体数量，偶数
chrom_length = 500   # 染色体长度

结果

找出两个最优解：

[2.3566456537597764, 2.3564076733830963]
[0.7849757859540485, 2.3563759723412123]

精确到小数点后六位：

F(x) = 1.0000002663624468
x = [0.7851439319246674, 2.356238727907994]
染色体 = [0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1,1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1,0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1]
适应值 = 0.9999997336375888
代数 = 839

在839代时候出现想要的精确到小数点后6位的解。

最后

感觉遗传算法挺玄学的，开局一串随机数，全靠变异，还容易陷入局部最优解的状况。如果有大致函数图像，可以尝试把初代种群洒在一个全局最优解的附近，这样开局就是高富帅了。变异几率高的话的确可以很快把适应值拉上去，但达到顶峰的时候会有更大的波动，很难得到想要的答案，每次快接近的时候就被一个变异给甩出去了。但是变异几率不高可能好多代都在原地踏步，我想到的解决方案就是，一开始变异几率高，先把适应值升高到一定程度之后，在把变异几率给调下来，这样就可以稍稍解决刚才说到的起步慢、波动大的两个问题。还有就是如果检测到发现自己陷入局部最优解（或者说长期适应值不增长），可以再次把变异几率调高来逃脱。如果染色体数量太多，会拖慢适应改变速度，染色体长度同理，交配几率的影响大概和变异几率一样吧。

Github：https://github.com/izoyo/Python-GeneticAlgorithm

添加新评论