Java教程

计算智能课程设计(遗传算法求解无约束单目标优化问题)

本文主要是介绍计算智能课程设计(遗传算法求解无约束单目标优化问题),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

写在前面

前天写完了基于传递闭包的模糊聚类,今天准备写“遗传算法求解无约束单目标优化问题”。昨天和npy玩了一下午,去齐白石艺术学院看了画展,一起在最高处看了夕阳,并在落日前接吻。

实验题目

遗传算法求解无约束单目标优化问题

实验目的

理解遗传算法原理,掌握遗传算法的基本求解步骤,包括选择、交叉、变异等,学会运用遗传算法求解无约束单目标优化问题。

背景知识

遗传算法(Genetic Algorithm)是借鉴生物界自然选择、适者生存遗传机制的一种随机搜索方法。遗传算法模拟了进化生物学中的遗传、突变、自然选择以及杂交等现象,是进化算法的一种。对于一个最优化问题,一定数量的候选解(每个候选解称为一个个体)的抽象表示(也称为染色体)的种群向更好的方向解进化,通过一代一代不断繁衍,使种群收敛于最适应的环境,从而求得问题的最优解。进化从完全随机选择的个体种群开始,一代一代繁殖、进化。在每一代中,整个种群的每个个体的适应度被评价,从当前种群中随机地选择多个个体(基于它们的适应度),通过自然选择、优胜劣汰和突变产生新的种群,该种群在算法的下一次迭代中成为当前种群。传统上,解一般用二进制表示(0 和 1 组成的串)。遗传算法的主要特点是直接对结构对象进行操作,不存在函数求导、连续、单峰的限定;具有内在的隐闭并行性和更好的全局寻优能力;采用概率化的寻优方法,能自动获取和指导优化搜索,自适应调整搜索方向,不需要确定的规则。遗传算法已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工智能等领域中的问题求解,已成为现代智能计算中的一项关键技术。

关键术语:
(1)个体( individuals):遗传算法中所处理的对象称为个体。个体通常可以含解的编码表示形式、适应度值等构成成分,因而可看成是一个结构整体。其中,主要成分是编码。

(2)种群(population):由个体构成的集合称为种群。

(3)位串(bit string):解的编码表示形式称为位串。解的编码表示可以是 0、1 二值串、0~9 十进制数字串或其他形式的串,可称为字符串或简称为串。位串和染色体(chromosome)相对应。在遗传算法的描述中,经常不加区分地使用位串和染色体这两个概念。位串/染色体与个体的关系:位串/染色体一般是个体的成分,个体还可含有适度值等成分。个体、染色体、位串或字符串有时在遗传算法中可不加区分地使用。

(4)种群规模(population scale):又称种群大小,指种群中所含个体的数目。

(5)基因(gene):位串中的每个位或元素统称为基因。基因反映个体的特征。同一位上的基因不同,个体的特征可能也不相同。基因对应于遗传学中的遗传物质单位。在 DNA 序列表示中,遗传物质单位也是用特定编码表示的。遗传算法中扩展了编码的概念,对于可行解,可用 0、1 二值、0~9 十个数字,以及其他形式的编码表示。例如,在 0、1 二值编码下,有一个串 S=1011,则其中的 1,0,1,1这 4 个元素分别称为基因。基因和位在遗传算法中也可不加区分地使用。

(6)适应度(fitness):个体对环境的适应程度称为适应度(fitness)。为了体现染色体的适应能力,通常引入一个对每个染色体都能进行度量的函数﹐称为适应度函数。

(7)选择(selection):在整个种群或种群的一部分中选择某个个体的操作。

(8)交叉(crossover):两个个体对应的一个或多个基因段的交换操作。

(9)变异(mutation):个体位串上某个基因的取值发生变化。如在 0、1 串表示下,某位的值从 0 变为 1,或由 1 变为 0。

遗传算法的基本流程如下:

本案例意在说明如何使用遗传算法求解无约束单目标优化问题,即求一元函数:

在区间[-1, 2]上的最大值。该函数图像如下:

由图像可知该函数在在区间[-1, 2]上有很多极大值和极小值,对于求其最大值或最小值的问题,很多单点优化的方法(梯度下降等)就不适合,这种情况下可以考虑使用遗传算法。。

示例代码

import numpy as np
import matplotlib.pyplot as plt


def fun(x):
    return x * np.sin(10*np.pi*x) + 2


Xs = np.linspace(-1, 2, 100)

np.random.seed(0)  # 令随机数种子=0,确保每次取得相同的随机数

