遗传算法工作原理、失效场景及字符串匹配实现相关问题问询
基于遗传算法的字符串匹配实现与核心问题
实现背景
- 自身学习方向为化学开发领域的相关算法,接触到遗传算法(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
相关产品推荐
相关产品推荐

