点击上方“进修编程”，选择“星标”公众号
超级无敌干货，第一时间送达！！！
人工智能 (AI) 彻底改变了我们解决问题和优化系统的方式。优化领域的两种流行方法是局部搜索优化 (LSO) 算法和遗传算法 (GA)。虽然两者都用于解决复杂问题，但它们的方法、用途和性能特征却有很大不同。
本文概述了人工智能中的遗传算法和局部搜索优化，并强调了两者之间的区别。
目录
遗传算法概述
局部搜索优化概述
遗传算法与局部搜索优化算法之间的差异
1. 搜索机制
2. 探索与利用
3.多样化的解决方案
4.计算的复杂性
5. 应用适用性
遗传算法与局部搜索优化的实现
导入所需库
生成随机城市
计算路线总距离
遗传算法
本地搜索优化
绘制路线
遗传算法概述
遗传算法 (GA)是一类受自然选择和遗传学原理启发的优化算法。它们特别适用于解决搜索空间大且复杂的复杂优化问题。遗传算法的关键组成部分包括：
总体：问题的一组潜在解决方案。
选择：根据个体的适应性从种群中选择个体来繁育下一代的过程。
交叉（重组）：将两个父级解决方案结合起来以产生后代。
突变：向个体引入小的随机变化以保持遗传多样性。
适应度函数：评估给定解决方案与最优方案的接近程度的函数。
GA 是迭代过程，涉及以下步骤：初始化、选择、交叉、变异和评估，重复进行直到满足终止标准，例如最大代数或令人满意的适应度水平。
局部搜索优化概述
局部搜索优化算法是一种迭代方法，它从初始解决方案开始，然后搜索其邻域以寻找更好的解决方案。它们对于组合优化问题特别有效，因为可以在局部有效地探索解决方案空间。主要特征包括：
初始解决方案：搜索的起点，可以随机选择或基于启发式方法。
邻域：通过对当前解决方案进行微小更改即可直接到达的一组解决方案。
评估：衡量解决方案质量的函数。
终止标准：算法停止的条件，例如固定的迭代次数或在一定数量的步骤中没有任何改进。
局部搜索方法包括爬山法、模拟退火法和禁忌搜索等技术，每种方法都有逃离局部最优并更有效地探索搜索空间的策略。
遗传算法与局部搜索优化算法之间的差异
虽然解决优化问题是遗传算法和局部搜索优化算法的共同目标，但它们的方法和特点存在显著差异。
1. 搜索机制
遗传算法 (GA)： GA 针对解决方案群体进行操作，同时检查解决方案空间的许多区域。通过采用这种基于群体的技术，GA 能够保留多样性并防止过早收敛到局部最优。
局部搜索优化： LSO 算法专注于检查当前答案周围的区域，每次只处理一个解决方案。虽然这种方法更直接，但更容易陷入局部最优。
2. 探索与利用
遗传算法：通过使用交叉和变异，遗传算法在开发和探索之间取得平衡。通过合并解决方案，交叉可以发现解决方案空间的新区域，而变异可以保留多样性并研究局部变体。
局部搜索优化： LSO 算法主要针对现有解决方案的邻近区域。它们使用移动运算符来调查邻近解决方案，但也可能需要其他技术（如模拟退火）来改进探索。
3.多样化的解决方案
遗传算法 (GA)：由于其基于种群的方法，GA 自然保留了广泛的解决方案，这有助于避免局部最优和深入的解决方案空间探索。
局部搜索优化 (LSO)方法可能会限制多样性，因为它们专注于单一解决方案。为了增加多样性，通常使用重新启动和从各种起始解决方案进行多次运行等策略。
4.计算的复杂性
遗传算法：由于遗传过程和每代对许多解决方案的检验，遗传算法的计算成本可能很高。但是，它们可以很好地并行化。
局部搜索优化：由于 LSO 算法每次评估和改进单个解决方案，因此它们通常具有更高的计算效率。虽然它们可以更快地识别局部最优，但它们可能需要更多次尝试才能摆脱它们。
5. 应用适用性
遗传算法：大型、不连续的解决方案空间非常适合解决复杂的多模态问题。在保持多样性至关重要的情况下，遗传算法效果很好。
局部搜索优化：当存在可靠的起始解决方案和相当平滑的解空间时，LSO 算法效果很好。在组合优化问题中，它们经常被使用。
遗传算法和局部搜索优化之间的主要区别
| 特征 | 遗传算法（GA） | 局部搜索优化 (LSO) |
|---|---|---|
| 搜索策略 | 基于人群 | 基于单一解决方案 |
| 初步解决方案 | 多个随机解决方案 | 单一初始解决方案 |
| 勘探 | 通过交叉和变异进行全局探索 | 附近地区的本地探索 |
| 优化 | 适合全局优化 | 通常用于局部优化 |
| 多样性 | 通过交叉和变异保持多样性 | 专注于改进单一解决方案 |
| 收敛 | 可以缓慢收敛 | 可以快速收敛到局部最优 |
| 逃生机制 | 变异和交叉有助于摆脱局部最优 | 模拟退火等策略有助于摆脱局部最优 |
| 复杂 | 由于种群和遗传操作导致计算成本更高 | 由于它适用于单一解决方案，因此计算成本较低 |
遗传算法与局部搜索优化的实现
在解决旅行商问题 (TSP) 等优化问题时，可以采用各种算法来找到最佳或接近最佳的解决方案。两种流行的方法是遗传算法 (GA) 和局部搜索优化 (LSO)。下面，我们将演示如何使用 Python 将这两种技术应用于 TSP。
导入所需库
首先，我们需要导入必要的库：
import numpy as npimport randomfrom scipy.spatial import distance_matriximport matplotlib.pyplot as plt
生成随机城市
我们首先为 TSP 生成随机城市：
# 生成随机城市def create_cities(num_cities):return np.random.rand(num_cities, 2)
计算路线总距离
为了评估路线的质量，我们计算其总距离：
# 计算路线的总距离def total_distance(route, dist_matrix):return sum(dist_matrix[route[i], route[i + 1]] for i in range(len(route) - 1)) + dist_matrix[route[-1], route[0]]
遗传算法
创建初始种群
初始种群是随机创建的：
# 创建初始人口def create_population(pop_size, num_cities):return [random.sample(range(num_cities), num_cities) for _ in range(pop_size)]
评估人口适应度
根据每条路线的总距离来评估适应度：
# 评估人口的适应度def assess_population(population, dist_matrix):return [total_distance(individual, dist_matrix) for individual inpopulation]
使用锦标赛选择法选择父代
我们使用锦标赛选择来选择交叉的父代：
# 选择：使用锦标赛选择选择父母def select_parents(population, fitness, tournature_size=3):selected = []for _ in range(len(population)):tournature = random.sample(list(zip(population, fitness)), tournature_size)selected.append(min(tournament, key=lambda x: x[1])[0])return selected
交叉和变异操作
我们执行有序交叉和交换变异：
# 交叉：有序交叉def crossover(parent1, parent2):size = len(parent1)start, end = sorted(random.sample(range(size), 2))child = [None] * sizechild[start:end] = parent1[start:end]ptr = endfor gene in parent2:if gene not in child:if ptr >= size:ptr = 0child[ptr] = geneptr += 1return child# 突变：交换突变def mutate(individual,mutation_rate=0.01):if random.random() <mutation_rate:i, j = random.sample(range(len(individual)), 2)individual[i], individual[j] = individual[j], individual[i]return individual
TSP 的遗传算法
遗传算法的主循环：
# Genetic Algorithm for TSPdef genetic_algorithm_tsp(cities, pop_size=100, num_generations=500, mutation_rate=0.01):dist_matrix = distance_matrix(cities, cities)population = create_population(pop_size, len(cities))for generation in range(num_generations):fitness = evaluate_population(population, dist_matrix)parents = select_parents(population, fitness)next_population = []for i in range(0, pop_size, 2):parent2 = random.sample(parents, 2)child1 = mutate(crossover(parent1, parent2), mutation_rate)child2 = mutate(crossover(parent2, parent1), mutation_rate)child2])population = next_populationbest_route = min(population, key=lambda ind: total_distance(ind, dist_matrix))return best_route, total_distance(best_route, dist_matrix)
局部搜索优化
局部搜索优化算法：
# Local Search Optimization for TSPdef local_search_tsp(cities, max_iterations=1000):dist_matrix = distance_matrix(cities, cities)def get_neighbors(route):neighbors = []for i in range(len(route)):for j in range(i + 1, len(route)):neighbor = route[:]neighbor[j] = neighbor[j], neighbor[i]neighbors.append(neighbor)return neighborsdef evaluate(route):return total_distance(route, dist_matrix)current_route = random.sample(range(len(cities)), len(cities))current_distance = evaluate(current_route)for iteration in range(max_iterations):neighbors = get_neighbors(current_route)next_route = min(neighbors, key=evaluate)next_distance = evaluate(next_route)if next_distance < current_distance:current_route = next_routecurrent_distance = next_distanceelse:breakreturn current_route, current_distance
绘制路线
最后，我们绘制路线来可视化结果：
# Function to plot the cities and the routedef plot_route(cities, route, title):plt.figure(figsize=(10, 6))plt.scatter(cities[:, 0], cities[:, 1], c='red')for i in range(len(route)):plt.plot([cities[route[i], 0], cities[route[(i + 1) % len(route)], 0]],[cities[route[i], 1], cities[route[(i + 1) % len(route)], 1]], 'b-')plt.title(title)plt.xlabel('X Coordinate')plt.ylabel('Y Coordinate')plt.show()
遗传算法与局部搜索优化的代码实现
import numpy as npimport randomfrom scipy.spatial import distance_matriximport matplotlib.pyplot as plt# Generate random citiesdef create_cities(num_cities):return np.random.rand(num_cities, 2)# Calculate the total distance of a routedef total_distance(route, dist_matrix):return sum(dist_matrix[route[i], route[i + 1]] for i in range(len(route) - 1)) + dist_matrix[route[-1], route[0]]# Create initial populationdef create_population(pop_size, num_cities):return [random.sample(range(num_cities), num_cities) for _ in range(pop_size)]# Evaluate fitness of the populationdef evaluate_population(population, dist_matrix):return [total_distance(individual, dist_matrix) for individual in population]# Selection: Select parents using tournament selectiondef select_parents(population, fitness, tournament_size=3):selected = []for _ in range(len(population)):tournament = random.sample(list(zip(population, fitness)), tournament_size)selected.append(min(tournament, key=lambda x: x[1])[0])return selected# Crossover: Ordered crossoverdef crossover(parent1, parent2):size = len(parent1)start, end = sorted(random.sample(range(size), 2))child = [None] * sizechild[start:end] = parent1[start:end]ptr = endfor gene in parent2:if gene not in child:if ptr >= size:ptr = 0child[ptr] = geneptr += 1return child# Mutation: Swap mutationdef mutate(individual, mutation_rate=0.01):if random.random() < mutation_rate:i, j = random.sample(range(len(individual)), 2)individual[i], individual[j] = individual[j], individual[i]return individual# Genetic Algorithm for TSPdef genetic_algorithm_tsp(cities, pop_size=100, num_generations=500, mutation_rate=0.01):dist_matrix = distance_matrix(cities, cities)population = create_population(pop_size, len(cities))for generation in range(num_generations):fitness = evaluate_population(population, dist_matrix)parents = select_parents(population, fitness)next_population = []for i in range(0, pop_size, 2):parent1, parent2 = random.sample(parents, 2)child1 = mutate(crossover(parent1, parent2), mutation_rate)child2 = mutate(crossover(parent2, parent1), mutation_rate)next_population.extend([child1, child2])population = next_populationbest_route = min(population, key=lambda ind: total_distance(ind, dist_matrix))return best_route, total_distance(best_route, dist_matrix)# Local Search Optimization for TSPdef local_search_tsp(cities, max_iterations=1000):dist_matrix = distance_matrix(cities, cities)def get_neighbors(route):neighbors = []for i in range(len(route)):for j in range(i + 1, len(route)):neighbor = route[:]neighbor[i], neighbor[j] = neighbor[j], neighbor[i]neighbors.append(neighbor)return neighborsdef evaluate(route):return total_distance(route, dist_matrix)current_route = random.sample(range(len(cities)), len(cities))current_distance = evaluate(current_route)for iteration in range(max_iterations):neighbors = get_neighbors(current_route)next_route = min(neighbors, key=evaluate)next_distance = evaluate(next_route)if next_distance < current_distance:current_route = next_routecurrent_distance = next_distanceelse:breakreturn current_route, current_distance# Function to plot the cities and the routedef plot_route(cities, route, title):plt.figure(figsize=(10, 6))plt.scatter(cities[:, 0], cities[:, 1], c='red')for i in range(len(route)):plt.plot([cities[route[i], 0], cities[route[(i + 1) % len(route)], 0]],[cities[route[i], 1], cities[route[(i + 1) % len(route)], 1]], 'b-')plt.title(title)plt.xlabel('X Coordinate')plt.ylabel('Y Coordinate')plt.show()# Generate random citiesnum_cities = 20cities = create_cities(num_cities)# Solve TSP using Genetic Algorithmbest_route_ga, best_distance_ga = genetic_algorithm_tsp(cities)print("Best route (GA):", best_route_ga)print("Best distance (GA):", best_distance_ga)# Solve TSP using Local Search Optimizationbest_route_lso, best_distance_lso = local_search_tsp(cities)print("Best route (LSO):", best_route_lso)print("Best distance (LSO):", best_distance_lso)# Plot the routesplot_route(cities, best_route_ga, f"Genetic Algorithm (Distance: {best_distance_ga:.2f})")plot_route(cities, best_route_lso, f"Local Search Optimization (Distance: {best_distance_lso:.2f})")
输出：
Best route (GA): [11, 16, 10, 1, 19, 5, 0, 14, 8, 13, 3, 18, 17, 12, 4, 9, 2, 7, 15, 6]Best distance (GA): 3.8821983753581844Best route (LSO): [14, 5, 10, 6, 15, 7, 9, 2, 11, 1, 19, 13, 18, 3, 17, 12, 4, 16, 8, 0]Best distance (LSO): 4.482746334228395
遗传算法
本地搜索优化
该代码演示了如何应用遗传算法和局部搜索优化来解决 TSP。遗传算法使用基于种群的交叉和变异方法，而局部搜索优化则依赖于探索当前解决方案的邻域。这两种方法各有优势，可以根据当前问题的具体要求进行选择。matlab\python程序设计找我
— 完 —