# 初始化原始种群
population = np.random.uniform(-1, 2, 10)  # 在[-1,2)上以均匀分布生成10个浮点数,做为初始种群

for pop, fit in zip(population, fun(population)):
    print("x=%5.2f, fit=%.2f" % (pop, fit))

plt.plot(Xs, fun(Xs))
plt.plot(population, fun(population), '*')
plt.show()


def encode(population, _min=-1, _max=2, scale=2**18, binary_len=18):  # population必须为float类型,否则精度不能保证
    # 标准化,使所有数据位于0和1之间,乘以scale使得数据间距拉大以便用二进制表示
    normalized_data = (population-_min) / (_max-_min) * scale
    # 转成二进制编码
    binary_data = np.array([np.binary_repr(x, width=binary_len)
                           for x in normalized_data.astype(int)])
    return binary_data


chroms = encode(population)  # 染色体英文(chromosome)


for pop, chrom, fit in zip(population, chroms, fun(population)):
    print("x=%.2f, chrom=%s, fit=%.2f" % (pop, chrom, fit))


def decode(popular_gene, _min=-1, _max=2, scale=2**18):  # 先把x从2进制转换为10进制,表示这是第几份
    # 乘以每份长度(长度/份数),加上起点,最终将一个2进制数,转换为x轴坐标
    return np.array([(int(x, base=2)/scale*3)+_min for x in popular_gene])


fitness = fun(decode(chroms))

for pop, chrom, dechrom, fit in zip(population, chroms, decode(chroms), fitness):
    print("x=%5.2f, chrom=%s, dechrom=%.2f, fit=%.2f" %
          (pop, chrom, dechrom, fit))

fitness = fitness - fitness.min() + 0.000001  # 保证所有的都为正
print(fitness)


def Select_Crossover(chroms, fitness, prob=0.6):  # 选择和交叉
    probs = fitness/np.sum(fitness)  # 各个个体被选择的概率
    probs_cum = np.cumsum(probs)  # 概率累加分布

    each_rand = np.random.uniform(size=len(fitness))  # 得到10个随机数,0到1之间

    # 轮盘赌,根据随机概率选择出新的基因编码
    # 对于each_rand中的每个随机数,找到被轮盘赌中的那个染色体
    newX = np.array([chroms[np.where(probs_cum > rand)[0][0]]
                    for rand in each_rand])

    # 繁殖,随机配对(概率为0.6)
    # 6这个数字怎么来的,根据遗传算法,假设有10个数,交叉概率为0.6,0和1一组,2和3一组。。。8和9一组,每组扔一个0到1之间的数字
    # 这个数字小于0.6就交叉,则平均下来应有三组进行交叉,即6个染色体要进行交叉
    pairs = np.random.permutation(
        int(len(newX)*prob//2*2)).reshape(-1, 2)  # 产生6个随机数,乱排一下,分成二列
    center = len(newX[0])//2  # 交叉方法采用最简单的,中心交叉法
    for i, j in pairs:
        # 在中间位置交叉
        x, y = newX[i], newX[j]
        newX[i] = x[:center] + y[center:]  # newX的元素都是字符串,可以直接用+号拼接
        newX[j] = y[:center] + x[center:]
    return newX


chroms = Select_Crossover(chroms, fitness)

dechroms = decode(chroms)
fitness = fun(dechroms)

for gene, dec, fit in zip(chroms, dechroms, fitness):
    print("chrom=%s, dec=%5.2f, fit=%.2f" % (gene, dec, fit))

# 对比一下选择和交叉之后的结果
fig, (axs1, axs2) = plt.subplots(1, 2, figsize=(14, 5))
axs1.plot(Xs, fun(Xs))
axs1.plot(population, fun(population), 'o')
axs2.plot(Xs, fun(Xs))
axs2.plot(dechroms, fitness, '*')
plt.show()

# 输入一个原始种群1,输出一个变异种群2  函数参数中的冒号是参数的类型建议符,告诉程序员希望传入的实参的类型。函数后面跟着的箭头是函数返回值的类型建议符,用来说明该函数返回的值是什么类型。


def Mutate(chroms: np.array):
    prob = 0.1  # 变异的概率
    clen = len(chroms[0])  # chroms[0]="111101101 000010110"    字符串的长度=18
    m = {'0': '1', '1': '0'}  # m是一个字典,包含两对:第一对0是key而1是value;第二对1是key而0是value
    newchroms = []  # 存放变异后的新种群
    each_prob = np.random.uniform(size=len(chroms))  # 随机10个数

    for i, chrom in enumerate(chroms):  # enumerate的作用是整一个i出来
        if each_prob[i] < prob:  # 如果要进行变异(i的用处在这里)
            pos = np.random.randint(clen)  # 从18个位置随机中找一个位置,假设是7
            # 0~6保持不变,8~17保持不变,仅将7号翻转,即0改为1,1改为0。注意chrom中字符不是1就是0
            chrom = chrom[:pos] + m[chrom[pos]] + chrom[pos+1:]
        newchroms.append(chrom)  # 无论if是否成立,都在newchroms中增加chroms的这个元素
    return np.array(newchroms)  # 返回变异后的种群


newchroms = Mutate(chroms)


def DrawTwoChroms(chroms1, chroms2, fitfun):  # 画2幅图,左边是旧种群,右边是新种群,观察平行的两幅图可以看出有没有差异
    Xs = np.linspace(-1, 2, 100)
    fig, (axs1, axs2) = plt.subplots(1, 2, figsize=(14, 5))
    dechroms = decode(chroms1)
    fitness = fitfun(dechroms)
    axs1.plot(Xs, fitfun(Xs))
    axs1.plot(dechroms, fitness, 'o')

    dechroms = decode(chroms2)
    fitness = fitfun(dechroms)
    axs2.plot(Xs, fitfun(Xs))
    axs2.plot(dechroms, fitness, '*')
    plt.show()


# 对比一下变异前后的结果
DrawTwoChroms(chroms, newchroms, fun)

# 上述代码只是执行了一轮,这里反复迭代
np.random.seed(0)  # 
population = np.random.uniform(-1, 2, 100)  # 这次多找一些点
chroms = encode(population)

for i in range(1000):
    fitness = fun(decode(chroms))
    fitness = fitness - fitness.min() + 0.000001  # 保证所有的都为正
    newchroms = Mutate(Select_Crossover(chroms, fitness))
    if i % 300 == 1:
        DrawTwoChroms(chroms, newchroms, fun)
    chroms = newchroms

DrawTwoChroms(chroms, newchroms, fun)

实验内容

运行和理解示例代码,回答下列问题:
1)代码第 64 行的语义是什么?两个[0]各自代表什么?最后 newX 有几个元素?

newX = np.array([chroms[np.where(probs_cum > rand)[0][0]]

for rand in each_rand])

2)代码第 70 行的语义是什么?为什么要除以 2 再乘以 2?reshape 中的-1 表示什么?

