睿智的智能优化算法3——利用遗传算法实现字符串配对

待我称王封你为后i 2024-04-18 12:50 70阅读 0赞

### 睿智的智能优化算法3——利用遗传算法实现字符串配对 ###

*  字符串配对
 *  求解过程
 *   *  1、编码方式
     *  2、计算适应度
     *  3、自然选择
     *  4、基因突变
     *  5、个体杂交
 *  实现代码
 *  GITHUB下载连接

好久都没有用过遗传算法了，觉得需要重新复习一下，而且考虑到遗传算法应该有其它作用，所以我又来了！关于什么是遗传算法，及其实现方式，大家可以关注我的另一篇博文[睿智的智能优化算法2——遗传算法的python实现][2_python]  
![在这里插入图片描述][20190723170158884.jpg_pic_center]

# 字符串配对 #

字符串配对的过程就是指定一条字符串，通过遗传算法的不断尝试，使其复现出这条字符串。  
其实现过程大概如下所示（思路来自于[莫烦python][python]不过我的实现方式与其有一定的不同）：

century： 0 get： RJSc-a
    century： 1 get： QBy4WX
    century： 2 get： n{
        Qs\X
    ……
    
    century： 21 get： XJi2WX
    century： 22 get： XAQ2WX
    century： 23 get： XJQ2WX
    [6, 'XJQ2WX']

# 求解过程 #

## 1、编码方式 ##

首先假设一个字符串，本文使用的例子是"XJQ2WX"。  
其对应的ASCII如图所示：  
![在这里插入图片描述][20190906194541287.png_pic_center]  
本文使用8位1、0来编码每个字符。编码方式如下：

# 该部分用于将字符对应的编码[1,0,1....,1,0]转换成对应的数字
    def binarytodecimal(self,binary):
        total = 0
        for j in range(len(binary)):
            total += binary[j] * (2**j)
        total = np.int8(total * 94 / 255 + 32)
        return total

如X对应的ASCII码是88，其编码后的结果就是10011000。  
![在这里插入图片描述][20190906200203564.png_pic_center]  
XJQ2WX对应的编码长度就是56位，每个个体的长度为56位，每个个体可以分为7段，每段8位，每段对应一个字符。

def pop_translate(self):
        pop_translate = []
        # 对每个个体进行转换
        # pop_size代表个体数量
        for i in range(self.pop_size):
            unit = []
            # 读出一个个体基因中每一段对应的数字
            # gene_size代表字符的个数
            # unit_length代表每个字符对应的编码长度
            for j in range(self.gene_size):
                low,high = j*self.unit_length,(j+1)*self.unit_length
                after = self.binarytodecimal(self.pop[i,low:high])
                unit.append(after)
            # 存入到转换后的种群中
            pop_translate.append(unit)
        return np.array(pop_translate,dtype = np.int8)

## 2、计算适应度 ##

本文首先通过pop\_translate函数得到转换成数字组形式的种群，再通过对比转换后的种群与目标字符串对应的ASCII码，计算出适应度，实现方式如下：

# 计算适应度
    def count_fitness(self):
        # 首先获取转换后的种群
        self.pop_t = self.pop_translate()
        # 将转换后的种群与目标字符串对应的ASCII码比较，计算出适应度
        fitness = (self.pop_t == TARGET_ASCII).sum(axis=1)
        return np.array(fitness)

## 3、自然选择 ##

自然选择依然采用轮盘赌的方式实现，通过np.random.choice函数实现相比于之前的方法更加简单：

# 自然选择
    def selection(self):
        self.fit_value = self.count_fitness()
        [bestindividual, bestfit] = self.best()
        # 利用np.random.choice实现轮盘赌
        idx = np.random.choice(np.arange(self.pop_size), 
        	size=self.pop_size, replace=True, 
        	p=self.fit_value/self.fit_value.sum())
        self.pop = self.pop[idx]
        return [bestindividual, bestfit]

## 4、基因突变 ##

在每次突变进行时，对每一个个体的每一段进行判断，如果某一段满足突变条件，则该段突变，实现方式如下：

def mutation(self):
        # 判断每一条染色体是否需要突变
        for i in range(self.pop_size):
            for j in range(self.gene_size):
                if (np.random.rand() < self.mutation_rate):
                    low,high = j*self.unit_length,(j+1)*self.unit_length
                    self.pop[i,low:high] = np.random.randint(0,2,size=self.unit_length)

## 5、个体杂交 ##

杂交方式与之前相同，判断每一个个体是否满足杂交条件，是的话随机选择杂交点，然后交换对应点的基因。

# 杂交
    def crossover(self):
        # 按照一定概率杂交
        for i in range(self.pop_size):
            # 判断是否达到杂交几率
            if (np.random.rand() < self.cross_rate):
                # 随机选取杂交点，然后交换结点的基因
                individual_size = self.gene_size*self.unit_length
                # 随机选择另一个个体进行杂交
                destination = np.random.randint(0,self.pop_size)
                # 生成每个基因进行交换的结点
                crosspoint = np.random.randint(0,2,size = individual_size).astype(np.bool) 
                # 进行赋值
                self.pop[i,crosspoint] = self.pop[destination,crosspoint]

# 实现代码 #

本次实现代码与上次相比最大的不同是通过类class的方式实现。

import numpy as np
    import math
    import random
    
    TARGET_PHRASE = 'XJQ2WX'            # 目标字符串
    POP_SIZE = 300                      # 种群数量
    CROSS_RATE = 0.4                    # 杂交几率
    MUTATION_RATE = 0.01                # 突变几率
    N_GENERATIONS = 1000                # 繁殖代数
    
    GENE_SIZE = len(TARGET_PHRASE)      # 获取字符串长度
    TARGET_ASCII = np.fromstring(TARGET_PHRASE, dtype=np.uint8)  # 从字符串转换到数字
    
    class GA():
        def __init__(self,gene_size,unit_length,cross_rate,mutation_rate,pop_size):
            # 基因长度代表字符串的长度
            self.gene_size = gene_size
            # 种群的大小代表种群中有几个个体
            self.pop_size = pop_size
            # 单位长度代表字符串每个字符所对应的编码长度
            self.unit_length = unit_length
            # 杂交几率
            self.cross_rate = cross_rate
            self.mutation_rate = mutation_rate
            self.pop = self.init_pop()
    
        # 初始化种群
        def init_pop(self):
            pop = []
            for _ in range(self.pop_size):
                pop.append(np.random.randint(0,2,size = self.gene_size*self.unit_length)) 
            return np.array(pop)
        
        # 将种群从[1,0,1....,1,0]编码转化成对应的数字
        def pop_translate(self):
            pop_translate = []
            for i in range(self.pop_size):
                unit = []
                # 读出一个个体基因中每一段对应的数字
                for j in range(self.gene_size):
                    low,high = j*self.unit_length,(j+1)*self.unit_length
                    after = self.binarytodecimal(self.pop[i,low:high])
                    unit.append(after)
                # 存入到转换后的种群中
                pop_translate.append(unit)
            return np.array(pop_translate,dtype = np.int8) 
    
        # 该部分用于将字符对应的编码[1,0,1....,1,0]转换成对应的数字
        def binarytodecimal(self,binary):
            total = 0
            for j in range(len(binary)):
                total += binary[j] * (2**j)
            total = np.int8(total * 94 / 255 + 32)
            return total
    
        # 计算适应度
        def count_fitness(self):
            # 首先获取转换后的种群
            self.pop_t = self.pop_translate()
            # 将转换后的种群与目标字符串对应的ASCII码比较，计算出适应度
            fitness = (self.pop_t == TARGET_ASCII).sum(axis=1)
            return np.array(fitness)
    
        # 自然选择
        def selection(self):
            self.fit_value = self.count_fitness()
            [bestindividual, bestfit] = self.best()
            # 利用np.random.choice实现轮盘赌
            idx = np.random.choice(np.arange(self.pop_size), size=self.pop_size, replace=True, p=self.fit_value/self.fit_value.sum())
            self.pop = self.pop[idx]
            return [bestindividual, bestfit]
    
        # 选出最大value对应的索引，取出个体与对应的适应度
        def best(self): 
            index = np.argmax(self.fit_value)
            bestfit = self.fit_value[index]
            print(self.pop[index])
            bestindividual = self.pop_t[index].tostring().decode('ascii')
            return [bestindividual, bestfit]
    
        # 杂交
        def crossover(self):
            # 按照一定概率杂交
            for i in range(self.pop_size):
                # 判断是否达到杂交几率
                if (np.random.rand() < self.cross_rate):
                    # 随机选取杂交点，然后交换结点的基因
                    individual_size = self.gene_size*self.unit_length
                    # 随机选择另一个个体进行杂交
                    destination = np.random.randint(0,self.pop_size)
                    # 生成每个基因进行交换的结点
                    crosspoint = np.random.randint(0,2,size = individual_size).astype(np.bool) 
                    # 进行赋值
                    self.pop[i,crosspoint] = self.pop[destination,crosspoint]
    
        # 基因突变
        def mutation(self):
            # 判断每一条染色体是否需要突变
            for i in range(self.pop_size):
                for j in range(self.gene_size):
                    if (np.random.rand() < self.mutation_rate):
                        low,high = j*self.unit_length,(j+1)*self.unit_length
                        self.pop[i,low:high] = np.random.randint(0,2,size=self.unit_length)
    
        def evolve(self):
            [bestindividual, bestfit] = self.selection()
            self.mutation()
            self.crossover()
            return [bestindividual, bestfit]
    
    # 初始化类
    test1 = GA(gene_size = GENE_SIZE,unit_length = 8,cross_rate = CROSS_RATE,
        mutation_rate = MUTATION_RATE,pop_size = POP_SIZE)
    
    results = []
    
    for i in range(N_GENERATIONS):
        [bestindividual, bestfit] = test1.evolve()
        results.append([bestfit,bestindividual])
        print("century：",i,"get：",bestindividual)
        if(bestindividual == TARGET_PHRASE):
            break
    results.sort()	
    print(results[-1]) #打印使得函数取得最大的个体，和其对应的适应度

实现结果为（实现的century次数不定）：

# GITHUB下载连接 #

[https://github.com/bubbliiiing/Optimization\_Algorithm][https_github.com_bubbliiiing_Optimization_Algorithm]

希望得到朋友们的喜欢。  
有问题的朋友可以提问噢。

[2_python]: https://blog.csdn.net/weixin_44791964/article/details/99826470
[20190723170158884.jpg_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/788fcf31e4bf4728b7de7a431f59774f.jpg
[python]: https://morvanzhou.github.io/tutorials/machine-learning/evolutionary-algorithm/2-02-genetic-algorithm-match-phrase/
[20190906194541287.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/227a7e565dfb4b3eae337778da67dc63.png
[20190906200203564.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/2160ca8869704f0f9eed31a00352fc84.png
[https_github.com_bubbliiiing_Optimization_Algorithm]: https://github.com/bubbliiiing/Optimization_Algorithm