遗传算法配送网络优化代码

遗传算法是一种模拟自然进化过程的优化算法，它通过模拟遗传、变异和选择等操作来搜索最优解。在配送网络优化中，遗传算法可以用于解决配送路径规划、车辆调度等问题。

以下是一个简单的遗传算法配送网络优化的代码示例：

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>

// 定义一个配送点的结构体
struct DeliveryPoint {
    int id;
    int x;
    int y;
};

// 计算两个配送点之间的距离
double calculateDistance(const DeliveryPoint& point1, const DeliveryPoint& point2) {
    int dx = point1.x - point2.x;
    int dy = point1.y - point2.y;
    return std::sqrt(dx*dx + dy*dy);
}

// 定义一个染色体（路径）的结构体
struct Chromosome {
    std::vector<int> genes;  // 基因序列，表示配送点的访问顺序
    double fitness;  // 适应度，表示路径的优劣程度
};

// 生成初始种群
std::vector<Chromosome> generateInitialPopulation(int populationSize, int numDeliveryPoints) {
    std::vector<Chromosome> population(populationSize);
    for (int i = 0; i < populationSize; ++i) {
        population[i].genes.resize(numDeliveryPoints);
        for (int j = 0; j < numDeliveryPoints; ++j) {
            population[i].genes[j] = j;
        }
        std::random_shuffle(population[i].genes.begin(), population[i].genes.end());
    }
    return population;
}

// 计算染色体的适应度
void calculateFitness(Chromosome& chromosome, const std::vector<DeliveryPoint>& deliveryPoints) {
    double totalDistance = 0.0;
    for (int i = 0; i < chromosome.genes.size() - 1; ++i) {
        int point1 = chromosome.genes[i];
        int point2 = chromosome.genes[i + 1];
        totalDistance += calculateDistance(deliveryPoints[point1], deliveryPoints[point2]);
    }
    chromosome.fitness = totalDistance;
}

// 选择操作，使用轮盘赌选择法
std::vector<Chromosome> selection(const std::vector<Chromosome>& population, int numSelections) {
    std::vector<Chromosome> selectedPopulation(numSelections);
    std::vector<double> fitnesses(population.size());
    double totalFitness = 0.0;
    for (int i = 0; i < population.size(); ++i) {
        fitnesses[i] = 1.0 / population[i].fitness;  // 适应度越小，距离越短，被选中的概率越大
        totalFitness += fitnesses[i];
    }
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_real_distribution<> dis(0.0, totalFitness);
    for (int i = 0; i < numSelections; ++i) {
        double r = dis(gen);
        double sum = 0.0;
        for (int j = 0; j < population.size(); ++j) {
            sum += fitnesses[j];
            if (sum >= r) {
                selectedPopulation[i] = population[j];
                break;
            }
        }
    }
    return selectedPopulation;
}

// 交叉操作，使用部分映射交叉法
void crossover(Chromosome& chromosome1, Chromosome& chromosome2) {
    int size = chromosome1.genes.size();
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(0, size - 1);
    int point1 = dis(gen);
    int point2 = dis(gen);
    if (point1 > point2) {
        std::swap(point1, point2);
    }
    std::vector<int> mapping(size, -1);
    for (int i = point1; i <= point2; ++i) {
        chromosome1.genes[i] = chromosome2.genes[i];
        mapping[chromosome2.genes[i]] = chromosome1.genes[i];
    }
    for (int i = 0; i < size; ++i) {
        if (i >= point1 && i <= point2) {
            continue;
        }
        int gene = chromosome1.genes[i];
        while (mapping[gene] != -1) {
            gene = mapping[gene];
        }
        chromosome1.genes[i] = gene;
    }
}

// 变异操作，使用交换变异法
void mutation(Chromosome& chromosome, double mutationRate) {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_real_distribution<> dis(0.0, 1.0);
    for (int i = 0; i < chromosome.genes.size(); ++i) {
        if (dis(gen) < mutationRate) {
            std::uniform_int_distribution<> dis2(i + 1, chromosome.genes.size() - 1);
            int j = dis2(gen);
            std::swap(chromosome.genes[i], chromosome.genes[j]);
        }
    }
}

// 遗传算法主函数
std::vector<int> geneticAlgorithm(const std::vector<DeliveryPoint>& deliveryPoints, int populationSize, int numGenerations, double mutationRate) {
    int numDeliveryPoints = deliveryPoints.size();
    std::vector<Chromosome> population = generateInitialPopulation(populationSize, numDeliveryPoints);
    for (int generation = 0; generation < numGenerations; ++generation) {
        for (int i = 0; i < populationSize; ++i) {
            calculateFitness(population[i], deliveryPoints);
        }
        std::sort(population.begin(), population.end(), [](const Chromosome& c1, const Chromosome& c2) {
            return c1.fitness < c2.fitness;
        });
        std::vector<Chromosome> selectedPopulation = selection(population, populationSize / 2);
        for (int i = 0; i < populationSize / 2; ++i) {
            crossover(selectedPopulation[i * 2], selectedPopulation[i * 2 + 1]);
        }
        for (int i = 0; i < populationSize / 2; ++i) {
            mutation(selectedPopulation[i], mutationRate);
        }
        population = selectedPopulation;
    }
    return population[0].genes;
}

int main() {
    // 假设有5个配送点，坐标分别为(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)
    std::vector<DeliveryPoint> deliveryPoints = {
        {0, 0, 0},
        {1, 1, 1},
        {2, 2, 2},
        {3, 3, 3},
        {4, 4, 4}
    };

    int populationSize = 100;
    int numGenerations = 100;
    double mutationRate = 0.01;

    std::vector<int> bestPath = geneticAlgorithm(deliveryPoints, populationSize, numGenerations, mutationRate);

    std::cout << "Best path: ";
    for (int i = 0; i < bestPath.size(); ++i) {
        std::cout << bestPath[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

这段代码实现了一个简单的遗传算法来优化配送网络中的路径。它首先生成一个初始种群，然后通过计算适应度、选择、交叉和变异等操作来不断优化种群，最终得到最优解。

请注意，这只是一个简单的示例代码，实际应用中可能需要根据具体问题进行修改和优化。另外，遗传算法的性能和结果可能会受到参数设置的影响，需要根据实际情况进行调整。