Κοινή χρήση τεχνολογίας

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

1. Ιστορικό ανάπτυξης

Ο γενετικός αλγόριθμος (GA) είναι ένας αλγόριθμος βελτιστοποίησης εμπνευσμένος από τη φυσική επιλογή και τη γενετική. Προτάθηκε για πρώτη φορά από τον Αμερικανό μελετητή John Holland στη δεκαετία του 1970, με στόχο να μελετήσει την προσαρμοστικότητα σε φυσικά συστήματα και να εφαρμοστεί σε προβλήματα βελτιστοποίησης στην επιστήμη των υπολογιστών.

Βασικό ιστορικό ανάπτυξης

• 1975: Ο John Holland πρότεινε για πρώτη φορά την έννοια του γενετικού αλγόριθμου στο βιβλίο του «Adaptation in Natural and Artificial Systems».

• δεκαετία του 1980: Οι γενετικοί αλγόριθμοι άρχισαν να χρησιμοποιούνται σε πεδία όπως η βελτιστοποίηση συναρτήσεων και η συνδυαστική βελτιστοποίηση και σταδιακά τράβηξαν την προσοχή.

• δεκαετία του 1990: Με τη βελτίωση της υπολογιστικής ισχύος των υπολογιστών, οι γενετικοί αλγόριθμοι έχουν χρησιμοποιηθεί ευρέως στη μηχανική, την οικονομία, τη βιολογία και άλλους τομείς.

• Δεκαετία 2000 έως σήμερα: Η θεωρία και η εφαρμογή των γενετικών αλγορίθμων έχουν αναπτυχθεί περαιτέρω και έχουν προκύψει μια ποικιλία βελτιωμένων αλγορίθμων, όπως π.χ.遗传编程(Γενετικός Προγραμματισμός)差分进化(Διαφορική Εξέλιξη) κ.λπ.

2. Μαθηματικές αρχές

Ο γενετικός αλγόριθμος είναι μια μέθοδος τυχαίας αναζήτησης που βασίζεται στη φυσική επιλογή και τη γενετική Η βασική του ιδέα είναι να προσομοιώσει τη διαδικασία της βιολογικής εξέλιξης.επιλέγω、σταυρόςκαιΜεταλλάξειςΛειτουργία, δημιουργεί συνεχώς μια νέα γενιά πληθυσμών, προσεγγίζοντας έτσι σταδιακά τη βέλτιστη λύση.

Βασικά βήματα γενετικού αλγορίθμου

1. αρχικοποίηση: Δημιουργήστε τυχαία τον αρχικό πληθυσμό.

2. επιλέγω: Επιλέξτε καλύτερα άτομα με βάση τη λειτουργία φυσικής κατάστασης.

3. σταυρός: Δημιουργήστε ένα νέο άτομο ανταλλάσσοντας μέρος των γονιδίων του γονικού ατόμου.

4. Μεταλλάξεις: Τυχαία αλλαγή ορισμένων γονιδίων ενός ατόμου.

5. επαναλέγω: Επαναλάβετε τις διαδικασίες επιλογής, διασταύρωσης και μετάλλαξης μέχρι να εκπληρωθεί η συνθήκη τερματισμού.

μαθηματική περιγραφή

Ας υποθέσουμε ότι το μέγεθος του πληθυσμού είναι N και το μήκος του χρωμοσώματος κάθε ατόμου είναι L. Η μαθηματική διαδικασία του γενετικού αλγορίθμου είναι η εξής:

1. αρχικοποίηση: Δημιουργία πληθυσμού , πού είναι το χρωμόσωμα.

2. Υπολογισμός φυσικής κατάστασης: Υπολογίστε την αξία φυσικής κατάστασης κάθε ατόμου.

3. επιλέγω: Επιλέξτε άτομα με βάση τις τιμές φυσικής κατάστασης Οι συνήθεις μέθοδοι που χρησιμοποιούνται περιλαμβάνουν την επιλογή ρουλέτας, την επιλογή τουρνουά κ.λπ.

