使用c++语言提供简单遗传算法示例

admin1

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

// 染色体长度
const int GEN_LEN = 10;

// 种群大小
const int POP_SIZE = 100;

// 变异概率
const double MUTATION_RATE = 0.05;

// 遗传代数
const int MAX_GENERATION = 1000;

// 样本函数
double fitness_func(std::vector<int>& gene)
{
    double x = 0.0;
    for (int i = 0; i < GEN_LEN; ++i) {
        x = x * 2 + gene[i];
    }
    return x * x;
}

// 初始化种群
void init_population(std::vector<std::vector<int>>& population)
{
    std::srand(std::time(nullptr));
    for (int i = 0; i < POP_SIZE; ++i) {
        std::vector<int> gene(GEN_LEN, 0);
        for (int j = 0; j < GEN_LEN; ++j) {
            gene[j] = std::rand() % 2;
        }
        population.push_back(gene);
    }
}

// 选择操作
void selection(std::vector<std::vector<int>>& population, std::vector<std::vector<int>>& offspring)
{
    // 使用轮盘赌选择算法进行选择
    std::vector<double> select_prob(POP_SIZE, 0.0);
    double fitness_sum = 0.0;
    for (int i = 0; i < POP_SIZE; ++i) {
        select_prob[i] = fitness_func(population[i]);
        fitness_sum += select_prob[i];
    }
    for (int i = 0; i < POP_SIZE; ++i) {
        select_prob[i] /= fitness_sum;
    }

    // 使用轮盘赌进行选择
    for (int i = 0; i < POP_SIZE; ++i) {
        double prob = std::rand() % 101 / 100.0;
        double psum = 0.0;
        for (int j = 0; j < POP_SIZE; ++j) {
            psum += select_prob[j];
            if (psum > prob) {
                offspring.push_back(population[j]);
                break;
            }
        }
    }
}

// 交叉操作
void crossover(std::vector<std::vector<int>>& offspring)
{
    for (int i = 0; i < POP_SIZE; i += 2) {
        int pos = std::rand() % GEN_LEN;
        std::vector<int> gene1 = offspring[i], gene2 = offspring[i + 1];
        for (int j = pos; j < GEN_LEN; ++j) {
            int temp = gene1[j];
            gene1[j] = gene2[j];
            gene2[j] = temp;
        }
        offspring[i] = gene1;
        offspring[i + 1] = gene2;
    }
}

// 变异操作
void mutation(std::vector<std::vector<int>>& offspring)
{
    for (int i = 0; i < POP_SIZE; ++i) {
        for (int j = 0; j < GEN_LEN; ++j) {
            double prob = std::rand() % 101 / 100.0;
            if (prob < MUTATION_RATE) {
                offspring[i][j] = 1 - offspring[i][j];
            }
        }
    }
}

// 寻找最优解
std::vector<int> find_best_gene(std::vector<std::vector<int>>& population)
{
    std::vector<int> best_gene(GEN_LEN, 0);
    double best_fitness = -1.0;
    for (int i = 0; i < POP_SIZE; ++i) {
        double fitness = fitness_func(population[i]);
        if (fitness > best_fitness) {
            best_fitness = fitness;
            best_gene = population[i];
        }
    }
    return best_gene;
}

int main()
{
    // 种群
    std::vector<std::vector<int>> population;
    // 初始化种群
    init_population(population);

    // 遗传算法的主循环
    for (int i = 0; i < MAX_GENERATION; ++i) {
        // 子代种群
        std::vector<std::vector<int>> offspring;
        // 选择操作
        selection(population, offspring);

        // 交叉操作
        crossover(offspring);

        // 变异操作
        mutation(offspring);

        // 种群更新
        population = offspring;

        // 输出种群最优解和对应的适应度值
        std::vector<int> best_gene = find_best_gene(population);
        double best_fitness = fitness_func(best_gene);
        std::cout << "Generation: " << i << "  Best gene: ";
        for (int j = 0; j < GEN_LEN; ++j) {
            std::cout << best_gene[j];
        }
        std::cout << "  Best fitness: " << best_fitness << std::endl;
    }

    return 0;
}

遗传算法的基本框架包括选择、交叉和变异操作，其中选择使用的是轮盘赌选择算法，交叉使用的是单点交叉法，变异是对某个位置的基因进行取反操作。在主循环中不断迭代进行这些操作，最终得到一个近似最优解。