Partage de technologie

Algorithme génétique Python34 (GA)

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. Historique du développement

L'algorithme génétique (GA) est un algorithme d'optimisation inspiré de la sélection naturelle et de la génétique. Il a été proposé pour la première fois par le chercheur américain John Holland dans les années 1970, dans le but d'étudier l'adaptabilité des systèmes naturels et appliqué aux problèmes d'optimisation en informatique.

Historique de développement clé

  • 1975: John Holland a proposé pour la première fois le concept d'algorithme génétique dans son livre "Adaptation in Natural and Artificial Systems".

  • années 1980: Les algorithmes génétiques ont commencé à être utilisés dans des domaines tels que l'optimisation des fonctions et l'optimisation combinatoire, et ont progressivement attiré l'attention.

  • années 1990: Avec l'amélioration de la puissance de calcul des ordinateurs, les algorithmes génétiques ont été largement utilisés dans l'ingénierie, l'économie, la biologie et d'autres domaines.

  • Années 2000 à aujourd'hui: La théorie et l'application des algorithmes génétiques se sont développées davantage et une variété d'algorithmes améliorés ont émergé, tels que遗传编程(Programmation génétique)差分进化(Évolution différentielle) etc.

2. Principes mathématiques

L'algorithme génétique est une méthode de recherche aléatoire basée sur la sélection naturelle et la génétique. Son idée de base est de simuler le processus d'évolution biologique.choisir、croixetMutationsL'exploitation génère continuellement une nouvelle génération de populations, se rapprochant ainsi progressivement de la solution optimale.

Étapes de base de l'algorithme génétique

  1. initialisation: Générer aléatoirement la population initiale.

  2. choisir: Sélectionnez de meilleurs individus en fonction de leur fonction physique.

  3. croix: Créer un nouvel individu en échangeant une partie des gènes de l'individu parent.

  4. Mutations: Modifier aléatoirement certains gènes d'un individu.

  5. Répéter: Répétez les processus de sélection, de croisement et de mutation jusqu'à ce que la condition de terminaison soit remplie.

description mathématique

