套料遗传算法（Bin Packing Genetic Algorithm）

admin

1. 套料遗传算法（Bin Packing Genetic Algorithm）是一种用于解决套料问题的优化算法。套料问题是指将一组物品尽可能有效地放入一组容器中，使得容器的利用率最高。
3. 以下是一个简单的套料遗传算法的C++代码示例：
5. cpp
6. #include <iostream>
7. #include <vector>
8. #include <algorithm>
9. #include <random>
11. // 定义物品结构体
12. struct Item {
13.     int id;
14.     int size;
15. };
17. // 定义容器结构体
18. struct Bin {
19.     int id;
20.     int capacity;
21.     std::vector<Item> items;
22. };
24. // 遗传算法参数
25. const int POPULATION采用SIZE = 100; // 种群大小
26. const int MAX采用GENERATIONS = 100; // 最大迭代次数
27. const double MUTATION采用RATE = 0.1; // 变异率
29. // 随机数生成器
30. std::random采用device rd;
31. std::mt19937 gen(rd());
32. std::uniform采用real采用distribution<> dis(0.0, 1.0);
34. // 计算容器利用率
35. double calculateFitness(const Bin& bin) {
36.     int totalSize = 0;
37.     for (const auto& item : bin.items) {
38.         totalSize += item.size;
39.     }
40.     return static采用cast<double>(totalSize) / bin.capacity;
41. }
43. // 初始化种群
44. std::vector<Bin> initializePopulation(int numBins, const std::vector<Item>& items) {
45.     std::vector<Bin> population;
46.     for (int i = 0; i < POPULATION采用SIZE; ++i) {
47.         Bin bin;
48.         bin.id = i;
49.         bin.capacity = numBins;
50.         population.push采用back(bin);
51.     }
52.     return population;
53. }
55. // 选择操作
56. std::vector<Bin> selection(const std::vector<Bin>& population) {
57.     std::vector<Bin> selectedPopulation;
58.     for (int i = 0; i < POPULATION采用SIZE; ++i) {
59.         int index1 = static采用cast<int>(dis(gen) * POPULATION采用SIZE);
60.         int index2 = static采用cast<int>(dis(gen) * POPULATION采用SIZE);
61.         selectedPopulation.push采用back(population[index1].items.size() > population[index2].items.size() ? population[index1] : population[index2]);
62.     }
63.     return selectedPopulation;
64. }
66. // 交叉操作
67. std::vector<Bin> crossover(const std::vector<Bin>& population) {
68.     std::vector<Bin> offspringPopulation;
69.     for (int i = 0; i < POPULATION采用SIZE; i += 2) {
70.         Bin parent1 = population[i];
71.         Bin parent2 = population[i + 1];
72.         Bin offspring1 = parent1;
73.         Bin offspring2 = parent2;
74.         int crossoverPoint = static采用cast<int>(dis(gen) * parent1.items.size());
75.         offspring1.items.insert(offspring1.items.end(), parent2.items.begin() + crossoverPoint, parent2.items.end());
76.         offspring2.items.insert(offspring2.items.end(), parent1.items.begin() + crossoverPoint, parent1.items.end());
77.         offspringPopulation.push采用back(offspring1);
78.         offspringPopulation.push采用back(offspring2);
79.     }
80.     return offspringPopulation;
81. }
83. // 变异操作
84. void mutation(std::vector<Bin>& population) {
85.     for (auto& bin : population) {
86.         for (auto& item : bin.items) {
87.             if (dis(gen) < MUTATION采用RATE) {
88.                 item.size = static采用cast<int>(dis(gen) * bin.capacity);
89.             }
90.         }
91.     }
92. }
94. // 打印最优解
95. void printBestSolution(const std::vector<Bin>& population) {
96.     double bestFitness = 0.0;
97.     const Bin* bestBin = nullptr;
98.     for (const auto& bin : population) {
99.         double fitness = calculateFitness(bin);
100.         if (fitness > bestFitness) {
101.             bestFitness = fitness;
102.             bestBin = &bin;
103.         }
104.     }
105.     std::cout << "Best solution: ";
106.     if (bestBin != nullptr) {
107.         for (const auto& item : bestBin->items) {
108.             std::cout << item.id << " ";
109.         }
110.     }
111.     std::cout << std::endl;
112. }
114. int main() {
115.     // 初始化物品
116.     std::vector<Item> items = {
117.         {1, 10},
118.         {2, 20},
119.         {3, 30},
120.         // ...
121.     };
123.     // 初始化种群
124.     std::vector<Bin> population = initializePopulation(100, items);
126.     // 迭代
127.     for (int generation = 0; generation < MAX采用GENERATIONS; ++generation) {
128.         // 选择
129.         std::vector<Bin> selectedPopulation = selection(population);
131.         // 交叉
132.         std::vector<Bin> offspringPopulation = crossover(selectedPopulation);
134.         // 变异
135.         mutation(offspringPopulation);
137.         // 更新种群
138.         population = offspringPopulation;
140.         // 输出最优解
141.         printBestSolution(population);
142.     }
144.     return 0;
145. }
146. 这段代码实现了一个简单的套料遗传算法，其中包括初始化种群、选择、交叉、变异等操作，并输出每一代的最优解。你可以根据实际需求进行修改和扩展。

复制代码

admin

