用c++实现遗传算法求解矩形排样

以下是一个简单的用C++实现遗传算法求解矩形排样的示例代码：

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

using namespace std;

// 矩形结构体，包含宽度和高度
struct Rect {
    int w, h;
};

// 个体结构体，包含矩形序列和适应度
struct Individual {
    vector<Rect> rects;
    double fitness;
};

// 生成指定数量的随机矩形
vector<Rect> generateRects(int n, int maxW, int maxH) {
    vector<Rect> rects(n);
    for (int i = 0; i < n; i++) {
        rects[i].w = rand() % maxW + 1;
        rects[i].h = rand() % maxH + 1;
    }
    return rects;
}

// 计算矩形序列的适应度，即矩形占用面积的倒数
double calcFitness(const vector<Rect>& rects, int width) {
    int area = 0;
    for (Rect rect : rects) {
        area += rect.w * rect.h;
    }
    return 1.0 / (area * width);
}

// 交叉操作，生成两个新个体
void crossover(const Individual& p1, const Individual& p2, Individual& c1, Individual& c2) {
    int n = p1.rects.size();
    int k = rand() % n;  // 随机选择交叉点
    c1.rects.insert(c1.rects.end(), p1.rects.begin(), p1.rects.begin() + k);
    for (Rect rect : p2.rects) {
        if (find(c1.rects.begin(), c1.rects.end(), rect) == c1.rects.end()) {
            c1.rects.push_back(rect);
        }
    }
    c1.fitness = calcFitness(c1.rects, width);
    c2.rects.insert(c2.rects.end(), p2.rects.begin(), p2.rects.begin() + k);
    for (Rect rect : p1.rects) {
        if (find(c2.rects.begin(), c2.rects.end(), rect) == c2.rects.end()) {
            c2.rects.push_back(rect);
        }
    }
    c2.fitness = calcFitness(c2.rects, width);
}

// 变异操作，生成一个新个体
void mutation(const Individual& p, Individual& c) {
    int n = p.rects.size();
    c.rects = p.rects;
    int k1 = rand() % n;  // 随机选择两个矩形
    int k2 = rand() % n;
    swap(c.rects[k1], c.rects[k2]);  // 交换位置
    c.fitness = calcFitness(c.rects, width);
}

// 选择操作，选择适应度最高的个体
void selection(const vector<Individual>& pop, Individual& best) {
    for (Individual ind : pop) {
        if (ind.fitness > best.fitness) {
            best = ind;
        }
    }
}

// 遗传算法主函数
void geneticAlgorithm(int n, int width, int height, int popSize, int maxGen, double pc, double pm) {
    srand(time(NULL));
    vector<Individual> pop(popSize);  // 种群
    Individual best;  // 最优解
    best.fitness = 0;
    for (int i = 0; i < popSize; i++) {
        pop[i].rects = generateRects(n, width, height);
        pop[i].fitness = calcFitness(pop[i].rects, width);
        selection(pop, best);
    }
    for (int gen = 1; gen <= maxGen; gen++) {
        vector<Individual> newPop(popSize);  // 新种群
        for (int i = 0; i < popSize; i += 2) {
            Individual p1 = pop[rand() % popSize];
            Individual p2 = pop[rand() % popSize];
            Individual c1, c2;
            crossover(p1, p2, c1, c2);
            if (rand() / double(RAND_MAX) < pc) {
                mutation(c1, c1);
            }
            if (rand() / double(RAND_MAX) < pc) {
                mutation(c2, c2);
            }
            newPop[i] = c1;
            newPop[i + 1] = c2;
        }
        pop = newPop;
        for (int i = 0; i < popSize; i++) {
            selection(pop, best);
        }
        cout << "Gen " << gen << ": best fitness = " << best.fitness << endl;
    }
}

int main() {
    int n = 10;  // 矩形数量
    int width = 100;  // 纸张宽度
    int height = 100;  // 纸张高度
    int popSize = 100;  // 种群大小
    int maxGen = 100;  // 最大迭代次数
    double pc = 0.8;  // 交叉概率
    double pm = 0.1;  // 变异概率
    geneticAlgorithm(n, width, height, popSize, maxGen, pc, pm);
    return 0;
}

以上代码仅为示例，实际问题中可能需要根据具体情况进行修改和优化。