pairs = np.random.permutation(

int(len(newX)*prob//2*2)).reshape(-1, 2) # 产生 6 个随机数乱排一下分成二列

3)请结合 Mutate 函数的内容,详述变异是如何实现的。

4)将代码第 145 行修改为 newchroms = Select_Crossover(chroms, fitness),即不再执行变异,执行结果有什么不同,为什么会出现这种变化?

5)轮盘让个体按概率被选择,对于适应度最高的个体而言,虽然被选择的概率高,但仍有可能被淘汰,从而在进化过程中失去当前最优秀的个体。一种改进方案是,让适应度最高的那个个体不参与选择,而是直接进入下一轮(直接晋级),这种方案被称为精英选择(elitist selection)。请修改Select 部分的代码,实现这一思路。

6)【选做】请借鉴示例代码,实现教材 P57 的例 2.6.1,即用遗传算法求解下列二元函数的最大值。

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

实验结果与分析

第一题

1)代码第 64 行的语义是什么?两个[0]各自代表什么?最后 newX 有几个元素?

newX = np.array([chroms[np.where(probs_cum > rand)[0][0]]

for rand in each_rand])

经过拆分,得到结果:


上面的代码等于
在这里插入图片描述
其中[]中的for为列表生成式,返回一个列表。第一个[0]表示np.where()生成tuple元组中数组的行索引,np.where()[0]的值是tuple中的第一个数组,由于本例只有一个数组,故只返回一个一维数组,第二个[0]是该一维数组的首位元素。

最后newX一共有100个元素。

第二题

2)代码第 70 行的语义是什么?为什么要除以 2 再乘以 2?reshape 中的-1 表示什么?

