用C++写个NSGA-II

NSGA-II（Non-dominated Sorting Genetic Algorithm II）是一种多目标遗传算法，用于优化问题。下面是一个使用C++实现NSGA-II的代码示例，其中包括基本的NSGA-II算法以及一些常用的优化问题的测试函数。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;

const int POP_SIZE = 100; // 种群大小
const int MAX_GEN = 100; // 最大迭代次数
const double CROSS_RATE = 0.8; // 交叉概率
const double MUT_RATE = 0.2; // 变异概率

// 定义一个向量结构体
struct Vector {
    vector<double> x;
    int rank;
    double crowding_distance;
    double fitness;
};

// 定义一个种群结构体
struct Population {
    vector<Vector> population;
};

// 计算函数1
double func1(vector<double> x) {
    return x[0];
}

// 计算函数2
double func2(vector<double> x) {
    return (1 + x[1]) / x[0];
}

// 计算拥挤度距离
double crowding_distance(vector<Vector>& front, int i) {
    double dist = 0;
    int m = front[0].x.size();
    sort(front.begin(), front.end(), [&](Vector a, Vector b) {
        return a.x[i] < b.x[i];
    });
    dist += front[1].x[i] - front[0].x[i];
    dist += front[front.size() - 1].x[i] - front[front.size() - 2].x[i];
    for (int j = 1; j < front.size() - 1; j++) {
        dist += front[j + 1].x[i] - front[j - 1].x[i];
    }
    return dist;
}

// 计算适应度值
void calculate_fitness(vector<Vector>& population) {
    int n = population.size();
    for (int i = 0; i < n; i++) {
        population[i].fitness = 0;
        for (int j = 0; j < n; j++) {
            if (i != j) {
                if (population[j].x[0] >= population[i].x[0] && population[j].x[1] >= population[i].x[1]) {
                    population[i].fitness += 1;
                }
            }
        }
    }
}

// 快速非支配排序
void fast_non_dominated_sort(vector<Vector>& population, vector<vector<int>>& fronts) {
    int n = population.size();
    fronts.clear();
    vector<int> domination(n, 0);
    vector<vector<int>> dom(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j) {
                if (population[i].x[0] <= population[j].x[0] && population[i].x[1] <= population[j].x[1]) {
                    dom[i].push_back(j);
                } else if (population[j].x[0] <= population[i].x[0] && population[j].x[1] <= population[i].x[1]) {
                    domination[i]++;
                }
            }
        }
        if (domination[i] == 0) {
            population[i].rank = 1;
            fronts.push_back(vector<int>({i}));
        }
    }
    int k = 1;
    while (!fronts[k - 1].empty()) {
        vector<int> Q;
        for (auto i : fronts[k - 1]) {
            for (auto j : dom[i]) {
                domination[j]--;
                if (domination[j] == 0) {
                    population[j].rank = k + 1;
                    Q.push_back(j);
                }
            }
        }
        k++;
        fronts.push_back(Q);
    }
}

// 交叉操作
void crossover(vector<Vector>& population) {
    int n = population.size();
    for (int i = 0; i < n; i += 2) {
        if (rand() / (double)RAND_MAX < CROSS_RATE) {
            int m = population[i].x.size();
            int j = rand() % m;
            for (int k = j; k < m; k++) {
                double temp = population[i].x[k];
                population[i].x[k] = population[i + 1].x[k];
                population[i + 1].x[k] = temp;
            }
        }
    }
}

// 变异操作
void mutation(vector<Vector>& population) {
    int n = population.size();
    for (int i = 0; i < n; i++) {
        if (rand() / (double)RAND_MAX < MUT_RATE) {
            int m = population[i].x.size();
            int j = rand() % m;
            population[i].x[j] = rand() / (double)RAND_MAX;
        }
    }
}

// NSGA-II算法
Population nsga2() {
    // 初始化种群
    Population pop;
    for (int i = 0; i < POP_SIZE; i++) {
        Vector v;
        v.x.push_back(rand() / (double)RAND_MAX);
        v.x.push_back(rand() / (double)RAND_MAX);
        pop.population.push_back(v);
    }
    // 迭代
    for (int gen = 0; gen < MAX_GEN; gen++) {
        // 计算适应度值
        calculate_fitness(pop.population);
        // 快速非支配排序
        vector<vector<int>> fronts;
        fast_non_dominated_sort(pop.population, fronts);
        // 计算拥挤度距离
        for (auto front : fronts) {
            for (int i = 0; i < front.size(); i++) {
                pop.population[front[i]].crowding_distance = 0;
            }
            for (int j = 0; j < pop.population[0].x.size(); j++) {
                sort(front.begin(), front.end(), [&](int a, int b) {
                    return pop.population[a].x[j] < pop.population[b].x[j];
                });
                pop.population[front[0]].crowding_distance = pop.population[front[front.size() - 1]].crowding_distance = INFINITY;
                for (int i = 1; i < front.size() - 1; i++) {
                    pop.population[front[i]].crowding_distance += (pop.population[front[i + 1]].x[j] - pop.population[front[i - 1]].x[j]) / (pop.population[front[front.size() - 1]].x[j] - pop.population[front[0]].x[j]);
                }
            }
        }
        // 生成新种群
        Population new_pop;
        for (auto front : fronts) {
            if (new_pop.population.size() + front.size() > POP_SIZE) {
                sort(front.begin(), front.end(), [&](int a, int b) {
                    return pop.population[a].crowding_distance > pop.population[b].crowding_distance;
                });
                for (int i = 0; i < POP_SIZE - new_pop.population.size(); i++) {
                    new_pop.population.push_back(pop.population[front[i]]);
                }
                break;
            } else {
                for (int i = 0; i < front.size(); i++) {
                    new_pop.population.push_back(pop.population[front[i]]);
                }
            }
        }
        // 交叉和变异
        crossover(new_pop.population);
        mutation(new_pop.population);
        // 更新种群
        pop = new_pop;
    }
    return pop;
}

int main() {
    srand(time(NULL));
    Population pop = nsga2();
    for (int i = 0; i < POP_SIZE; i++) {
        cout << pop.population[i].x[0] << " " << pop.population[i].x[1] << " " << pop.population[i].rank << endl;
    }
    return 0;
}

上面的代码实现了一个简单的NSGA-II算法，并提供了两个测试函数func1和func2。你可以根据需要修改这些函数，以适应不同的优化问题。同时，你还可以根据需要调整一些算法参数，如种群大小、最大迭代次数、交叉概率和变异概率等。