人工智能导论实验——基于遗传算法的随机优化搜索

基于遗传算法的随机优化搜索

目录

一、基本概念

1.个体与种群 个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。

· 种群(population)就是模拟生物种群而干个体组成的群体, 它一般是整个搜索空间的一个很小的子集。

2.适应度与适应度函数

· 适应度(fitness)就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。

·适应度函数(fitness function)就是问题中的 全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。

3.染色体与基因

染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基（gene）。

例如：

个体 染色体

9 ---- 1001

（2，5，6） ---- 010 101 110

4.遗传操作

亦称遗传算子(genetic operator)，就是关于染色体的运算。遗传算法中有三种遗传操作：

·选择-复制(selection-reproduction)

·交叉(crossover，亦称交换、交配或杂交)

·变异(mutation，亦称突变)

选择-复制通常做法是：对于一个规模为N的种群S,按每个染色体xi∈S的选择概率P(xi)所决定的选中机会, 分N次从S中随机选定N个染色体, 并进行复制。

这里的选择概率P(xi)的计算公式为

交叉 就是互换两个染色体某些位上的基因

例如, 设染色体 S1=01001011, S2=10010101, 交换其后4位基因, 即

变异 就是改变染色体某个(些)位上的基因

例如, 设染色体 s=11001101 将其第三位上的0变为1, 即

S=11001101 →11101101= S′。

S′也可以看做是原染色体S的子代染色体。

二、基本遗传算法

遗传算法基本流程框图

算法中的一些控制参数：

·种群规模

·最大换代数

·交叉率(crossover rate)就是参加交叉运算的染色体个数占全体染色体总数的比例，记为PC ,取值范围一般为0.4～0.99。

·变异率(mutation rate)是指发生变异的基因位数所占全体染色体的基因总位数的比例，记为Pm，取值范围一般为0.0001～0.1。

基本遗传算法解决步骤：

①在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T；

② 随机产生U中的N个个体S1, S2, …, SN，组成初始种群S={S1, S2, …, SN}，置代数计数器t=1；

③计算S中每个个体的适应度f() ；

④若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。

⑤按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1；

⑥按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；

⑦按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；

⑧将群体S3作为新一代种群，即用S3代替S，t = t+1，转步3；

三、遗传算法应用举例

利用遗传算法求解区间［0,31］上的二次函数y=x2的最大值

分析

