在非线性函数的最优化问题中,梯度下降之类的爬山法,常常会陷入局部最优解,因为爬山法只对“邻近”的点作比较，所以目光比较“短浅”,所以诞生出许多元启发算法,其中比较著名的有受到金属热加工启发创造的模拟退火算法和受到生物进化启发创造的遗传算法等.本文来介绍一下遗传算法.

遗传一词来源于生物学的基因遗传,如果把进化比作一个非线性函数,那么它一定有非常多的局部最优解,生物进化好比在寻找个体基因的最优解,大自然通过自然选择的方式让优秀的基因繁衍生息,杀死不适合生存的基因,最终生物进化成为了一个复杂的物种,大多数个体在最优解上.

遗传算法算法的思想和过程与生物进化的思想一致,只不过这里的基因突变,基因交换等都是我们人为制造的.而自然选择过程则是符合我们要求的留下,与预期相差太远的则杀死.

遗传算法实例

拿一个例子来说,求解函数

在区间[0,10]的最大值。这个函数大概长这样：

首先我们来设计基因,其实基因就是x的值,基因突变就相当于x值随机变化,从而有可能找到最优解.我们用10位的二级制数来代表基因,这相当于将[0,10]这个区间分成了个点,每个基因代表其中的一个点,我们期望通过进化来获取最好的基因.

生物界的基因通过两性交配的方式使基因多样化,为了模拟这个过程,我们也随机选取一对个体,以一定概率交换他们的某个基因.生物还有基因突变的特性,我们也随机选取某个个体,然后随机改变他的某个基因.

自然选择是优胜劣汰的过程,适应环境的的以繁衍,不适应环境的就会死亡,我们以适应度较高的个体替换适应度较低的个体,这样来模拟自然选择的过程.其中适应度就是函数值的大小,不过适应度不可以有负数,所以我们用每个点的函数值减掉最小值得到适应度.

import numpy as np
import matplotlib.pyplot as plt

DNA_SIZE = 10            # DNA长度
POP_SIZE = 100           # 人口数量
CROSS_RATE = 0.8         # 基因交换率
MUTATION_RATE = 0.003    # 变异率
N_GENERATIONS = 100      # 迭代次数
X_BOUND = [0, 10]        # x取值范围


# 需要找全局最优点的函数
def F(x):
    return x + 10*np.sin(5*x) + 7*np.cos(4*x)

# 适应度函数,越高适应度越大
def get_fitness(pred):
    return pred + 1e-3 - np.min(pred)


# 将二进制DNA转换为十进制
def translateDNA(pop):
    return pop.dot(2 ** np.arange(DNA_SIZE)[::-1]) / float(2**DNA_SIZE-1) * X_BOUND[1]

# 自然选择
def select(pop, fitness):
    idx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, p=fitness/fitness.sum())
    return pop[idx]

# 进行交叉
def crossover(person, 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)
        # 交换
        person[cross_points], pop[i_, cross_points] = pop[i_, cross_points], person[cross_points]

# 突变
def mutate(person):
    for point in range(DNA_SIZE):
        if np.random.rand() < MUTATION_RATE:
            person[point] = 1 if person[point] == 0 else 0

# 初始化基因
pop = np.random.randint(2, size=(POP_SIZE, DNA_SIZE))

# 开始迭代
for _ in range(N_GENERATIONS):
    # 计算函数值
    F_values = F(translateDNA(pop))
    # 计算适应度
    fitness = get_fitness(F_values)
    # 打印适应度最大的值
    best = translateDNA(pop[np.argmax(fitness), :])
    #print(best)
    # 自然选择
    pop = select(pop, fitness)
    # 交叉与进化
    for person in pop:
        # 交叉
        crossover(person, pop)
        # 突变
        mutate(person)


x = np.linspace(*X_BOUND, 200)
plt.plot(x, F(x))
plt.scatter(best,F(best),c='r')
plt.show()

遗传算法

遗传算法实例

发表评论