1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4. #include <random>
6. // 定义材料的结构体
7. struct Material {
8.     int length;
9.     int demand;
10. };
12. // 定义染色体的结构体
13. struct Chromosome {
14.     std::vector<int> genes;
15.     int fitness;
16. };
18. // 初始化种群
19. std::vector<Chromosome> initializePopulation(int populationSize, int geneSize) {
20.     std::vector<Chromosome> population;
21.     for (int i = 0; i < populationSize; i++) {
22.         Chromosome chromosome;
23.         chromosome.genes.resize(geneSize);
24.         for (int j = 0; j < geneSize; j++) {
25.             chromosome.genes[j] = rand() % 2; // 随机生成0或1
26.         }
27.         chromosome.fitness = 0;
28.         population.push采用back(chromosome);
29.     }
30.     return population;
31. }
33. // 计算染色体的适应度
34. void calculateFitness(Chromosome& chromosome, const std::vector<Material>& materials, int targetLength) {
35.     int totalLength = 0;
36.     int totalDemand = 0;
37.     for (int i = 0; i < chromosome.genes.size(); i++) {
38.         if (chromosome.genes[i] == 1) {
39.             totalLength += materials[i].length;
40.             totalDemand += materials[i].demand;
41.         }
42.     }
43.     chromosome.fitness = (totalLength >= targetLength) ? totalDemand : 0;
44. }
46. // 选择操作
47. std::vector<Chromosome> selection(const std::vector<Chromosome>& population, int tournamentSize) {
48.     std::vector<Chromosome> selectedPopulation;
49.     for (int i = 0; i < population.size(); i++) {
50.         std::vector<int> tournamentIndices;
51.         for (int j = 0; j < tournamentSize; j++) {
52.             int index = rand() % population.size();
53.             tournamentIndices.push采用back(index);
54.         }
55.         int maxFitness = -1;
56.         int maxIndex = -1;
57.         for (int j = 0; j < tournamentIndices.size(); j++) {
58.             int index = tournamentIndices[j];
59.             if (population[index].fitness > maxFitness) {
60.                 maxFitness = population[index].fitness;
61.                 maxIndex = index;
62.             }
63.         }
64.         selectedPopulation.push采用back(population[maxIndex]);
65.     }
66.     return selectedPopulation;
67. }
69. // 交叉操作
70. std::vector<Chromosome> crossover(const std::vector<Chromosome>& population, double crossoverRate) {
71.     std::vector<Chromosome> offspringPopulation;
72.     for (int i = 0; i < population.size(); i += 2) {
73.         Chromosome parent1 = population[i];
74.         Chromosome parent2 = population[i + 1];
75.         Chromosome offspring1 = parent1;
76.         Chromosome offspring2 = parent2;
77.         if (rand() / double(RAND采用MAX) < crossoverRate) {
78.             int crossoverPoint = rand() % parent1.genes.size();
79.             for (int j = crossoverPoint; j < parent1.genes.size(); j++) {
80.                 offspring1.genes[j] = parent2.genes[j];
81.                 offspring2.genes[j] = parent1.genes[j];
82.             }
83.         }
84.         offspringPopulation.push采用back(offspring1);
85.         offspringPopulation.push采用back(offspring2);
86.     }
87.     return offspringPopulation;
88. }
90. // 变异操作
91. void mutation(std::vector<Chromosome>& population, double mutationRate) {
92.     for (int i = 0; i < population.size(); i++) {
93.         for (int j = 0; j < population[i].genes.size(); j++) {
94.             if (rand() / double(RAND采用MAX) < mutationRate) {
95.                 population[i].genes[j] = 1 - population[i].genes[j]; // 变异
96.             }
97.         }
98.     }
99. }
101. // 打印最优解
102. void printBestSolution(const std::vector<Chromosome>& population, const std::vector<Material>& materials, int targetLength) {
103.     int maxFitness = -1;
104.     int maxIndex = -1;
105.     for (int i = 0; i < population.size(); i++) {
106.         if (population[i].fitness > maxFitness) {
107.             maxFitness = population[i].fitness;
108.             maxIndex = i;
109.         }
110.     }
111.     std::cout << "Best solution: ";
112.     for (int i = 0; i < population[maxIndex].genes.size(); i++) {
113.         if (population[maxIndex].genes[i] == 1) {
114.             std::cout << "Material " << i + 1 << " (Length: " << materials[i].length << ", Demand: " << materials[i].demand << ") ";
115.         }
116.     }
117.     std::cout << std::endl;
118.     std::cout << "Total Length: " << maxFitness << std::endl;
119.     std::cout << "Target Length: " << targetLength << std::endl;
120. }
122. int main() {
123.     // 定义材料和目标长度
124.     std::vector<Material> materials = { {10, 5}, {15, 8}, {20, 10}, {25, 12} };
125.     int targetLength = 50;
127.     // 定义遗传算法的参数
128.     int populationSize = 100;
129.     int geneSize = materials.size();
130.     int tournamentSize = 5;
131.     double crossoverRate = 0.8;
132.     double mutationRate = 0.01;
133.     int maxGenerations = 100;
135.     // 初始化种群
136.     std::vector<Chromosome> population = initializePopulation(populationSize, geneSize);
138.     // 迭代进化
139.     for (int generation = 0; generation < maxGenerations; generation++) {
140.         // 计算适应度
141.         for (int i = 0; i < population.size(); i++) {
142.             calculateFitness(population[i], materials, targetLength);
143.         }
145.         // 打印当前最优解
146.         printBestSolution(population, materials, targetLength);
148.         // 选择操作
149.         std::vector<Chromosome> selectedPopulation = selection(population, tournamentSize);
151.         // 交叉操作
152.         std::vector<Chromosome> offspringPopulation = crossover(selectedPopulation, crossoverRate);
154.         // 变异操作
155.         mutation(offspringPopulation, mutationRate);
157.         // 更新种群
158.         population = offspringPopulation;
159.     }
161.     return 0;
162. }

复制代码