python遗传算法求解组合优化

### 遗传算法概述

遗传算法是一种模拟自然选择和遗传机制的元启发式搜索方法，适用于求解复杂优化问题。该算法基于种群进化概念，通过选择、交叉以及变异操作来探索可行解空间并逐渐逼近全局最优解[^1]。

### Python实现遗传算法框架

为了构建一个能够处理组合优化问题的基础遗传算法模型，以下是简化版本的主要组成部分：

#### 初始化参数设置

import random
from typing import List, Tuple

class GeneticAlgorithmConfig:
    def __init__(self,
                 population_size: int = 50,
                 mutation_rate: float = 0.01,
                 crossover_rate: float = 0.8,
                 elitism_count: int = 2,
                 generations: int = 100):
        """
        Initializes the genetic algorithm configuration.
        
        :param population_size: Number of individuals in each generation.
        :param mutation_rate: Probability that an individual will undergo mutation.
        :param crossover_rate: Probability that two parents will exchange genes during reproduction.
        :param elitism_count: Number of top performers to carry over into next generation without modification.
        :param generations: Total number of iterations or 'generations' for evolution process.
        """
        self.population_size = population_size
        self.mutation_rate = mutation_rate
        self.crossover_rate = crossover_rate
        self.elitism_count = elitism_count
        self.generations = generations

#### 定义个体类

class Individual:
    def __init__(self, chromosome_length: int):
        """Initializes a new instance with randomly generated chromosomes."""
        self.chromosome = [random.randint(0, 1) for _ in range(chromosome_length)]
    
    @property
    def fitness(self) -> float:
        """Calculates and returns this individual's fitness score based on its chromosome."""
        raise NotImplementedError("Fitness function must be defined.")

#### 创建初始种群

def create_initial_population(config: GeneticAlgorithmConfig, chromosome_length: int) -> List[Individual]:
    return [Individual(chromosome_length=chromosome_length) for _ in range(config.population_size)]

#### 实现选择算子

def select_parents(population: List[Individual], config: GeneticAlgorithmConfig) -> Tuple[List[int]]:
    parent_indices = []
    total_fitness = sum(individual.fitness for individual in population)
    probabilities = [(individual.fitness / total_fitness) for individual in population]

    while len(parent_indices) < (config.population_size - config.elitism_count):
        selected_index = weighted_random_choice(probabilities)
        if selected_index not in parent_indices:
            parent_indices.append(selected_index)

    elite_indices = sorted(range(len(population)), key=lambda i: population[i].fitness)[-config.elitism_count:]
    return tuple(elite_indices + parent_indices[:len(parent_indices)-config.elitism_count])

辅助函数`weighted_random_choice()`用于按权重随机选取索引：

def weighted_random_choice(weights: list[float]) -> int:
    cumulative_weights = []
    current_sum = 0
    for w in weights:
        current_sum += w
        cumulative_weights.append(current_sum)
    r = random.uniform(0, current_sum)
    selection = bisect.bisect_left(cumulative_weights, r)
    return selection

#### 设计交叉算子

def perform_crossover(parents: List[Tuple[int]], offspring: List[Individual]):
    for idx in range(0, len(offspring), 2):  # Iterate through pairs of children
        p1_idx, p2_idx = parents[idx % len(parents)], parents[(idx+1) % len(parents)]

        if random.random() <= config.crossover_rate:
            point = random.randint(1, len(offspring[p1_idx].chromosome)-2)
            
            child1_chrom = offspring[p1_idx].chromosome[:point] + offspring[p2_idx].chromosome[point:]
            child2_chrom = offspring[p2_idx].chromosome[:point] + offspring[p1_idx].chromosome[point:]

            offspring[p1_idx].chromosome[:] = child1_chrom[:]
            offspring[p2_idx].chromosome[:] = child2_chrom[:]

#### 应用变异算子

def apply_mutation(offspring: List[Individual], config: GeneticAlgorithmConfig):
    for indv in offspring:
        for gene_pos in range(len(indv.chromosome)):
            if random.random() < config.mutation_rate:
                indv.chromosome[gene_pos] ^= 1  # Flip bit value at position `gene_pos`.

#### 进化流程控制逻辑

def evolve(ga_config: GeneticAlgorithmConfig, problem_specific_setup=None):
    best_solution = None
    
    # Initialize first-generation population
    initial_pop = create_initial_population(ga_config, chromosome_length=problem_specific_setup['chromosome_length'])
    
    for gen_num in range(ga_config.generations):
        # Evaluate all solutions within current pop
        eval_results = evaluate_all(initial_pop, **problem_specific_setup)
        
        # Select mating pool from evaluated results using roulette wheel method
        chosen_pairs = select_parents(eval_results, ga_config)
        
        # Create empty array for storing newly created offsprings
        next_gen_offsprings = initialize_next_generation(eval_results[chosen_pair][0] for chosen_pair in chosen_pairs)
        
        # Perform crossovers between paired mates
        perform_crossover(chosen_pairs, next_gen_offsprings)
        
        # Apply mutations across entire set of potential survivors
        apply_mutation(next_gen_offsprings, ga_config)
        
        # Replace old population with updated one after applying elitist strategy
        update_population_with_elites_and_newbies(initial_pop, next_gen_offsprings, ga_config.elitism_count)
        
        # Track progress by keeping track of fittest member found so far
        record_best_found_so_far(best_solution, get_fittest_member_from_current_gen())
    
    return best_solution

上述代码片段展示了如何创建基本结构化的遗传算法模板，但请注意实际应用时还需要针对特定的应用场景调整细节，比如定义适应度评分标准(`evaluate_all`)、初始化新代群体(`initialize_next_generation`)等辅助功能的具体实现方式[^3]。