Compartir tecnología

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

1. Historia del desarrollo

El algoritmo genético (GA) es un algoritmo de optimización inspirado en la selección natural y la genética. Fue propuesto por primera vez por el académico estadounidense John Holland en la década de 1970, con el objetivo de estudiar la adaptabilidad en sistemas naturales y aplicarlo a problemas de optimización en informática.

Historial de desarrollo clave

• 1975: John Holland propuso por primera vez el concepto de algoritmo genético en su libro "Adaptación en sistemas naturales y artificiales".

• década de 1980: Los algoritmos genéticos comenzaron a utilizarse en campos como la optimización de funciones y la optimización combinatoria, y gradualmente atrajeron la atención.

• década de 1990: Con la mejora de la potencia informática de las computadoras, los algoritmos genéticos se han utilizado ampliamente en ingeniería, economía, biología y otros campos.

• 2000 hasta el presente: La teoría y la aplicación de los algoritmos genéticos se han desarrollado aún más y han surgido una variedad de algoritmos mejorados, como遗传编程(Programación genética)差分进化(Evolución Diferencial) etc.

2. Principios matemáticos

El algoritmo genético es un método de búsqueda aleatoria basado en la selección natural y la genética. Su idea básica es simular el proceso de evolución biológica.elegir、cruzyMutacionesOperación, genera continuamente una nueva generación de poblaciones, acercándose así gradualmente a la solución óptima.

Pasos básicos del algoritmo genético.

1. inicialización: Genera aleatoriamente la población inicial.

2. elegir: Seleccione mejores individuos según su función física.

3. cruz: Crea un nuevo individuo intercambiando parte de los genes del individuo padre.

4. Mutaciones: Altera aleatoriamente algunos genes de un individuo.

5. Iterar: Repita los procesos de selección, cruce y mutación hasta que se cumpla la condición de terminación.

descripción matemática

Supongamos que el tamaño de la población es N y la longitud cromosómica de cada individuo es L. El proceso matemático del algoritmo genético es el siguiente:

1. inicialización: Genera población, donde está el cromosoma.

2. Cálculo de aptitud: Calcule el valor de aptitud de cada individuo.

3. elegir: Seleccione individuos según sus valores de condición física. Los métodos comúnmente utilizados incluyen la selección en la ruleta, la selección en torneos, etc.

4. cruz: Seleccione algunos individuos para la operación cruzada para generar nuevos individuos.

5. Mutaciones: Realice operaciones de mutación en algunos individuos nuevos para generar individuos mutados.

6. actualizar población: Reemplazar individuos antiguos con individuos nuevos para formar una nueva generación de población.

7. Condición de terminación: Si se alcanza la condición de terminación preestablecida (como el número de iteraciones o el umbral de aptitud), se genera la solución óptima.

3. Escenarios de aplicación

Los algoritmos genéticos se han utilizado ampliamente en muchos campos debido a su adaptabilidad y robustez:

Optimización de ingeniería

• Optimización estructural: Diseño de estructura liviana y de alta resistencia.

• Optimización de parámetros: Ajuste los parámetros del sistema para un rendimiento óptimo.

Economía y Finanzas

• Optimización de cartera: Asigne activos de inversión para maximizar la rentabilidad.

• predicción del mercado: Predecir los precios de las acciones y las tendencias del mercado.

bioinformática

• Comparación de secuencias genéticas: Comparar y analizar secuencias de ADN.

• Predicción de la estructura de las proteínas.: Predice la estructura tridimensional de una proteína.

aprendizaje automático

• Entrenamiento de redes neuronales: Optimizar los pesos y la estructura de las redes neuronales.

• Selección de características: seleccione las características que sean más beneficiosas para la clasificación o la regresión.

4. Implementación visual de ejemplos de Python.

El siguiente ejemplo de código implementa un algoritmo genético para resolver el problema del viajante.旅行商问题(TSP) es un problema de optimización combinatoria clásico que tiene como objetivo encontrar el camino más corto para que un viajante de comercio visite cada ciudad en un conjunto dado de ciudades exactamente una vez y finalmente regrese a la ciudad de partida, es decir, minimizar la distancia total de viaje o Costo, ampliamente utilizado en logística, programación de producción y otros campos.

Primero definimos todas las capitales de provincia de China (incluidasTaipei, capital de la provincia china de Taiwán) y sus datos de coordenadas, y utilizar哈夫曼公式Calcula la distancia entre dos puntos y luego pasa.遗传算法Cree una población inicial, reproduzca, mute y genere la próxima generación, optimice continuamente la ruta y finalmente registre la distancia y la ruta correspondiente de la ruta más corta en cada generación, encuentre la ruta más corta en todas las iteraciones y muéstrela visualmente en el mapa.Todas las ubicaciones de la ciudad、La aptitud cambia con el número de iteraciones. Además del camino óptimo, el resultado final muestra el camino más corto desde Chongqing a través de todas las ciudades y su distancia total. Se realizaron un total de dos entrenamientos. El primer número de iteración fue 2000 y el tiempo de ejecución fue de aproximadamente 3 minutos. El segundo número de iteración se estableció en 20000 y el tiempo de ejecución fue de aproximadamente 15 minutos.

Para resumir en una frase: comenzando desde Chongqing, viaje a todas las capitales de provincia de China y utilice algoritmos genéticos para encontrar el camino más corto. La siguiente es la implementación del código:

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

Visualización de la ubicación de todas las capitales de provincia de China:

El número de iteraciones es 2000 (la distancia más corta es 31594 kilómetros):

Encuentre la iteración del camino más corto en el proceso de iteración histórica y visualice el camino más corto.

Caso 2: El número de iteraciones es 20.000 (la distancia más corta obtenida es 29.768 kilómetros)

Encuentre la iteración con la ruta más corta en el proceso de iteración histórica y visualice la ruta más corta para esa iteración.

El contenido anterior está resumido de Internet. Si es útil, reenvíelo. ¡Hasta la próxima!