C++聚类算法与遗传算法的结合

C++聚类算法与遗传算法的结合是一个有趣且具有挑战性的研究课题。聚类算法用于将数据分组，而遗传算法则用于优化问题求解。将这两种算法结合，可以在聚类过程中寻找最优解。

以下是一个简单的C++示例，展示了如何将K-means聚类算法与遗传算法结合：

#include <iostream>
#include <vector>
#include <cmath>
#include <random>
#include <algorithm>

// K-means聚类算法
void kmeans(std::vector<std::vector<double>>& data, int k, std::vector<std::vector<double>>& centroids) {
    int n = data.size();
    std::vector<int> labels(n, -1);
    std::vector<std::vector<double>> centroids_new(k, std::vector<double>(data[0].size(), 0));

    // 初始化质心
    for (int i = 0; i < k; ++i) {
        centroids_new[i] = data[rand() % n];
    }

    // 迭代过程
    bool converged = false;
    while (!converged) {
        converged = true;

        // 计算每个点到质心的距离并更新标签
        for (int i = 0; i < n; ++i) {
            double min_dist = std::numeric_limits<double>::max();
            int min_idx = -1;
            for (int j = 0; j < k; ++j) {
                double dist = 0;
                for (int d = 0; d < data[i].size(); ++d) {
                    dist += pow(data[i][d] - centroids_new[j][d], 2);
                }
                if (dist < min_dist) {
                    min_dist = dist;
                    min_idx = j;
                }
            }
            labels[i] = min_idx;

            // 更新质心
            for (int d = 0; d < data[i].size(); ++d) {
                centroids_new[min_idx][d] += data[i][d];
            }
            centroids_new[min_idx][d] /= n;
        }

        // 检查质心是否收敛
        for (int i = 0; i < k; ++i) {
            bool is_converged = true;
            for (int j = i + 1; j < k; ++j) {
                if (std::linalg::norm(centroids_new[i] - centroids_new[j]) > 1e-6) {
                    is_converged = false;
                    break;
                }
            }
            if (!is_converged) {
                converged = false;
                break;
            }
        }

        // 更新质心
        centroids = centroids_new;
    }
}

// 遗传算法
std::vector<int> genetic_algorithm(std::vector<std::vector<double>>& data, int k, int population_size, int max_generations) {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(0, k - 1);

    // 初始化种群
    std::vector<std::vector<int>> population(population_size, std::vector<int>(data[0].size(), -1));
    for (int i = 0; i < population_size; ++i) {
        for (int j = 0; j < data[0].size(); ++j) {
            population[i][j] = dis(gen);
        }
    }

    // 迭代过程
    for (int gen = 0; gen < max_generations; ++gen) {
        // 计算适应度
        std::vector<int> fitness(population_size, 0);
        for (int i = 0; i < population_size; ++i) {
            fitness[i] = 0;
            for (int j = 0; j < data.size(); ++j) {
                double min_dist = std::numeric_limits<double>::max();
                int min_idx = -1;
                for (int l = 0; l < k; ++l) {
                    double dist = 0;
                    for (int d = 0; d < data[j].size(); ++d) {
                        dist += pow(data[j][d] - population[i][d], 2);
                    }
                    if (dist < min_dist) {
                        min_dist = dist;
                        min_idx = l;
                    }
                }
                fitness[i] += min_dist;
            }
        }

        // 选择
        std::vector<int> selected;
        std::vector<double> fitness_sum(population_size, 0);
        for (int i = 0; i < population_size; ++i) {
            double rand_val = static_cast<double>(rand()) / RAND_MAX;
            double cumulative_fitness = 0;
            for (int j = 0; j < population_size; ++j) {
                cumulative_fitness += fitness[j];
                if (rand_val < cumulative_fitness) {
                    selected.push_back(j);
                    break;
                }
            }
        }

        // 交叉
        std::vector<std::vector<int>> offspring(population_size, std::vector<int>(data[0].size(), -1));
        for (size_t i = 0; i < selected.size(); i += 2) {
            int parent1 = selected[i];
            int parent2 = selected[i + 1];
            for (int j = 0; j < data[0].size(); ++j) {
                if (rand() % 2 == 0) {
                    offspring[i][j] = parent1[j];
                } else {
                    offspring[i][j] = parent2[j];
                }
            }
        }

        // 变异
        for (size_t i = 0; i < offspring.size(); ++i) {
            int idx = rand() % data[0].size();
            offspring[i][idx] = dis(gen);
        }

        // 更新种群
        population = offspring;
    }

    // 返回最优解
    int best_idx = 0;
    double min_fitness = fitness[0];
    for (int i = 1; i < population_size; ++i) {
        if (fitness[i] < min_fitness) {
            min_fitness = fitness[i];
            best_idx = i;
        }
    }

    return population[best_idx];
}

int main() {
    std::vector<std::vector<double>> data = {{1, 2}, {1, 4}, {1, 0}, {10, 2}, {10, 4}, {10, 0}};
    int k = 2;
    int population_size = 10;
    int max_generations = 50;

    std::vector<std::vector<double>> centroids = genetic_algorithm(data, k, population_size, max_generations);
    kmeans(data, k, centroids);

    std::cout << "质心: ";
    for (const auto& centroid : centroids) {
        std::cout << "(" << centroid[0] << ", " << centroid[1] << ") ";
    }
    std::cout << std::endl;

    return 0;
}

这个示例中，我们首先使用遗传算法找到一组初始质心，然后将这些质心作为K-means算法的输入。K-means算法会迭代地更新质心和标签，直到收敛。最后，我们输出找到的最优质心。