遗传算法详解：原理、实现与应用

创作时间:

作者:

@小白创作中心

遗传算法详解：原理、实现与应用

引用

CSDN

https://blog.csdn.net/sfy996/article/details/141105778

遗传算法是一种模拟自然界的进化过程来寻找问题最优解的全局搜索算法。它通过模拟自然界的遗传、交叉和变异过程来不断进化一组解，直到找到接近最优解的解决方案。遗传算法具有全局搜索能力，不易陷入局部最优解，适用于解决旅行商问题、装箱问题、调度问题等复杂优化问题。

算法描述

概括

一种模拟自然界的进化过程来寻找问题最优解的全局搜索算法。其基本思想是通过模拟自然界的遗传，交叉和变异过程来不断进化一组解，直到找到接近最优解的解决方案。这个过程涉及到对解决方案的编码，适应度评估，选择，交叉和变异等操作。

术语解释

染色体（个体）：代表一个解决方案的字符串（二进制算法中由0和1组成）。
基因：问题解决方案的基本单位，如在TSP问题中，若514325表示一条染色体，那么“5”“1”等则表示其中的基因。
种群：一组染色体，即一组候选解。该算法在每一代中对种群进行操作，以寻找最优解。
适应度：通常是一个函数，用于评估染色体对应的解决方案在解决问题时的优劣。
选择：根据染色体的适应度，从当前种群中选择染色体进入下一代的过程。适应度越高，越容易被选中。
交叉：模拟生物学中基因交换的过程，将父代染色体的部分片段进行交换产生新个体（新染色体）。
变异：对染色体进行随机改变的过程，可以避免算法过早收敛到局部最优解。

算法步骤

初始化种群：随机生成一组个体，构成初始种群。
适应度评估：对种群中的每一个个体计算适应度，适应度函数根据问题定义，用来评价每个解的质量。
选择：根据适应度，选择个体进入下一代。常用方法有轮盘赌选择，锦标赛选择等。
交叉：对选中的个体进行两两配对，并按照一定概率交换它们的部分基因，产生新的个体。
变异：对新产生的个体按照一定概率改变其一个或几个基因的位置，以增加种群多样性。
生成新种群：用产生的新个体替换掉旧种群中的一部分个体，形成新一代的种群。
收敛检验：判断算法是否满足终止条件，若满足，则停止进化过程，输出最优解，反之，返回到第二步。

方法介绍

编码和解码

二进制编码：每个基因都由一个二进制数表示。解码即将二进制转化为十进制
实数编码：直接用实数表示每个基因，eg.[x1,x2,x3]

计算适应度

必须保证适应度函数值为正值
最大值优化问题F（x)=G（x)+Cmin,当G(x)+Cmin>0时，否则F（x)=0
最小值优化问题F(x)=Cmax-G(x),当Cmax-G(x)>0时，否则F（x)=0
背包问题：通过计算物品的总价值来评价适应度，并根据背包的容量进行限制，超过时，设置惩罚函数来减少适应度。

def fitness(individual):
  total_weight=0
  total_value=0
  for i in range(n):
    if individual[i]==1:
      total_weight+=items[i][0]
      total_value+=items[i][1]
  penalty=max(0,total_weight-C)
  return total_value-penalty

旅行商问题：一般以路径长短评价适应度，路径越短，适应度越高。
调度问题：一般以时间长短评价适应度。

选择

锦标赛选择
1. 首先确定每次选择的个体数量x。
2. 在种群中随机选择x个个体(每个个体入选概率相同) 构成组，根据每个个体的适应度值，选择其中适应度值最好的个体进入子代种群。
3. 将步骤2重复操作n次，并将得到的n个体构成新一代种群。

import random
# 一元锦标赛选择
def tournament_selection(population, tournament_size=2):
    selected = []
    # 对种群中的每个个体进行锦标赛选择
    for _ in range(len(population)):
        tournament = random.sample(population, tournament_size)
        # 选择适应度最高的个体
        winner = max(tournament, key=fitness)
        selected.append(winner)
    return selected

轮盘赌选择

