Python34 Genetic Algorithm (GA)

2024-07-12

1. Kehityshistoria

Genetic Algorithm (GA) on optimointialgoritmi, joka on saanut inspiraationsa luonnollisesta valinnasta ja genetiikasta. Amerikkalainen tutkija John Holland ehdotti sitä ensimmäisen kerran 1970-luvulla, ja sen tavoitteena oli tutkia sopeutumiskykyä luonnollisissa järjestelmissä ja sitä sovellettiin tietojenkäsittelytieteen optimointiongelmiin.

Keskeinen kehityshistoria

1975: John Holland ehdotti ensimmäisen kerran geneettisen algoritmin käsitettä kirjassaan "Adaptation in Natural and Artificial Systems".
1980-luku: Geneettisiä algoritmeja alettiin käyttää sellaisilla aloilla kuin toimintojen optimointi ja kombinatorinen optimointi, ja ne herättivät vähitellen huomiota.
1990-luku: Tietokoneiden laskentatehon parantuessa geneettisiä algoritmeja on käytetty laajalti tekniikassa, taloudessa, biologiassa ja muilla aloilla.
2000-luvulta nykypäivään: Geneettisten algoritmien teoria ja sovellus ovat kehittyneet edelleen, ja useita parannettuja algoritmeja on syntynyt, kuten esim.遗传编程(Geneettinen ohjelmointi).差分进化(Differential Evolution) jne.

2. Matemaattiset periaatteet

Geneettinen algoritmi on luonnonvalintaan ja genetiikkaan perustuva satunnaishakumenetelmä. Sen perusideana on simuloida biologista evoluutioprosessia.valita、ylittääjaMutaatiotKäyttö, jatkuvasti luoda uuden sukupolven populaatioita, jolloin vähitellen lähestyy optimaalista ratkaisua.

Geneettisen algoritmin perusvaiheet

alustus: Luo alkupopulaatio satunnaisesti.
valita: Valitse parempia yksilöitä kuntotoiminnan perusteella.
ylittää: Luo uusi yksilö vaihtamalla osa vanhemman yksilön geeneistä.
Mutaatiot: Muuta satunnaisesti joitain yksilön geenejä.
Toistaa: Toista valinta-, jako- ja mutaatioprosessit, kunnes lopetusehto täyttyy.

matemaattinen kuvaus

Oletetaan, että populaation koko on N ja kunkin yksilön kromosomin pituus on L. Geneettisen algoritmin matemaattinen prosessi on seuraava:

alustus: Luo populaatio, missä on kromosomi.
Kuntolaskenta: Laske jokaisen henkilön kunto-arvo.
valita: Valitse yksilöt kuntoarvojen perusteella. Yleisesti käytettyjä menetelmiä ovat ruletin valinta, turnausvalinta jne.
ylittää: Valitse joitakin yksilöitä jakotoimintoa varten luodaksesi uusia yksilöitä.
Mutaatiot: Suorita mutaatiotoimenpiteitä joillekin uusille yksilöille mutatoituneiden yksilöiden luomiseksi.
päivittää väestöä: Korvaa vanhat yksilöt uusilla yksilöillä uuden sukupolven muodostamiseksi.
Päättymisehto: Jos esiasetettu lopetusehto (kuten iteraatioiden määrä tai kuntokynnys) saavutetaan, tulostetaan optimaalinen ratkaisu.

3. Sovellusskenaariot

Geneettisiä algoritmeja on käytetty laajalti monilla aloilla niiden mukautuvuuden ja kestävyyden vuoksi:

Tekninen optimointi

Rakenneoptimointi: Suunnittele kevyt ja luja rakenne.
Parametrien optimointi: Säädä järjestelmän parametreja optimaalisen suorituskyvyn saavuttamiseksi.

Talous ja rahoitus

Portfolion optimointi: Kohdista sijoitusomaisuutta tuoton maksimoimiseksi.
markkinoiden ennuste: Ennusta osakekursseja ja markkinatrendejä.

bioinformatiikka

Geenisekvenssien vertailu: Vertaa ja analysoi DNA-sekvenssejä.
Proteiinirakenteen ennuste: Ennusta proteiinin kolmiulotteinen rakenne.

koneoppimista

Neuroverkkokoulutus: Optimoi hermoverkkojen painot ja rakenne.
Ominaisuuden valinta: Valitse ominaisuudet, joista on eniten hyötyä luokittelussa tai regressiossa.

4. Python-esimerkkien visuaalinen toteutus

Seuraava koodiesimerkki toteuttaa geneettisen algoritmin matkustavan myyjän ongelman ratkaisemiseksi.旅行商问题(TSP) on klassinen kombinatorinen optimointitehtävä, jonka tavoitteena on löytää lyhin reitti, jolla matkustava myyjä voi käydä tietyn kaupunkijoukon kussakin kaupungissa täsmälleen kerran ja palata lopulta lähtökaupunkiin, eli minimoimaan kokonaismatkan tai Kustannukset, joita käytetään laajalti logistiikassa, tuotannon aikatauluissa ja muilla aloilla.

Määrittelemme ensin kaikki Kiinan provinssien pääkaupungit (mukaan lukienTaipei, Kiinan Taiwanin maakunnan pääkaupunki) ja sen koordinaattitiedot ja käyttö哈夫曼公式Laske kahden pisteen välinen etäisyys ja ohita sitten遗传算法Luo alkuperäinen populaatio, kopioi, mutatoi ja luo seuraava sukupolvi, optimoi polku jatkuvasti ja lopuksi tallenna lyhimmän polun etäisyys ja vastaava polku jokaisessa sukupolvessa, etsi lyhin polku kaikissa iteraatioissa ja näytä se visuaalisesti kartallaKaikki kaupunkipaikat、Kunto muuttuu iteraatioiden määrän mukaan Optimaalisen polun lisäksi lopputulos näyttää lyhimmän polun Chongqingista kaikkien kaupunkien läpi ja sen kokonaisetäisyyden. Harjoituksia suoritettiin yhteensä kaksi. Ensimmäinen iteraatioluku oli 2000 ja suoritusaika oli noin 3 minuuttia.

Yhteenvetona yhteen lauseeseen: alkaen Chongqingista, matkusta kaikkiin Kiinan provinssien pääkaupunkeihin ja käytä geneettisiä algoritmeja löytääksesi lyhimmän polun. Seuraava on koodin toteutus:


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()