C++实现的基本遗传算法框架来解决一维套料的示例代码

admin1

一维下料问题（也称为一维装箱问题或一维切割问题）是指如何从固定长度的原材料中切割出所需的各种尺寸的物品，使得浪费最少。遗传算法（GA）可以用来解决这类优化问题，通过模仿自然选择和遗传机制来搜索最优解。以下是一个基本的遗传算法框架用于解决一维下料问题的C++示例代码：

```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>

const int POPULATION_SIZE = 100;      // 种群大小
const int GENERATIONS = 1000;         // 迭代代数
const double MUTATION_RATE = 0.05;    // 变异率
const double CROSSOVER_RATE = 0.8;    // 交叉率

struct Individual {
    std::vector<int> genes;
    double fitness;
};

// 计算适应度函数
double calculateFitness(const std::vector<int>& genes, const std::vector<int>& lengths, int rawLength)
{
    int totalLength = 0;
    for (int i = 0; i < genes.size(); ++i)
        totalLength += lengths[i] * genes[i];
    return (rawLength * genes.size() - totalLength) * -1.0;
}

// 随机生成个体
Individual createIndividual(const std::vector<int>& lengths, int rawLength)
{
    Individual individual;
    individual.genes.resize(lengths.size());
    for (int i = 0; i < lengths.size(); ++i)
        individual.genes[i] = rand() % 10; // 随机生成基因
    individual.fitness = calculateFitness(individual.genes, lengths, rawLength);
    return individual;
}

// 创建初始种群
std::vector<Individual> createPopulation(int size, const std::vector<int>& lengths, int rawLength)
{
    std::vector<Individual> population(size);
    for (int i = 0; i < size; ++i)
        population[i] = createIndividual(lengths, rawLength);
    return population;
}

// 选择操作
Individual selection(const std::vector<Individual>& population)
{
    std::vector<double> fitnessSum;
    double sum = 0;
    for (const auto& individual : population)
    {
        sum += individual.fitness;
        fitnessSum.push_back(sum);
    }
   
    double randomFitness = static_cast<double>(rand()) / RAND_MAX * sum;
    auto it = std::upper_bound(fitnessSum.begin(), fitnessSum.end(), randomFitness);
    return population[std::distance(fitnessSum.begin(), it)];
}

// 交叉操作
std::pair<Individual, Individual> crossover(Individual parent1, Individual parent2)
{
    int crossPoint = rand() % parent1.genes.size();
    Individual child1 = parent1, child2 = parent2;
   
    for (int i = crossPoint; i < parent1.genes.size(); ++i)
    {
        child1.genes[i] = parent2.genes[i];
        child2.genes[i] = parent1.genes[i];
    }
   
    child1.fitness = calculateFitness(child1.genes, parent1.genes);
    child2.fitness = calculateFitness(child2.genes, parent2.genes);
   
    return {child1, child2};
}

// 变异操作
void mutate(Individual& individual)
{
    int geneIndex = rand() % individual.genes.size();
    individual.genes[geneIndex]++;
    individual.fitness = calculateFitness(individual.genes, individual.genes);
}

// 主遗传算法循环
std::vector<Individual> geneticAlgorithm(const std::vector<int>& lengths, int rawLength)
{
    std::vector<Individual> population = createPopulation(POPULATION_SIZE, lengths, rawLength);
    for (int gen = 0; gen < GENERATIONS; ++gen)
    {
        std::vector<Individual> newPopulation;
        
        while (newPopulation.size() < POPULATION_SIZE)
        {
            Individual parent1 = selection(population);
            Individual parent2 = selection(population);
            
            if (static_cast<double>(rand()) / RAND_MAX < CROSSOVER_RATE)
            {
                auto children = crossover(parent1, parent2);
                newPopulation.push_back(children.first);
                newPopulation.push_back(children.second);
            }
            else
            {
                newPopulation.push_back(parent1);
                newPopulation.push_back(parent2);
            }
            
            // 变异
            for (auto& individual : newPopulation)
            {
                if (static_cast<double>(rand()) / RAND_MAX < MUTATION_RATE)
                    mutate(individual);
            }
        }
        
        // 精英策略
        std::sort(newPopulation.begin(), newPopulation.end(), [](const Individual& a, const Individual& b){ return a.fitness > b.fitness; });
        population = newPopulation;
    }
   
    return population;
}

int main()
{
    srand(time(0)); // 设置随机数种子
    std::vector<int> lengths = {10, 20, 30}; // 物品长度
    int rawLength = 100; // 原材料长度

    std::vector<Individual> finalPopulation = geneticAlgorithm(lengths, rawLength);
   
    // 输出最优个体
    Individual best = *std::max_element(finalPopulation.begin(), finalPopulation.end(), [](const Individual& a, const Individual& b){ return a.fitness < b.fitness; });
    std::cout << "Best individual fitness: " << best.fitness << std::endl;
    std::cout << "Genes: ";
    for (int gene : best.genes)
        std::cout << gene << " ";
    std::cout << std::endl;
   
    return 0;
}
```

上述代码定义了一个遗传算法的框架，用于解决一维下料问题。它首先创建一个初始种群，然后执行多代进化，每一代包括选择、交叉和变异操作。最后输出最优个体，即能够从原材料中切割出所需物品且浪费最小的方案。

请注意，这个遗传算法示例是简化的，实际应用中可能需要更复杂的编码方式和更精细的参数调整来提高算法的性能和鲁棒性。例如，可能需要考虑基因编码的约束（比如，不允许切割出的物品长度超过原材料长度），以及更复杂的适应度函数和选择、交叉、变异策略。