import random
# 轮盘赌选择
def roulette_wheel_selection(population):
    # 计算适应度和
    total_fitness = sum(fitness(individual) for individual in population)
    
    # 计算每个个体的选择概率
    selection_probs = [fitness(individual) / total_fitness for individual in population]
    
    # 构建累积概率分布
    cumulative_probs = [sum(selection_probs[:i+1]) for i in range(len(selection_probs))]
    
    # 选择个体
    selected_population = []
    for _ in range(len(population)):
        # 生成一个随机数
        p = random.random()
        # 根据随机数选择个体
        for i, cp in enumerate(cumulative_probs):
            if p < cp:
                selected_population.append(population[i])
                break
    return selected_population

交叉

单点交叉：选择两条染色体（个体），在随机选择的位置点上进行切割并交换右侧的部分，从而得到两个不同的染色体（个体）

import random
# 简单的单点交叉方式
def sing_muta(list1, list2):
    # 假设len(list1) == len(list2)
    # 随机选择交叉点
    cross_pt = random.randint(0, len(list1) - 2)
    list1_cut = list1[cross_pt + 1: len(list1)]
    list2_cut = list2[cross_pt + 1: len(list2)]
    new_list1 = list1[0: cross_pt + 1]
    new_list1.append(list2_cut)
    new_list2 = list2[0: cross_pt + 1]
    new_list2.append(list1_cut)
    return new_list1, new_list2
list1 = [1, 2, 3, 4, 5, 6, 7, 8]
list2 = [10, 20, 30, 40, 50, 60, 70, 80]
for i in range(5):
    print(sing_muta(list1, list2))

多点交叉：又称广义交叉，在个体染色体中随机设置多个交叉点，然后进行基因交换。
部分匹配交叉（PMX）
1. 随机选择一对染色体（父代）中几个基因的起止位置（两染色体被选位置相同）。
2. 交换这两组基因的位置。
3. 做冲突检测，根据交换的两组基因建立一个映射关系，如图所示，以7-5-2这一映射关系为例，可以看到第二步结果中子代1存在两个基因7，这时将其通过映射关系转变为基因2，以此类推至没有冲突为止。最后所有冲突的基因都会经过映射，保证形成的新一对子代基因无冲突。
  最终结果为：
基于位置的交叉（PBX）
1. 初始化子代：创建两个空的子代个体，其长度与父代个体相同。
2. 选择交叉段：随机选择一个交叉段，该交叉段将从一个父代中复制到第一个子代，而剩余的基因将从另一个父代中复制到第二个子代。这一步通常使用随机生成的交叉点来实现。
3. 复制交叉段：将选定的交叉段从一个父代复制到第一个子代，保持原始的顺序不变。
4. 映射剩余基因：从另一个父代中选择剩余的基因，并根据其在第一个子代中的位置将它们复制到第二个子代中。这里的关键是要确保新复制的基因不会导致重复或冲突。
5. 填充子代：使用以上步骤生成的两个子代，分别作为下一代的一部分，用于进一步的进化。
循环交叉：某个父代上随机选择1个基因，然后找到另一个父代相应位置上的基因编号，再回到第一个父代找到同编号的基因的位置，重复先前工作，直至形成长个环，环中的所有基因的位置即为最后选中的位置用父代染色体1中选中的基因生成子代，并保证位置对应，最后将父代染色体2中剩余基因放入子代中，另一个子代以相同方式获得。
OX交叉

def order_crossover(parent1, parent2):
    # 创建两个子代，初始化为与父代相同的长度
    child1 = [-1] * len(parent1)
    child2 = [-1] * len(parent2)
    # 选择两个随机交叉点
    start, end = sorted(random.sample(range(len(parent1)), 2))
    # 复制父代1中的交叉段到子代1中
    child1[start:end+1] = parent1[start:end+1]
    # 复制父代2中未在子代1中的基因到子代1中，保持顺序
    idx = end + 1
    for gene in parent2[end+1:] + parent2[:end+1]:
        if gene not in child1:
            child1[idx % len(parent1)] = gene
            idx += 1
    child2[start:end+1] = parent2[start:end+1]
    # 同样的操作对子代2执行
    idx = end + 1
    for gene in parent1[end+1:] + parent1[:end+1]:
        if gene not in child2:
            child2[idx % len(parent2)] = gene
            idx += 1
    return child1, child2