4. σταυρός: Επιλέξτε ορισμένα άτομα για λειτουργία crossover για να δημιουργήσετε νέα άτομα.

5. Μεταλλάξεις: Εκτελέστε λειτουργίες μετάλλαξης σε ορισμένα νέα άτομα για να δημιουργήσετε μεταλλαγμένα άτομα.

6. ενημέρωση πληθυσμού: Αντικαταστήστε τα παλιά άτομα με νέα άτομα για να σχηματίσετε μια νέα γενιά πληθυσμού.

7. Προϋπόθεση τερματισμού: Εάν επιτευχθεί η προκαθορισμένη συνθήκη τερματισμού (όπως ο αριθμός επαναλήψεων ή το κατώφλι καταλληλότητας), η βέλτιστη λύση προκύπτει.

3. Σενάρια εφαρμογής

Οι γενετικοί αλγόριθμοι έχουν χρησιμοποιηθεί ευρέως σε πολλούς τομείς λόγω της προσαρμοστικότητας και της ευρωστίας τους:

Μηχανική βελτιστοποίηση

• Δομική βελτιστοποίηση: Σχεδιάστε ελαφριά και υψηλής αντοχής δομή.

• Βελτιστοποίηση παραμέτρων: Προσαρμόστε τις παραμέτρους του συστήματος για βέλτιστη απόδοση.

Οικονομικά και Χρηματοοικονομικά

• Βελτιστοποίηση χαρτοφυλακίου: Κατανομή επενδυτικών περιουσιακών στοιχείων για μεγιστοποίηση των αποδόσεων.

• πρόβλεψη αγοράς: Προβλέψτε τις τιμές των μετοχών και τις τάσεις της αγοράς.

βιοπληροφορικής

• Σύγκριση αλληλουχίας γονιδίων: Συγκρίνετε και αναλύστε αλληλουχίες DNA.

• Πρόβλεψη δομής πρωτεΐνης: Προβλέψτε την τρισδιάστατη δομή μιας πρωτεΐνης.

μηχανική μάθηση

• Εκπαίδευση νευρωνικών δικτύων: Βελτιστοποιήστε τα βάρη και τη δομή των νευρωνικών δικτύων.

• Επιλογή χαρακτηριστικών: Επιλέξτε τα χαρακτηριστικά που είναι πιο ωφέλιμα για ταξινόμηση ή παλινδρόμηση.

4. Οπτική υλοποίηση παραδειγμάτων Python

Το ακόλουθο παράδειγμα κώδικα υλοποιεί έναν γενετικό αλγόριθμο για την επίλυση του προβλήματος του πλανόδιου πωλητή.旅行商问题(TSP) είναι ένα κλασικό πρόβλημα συνδυαστικής βελτιστοποίησης που στοχεύει στην εύρεση της συντομότερης διαδρομής για έναν ταξιδιώτη πωλητή για να επισκεφθεί κάθε μία από ένα δεδομένο σύνολο πόλεων ακριβώς μία φορά και τελικά να επιστρέψει στην πόλη εκκίνησης, δηλαδή να ελαχιστοποιήσει τη συνολική απόσταση ταξιδιού ή το κόστος, ευρέως χρησιμοποιούνται στα logistics, στον προγραμματισμό παραγωγής και σε άλλους τομείς.

