遗传算法

• 遗传算法的本质：
  1. 创建族群
  2. 交换染色体信息
  3. 染色体信息变异
  4. 族群的优胜劣汰
• 代码本质：
  1. 创建随机解集
  2. 两解交换信息
  3. 选择信息变异
  4. 去除劣势的解

例题：

• 在一个长度为n的数组nums中选择十个元素，使得十个元素的和与原数组的所有元素之和的1/10无限接近。
• 如 n = 50 n=50 n=50， s u m ( n u m s ) = 1000 sum(nums)=1000 sum(nums)=1000,选择的元素列表 a n s w e r answer answer要满足 ∣ s u m ( a n s w e r ) − 100 ∣ < e |sum(answer)-100|<e ∣sum(answer)−100∣<e， e e e尽可能小。
• 代码：

import random


def create_answer(numbers_set, n):  # 生成随机解集
    result = []  # 创建一个返回的list
    for i in range(n):
        result.append(random.sample(numbers_set, 10))  # 在numbers_set中再随机抽取10个元素
    return result  # 返回result的list


def error_level(new_answer, numbers_set):  # 计算误差
    error = []  # 用于存放误差值
    right_answer = sum(numbers_set) / 10  # right_answer是原始数据和的十分之一
    # 对解集中的每一个解计算误差
    for item in new_answer:
        value = abs(right_answer - sum(item))  # 用原始数据和的十分之一减去解的值算出每个解的误差
        if value == 0:
            error.append(10)  # 误差为0放入10 1/0.1 (误差最小为1，钱步骤除以10之后最小误差变为0.1，所以放入0.1的倒数)
        else:
            error.append(1 / value)  # 放入误差分之一
    return error  # 返回error的list


def choice_selected(old_answer, numbers_set):  # 选择并交换信息
    result = []
    error = error_level(old_answer, numbers_set)  # 计算误差系数
    error_one = [item / sum(error) for item in error]  # 归一化
    for i in range(1, len(error_one)):
        error_one[i] += error_one[i - 1]  #
    for i in range(len(old_answer) // 2):
        temp = []
        for j in range(2):
            rand = random.uniform(0, 1)
            for k in range(len(error_one)):
                if k == 0:
                    if rand < error_one[k]:
                        temp.append(old_answer[k])
                else:
                    if rand >= error_one[k - 1] and rand < error_one[k]:
                        temp.append(old_answer[k])
        rand = random.randint(0, 6)
        temp_1 = temp[0][:rand] + temp[1][rand:rand + 3] + temp[0][rand + 3:]
        temp_2 = temp[1][:rand] + temp[0][rand:rand + 3] + temp[1][rand + 3:]
        result.append(temp_1)
        result.append(temp_2)
    return result


def variation(old_answer, numbers_set, pro):  # 概率变异，解中某元素随机替换 pro是变异概率
    for i in range(len(old_answer)):
        rand = random.uniform(0, 1)
        if rand < pro:
            rand_num = random.randint(0, 9)
            old_answer[i] = old_answer[i][:rand_num] + random.sample(numbers_set, 1) + old_answer[i][rand_num + 1:]
    return old_answer


numbers_set = random.sample(range(0, 1000), 50)  # 从0-1000中随机选取50个数作为原始数据numbers_set
middle_answer = create_answer(numbers_set, 100)  # 创建解集(100次循环，生成一百组结果）
first_answer = middle_answer[0]  # 原始解
great_answer = []  # 保存最好的解
for i in range(1000):
    middle_answer = choice_selected(middle_answer, numbers_set)
    middle_answer = variation(middle_answer, numbers_set, 0.1)
    # 选择表现最好的误差
    error = error_level(middle_answer, numbers_set)
    index = error.index(max(error))
    great_answer.append([middle_answer[index], error[index]])  # 将最好解的系数和值放入great_answer

great_answer.sort(key=lambda x: x[1], reverse=True)  # 按照列表中第二个元素排序
print("正确答案：", sum(numbers_set) / 10)
print("最优解：", great_answer[0][0])
print("最优解的和：", sum(great_answer[0][0]))
print("选择系数：", great_answer[0][1])
print("最初解的和：", sum(first_answer))