Technology Sharing

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

1. Development History

Genetic Algorithm (GA) is an optimization algorithm inspired by natural selection and genetics. It was first proposed by American scholar John Holland in the 1970s to study adaptability in natural systems and apply it to optimization problems in computer science.

Key development history

• 1975: John Holland first proposed the concept of genetic algorithm in his book "Adaptation in Natural and Artificial Systems".

• 1980s: Genetic algorithms began to be applied in fields such as function optimization and combinatorial optimization, and gradually attracted attention.

• 1990s: With the improvement of computer computing power, genetic algorithms have been widely used in engineering, economics, biology and other fields.

• 2000s to present: The theory and application of genetic algorithms have been further developed, and many improved algorithms have emerged, such as遗传编程（Genetic Programming）、差分进化(Differential Evolution) and so on.

2. Mathematical principles

Genetic algorithm is a random search method based on natural selection and genetics. Its basic idea is to simulate the biological evolution process.choose、crossandMutationsOperation, continuously generating a new generation of population, thus gradually approaching the optimal solution.

The basic steps of genetic algorithm

1. initialization: Randomly generate the initial population.

2. choose: Select better individuals according to the fitness function.

3. cross: New individuals are produced by exchanging some genes of parent individuals.

4. Mutations: Randomly change some of an individual's genes.

5. Iteration: Repeat the selection, crossover, and mutation process until the termination condition is met.

Mathematical description

Assuming the population size is N and the chromosome length of each individual is L, the mathematical process of the genetic algorithm is as follows:

1. initialization: Generate a population , where is a chromosome.

2. Fitness calculation: Calculate the fitness value of each individual.

3. choose: Select individuals based on fitness values. Common methods include roulette selection, tournament selection, etc.

4. cross: Select some individuals for crossover operation to generate new individuals.

5. Mutations: Perform mutation operations on some new individuals to generate mutant individuals.

6. Update population: Replace old individuals with new ones to form a new generation of population.

7. Termination condition: If the preset termination condition (such as the number of iterations or fitness threshold) is reached, the optimal solution is output.

3. Application scenarios

Genetic algorithms have been widely used in many fields due to their adaptability and robustness:

Engineering Optimization

• Structural Optimization: Design lightweight and high-strength structure.

• Parameter optimization: Adjust system parameters for optimal performance.

Economics and Finance

• Portfolio Optimization: Allocate investment assets to maximize returns.

• market prediction: Predict stock prices and market trends.

Bioinformatics

• Gene sequence alignment: Perform DNA sequence comparison and analysis.

• Protein structure prediction: Predict the three-dimensional structure of proteins.

Machine Learning

• Neural network training: Optimize the weights and structure of neural networks.

• Feature Selection: Select the features that are most useful for classification or regression.

4. Visualization of Python Examples

The following code example implements a genetic algorithm that solves the traveling salesman problem.旅行商问题The Traveling Salesman Program (TSP) is a classic combinatorial optimization problem that aims to find the shortest path for a traveling salesman to visit each city in a given set of cities exactly once and eventually return to the starting city, that is, to minimize the total travel distance or cost. It is widely used in logistics, production scheduling and other fields.

We first define all provincial capital cities in China (includingTaipei, the capital of Taiwan Province of China) and their coordinates, and use哈夫曼公式Calculate the distance between two points, and then use遗传算法Create an initial population, reproduce, mutate and generate the next generation, continuously optimize the path, and finally record the distance and corresponding path of the shortest path in each generation, find the shortest path in all iterations, and visualize it on the mapAll city locations、Fitness changes with the number of iterationsThe final result shows the shortest path from Chongqing through all cities and its total distance. The training was conducted twice. The first training was conducted with 2000 iterations and a running time of about 3 minutes. The second training was conducted with 20000 iterations and a running time of about 15 minutes.

To sum it up in one sentence: Starting from Chongqing, travel to all the provincial capitals in China and use genetic algorithms to find the shortest path. The following is the code implementation:

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

Visualization of the locations of all provincial capitals in China:

The number of iterations is 2,000 (the shortest distance is 31,594 kilometers):

Find the iteration with the shortest path in the history of iterations and visualize the shortest path.

Case 2: The number of iterations is 20,000 (the shortest distance is 29,768 kilometers)

Find the iteration with the shortest path in the historical iteration process and visualize the shortest path of that iteration.

The above content is summarized from the Internet. If it is helpful, please forward it. See you next time!