Αρχικά ορίζουμε όλες τις επαρχιακές πρωτεύουσες στην Κίνα (συμπεριλαμβανομένωνΤαϊπέι, πρωτεύουσα της επαρχίας Ταϊβάν της Κίνας) και τα δεδομένα συντεταγμένων και η χρήση τους哈夫曼公式Υπολογίστε την απόσταση μεταξύ δύο σημείων και μετά περάστε遗传算法Δημιουργήστε έναν αρχικό πληθυσμό, αναπαραγωγή, μετάλλαξη και δημιουργία της επόμενης γενιάς, βελτιστοποιήστε συνεχώς τη διαδρομή και τέλος καταγράψτε την απόσταση και την αντίστοιχη διαδρομή της συντομότερης διαδρομής σε κάθε γενιά, βρείτε τη συντομότερη διαδρομή σε όλες τις επαναλήψεις και εμφανίστε την οπτικά στον χάρτηΌλες οι τοποθεσίες της πόλης、Η φυσική κατάσταση αλλάζει με τον αριθμό των επαναλήψεων Εκτός από τη βέλτιστη διαδρομή, το τελικό αποτέλεσμα δείχνει τη συντομότερη διαδρομή από το Chongqing σε όλες τις πόλεις και τη συνολική απόσταση. Συνολικά δύο φορές εκπαίδευσης, ο πρώτος αριθμός επανάληψης είναι 2000, ο χρόνος εκτέλεσης είναι περίπου 3 λεπτά, ο δεύτερος αριθμός επανάληψης ορίζεται σε 20000, ο χρόνος εκτέλεσης είναι περίπου 15 λεπτά.

Για να συνοψίσουμε σε μια φράση: ξεκινώντας από το Chongqing, ταξιδέψτε σε όλες τις επαρχιακές πρωτεύουσες της Κίνας και χρησιμοποιήστε γενετικούς αλγόριθμους για να βρείτε το συντομότερο μονοπάτι. Ακολουθεί η υλοποίηση του κώδικα:

import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.basemap import Basemap
import random
from math import radians, sin, cos, sqrt, atan2
 
# 设置随机种子以保证结果可重复
random.seed(42)
np.random.seed(42)
 
# 定义城市和坐标列表，包括台北
cities = {
    "北京": (39.9042, 116.4074),
    "天津": (39.3434, 117.3616),
    "石家庄": (38.0428, 114.5149),
    "太原": (37.8706, 112.5489),
    "呼和浩特": (40.8426, 111.7511),
    "沈阳": (41.8057, 123.4315),
    "长春": (43.8171, 125.3235),
    "哈尔滨": (45.8038, 126.5349),
    "上海": (31.2304, 121.4737),
    "南京": (32.0603, 118.7969),
    "杭州": (30.2741, 120.1551),
    "合肥": (31.8206, 117.2272),
    "福州": (26.0745, 119.2965),
    "南昌": (28.6820, 115.8579),
    "济南": (36.6512, 117.1201),
    "郑州": (34.7466, 113.6254),
    "武汉": (30.5928, 114.3055),
    "长沙": (28.2282, 112.9388),
    "广州": (23.1291, 113.2644),
    "南宁": (22.8170, 108.3665),
    "海口": (20.0174, 110.3492),
    "重庆": (29.5638, 106.5507),
    "成都": (30.5728, 104.0668),
    "贵阳": (26.6477, 106.6302),
    "昆明": (25.0460, 102.7097),
    "拉萨": (29.6520, 91.1721),
    "西安": (34.3416, 108.9398),
    "兰州": (36.0611, 103.8343),
    "西宁": (36.6171, 101.7782),
    "银川": (38.4872, 106.2309),
    "乌鲁木齐": (43.8256, 87.6168),
    "台北": (25.032969, 121.565418)
}
 
# 城市列表和坐标
city_names = list(cities.keys())
locations = np.array(list(cities.values()))
chongqing_index = city_names.index("重庆")
 
# 使用哈夫曼公式计算两点间的距离
def haversine(lat1, lon1, lat2, lon2):
    R = 6371.0  # 地球半径，单位为公里
    dlat = radians(lat2 - lat1)
    dlon = radians(lon1 - lon2)
    a = sin(dlat / 2)**2 + cos(radians(lat1)) * cos(radians(lat2)) * sin(dlon / 2)**2
    c = 2 * atan2(sqrt(a), sqrt(1 - a))
    distance = R * c
    return distance
 
# 计算路径总距离的函数，单位为公里
def calculate_distance(path):
    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))
 
