[ Untitled ]

Created2023-12-13Updated2023-12-22

遗传算法

常用步骤

变异、交叉、适应度计算、选择

变异（基因突变）

设置变异率，判断当前个体是否可以变异

1
2
3
mutation_rate = 0.1
if random.random() < mutation_rate:
	....

设置个体变异比例，判断当前个体能够变异的bits在哪里

1
2
3
4
mutate_point = random.sample(range(1, len(chromosome)), int(len(chromosome) * mutation_point_rate))
mutate_point.sort()
for i in mutate_point:
    chromosome[i] = chromosome[i] ^ 1

交叉（染色体交换）

可以设置一个交叉点，也可以设置多个交叉点，通常是百分之五十交叉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 交叉操作
def crossover(parent1, parent2):
    if random.random() < crossover_rate:
        # 随机选择50个不同的交叉点
        crossover_points = random.sample(range(1, len(parent1)), 50)
        crossover_points.sort()  # 将交叉点按顺序排列
        child1 = []
        child2 = []
        parent_switch = True  # 用于交替选择父代
        for i in range(len(parent1)):
            if i in crossover_points:
                # 如果当前位置是交叉点，则切换到另一个父代
                #print("test")
                parent_switch = not parent_switch
            if parent_switch:
                child1.append(parent1[i])
                child2.append(parent2[i])
            else:
                child1.append(parent2[i])
                child2.append(parent1[i])
        return child1, child2
    else:
        return parent1, parent2

适应度计算

即将生成的后代个体与期望达到的目标进行对比，计算差距，即适应度。

  • 二进制测试：与能够触发crash的目标进行适应度计算
  • CANID测试：与能够响应车机的CANID进行适应度计算
1
2
3
4
5
6
7
8
9
10
# 计算适应度函数
def fitness(chromosome):
    data = []
    for i in range(num_targets):
        target_value = input_data[i]
        binary_str = ''.join(map(str, chromosome[i * num_bits:(i + 1) * num_bits]))
        decimal_value = int(binary_str, 2)
        data.append(decimal_value)
    fitness_value = sum(abs(data[i] - input_data[i]) for i in range(num_targets))
    return fitness_value

这里的input_data即为期望达到的目标

选择

当种群达到一定规模后，需要控制种群数量，留下更多的优质基因，那么这时候就需要进行自然选择了，也就是选择那些和期望目标差距更小，适应度更小的后代。

1
2
3
4
5
6
7
8
# 选择操作
def selection(population):
    fitness_values = [fitness(chromosome) for chromosome in population]
    total_fitness = sum(fitness_values)
    probabilities = [fitness_value / total_fitness for fitness_value in fitness_values]
    selected_indices = random.choices(range(population_size), probabilities, k=population_size)
    selected_population = [population[i] for i in selected_indices]
    return selected_population

去世

按理说应该要加入这个算法的，即当繁殖几代之后，那些老一代就应该死去，不管是不是最优的

主要遗传算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 主要遗传算法循环
def genetic_algorithm():
    # print("aaaa")
    population = initialize_population()
    for generation in range(num_generations):
        population = selection(population)
        new_population = []
        while len(new_population) < population_size:
            parent1, parent2 = random.sample(population, 2)
            child1, child2 = crossover(parent1, parent2)
            child1 = mutate(child1)
            child2 = mutate(child2)
            new_population.extend([child1, child2])
        population = new_population
        best_chromosome = min(population, key=fitness)
        best_data = []
        for i in range(num_targets):
            binary_str = ''.join(map(str, best_chromosome[i * num_bits:(i + 1) * num_bits]))
            decimal_value = hex(int(binary_str, 2))
            best_data.append(decimal_value)
        print(f"Generation {generation + 1}: Fitness = {fitness(best_chromosome)}, Data = {best_data}")

依据设定最大种群数量，不断进行繁殖，直到种群数量已满，再进行下一轮的繁殖得到的后代应该进行自然选择。

模拟退火

主要就是降温和计算概率是否替换新的一代。

以旅行商TSP问题为例子

总的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def simulated_annealing_tsp(cities, initial_temperature=1000.0, cooling_rate=0.95, min_temperature=0.1):
    # 生成一个初始路径
    current_path = list(range(len(cities)))
    random.shuffle(current_path)
    current_distance = total_distance(current_path)

    temperature = initial_temperature

    while temperature > min_temperature:
        # 生成一个新路径
        new_path = current_path.copy()
        index1, index2 = random.sample(range(len(new_path)), 2)
        new_path[index1], new_path[index2] = new_path[index2], new_path[index1]
        new_distance = total_distance(new_path)

        # 判断新路径是否被接受
        if new_distance < current_distance:
            current_path, current_distance = new_path, new_distance
        else:
            delta = new_distance - current_distance
            probability = math.exp(-delta / temperature)
            if random.random() < probability:
                current_path, current_distance = new_path, new_distance

        # 降低温度
        temperature *= cooling_rate

    return current_path, current_distance

# 执行模拟退火算法
sa_best_path, sa_best_distance = simulated_annealing_tsp(cities)
print("最优路径:", sa_best_path)
print("最优距离:", total_distance(sa_best_path))

  • 设定初始温度，降温比例，最小温度，初代路径

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    #初始温度
    initial_temperature=1000.0
    #降温率
    cooling_rate=0.95
    #最小温度
    min_temperature=0.1
    #初代路径
    current_path = list(range(len(cities)))
    random.shuffle(current_path)
    current_distance = total_distance(current_path)

    temperature = initial_temperature

  • 判断是否达到最低温度

    1
    while temperature > min_temperature:

    • 生成新的路径

      • 如果新的路径更优秀，距离更短，那么就直接替换

        1
        2
        3
        4
        5
        6
        7
        8
        9
        #生成新的路径
        new_path = current_path.copy()
        index1, index2 = random.sample(range(len(new_path)), 2)
        new_path[index1], new_path[index2] = new_path[index2], new_path[index1]
        new_distance = total_distance(new_path)

        # 判断新路径是否被接受，如果距离更短，无条件接收
        if new_distance < current_distance:
            current_path, current_distance = new_path, new_distance

      • 如果新的一代更差，那么就依据当前温度，计算替换概率，（温度越高，概率越大），概率越大的，新的替换旧的概率就越大，然后降低问题。

        这个计算概率不知道怎么个计算法

        1
        2
        3
        4
        5
        6
        7
        else:
            #计算概率
            delta = new_distance - current_distance
            probability = math.exp(-delta / temperature)
            #依据概率判断是否进行距离路径替换
            if random.random() < probability:
                current_path, current_distance = new_path, new_distance

      • 降低温度

        1
        2
        # 降低温度
        temperature *= cooling_rate

  • 依次类推，直到达到最低温度跳出循环