You need to enable JavaScript to run this app. 遗传算法工作原理、失效场景及字符串匹配实现相关问题问询
优惠活动
大模型
产品
解决方案
定价
更多

遗传算法工作原理、失效场景及字符串匹配实现相关问题问询

基于遗传算法的字符串匹配实现与核心问题

实现背景

  • 自身学习方向为化学开发领域的相关算法,接触到遗传算法(Genetic Algorithm, GA)后,编写了简单GA程序,目标是从给定符号集合(即基因库)中精准定位指定的目标字符串
  • 程序用到的固定常量定义:
    • 基因库字符串:genes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ 1234567890, .-;:_!\"#%&/()=?@${[]}"
    • 待匹配目标字符串定义:target = to be or not be that is the question

核心代码实现

个体类(头文件部分实现)

# 遗传算法中的染色体代表问题的一个可行解
import random 

genes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP \
QRSTUVWXYZ 1234567890, .-;:_!\"#%&/()=?@${[]}"


class Individual: 
    # 定义个体属性
    def __init__(self, chromosome):
        self.chromosome = chromosome # 代表实际的解
        self.fitness = self.calc_fitness() 
        
    def mutated_genes(self): 
        # 对个体的基因进行随机突变
        gene = random.choice(genes) 
        return gene 
    
    def create_gnome(self, target):
        gnome_len = len(target) 
        return [self.mutated_genes() for _ in range(gnome_len)]
    
    def mate(self, par2):
        # 与另一个个体完成交配产生后代
        child_chromosome = [] 
        for gp1, gp2 in zip(self.chromosome, par2.chromosome):
            # 生成随机数
            prob = random.random() 
            
            # 随机数小于0.45时,取父代1的基因
            if prob < 0.45:
                child_chromosome.append(gp1)
            elif prob < 0.9:
                # 随机数在0.45-0.9区间时,取父代2的基因
                child_chromosome.append(gp2)
            else: 
                # 随机突变产生新基因
                child_chromosome.append(self.mutated_genes()) 
                
        return Individual(child_chromosome)
                
    def calc_fitness(self):
        # 计算适应度得分
        # 得分定义为字符串中与目标不匹配的字符数量
        fitness = 0
        for gs,gt in zip(self.chromosome, target):
            if gs != gt:
                fitness += 1
        return fitness 

驱动运行代码

%run "string_search.ipynb"
population_size = 100 
target = "to be or not to be that is the question" 
generation = 1 # 初始化进化代数
found = False # 终止标记
population = [] 
# 初始化种群
for i in range(population_size):
    indiv = Individual([])
    gnome = indiv.create_gnome(target)
    population.append(Individual(gnome))
while not found: 
    # 按适应度得分从小到大排序种群
    population = sorted(population, key = lambda x:x.fitness)
    # 若种群中适应度最低的个体得分为0,停止搜索
    if population[0].fitness == 0:
        found = True 
        break 
    # 否则生成新的一代
    new_generation = [] 
    # 适应度最高的10%个体直接进入下一代
    s = int(0.1*population_size)
    new_generation.extend(population[:s])
    
    # 从适应度前50%的个体中随机选亲代交配,产生剩余90%的新个体
    s = int(0.9*population_size)
    for i in range(s):
        parent1 = random.choice(population[:50]) # 从种群前50%中选父代1
        parent2 = random.choice(population[:50]) # 从种群前50%中选父代2
        child = parent1.mate(parent2) 
        new_generation.append(child) 
    population = new_generation 
    generation += 1 
    str_chr = "".join(population[0].chromosome)
    print("Generation: {} \t String: {} \t Fitness: {}".format(generation, str_chr, population[0].fitness))

运行现象与结果

  • 程序运行后期的典型收敛过程片段:
.
.
.
Generation: 14465    String: to be or not to be that is the 8uestion     Fitness: 1
Generation: 14466    String: to be or not to be that is the 8uestion     Fitness: 1
Generation: 14467    String: to be or not to be that is the 8uestion     Fitness: 1
Generation: 14468    String: to be or not to be that is the 8uestion     Fitness: 1
Generation: 14469    String: to be or not to be that is the 8uestion     Fitness: 1
Generation: 14470    String: to be or not to be that is the question     Fitness: 1
  • 观察到的特殊现象:算法可以收敛到仅差1个字符的匹配结果,即question被错误匹配为8uestion。

待解答的核心问题

  • 遗传算法为何能达到当前的运行效果,在哪些场景下会完全失效?
  • 程序为何会在Fitness = 1的状态长时间停滞(收敛平台期),经过大量迭代后才收敛到真实解?
  • 为什么增大种群规模能够提升收敛速率?
  • 如果将交叉过程中接受父代1基因的概率,改为基于适应度得分动态调整,算法效果是否会变好?

已查阅的现有资料大多仅停留在代码实现层面,或是经验性总结“种群规模越大收敛时间越短”,希望得到原理层面的专业解答与优化建议。


内容的提问来源于stack exchange,提问作者megamence

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.11 02:27:03