# 创建初始种群
def create_initial_population(size, num_cities):
    population = []
    for _ in range(size):
        individual = random.sample(range(num_cities), num_cities)
        # 确保重庆为起点
        individual.remove(chongqing_index)
        individual.insert(0, chongqing_index)
        population.append(individual)
    return population
 
# 对种群进行排名
def rank_population(population):
    # 按照路径总距离对种群进行排序
    return sorted([(i, calculate_distance(individual)) for i, individual in enumerate(population)], key=lambda x: x[1])
 
# 选择交配池
def select_mating_pool(population, ranked_pop, elite_size):
    # 选择排名前elite_size的个体作为交配池
    return [population[ranked_pop[i][0]] for i in range(elite_size)]
 
# 繁殖新个体
def breed(parent1, parent2):
    # 繁殖两个父母生成新个体
    geneA = int(random.random() * (len(parent1) - 1)) + 1
    geneB = int(random.random() * (len(parent1) - 1)) + 1
    start_gene = min(geneA, geneB)
    end_gene = max(geneA, geneB)
    child = parent1[:start_gene] + parent2[start_gene:end_gene] + parent1[end_gene:]
    child = list(dict.fromkeys(child))
    missing = set(range(len(parent1))) - set(child)
    for m in missing:
        child.append(m)
    # 确保重庆为起点
    child.remove(chongqing_index)
    child.insert(0, chongqing_index)
    return child
 
# 突变个体
def mutate(individual, mutation_rate):
    for swapped in range(1, len(individual) - 1):
        if random.random() < mutation_rate:
            swap_with = int(random.random() * (len(individual) - 1)) + 1
            individual[swapped], individual[swap_with] = individual[swap_with], individual[swapped]
    return individual
 
# 生成下一代
def next_generation(current_gen, elite_size, mutation_rate):
    ranked_pop = rank_population(current_gen)
    mating_pool = select_mating_pool(current_gen, ranked_pop, elite_size)
    children = []
    length = len(mating_pool) - elite_size
    pool = random.sample(mating_pool, len(mating_pool))
    for i in range(elite_size):
        children.append(mating_pool[i])
    for i in range(length):
        child = breed(pool[i], pool[len(mating_pool)-i-1])
        children.append(child)
    next_gen = [mutate(ind, mutation_rate) for ind in children]
    return next_gen
 
# 遗传算法主函数
def genetic_algorithm(population, pop_size, elite_size, mutation_rate, generations):
    pop = create_initial_population(pop_size, len(population))
    progress = [(0, rank_population(pop)[0][1], pop[0])]  # 记录每代的最短距离和代数
    for i in range(generations):
        pop = next_generation(pop, elite_size, mutation_rate)
        best_route_index = rank_population(pop)[0][0]
        best_distance = rank_population(pop)[0][1]
        progress.append((i + 1, best_distance, pop[best_route_index]))
    best_route_index = rank_population(pop)[0][0]
    best_route = pop[best_route_index]
    return best_route, progress
 
# 调整参数
pop_size = 500       # 增加种群大小
elite_size = 100     # 增加精英比例
mutation_rate = 0.005 # 降低突变率
generations = 20000   # 增加迭代次数
 
# 运行遗传算法
best_route, progress = genetic_algorithm(city_names, pop_size, elite_size, mutation_rate, generations)
 
# 找到最短距离及其对应的代数
min_distance = min(progress, key=lambda x: x[1])
best_generation = min_distance[0]
best_distance = min_distance[1]
 
# 图1：地图上显示城市位置
fig1, ax1 = plt.subplots(figsize=(10, 10))
m1 = Basemap(projection='merc', llcrnrlat=18, urcrnrlat=50, llcrnrlon=80, urcrnrlon=135, resolution='l', ax=ax1)
m1.drawcoastlines()
m1.drawcountries()
m1.fillcontinents(color='lightgray', lake_color='aqua')
m1.drawmapboundary(fill_color='aqua')
for i, (lat, lon) in enumerate(locations):
    x, y = m1(lon, lat)
    m1.plot(x, y, 'bo')
    ax1.text(x, y, str(i), fontsize=8)
