头歌——人工智能（遗传算法）

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

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

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

函数图像如下：

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

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

#encoding=utf8
import numpy as npDNA_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 0return childdef 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 npDNA_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, swapAreturn 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[:] = childreturn popdef 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