第1关：遗传算法求解函数最值

编程要求
在右侧编辑器补充代码，实现遗传算法。并求解函数f(x)在区间[0,5]上的最大值:

f(x)=xsin(10x)+xcos(2x)

函数图像如下：

测试说明
平台会调用你实现的方法，求解函数最优解，若你求得最优解与正确答案绝对值小于0.1则视为通关，否则输出你求得的最优解。

开始你的任务吧，祝你成功！

#encoding=utf8
import numpy as np

DNA_SIZE = 10  # 染色体大小
POP_SIZE = 100  # 种群大小
CROSS_RATE = 0.8  # 交叉概率
MUTATION_RATE = 0.003  # 变异概率
N_GENERATIONS = 1000  # 进化次数
X_BOUND = [0, 5]  # 变量范围

# 获取染色体适应度
def get_fitness(pred): 
    return pred + 1e-3 - np.min(pred)

# 解码
def translateDNA(pop): 
    return pop.dot(2 ** np.arange(DNA_SIZE)[::-1]) / float(2**DNA_SIZE - 1) * X_BOUND[1]

# 选择适应度高的染色体
def select(pop, fitness):    
    idx = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True,
                           p=fitness / fitness.sum())
    return pop[idx]

# 交叉
def crossover(parent, pop):     
    if np.random.rand() < CROSS_RATE:
        i_ = np.random.randint(0, POP_SIZE, size=1)                             
        cross_points = np.random.randint(0, 2, size=DNA_SIZE).astype(np.bool)   
        parent[cross_points] = pop[i_, cross_points]                            
    return parent

# 变异
def mutate(child):
    for point in range(DNA_SIZE):
        if np.random.rand() < MUTATION_RATE:
            child[point] = 1 if child[point] == 0 else 0
    return child

def ga(F):
    '''
    F: 需要求解的函数
    x: 最优解
    '''
    # ********* Begin ********* #
    # 初始化种群
    pop = np.random.randint(2, size=(POP_SIZE, DNA_SIZE))

    # 开始进化
    for generation in range(N_GENERATIONS):
        # 计算函数值
        decoded = translateDNA(pop)
        pred = F(decoded)

        # 计算适应度
        fitness = get_fitness(pred)

        # 选择适应度高的个体
        pop = select(pop, fitness)

        # 通过交叉变异选择新的染色体
        new_pop = np.empty_like(pop)
        for parent_index in range(POP_SIZE):
            parent = pop[parent_index]
            child = crossover(parent, pop)
            child = mutate(child)
            new_pop[parent_index] = child

        # 子代代替父代
        pop = new_pop

    # 获取最优解
    best_index = np.argmax(fitness)
    x = translateDNA(pop[best_index])  # 解码获得最优解

    # ********* End ********* #
    return x

# 测试函数（例：求解 f(x) = -x^2 + 5x）
def objective_function(x):
    return -x**2 + 5*x

# 执行遗传算法
optimal_solution = ga(objective_function)

第2关：遗传算法解决TSP问题

编程要求
在右侧编辑器补充代码，实现遗传算法。并求解商客旅行最短路线距离，城市坐标如下：

city = np.array([[0.01360298, 0.4581784 ],
[0.66441875, 0.46481977],
[0.55980498, 0.19154023],
[0.12535054, 0.16271053],
[0.47544932, 0.35714676],
[0.81562109, 0.63469573],
[0.77387573, 0.52801719],
[0.95461222, 0.47996912],
[0.14426016, 0.32351287],
[0.94679974, 0.23545779]])
城市分布图像如下：

测试说明
程序会调用你实现的遗传算法求解最短路径距离，若距离与正确距离差值低于0.1则视为通关，否则输出你所解的距离值。

开始你的任务吧，祝你成功！

#encoding=utf8
import numpy as np

DNA_size = 10  # 染色体大小
POP_size = 100  # 种群大小
CROSS_RATE = 0.1  # 交叉概率
MUTATE_RATE = 0.02  # 变异概率
N_GENERATIONS = 1000  # 进化次数

def translateDNA(DNA, city_position): 
    line_x = np.empty_like(DNA, dtype=np.float64)
    line_y = np.empty_like(DNA, dtype=np.float64)
    for i, d in enumerate(DNA):
        city_coord = city_position[d]
        line_x[i, :] = city_coord[:, 0]
        line_y[i, :] = city_coord[:, 1]
    return line_x, line_y

# 计算适应度与总距离
def get_fitness(line_x, line_y):
    total_distance = np.empty((line_x.shape[0],), dtype=np.float64)
    for i, (xs, ys) in enumerate(zip(line_x, line_y)):
        total_distance[i] = np.sum(np.sqrt(np.square(np.diff(xs)) + np.square(np.diff(ys))))
    fitness = np.exp(DNA_size * 2 / total_distance)  # 适应度与距离成反比
    return fitness, total_distance

# 选择适应度高的染色体
def select(pop, fitness):
    idx = np.random.choice(np.arange(POP_size), size=POP_size, replace=True, p=fitness / fitness.sum())
    return pop[idx]

# 交叉
def crossover(parent, pop):
    if np.random.rand() < CROSS_RATE:
        i_ = np.random.randint(0, POP_size, size=1)                        
        cross_points = np.random.randint(0, 2, DNA_size).astype(np.bool)   
        keep_city = parent[~cross_points]                                       
        swap_city = pop[i_, np.in1d(pop[i_].ravel(), keep_city, invert=True)]
        parent[:] = np.concatenate((keep_city, swap_city))
    return parent

# 变异
def mutate(child):
    for point in range(DNA_size):
        if np.random.rand() < MUTATE_RATE:
            swap_point = np.random.randint(0, DNA_size)
            swapA, swapB = child[point], child[swap_point]
            child[point], child[swap_point] = swapB, swapA
    return child

# 进化
def evolve(pop, fitness):
    pop = select(pop, fitness)
    pop_copy = pop.copy()
    for parent in pop:  
        child = crossover(parent, pop_copy)
        child = mutate(child)
        parent[:] = child
    return pop

def ga(city):
    '''
    city(ndarray):所有城市坐标
    distance(float):最短路线距离
    '''
    # ********* Begin ********* #
    # 初始化种群
    pop = np.random.permutation(np.tile(np.arange(DNA_size), (POP_size, 1)))

    # 进入进化循环
    for generation in range(N_GENERATIONS):
        # 获取每个城市横坐标与纵坐标
        line_x, line_y = translateDNA(pop, city)

        # 获取适应度与总距离
        fitness, total_distance = get_fitness(line_x, line_y)

        # 进化
        pop = evolve(pop, fitness)

        # 获取最大适应度索引
        best_idx = np.argmax(fitness)

        # 获取最短距离
        distance = total_distance[best_idx]

    # ********* End ********* #
    return distance