pairs = np.random.permutation(

int(len(newX)*prob//2*2)).reshape(-1, 2) # 产生 6 个随机数乱排一下分成二列
  • 随机生成6个在[0,5]之间的数字,并将其排列成二维的形状是(3,2)的数组。

  • newX一共有十个元素,可以理解成有十条染色体。因为要随机配对,所以我们把染色体两两分组,这样//2表示一共分成了五组。分成五组后,乘以随机配对概率,得到一共有三组染色体要进行配对。配对是单条染色体与另一个单条染色体进行的行为,故我们要乘以2,表示一共有六条染色体之间要配对。

  • reshape中的-1表示,通过列数对数组的行数进行自动计算。新的shape属性应该要与原来的配套,如果等于-1的话,那么Numpy会根据剩下的维度计算出数组的另外一个shape属性值。

第三题

3)请结合 Mutate 函数的内容,详述变异是如何实现的。

def Mutate(chroms: np.array):
    prob = 0.1  # 变异的概率
    clen = len(chroms[0])  # chroms[0]="111101101 000010110"    字符串的长度=18
    m = {'0': '1', '1': '0'}  # m是一个字典,包含两对:第一对0是key而1是value;第二对1是key而0是value
    newchroms = []  # 存放变异后的新种群
    each_prob = np.random.uniform(size=len(chroms))  # 随机10个数

    for i, chrom in enumerate(chroms):  # enumerate的作用是整一个i出来
        if each_prob[i] < prob:  # 如果要进行变异(i的用处在这里)
            pos = np.random.randint(clen)  # 从18个位置随机中找一个位置,假设是7
            # 0~6保持不变,8~17保持不变,仅将7号翻转,即0改为1,1改为0。注意chrom中字符不是1就是0
            chrom = chrom[:pos] + m[chrom[pos]] + chrom[pos+1:]
        newchroms.append(chrom)  # 无论if是否成立,都在newchroms中增加chroms的这个元素
    return np.array(newchroms)  # 返回变异后的种群
  1. 首先,得到变异概率与单个染色体的长度(二进制数位数),再利用字典对变异的两种情况做一个存储。
  2. newchroms是存放变异后新种群的array。
  3. 通过each_prob计算出每个染色体的随机变异概率
  4. 遍历染色体,如果随机变异概率低于变异概率,则发生变异
  5. 发生变异,通过计算pos,从染色体中随机找个位置变异,即二进制数某个位发生突变
  6. 无论染色体是否发生变异,都在新种群中添加染色体(发生突变的与岁月静好的都算)
  7. 返回整个新的种群

未修改前:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
修改后:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
执行结果变化如上。

染色体进行过交叉后,不再发生变异。少了一次变异,新种群与原种群概率上讲,差异要更小一些。

第五题

5)轮盘让个体按概率被选择,对于适应度最高的个体而言,虽然被选择的概率高,但仍有可能被淘汰,从而在进化过程中失去当前最优秀的个体。一种改进方案是,让适应度最高的那个个体不参与选择,而是直接进入下一轮(直接晋级),这种方案被称为精英选择(elitist selection)。请修改Select 部分的代码,实现这一思路。

def Select_Crossover(chroms, fitness, prob=0.6):  # 选择和交叉
    probs = fitness/np.sum(fitness)  # 各个个体被选择的概率

    probs_cum = np.cumsum(probs)  # 概率累加分布

    each_rand = np.random.uniform(size=len(fitness))  # 得到10个随机数,0到1之间

    # 轮盘赌,根据随机概率选择出新的基因编码
    # 对于each_rand中的每个随机数,找到被轮盘赌中的那个染色体

    # 修改代码处
    ak = chroms[np.argmax(probs_cum)]
    np.delete(chroms,np.argmax(probs_cum))
    # 修改代码处
    newX = np.array([chroms[np.where(probs_cum > rand)[0][0]]
                    for rand in each_rand])

    # 繁殖,随机配对(概率为0.6)
    # 6这个数字怎么来的,根据遗传算法,假设有10个数,交叉概率为0.6,0和1一组,2和3一组。。。8和9一组,每组扔一个0到1之间的数字
    # 这个数字小于0.6就交叉,则平均下来应有三组进行交叉,即6个染色体要进行交叉
    pairs = np.random.permutation(
        int(len(newX)*prob//2*2)).reshape(-1, 2)  # 产生6个随机数,乱排一下,分成二列
    center = len(newX[0])//2  # 交叉方法采用最简单的,中心交叉法
    for i, j in pairs:
        # 在中间位置交叉
        x, y = newX[i], newX[j]
        newX[i] = x[:center] + y[center:]  # newX的元素都是字符串,可以直接用+号拼接
        newX[j] = y[:center] + x[center:]
    # 修改代码处
    np.append(newX,ak)
    # 修改代码处
    return newX
这篇关于计算智能课程设计(遗传算法求解无约束单目标优化问题)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!