原问题可转化为在区间［0, 31]中搜索能使y取最大值的点a的问题。那么，[0, 31中的点x就是个体, 函数值f(x)恰好就可以作为x的适应度，区间［0, 31］就是一个(解)空间 。这样, 只要能给出个体x的适当染色体编码, 该问题就可以用遗传算法来解决。

解

(1) 设定种群规模,编码染色体，产生初始种群。

将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1:

S1= 13 (01101), S2= 24 (11000)

S3= 8 (01000), S4= 19 (10011)

(2) 定义适应度函数

取适应度函数：f (x)=x2

(3)计算各代种群中的各个体的适应度, 并对其染色体进行遗传操作,直到适应度最高的个体(即31（11111）)出现为止。

首先计算种群S1中各个体

S1= 13(01101), S2= 24(11000)

S3= 8(01000), S4= 19(10011)

的适应度f (Si)

容易求得

f (S1) = f(13) = 132 = 169

f (S2) = f(24) = 242 = 576

f (S3) = f(8) = 82 = 64

f (S4) = f(19) = 192 = 361

再计算种群S1中各个体的选择概率。

计算公式为：

由此可得

P(S1) = P(13) = 0.14 , P(S2) = P(24) = 0.49

P(S3) = P(8) = 0.06 ,P(S4) = P(19) = 0.31

赌轮选择示意图如下：

在算法中赌轮选择法可用下面的子过程来模拟:

①在［0, 1］区间内产生一个均匀分布的随机数r。

②若r≤q1,则染色体x1被选中。

③若qk-1

选择-复制

设从区间［0, 1］中产生4个随机数如下:

r1 = 0.450126, r2 = 0.110347

r3 = 0.572496, r4 = 0.98503

于是，经复制得群体：

S1’ =11000（24）, S2’ =01101（13）

S3’ =11000（24）, S4’ =10011（19）

交叉

设交叉率pc=100%基于遗传算法的随机优化搜索，即S1中的全体染色体都参加交叉运算。

设S1’与S2’配对，S3’与S4’配对。分别交换后两位基因，得新染色体：

S1’’=11001（25）, S2’’=01100（12）

S3’’=11011（27）, S4’’=10000（16）

变异

设变异率pm=0.001。这样，群体S1中共有5×4×0.001=0.02 位基因可以变异。

0.02位显然不足1位，所以本轮遗传操作不做变异。

于是，得到第二代种群S2：

S1=11001（25）, S2=01100（12）

S3=11011（27）, S4=10000（16）

假设这一轮选择-复制操作中，种群S2中的4个染色体都被选中，则得到群体：

S1’=11001（25）, S2’= 01100（12）

S3’=11011（27）, S4’= 10000（16）

做交叉运算，让s1’与s2’，s3’与s4’ 分别交换后三位基因，得

S1’’ =11100（28）, S2’’ = 01001（9）

S3’’ =11000（24）, S4’’ = 10011（19）

这一轮仍然不会发生变异。

于是，得第三代种群S3：

S1=11100（28）, S2=01001（9）

S3=11000（24）, S4=10011（19）

设这一轮的选择-复制结果为：

S1’=11100（28）, S2’=11100（28）

S3’=11000（24）, S4’=10011（19）

做交叉运算，让s1’与s4’，s2’与s3’ 分别交换后两位基因，得

S1’’=11111（31）, S2’’=11100（28）

S3’’=11000（24）,S4’’=10000（16）

这一轮仍然不会发生变异。

于是，得第四代种群S4：

S1=11111（31）, S2=11100（28）

S3=11000（24）, S4=10000（16）

显然，在这一代种群中已经出现了适应度最高的染色体S1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。

然后，将染色体“11111”解码为表现型，即得所求的最优解：31。

将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。

总结：

遗传算法的特点与优势：

①遗传算法一般是直接在解空间搜索, 而不像图搜索那样一般是在问题空间搜索, 最后才找到解。

②遗传算法的搜索随机地始于搜索空间的一个点集, 而不像图搜索那样固定地始于搜索空间的初始节点或终止节点,所以遗传算法是一种随机搜索算法。

③遗传算法总是在寻找优解, 而不像图搜索那样并非总是要求优解, 而一般是设法尽快找到解, 所以遗传算法又是一种优化搜索算法。

④遗传算法的搜索过程是从空间的一个点集(种群)到另一个点集(种群)的搜索,而不像图搜索那样一般是从空间的一个点到另一个点地搜索。 因而它实际是一种并行搜索, 适合大规模并行计算,而且这种种群到种群的搜索有能力跳出局部最优解。

⑤遗传算法的适应性强, 除需知适应度函数外, 几乎不需要其他的先验知识。

⑥遗传算法长于全局搜索, 它不受搜索空间的限制性假设的约束,不要求连续性, 能以很大的概率从离散的、多极值的、 含有噪声的高维问题中找到全局最优解。

四、遗传算法的应用

1.遗传算法在人工智能的众多领域便得到了广泛应用。例如，机器学习、聚类、控制（如煤气管道控制）、规划（如生产任务规划）、设计（如通信网络设计、布局设计）、调度（如作业车间调度、机器调度、运输问题）、配置（机器配置、分配问题）、组合优化（如TSP、背包问题）、函数的最大值以及图像处理和信号处理等等。

2.另一方面，人们又将遗传算法与其他智能算法和技术相结合，使其问题求解能力得到进一步扩展和提高。例如，将遗传算法与模糊技术、神经网络相结合，已取得了不少成果。

五、Python实现：

# -*- coding: utf-8 -*-
import random
import matplotlib.pyplot as plt
from tqdm import tqdm
import numpy as np
from math import *
kind = 30
DNA = []
NDNA = [0] * kind
Crossover_rate = 0.6
Mutation_rate = 0.05
N = 500
def fitness(x):
    return x ** 2
def update():
    for i in range(kind):
        NDNA[i] = fitness(DNA[i]) - fitness(min(DNA)) * 0.95
    sums = sum(NDNA)
    ssum = 0
    for i in range(kind):
        ssum += NDNA[i]
        NDNA[i] = ssum / sums
def init():
    for i in range(kind):
        DNA.append(random.random() * 31.0)
    update()
def selection():
    DNAn = []
    for i in range(kind):
        num = random.random()
        for j in range(kind):
            if j == 0 and num <= NDNA[j]:
                DNAn.append(DNA[j])
            elif num <= NDNA[j] and num > NDNA[j - 1]:
                DNAn.append(DNA[j])
    for i in range(kind):
        DNA[i] = DNAn[i]
    update()
def cross():
    aa = random.randint(0, kind - 1)
    bb = random.randint(0, kind - 1)
    t1 = random.random()
    ans1 = DNA[aa] * t1 + DNA[bb]
    ans2 = DNA[bb] * t1 + DNA[aa]
    if ans1 <= 31.0:
        DNA[aa] = ans1
    if ans2 <= 31.0:
        DNA[bb] = ans2
    update()
def variation():
    aa = random.randint(0, kind - 1)
    bb = random.random()
    if bb >= 0.5:
        DNA[aa] = fmod(DNA[aa] * 1.05, 31.0)
    else:
        DNA[aa] = fmod(DNA[aa] * 0.95, 31.0)
    update()
if __name__ == '__main__':
    init()
    ans = []
    an = []
    for i in tqdm(range(N)):
        selection()
        crand = random.random()
        mrand = random.random()
        if crand <= Crossover_rate:
            cross()
        if mrand <= Mutation_rate:
            variation()
        # print('DNAs are', DNA, end=' ')
        ans.append(max(DNA) ** 2)
        # print('The optimal solution now is', max(ans))
        an.append(max(ans))
    print('y=x^2在[0,31]上最大值为：', max(ans))
    plt.subplot(121)
    a = np.arange(0, 32, 1)
    plt.plot(a, a * a, label='y = x^2')
    plt.xlabel('x')
    plt.ylabel('y=x^2')
    dna = np.array(DNA)
    plt.plot(dna, dna * dna, 'o')
    plt.axis([0, 32, 0, 1000])
    plt.subplot(122)
    b = np.arange(0, N, 1)
    anss = np.array(an)
    ansss = np.array(ans)
    plt.plot(b, anss, linewidth=6.0, label='max', color='blue')
    plt.plot(b, ansss, '-.', linewidth=1.5, label='now', color='red')
    plt.legend()
    plt.show()

（编辑：成都站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!