ax1.set_title('City Locations')
plt.show()
 
# 图2：适应度随迭代次数变化
fig2, ax2 = plt.subplots(figsize=(10, 5))
ax2.plot([x[1] for x in progress])
ax2.set_ylabel('Distance (km)')
ax2.set_xlabel('Generation')
ax2.set_title('Fitness over Iterations')
# 在图中标注最短距离和对应代数
ax2.annotate(f'Gen: {best_generation}nDist: {best_distance:.2f} km', 
             xy=(best_generation, best_distance), 
             xytext=(best_generation, best_distance + 100),
             arrowprops=dict(facecolor='red', shrink=0.05))
plt.show()
 
# 图3：显示最优路径
fig3, ax3 = plt.subplots(figsize=(10, 10))
m2 = Basemap(projection='merc', llcrnrlat=18, urcrnrlat=50, llcrnrlon=80, urcrnrlon=135, resolution='l', ax=ax3)
m2.drawcoastlines()
m2.drawcountries()
m2.fillcontinents(color='lightgray', lake_color='aqua')
m2.drawmapboundary(fill_color='aqua')
 
# 绘制最优路径和有向箭头
for i in range(len(best_route) - 1):
    x1, y1 = m2(locations[best_route[i]][1], locations[best_route[i]][0])
    x2, y2 = m2(locations[best_route[i + 1]][1], locations[best_route[i + 1]][0])
    m2.plot([x1, x2], [y1, y2], color='g', linewidth=1, marker='o')
 
# 只添加一个代表方向的箭头
mid_index = len(best_route) // 2
mid_x1, mid_y1 = m2(locations[best_route[mid_index]][1], locations[best_route[mid_index]][0])
mid_x2, mid_y2 = m2(locations[best_route[mid_index + 1]][1], locations[best_route[mid_index + 1]][0])
ax3.annotate('', xy=(mid_x2, mid_y2), xytext=(mid_x1, mid_y1), arrowprops=dict(facecolor='blue', shrink=0.05))
 
# 在最优路径图上绘制城市位置
for i, (lat, lon) in enumerate(locations):
    x, y = m2(lon, lat)
    m2.plot(x, y, 'bo')
    ax3.text(x, y, str(i), fontsize=8)
 
# 添加起点和终点标记
start_x, start_y = m2(locations[best_route[0]][1], locations[best_route[0]][0])
end_x, end_y = m2(locations[best_route[-1]][1], locations[best_route[-1]][0])
ax3.plot(start_x, start_y, marker='^', color='red', markersize=15, label='Start (Chongqing)')  # 起点
ax3.plot(end_x, end_y, marker='*', color='blue', markersize=15, label='End')   # 终点
 
# 添加总距离的图例
ax3.legend(title=f'Total Distance: {best_distance:.2f} km')
 
ax3.set_title('Optimal Path')
plt.show()
 

Οπτικοποίηση τοποθεσίας όλων των επαρχιακών πρωτευουσών στην Κίνα:

Ο αριθμός των επαναλήψεων είναι 2.000 (η μικρότερη απόσταση είναι 31594 χιλιόμετρα):

Βρείτε την επανάληψη της συντομότερης διαδρομής στη διαδικασία ιστορικής επανάληψης και οραματιστείτε τη συντομότερη διαδρομή.

Περίπτωση 2: Ο αριθμός των επαναλήψεων είναι 20.000 (η μικρότερη απόσταση που επιτυγχάνεται είναι 29.768 χιλιόμετρα)

Βρείτε την επανάληψη με τη συντομότερη διαδρομή στη διαδικασία ιστορικής επανάληψης και οραματιστείτε τη συντομότερη διαδρομή για αυτήν την επανάληψη.

Το παραπάνω περιεχόμενο συνοψίζεται από το Διαδίκτυο, εάν είναι χρήσιμο, προωθήστε το την επόμενη φορά.