基于遗传算法的组合优化问题中避免重复选取的解决方案

问题核心 #

你当前的遗传算法实现中，交叉操作（cxTwoPoint）会破坏个体中索引的唯一性，导致同一人员被重复选取。初始个体用random.sample生成无重复索引，但交叉时直接交换片段会引入重复，最终导致选中的对照组出现重复样本。

解决方案 #

关键是使用适合无重复索引场景的遗传算子，同时保证计算效率：

1. 替换交叉算子为有序交叉（cxOrdered）：该算子专为排列/无重复元素的个体设计，交叉后会自动维持所有索引的唯一性，不会产生重复。
2. 保留洗牌变异（mutShuffleIndexes）：该算子仅打乱个体内索引的顺序，不会引入重复，适合当前场景。

修改后的代码 #

以下是调整核心部分后的完整代码，标注了修改点：

import pandas as pd
import numpy as np
from deap import base, creator, tools, algorithms
import random
import time

# Dictionary of configuration variables
CONFIG = {
    "file_path": 'C:/Python用/test1_GENIE.csv', #File path of read data
    "population_size": 1000, 
    "generations": 100, 
    "cxpb": 0.5, 
    "mutpb": 0.2, 
    "n_control": 2000, 
    "pass_threshold": 0.05, 
    "output_path": 'outputpath' 
}

# File path
file_path = CONFIG["file_path"]

# data load
data = pd.read_csv(file_path)

# Separate data into test and control groups
test_group = data[data['is_test'] == 1]
control_group = data[data['is_test'] == 0]

# Calculation of mean value agreement for each column
def calculate_match_rates_vectorized(test_group, control_group, columns):
    # Calculate the mean of the test and control groups for each column
    means_test = test_group[columns].mean()
    means_control = control_group[columns].mean()

    # Replace zero values with smaller numbers to avoid dividing by zero
    means_control[means_control == 0] = np.finfo(float).eps

    # Calculation of Match Ratio
    match_rates = abs(1 - (means_test / means_control))
    return match_rates


# Calculation of the evaluation function
columns = data.columns[3:]

# Genetic Algorithm Parameters
POPULATION_SIZE = CONFIG["population_size"]
GENERATIONS = CONFIG["generations"]
CXPB = CONFIG["cxpb"]
MUTPB = CONFIG["mutpb"]
N_CONTROL = CONFIG["n_control"]

# objective function
def evaluate(individual):
    # 可选调试：检查是否有重复索引（上线前可移除）
    # if len(set(individual)) != len(individual):
    #     raise ValueError("重复索引出现")
    selected_control_group = control_group.iloc[individual]
    match_rates = calculate_match_rates_vectorized(test_group, selected_control_group, columns)
    max_match_rate = max(match_rates)
    return (max_match_rate,)


# Genetic Algorithm Initialization
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)

toolbox = base.Toolbox()
toolbox.register("indices", random.sample, range(len(control_group)), N_CONTROL)
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.indices)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

toolbox.register("evaluate", evaluate)
# --- 修改点1：替换交叉算子为cxOrdered ---
toolbox.register("mate", tools.cxOrdered)
# --- 修改点2：保留mutShuffleIndexes（本身不会产生重复） ---
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)

# Record current time before algorithm execution
start_time = time.time()

# Running Genetic Algorithms
def main():
    random.seed(64)
    pop = toolbox.population(n=POPULATION_SIZE)
    hof = tools.HallOfFame(1)
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", np.mean)
    stats.register("min", np.min)
    stats.register("max", np.max)

    pop, log = algorithms.eaSimple(pop, toolbox, cxpb=CXPB, mutpb=MUTPB, ngen=GENERATIONS, 
                                   stats=stats, halloffame=hof, verbose=True)

    # Record the time after the algorithm is executed and calculate the execution time
    end_time = time.time()
    elapsed_time = end_time - start_time
    print(f"run time: {elapsed_time} sec")
    
    # Output the index of the best individuals of the last generation to a CSV file
    best_individual = hof[0]
    best_control_group = control_group.iloc[best_individual]
    output_path = CONFIG["output_path"]
    best_control_group.to_csv(output_path, index=False)

    # Display of success message
    print(f"Data has been successfully saved. Save to: {output_path}")
    
    return pop, log, hof

if __name__ == "__main__":
    pop, log, hof = main()

效率说明 #

• cxOrdered的时间复杂度与原cxTwoPoint一致，均为O(n)，对于2000长度的个体，不会明显降低计算效率。
• 无需额外的去重操作（如遍历检查重复），避免了不必要的性能开销。

内容的提问来源于stack exchange，提问作者Yosuke