Supposons que la taille de la population soit N et que la longueur des chromosomes de chaque individu soit L. Le processus mathématique de l'algorithme génétique est le suivant :

  1. initialisation: Générer une population, où se trouve le chromosome.

  2. Calcul de condition physique: Calculez la valeur de condition physique de chaque individu.

  3. choisir: Sélectionnez les individus en fonction des valeurs de forme physique. Les méthodes couramment utilisées incluent la sélection à la roulette, la sélection en tournoi, etc.

  4. croix: Sélectionnez quelques individus pour une opération de croisement afin de générer de nouveaux individus.

  5. Mutations: Effectuer des opérations de mutation sur certains nouveaux individus pour générer des individus mutés.

  6. mettre à jour la population: Remplacer les anciens individus par de nouveaux individus pour former une nouvelle génération de population.

  7. Condition de résiliation: Si la condition de terminaison prédéfinie (telle que le nombre d'itérations ou le seuil de fitness) est atteinte, la solution optimale est générée.

3. Scénarios d'application

Les algorithmes génétiques ont été largement utilisés dans de nombreux domaines en raison de leur adaptabilité et de leur robustesse :

Optimisation de l'ingénierie

  • Optimisation structurelle: Conception d'une structure légère et à haute résistance.

  • Optimisation des paramètres: Ajustez les paramètres du système pour des performances optimales.

Économie et Finance

  • Optimisation du portefeuille: Allouer les actifs d’investissement pour maximiser les rendements.

  • prévision du marché: Prédire les cours des actions et les tendances du marché.

bioinformatique

  • Comparaison des séquences génétiques: Comparer et analyser des séquences d'ADN.

  • Prédiction de la structure des protéines: Prédire la structure tridimensionnelle d'une protéine.

apprentissage automatique

  • Formation aux réseaux de neurones: Optimiser les poids et la structure des réseaux de neurones.

  • Sélection de fonctionnalité: sélectionnez les fonctionnalités les plus utiles pour la classification ou la régression.

4. Implémentation visuelle d'exemples Python

image

L'exemple de code suivant implémente un algorithme génétique pour résoudre le problème du voyageur de commerce.旅行商问题(TSP) est un problème d'optimisation combinatoire classique qui vise à trouver le chemin le plus court permettant à un voyageur de commerce de visiter chaque ville d'un ensemble de villes donné exactement une fois et finalement de revenir à la ville de départ, c'est-à-dire de minimiser la distance totale de déplacement ou Coût, largement utilisé dans la logistique, la planification de la production et d'autres domaines.

Nous définissons d'abord toutes les capitales provinciales de Chine (y comprisTaipei, la capitale de la province chinoise de Taiwan) et ses données de coordonnées, et utiliser哈夫曼公式Calculez la distance entre deux points puis passez遗传算法Créez une population initiale, reproduisez, mute et générez la génération suivante, optimisez continuellement le chemin, et enfin enregistrez la distance et le chemin correspondant du chemin le plus court dans chaque génération, trouvez le chemin le plus court dans toutes les itérations et affichez-le visuellement sur la carte.Tous les emplacements de la ville、La forme physique change avec le nombre d'itérations En plus du trajet optimal, le résultat final montre le trajet le plus court depuis Chongqing à travers toutes les villes et sa distance totale. Au total, deux formations ont été effectuées. Le premier numéro d'itération était de 2 000 et la durée d'exécution était d'environ 3 minutes. Le deuxième numéro d'itération était fixé à 20 000 et la durée d'exécution était d'environ 15 minutes.

Pour résumer en une phrase : à partir de Chongqing, voyagez dans toutes les capitales provinciales de Chine et utilisez des algorithmes génétiques pour trouver le chemin le plus court. Voici l'implémentation du code :

  1. import numpy as np
  2. import matplotlib.pyplot as plt
  3. from mpl_toolkits.basemap import Basemap
  4. import random
  5. from math import radians, sin, cos, sqrt, atan2
  6.  
  7. # 设置随机种子以保证结果可重复
  8. random.seed(42)
  9. np.random.seed(42)
  10.  
  11. # 定义城市和坐标列表，包括台北
  12. cities = {
  13.     "北京": (39.9042, 116.4074),
  14.     "天津": (39.3434, 117.3616),
  15.     "石家庄": (38.0428, 114.5149),
  16.     "太原": (37.8706, 112.5489),
  17.     "呼和浩特": (40.8426, 111.7511),
  18.     "沈阳": (41.8057, 123.4315),
  19.     "长春": (43.8171, 125.3235),
  20.     "哈尔滨": (45.8038, 126.5349),
  21.     "上海": (31.2304, 121.4737),
  22.     "南京": (32.0603, 118.7969),
  23.     "杭州": (30.2741, 120.1551),
  24.     "合肥": (31.8206, 117.2272),
  25.     "福州": (26.0745, 119.2965),
  26.     "南昌": (28.6820, 115.8579),
  27.     "济南": (36.6512, 117.1201),
  28.     "郑州": (34.7466, 113.6254),
  29.     "武汉": (30.5928, 114.3055),
  30.     "长沙": (28.2282, 112.9388),
  31.     "广州": (23.1291, 113.2644),
  32.     "南宁": (22.8170, 108.3665),
  33.     "海口": (20.0174, 110.3492),
  34.     "重庆": (29.5638, 106.5507),
  35.     "成都": (30.5728, 104.0668),
  36.     "贵阳": (26.6477, 106.6302),
  37.     "昆明": (25.0460, 102.7097),
  38.     "拉萨": (29.6520, 91.1721),
  39.     "西安": (34.3416, 108.9398),
  40.     "兰州": (36.0611, 103.8343),
  41.     "西宁": (36.6171, 101.7782),
  42.     "银川": (38.4872, 106.2309),
  43.     "乌鲁木齐": (43.8256, 87.6168),
  44.     "台北": (25.032969, 121.565418)
  45. }
  46.  
  47. # 城市列表和坐标
  48. city_names = list(cities.keys())
  49. locations = np.array(list(cities.values()))
  50. chongqing_index = city_names.index("重庆")
  51.  
  52. # 使用哈夫曼公式计算两点间的距离
  53. def haversine(lat1, lon1, lat2, lon2):
  54.     R = 6371.0  # 地球半径，单位为公里
  55.     dlat = radians(lat2 - lat1)
  56.     dlon = radians(lon1 - lon2)
  57.     a = sin(dlat / 2)**2 + cos(radians(lat1)) * cos(radians(lat2)) * sin(dlon / 2)**2
  58.     c = 2 * atan2(sqrt(a), sqrt(1 - a))
  59.     distance = R * c
  60.     return distance
  61.  
  62. # 计算路径总距离的函数，单位为公里
  63. def calculate_distance(path):
  64.     return sum(haversine(locations[path[i]][0], locations[path[i]][1], locations[path[i + 1]][0], locations[path[i + 1]][1]) for i in range(len(path) - 1))
  65.  
  66. # 创建初始种群
  67. def create_initial_population(size, num_cities):
  68.     population = []
  69.     for _ in range(size):
  70.         individual = random.sample(range(num_cities), num_cities)
  71.         # 确保重庆为起点
  72.         individual.remove(chongqing_index)
  73.         individual.insert(0, chongqing_index)
  74.         population.append(individual)
  75.     return population
  76.  
  77. # 对种群进行排名
  78. def rank_population(population):
  79.     # 按照路径总距离对种群进行排序
  80.     return sorted([(i, calculate_distance(individual)) for i, individual in enumerate(population)], key=lambda x: x[1])
  81.  
  82. # 选择交配池
  83. def select_mating_pool(population, ranked_pop, elite_size):
  84.     # 选择排名前elite_size的个体作为交配池
  85.     return [population[ranked_pop[i][0]] for i in range(elite_size)]
  86.  
  87. # 繁殖新个体
  88. def breed(parent1, parent2):
  89.     # 繁殖两个父母生成新个体
  90.     geneA = int(random.random() * (len(parent1) - 1)) + 1
  91.     geneB = int(random.random() * (len(parent1) - 1)) + 1
  92.     start_gene = min(geneA, geneB)
  93.     end_gene = max(geneA, geneB)
  94.     child = parent1[:start_gene] + parent2[start_gene:end_gene] + parent1[end_gene:]
  95.     child = list(dict.fromkeys(child))
  96.     missing = set(range(len(parent1))) - set(child)
  97.     for m in missing:
  98.         child.append(m)
  99.     # 确保重庆为起点
  100.     child.remove(chongqing_index)
  101.     child.insert(0, chongqing_index)
  102.     return child
  103.  
  104. # 突变个体
  105. def mutate(individual, mutation_rate):
  106.     for swapped in range(1, len(individual) - 1):
  107.         if random.random() < mutation_rate:
  108.             swap_with = int(random.random() * (len(individual) - 1)) + 1
  109.             individual[swapped], individual[swap_with] = individual[swap_with], individual[swapped]
  110.     return individual
  111.  
  112. # 生成下一代
  113. def next_generation(current_gen, elite_size, mutation_rate):
  114.     ranked_pop = rank_population(current_gen)
  115.     mating_pool = select_mating_pool(current_gen, ranked_pop, elite_size)
  116.     children = []
  117.     length = len(mating_pool) - elite_size
  118.     pool = random.sample(mating_pool, len(mating_pool))
  119.     for i in range(elite_size):
  120.         children.append(mating_pool[i])
  121.     for i in range(length):
  122.         child = breed(pool[i], pool[len(mating_pool)-i-1])
  123.         children.append(child)
  124.     next_gen = [mutate(ind, mutation_rate) for ind in children]
  125.     return next_gen
  126.  
  127. # 遗传算法主函数
  128. def genetic_algorithm(population, pop_size, elite_size, mutation_rate, generations):
  129.     pop = create_initial_population(pop_size, len(population))
  130.     progress = [(0, rank_population(pop)[0][1], pop[0])]  # 记录每代的最短距离和代数
  131.     for i in range(generations):
  132.         pop = next_generation(pop, elite_size, mutation_rate)
  133.         best_route_index = rank_population(pop)[0][0]
  134.         best_distance = rank_population(pop)[0][1]
  135.         progress.append((i + 1, best_distance, pop[best_route_index]))
  136.     best_route_index = rank_population(pop)[0][0]
  137.     best_route = pop[best_route_index]
  138.     return best_route, progress
  139.  
  140. # 调整参数
  141. pop_size = 500       # 增加种群大小
  142. elite_size = 100     # 增加精英比例
  143. mutation_rate = 0.005 # 降低突变率
  144. generations = 20000   # 增加迭代次数
  145.  
  146. # 运行遗传算法
  147. best_route, progress = genetic_algorithm(city_names, pop_size, elite_size, mutation_rate, generations)
  148.  
  149. # 找到最短距离及其对应的代数
  150. min_distance = min(progress, key=lambda x: x[1])
  151. best_generation = min_distance[0]
  152. best_distance = min_distance[1]
  153.  
  154. # 图1：地图上显示城市位置
  155. fig1, ax1 = plt.subplots(figsize=(10, 10))
  156. m1 = Basemap(projection='merc', llcrnrlat=18, urcrnrlat=50, llcrnrlon=80, urcrnrlon=135, resolution='l', ax=ax1)
  157. m1.drawcoastlines()
  158. m1.drawcountries()
  159. m1.fillcontinents(color='lightgray', lake_color='aqua')
  160. m1.drawmapboundary(fill_color='aqua')
  161. for i, (lat, lon) in enumerate(locations):
  162.     x, y = m1(lon, lat)
  163.     m1.plot(x, y, 'bo')
  164.     ax1.text(x, y, str(i), fontsize=8)
  165. ax1.set_title('City Locations')
  166. plt.show()
  167.  
  168. # 图2：适应度随迭代次数变化
  169. fig2, ax2 = plt.subplots(figsize=(10, 5))
  170. ax2.plot([x[1] for x in progress])
  171. ax2.set_ylabel('Distance (km)')
  172. ax2.set_xlabel('Generation')
  173. ax2.set_title('Fitness over Iterations')
  174. # 在图中标注最短距离和对应代数
  175. ax2.annotate(f'Gen: {best_generation}nDist: {best_distance:.2f} km', 
  176.              xy=(best_generation, best_distance), 
  177.              xytext=(best_generation, best_distance + 100),
  178.              arrowprops=dict(facecolor='red', shrink=0.05))
  179. plt.show()
  180.  
  181. # 图3：显示最优路径
  182. fig3, ax3 = plt.subplots(figsize=(10, 10))
  183. m2 = Basemap(projection='merc', llcrnrlat=18, urcrnrlat=50, llcrnrlon=80, urcrnrlon=135, resolution='l', ax=ax3)
  184. m2.drawcoastlines()
  185. m2.drawcountries()
  186. m2.fillcontinents(color='lightgray', lake_color='aqua')
  187. m2.drawmapboundary(fill_color='aqua')
  188.  
  189. # 绘制最优路径和有向箭头
  190. for i in range(len(best_route) - 1):
  191.     x1, y1 = m2(locations[best_route[i]][1], locations[best_route[i]][0])
  192.     x2, y2 = m2(locations[best_route[i + 1]][1], locations[best_route[i + 1]][0])
  193.     m2.plot([x1, x2], [y1, y2], color='g', linewidth=1, marker='o')
  194.  
  195. # 只添加一个代表方向的箭头
  196. mid_index = len(best_route) // 2
  197. mid_x1, mid_y1 = m2(locations[best_route[mid_index]][1], locations[best_route[mid_index]][0])
  198. mid_x2, mid_y2 = m2(locations[best_route[mid_index + 1]][1], locations[best_route[mid_index + 1]][0])
  199. ax3.annotate('', xy=(mid_x2, mid_y2), xytext=(mid_x1, mid_y1), arrowprops=dict(facecolor='blue', shrink=0.05))
  200.  
  201. # 在最优路径图上绘制城市位置
  202. for i, (lat, lon) in enumerate(locations):
  203.     x, y = m2(lon, lat)
  204.     m2.plot(x, y, 'bo')
  205.     ax3.text(x, y, str(i), fontsize=8)
  206.  
  207. # 添加起点和终点标记
  208. start_x, start_y = m2(locations[best_route[0]][1], locations[best_route[0]][0])
  209. end_x, end_y = m2(locations[best_route[-1]][1], locations[best_route[-1]][0])
  210. ax3.plot(start_x, start_y, marker='^', color='red', markersize=15, label='Start (Chongqing)')  # 起点
  211. ax3.plot(end_x, end_y, marker='*', color='blue', markersize=15, label='End')   # 终点
  212.  
  213. # 添加总距离的图例
  214. ax3.legend(title=f'Total Distance: {best_distance:.2f} km')
  215.  
  216. ax3.set_title('Optimal Path')
  217. plt.show()
  218.

Visualisation de l'emplacement de toutes les capitales provinciales de Chine :

image

Le nombre d'itérations est de 2 000 (la distance la plus courte est de 31 594 kilomètres) :

Trouvez l'itération du chemin le plus court dans le processus d'itération historique et visualisez le chemin le plus court.

image

image

Cas 2 : Le nombre d'itérations est de 20 000 (la distance la plus courte obtenue est de 29 768 kilomètres)

Trouvez l'itération avec le chemin le plus court dans le processus d'itération historique et visualisez le chemin le plus court pour cette itération.

image

image

Le contenu ci-dessus est résumé à partir d'Internet. S'il est utile, veuillez le transmettre à la prochaine fois !

Profil personnel

Il se consacre à la recherche technologique depuis plus de 30 ans et maîtrise divers langages tels que java, linux, javascript, php, css, etc. Il a apporté de nombreuses contributions dans le domaine de l'open source. station de documentation pour les développeurs pour partager certains problèmes de développement technologique pour référence future.

mes coordonnées

Mail