遗传算法是一种基于自然选择的技术,用于解决复杂问题。由于问题很复杂,遗传算法(而不是其他方法)被用来得出解决问题的合理方案。本文介绍遗传算法的基础知识以及如何用Python来实现。
适应度函数
适应度函数衡量所考虑的解决方案与问题的最佳解决方案的接近程度。它为人群中的每个人提供了适应度水平,描述了当前一代人的质量或效率。这个分值定义了选择,而更高的适应度值表明是经过优化的解决方案。
比如说,假设我们在处理一个实际的函数f(x),其中x是一组参数。要找到的最优值是x,这样f(x)就取最大值。
选择
这个过程决定了当前一代人中哪些个体受到青睐,从而繁殖、为下一代做出贡献。可以确定许多选择方法,每种方法都有自己的特点和适合的上下文。
根据个体的适应度水平,选择个体的概率也是最大的。
随机抽取一组,选择其中最好的。
根据适合度对人进行排序,选择机会则根据适合度分数按比例分配。
交叉
交叉是遗传算法的一个基本概念,其目的是交换两个亲本的遗传信息,形成一个或多个后代。这个过程非常类似自然界中发生的生物的交叉和重组。运用遗传的基本原理,交叉试图产生具有双亲理想特征的后代,从而在下一代中有更好的适应性。交叉是一个比较宽泛的概念,可以分为几种类型,每种类型都有其特点和可以有效运用的领域。
突变
在遗传算法中,突变之所以至关重要,是由于它提供了多样性,多样性是避免直接向最优解区域收敛的关键因素。因此,获得单个突变基因串的随机变化,算法可以进入仅通过交叉操作无法企及的最优解空间的其他区域。这个随机过程保证了无论怎样,人群都会进化,或者在遗传算法确定的搜索空间区域内移动其位置。
不妨用Python实现遗传算法。
问题定义
问题:对具体函数进行计算;f (x) = x^2f(x) = x^2,只对x值取整。
适应度函数:对于染色体二进制为x的情况,适应度函数的一个例子可能是f(x)= x^2。
复制
def fitness(chromosome):
x = int(''.join(map(str, chromosome)), 2)
return x ** 2
人群初始化
生成一个给定长度的随机染色体。
复制
def generate_chromosome(length):
return [random.randint(0, 1) for _ in range(length)]
def generate_population(size, chromosome_length):
return [generate_chromosome(chromosome_length) for _ in range(size)]
population_size = 10
chromosome_length = 5
population = generate_population(population_size, chromosome_length)
适应度评估
评估人群中每个染色体的适应度。
复制
fitnesses = [fitness(chromosome) for chromosome in population]
选择
使用轮盘选择法根据适合度选择亲本染色体。
复制
def select_pair(population, fitnesses):
total_fitness = sum(fitnesses)
selection_probs = [f / total_fitness for f in fitnesses]
parent1 = population[random.choices(range(len(population)), selection_probs)[0]]
parent2 = population[random.choices(range(len(population)), selection_probs)[0]]
return parent1, parent2
交叉
使用单点交叉,在父本基因串中选择一个随机的交叉位置,并在两个基因串之间交换这个位置之后的所有基因值。
复制
def crossover(parent1, parent2):
point = random.randint(1, len(parent1) - 1)
offspring1 = parent1[:point] + parent2[point:]
offspring2 = parent2[:point] + parent1[point:]
return offspring1, offspring2
突变
通过以一定的概率翻转比特来实现突变。
复制
def mutate(chromosome, mutation_rate):
return [gene if random.random() > mutation_rate else 1 - gene for gene in chromosome]
mutation_rate = 0.01
总之,由于模拟物种进化,遗传算法对于解决无法直接解决的优化问题具有一致性和有效性。因此,一旦您掌握了遗传算法的基本要素,并了解了如何用Python实现遗传算法,解决复杂任务就会容易得多。选择、交叉和突变使您能够对解决方案进行修改,并不断获得最佳或接近最佳的答案。但愿您已准备好将遗传算法运用到自己的任务中,从而在不同的任务和问题解决中得到改进。
![](http://static.shengco.com.cn/image/4yp3o5h8mq03/a626b359136f7e6592859d4a8e01ec87.jpeg)
![](http://static.shengco.com.cn/image/4yp3j33d60yy/f2b9ddeb790f168c30abda370aac029b.jpeg)
![](http://static.shengco.com.cn/image/4yp3963aejlm/3a9f76903539d936d22d6e5bc49d6096.jpeg)
![](http://static.shengco.com.cn/image/4yp3487apeea/a89961210bc606ef36db851d897a45e7.jpeg)
![](http://static.shengco.com.cn/image/4yp2u2jictko/d2f5e842b6cefdfe94b8dfc7938ac189.jpeg)
![](http://static.shengco.com.cn/image/4yp2k70a7ks1/e3b56766bb6414a78248067646f33d3f.jpeg)
![](http://static.shengco.com.cn/image/4yp2f6abh2eh/15af0d8046d34cb5d0312a2bb03efb83.jpeg)
![](http://static.shengco.com.cn/image/4yp2060371c2/b6216de0c953f210893a0322449a940d.jpeg)
![](http://static.shengco.com.cn/image/4yp2071byku4/1cd4502db9fc1df8518a7ed3deea02ea.jpeg)
![](http://static.shengco.com.cn/image/4yp1v459txt2/e1ca853ddeea387cc6a74ba75508e224.jpeg)
![](http://static.shengco.com.cn/image/4yp1b85dtzv0/769f0ba4f9965ecb0a9d593267e3da16.jpeg)
![](http://static.shengco.com.cn/image/4yp11gdn5lxi/109fe537541be105dfbd833703d7a7dc.jpeg)
![](http://static.shengco.com.cn/image/4yp0r93zf292/e32c32d2241947b7abea2bee8f534f3a.jpeg)
![](http://static.shengco.com.cn/image/4yp0r6c0xy9s/0a932ba62d422d832b55a8c12cdd8a70.jpeg)
![](http://static.shengco.com.cn/image/4yp0r4j4qeg3/a7018bf2776b39fdc670fc5b77e89cfe.jpeg)
![](http://static.shengco.com.cn/image/4yp0r2bwklmn/aaab8e8cd1d82e4375699c7e5f2707c7.jpeg)
![](http://static.shengco.com.cn/image/4yp0r3egml2o/d5aed1054c0bc718da8df958483f24f9.jpeg)
![](http://static.shengco.com.cn/image/4yp0m8110fxs/04327eb7606224d404dda56693068dbd.jpeg)
![](http://static.shengco.com.cn/image/4yp0hrbulg0j/e73d99d20530d0a11c9d4c6d5b1388be.jpeg)
![](http://static.shengco.com.cn/image/4yp0hqfgc4v7/d771ba9acc7f7e5f3ee9ea0e084745a4.jpeg)