技術共有

Python34 遺伝的アルゴリズム (GA)

2024-07-12

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

1. 開発経緯

遺伝的アルゴリズム (GA) は、自然選択と遺伝学にヒントを得た最適化アルゴリズムです。これは、自然システムにおける適応性を研究することを目的として、1970 年代にアメリカの学者ジョン ホランドによって最初に提案され、コンピューター サイエンスの最適化問題に適用されました。

主な開発の歴史

  • 1975年: ジョン・ホランドは、著書「自然および人工システムの適応」で遺伝的アルゴリズムの概念を初めて提案しました。

  • 1980年代：遺伝的アルゴリズムは関数最適化や組み合わせ最適化などの分野で使われ始め、徐々に注目を集めてきました。

  • 1990年代：コンピュータの計算能力の向上に伴い、遺伝的アルゴリズムは工学、経済学、生物学などの分野で広く使用されています。

  • 2000年代から現在まで：遺伝的アルゴリズムの理論と応用はさらに発展し、次のようなさまざまな改良されたアルゴリズムが登場しました。遗传编程（遺伝的プログラミング）、差分进化（差分進化）など

2. 数学的原理

遺伝的アルゴリズムは、自然選択と遺伝学に基づいたランダム検索手法であり、その基本的な考え方は、生物学的進化のプロセスをシミュレートすることです。選ぶ、クロスそして突然変異操作により、新しい世代の集団が継続的に生成され、それによって徐々に最適解に近づきます。

遺伝的アルゴリズムの基本的な手順

  1. 初期化: 初期集団をランダムに生成します。

  2. 選ぶ: フィットネス関数に基づいてより優れた個体を選択します。

  3. クロス：親個体の遺伝子の一部を交換して新しい個体を作ります。

  4. 突然変異：個体の一部の遺伝子をランダムに変更します。

  5. 反復する: 終了条件が満たされるまで、選択、交叉、突然変異のプロセスを繰り返します。

数学的記述

集団サイズを N、各個体の染色体長を L と仮定します。遺伝的アルゴリズムの数学的プロセスは次のとおりです。

  1. 初期化: 集団を生成します。ここで、 は染色体です。

  2. 体力計算：各個人の適応度値を計算します。

  3. 選ぶ: フィットネス値に基づいて個人を選択します。一般的に使用される方法には、ルーレット選択、トーナメント選択などが含まれます。

  4. クロス: いくつかの個体を選択して交叉操作を行い、新しい個体を生成します。

  5. 突然変異: いくつかの新しい個体に対して突然変異操作を実行し、突然変異した個体を生成します。

  6. 人口を更新する: 古い個体を新しい個体に置き換えて、新世代の個体群を形成します。

  7. 終了条件: あらかじめ設定した終了条件(反復回数や適応度閾値など)に達した場合に最適解を出力します。

3. 応用シナリオ

遺伝的アルゴリズムは、その適応性と堅牢性により、多くの分野で広く使用されています。

エンジニアリングの最適化

  • 構造の最適化：軽量かつ高強度な構造を設計。

  • パラメータの最適化: 最適なパフォーマンスが得られるようにシステム パラメータを調整します。

経済と金融

  • ポートフォリオの最適化: 収益を最大化するために投資資産を配分します。

  • 市場予測: 株価と市場動向を予測します。

バイオインフォマティクス

  • 遺伝子配列の比較: DNA 配列を比較および分析します。

  • タンパク質の構造予測: タンパク質の立体構造を予測します。

機械学習

  • ニューラルネットワークトレーニング: ニューラル ネットワークの重みと構造を最適化します。

  • 機能の選択: 分類または回帰に最も有益な特徴を選択します。

4. Python サンプルの視覚的な実装

写真

次のコード例は、巡回セールスマン問題を解決する遺伝的アルゴリズムを実装しています。旅行商问题(TSP) は古典的な組み合わせ最適化問題で、巡回セールスマンが指定された一連の都市の各都市を正確に 1 回訪問し、最終的に出発都市に戻るための最短経路を見つけること、つまり総移動距離を最小限に抑えることを目的としています。コスト。物流、生産スケジュール、その他の分野で広く使用されています。

まず、中国のすべての省都（省都を含む）を定義します。中国台湾省の首都、台北) とその座標データを使用し、哈夫曼公式2 点間の距離を計算して通過します遗传算法初期集団を作成し、再生産、突然変異を起こし、次の世代を生成し、パスを継続的に最適化して、最後に各世代の最短パスの距離と対応するパスを記録し、すべての反復で最短パスを見つけて地図上に視覚的に表示します。市内のすべての場所、反復回数に応じてフィットネスが変化する最適なパスだけでなく、最終結果には、重慶からすべての都市を通る最短パスとその合計距離が表示されます。合計 2 つのトレーニングが実行されました。最初の反復数は 2000 で、実行時間は約 3 分でした。2 番目の反復数は 20000 に設定され、実行時間は約 15 分でした。

一言で要約すると、重慶から出発して中国のすべての省都を訪れ、遺伝的アルゴリズムを使用して最短経路を見つけます。コードの実装は次のとおりです。

  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.

中国のすべての省都の位置の視覚化:

写真

反復数は 2,000 です (最短距離は 31594 キロメートル)。

過去の反復プロセスで最短パスの反復を見つけて、最短パスを視覚化します。

写真

写真

ケース 2: 反復回数は 20,000 です (取得された最短距離は 29,768 キロメートル)

過去の反復プロセスで最短パスを持つ反復を見つけて、その反復の最短パスを視覚化します。

写真

写真

上記の内容はインターネットからまとめたものです。お役に立ちましたら、また次回お楽しみください。

個人プロフィール

彼は 30 年以上テクノロジーの研究に専念しており、java、linux、javascript、php、css などのさまざまな言語に堪能であり、オープンソース分野で多くの貢献を行っています。将来の参考のために技術開発におけるいくつかの問題を共有する開発者ドキュメント ステーション。

プライベートな連絡先の最初の情報

送料