二次分配问题（遗传算法求解）

遗传算的思想和求解方式，请移步看博客遗传算法（GA）概述_遗传算法提供了一种求解复杂系统优化问题的通用框架,不依赖于问题的具体领域-CSDN博客

QAP 的解决思想可以概括为以下步骤：

编码表示：设计一个适当的编码方式来表示问题的解。在 QAP 中，可以使用排列（permutation）来表示物体的分配方案。每个位置上的值代表物体在目标位置上的分配情况。

初始种群生成：使用随机方式或启发式方法生成初始种群。初始种群由一组个体组成，每个个体都是问题解的一个可能方案（即一个排列）。

适应度评估：根据问题的目标函数（成本函数或距离函数）计算每个个体的适应度值。适应度值表示个体在问题中的优劣程度。

选择操作：使用选择算子（如轮盘赌选择、锦标赛选择等）从当前种群中选择一部分个体作为父代，用于产生下一代的后代。

交叉操作：通过交叉操作（如单点交叉、多点交叉等），将选中的父代个体组合生成新的后代个体。

变异操作：对新生成的后代个体进行变异操作，引入随机性，以增加搜索空间的探索能力。

更新种群：根据选择、交叉和变异操作生成的后代个体，更新当前种群，形成下一代种群。

终止条件判断：检查是否满足终止条件，如达到最大迭代次数、适应度达到目标值等。如果满足条件，算法终止；否则，返回第4步。

输出结果：根据终止条件确定的最优个体，作为最终的解决方案输出。

代码方面依然使用了上篇文章所使用的类的思想，代码如下

#ifndef GA_SEARCH_H
#define GA_SEARCH_H
#include "QAPSolver.h"


class GASearch : public QAPSolver
{
public:

    GASearch(const std::vector<std::vector<int>>& flowMatrix_, const std::vector<std::vector<int>>& distanceMatrix_) : QAPSolver(flowMatrix_, distanceMatrix_) {};

    void execute() override;

    /// <summary>
    /// 初始化参数
    /// </summary>
    /// <param name="popSize_">种群大小</param>
    /// <param name="maxIterations_">最大迭代次数</param>
    /// <param name="mutationRate_">变异概率</param>
    void init(int popSize_, int maxIterations_, double mutationRate_,double crossoverRate_,int tournamentSize_);

private:

    int popSize; // 种群大小
    int maxIterations; // 最大迭代次数
    int tournamentSize;
    double mutationRate; // 变异概率
    double crossoverRate;

    // 设计种群
    struct Individual
    {
        // 排列方式
        std::vector<int> permutation;
        //适应度
        int fitness;

        Individual() :fitness(0) {}
    };


    // 初始化种群
    std::vector<Individual> init_population();

    //变异操作
    void mutation(Individual& individual);

    /// <summary>
    /// 在群落中寻找最佳解
    /// </summary>
    /// <param name="populations"></param>
    void findBestIndividual(const std::vector<Individual>& populations);

    // 交叉操作
    Individual crossover(const Individual& parent1, const Individual& parent2);
    // 选择操作 使用的时锦标赛
    Individual tournamentSelection(const std::vector<Individual>& populations);
    // 更新种群
    std::vector<Individual> updatePopulation(const std::vector<Individual>& populations);

};
#endif // !GA_SEARCH_H

.cpp文件如下

#include "GASearch.h"


void GASearch::execute()
{
	
	std::vector<Individual> populations =  init_population();
	for (int index = 0; index < maxIterations; index++)
	{
		for (auto& individual : populations)
		{
			individual.fitness = calculateCost(individual.permutation);
		}

		populations = updatePopulation(populations);

	}

	findBestIndividual(populations);
}

void GASearch::init(int popSize_, int maxIterations_, double mutationRate_, double crossoverRate_, int tournamentSize_)
{
	popSize = popSize_;
	maxIterations = maxIterations_;
	mutationRate = mutationRate_;
	crossoverRate = crossoverRate_;
	tournamentSize = tournamentSize_;
}

std::vector<GASearch::Individual> GASearch::init_population()
{
	std::vector<Individual> populations(popSize);

	for (auto& individual : populations)
	{
		individual.permutation.resize(dimension);
		std::iota(individual.permutation.begin(), individual.permutation.end(), 0);
		std::shuffle(individual.permutation.begin(), individual.permutation.end(), gen);
	}
	return populations;
}

void GASearch::mutation(Individual& individual)
{

	std::uniform_int_distribution<int> indexDist(0, dimension - 1);

	for (int i = 0; i < dimension; i++)
	{
		if (rand01() < mutationRate)
		{
			int index1 = indexDist(gen);
			int index2 = indexDist(gen);

			std::swap(individual.permutation[index1], individual.permutation[index2]);
		}
	}
	
}

void GASearch::findBestIndividual(const std::vector<Individual>& populations)
{
	Individual bestIndividual;
	for (const auto& individual : populations) {
		if (bestIndividual.fitness == 0 || individual.fitness < bestIndividual.fitness) {
			bestSolution = individual.permutation;
		}
	}
}

GASearch::Individual GASearch::crossover(const Individual& parent1, const Individual& parent2)
{
	std::uniform_int_distribution<int> indexDist(0, dimension - 1);

	int index1 = indexDist(gen);
	int index2 = indexDist(gen);

	if (index1 > index2) {
		std::swap(index1, index2);
	}

	Individual child;
	child.permutation.resize(dimension);

	std::vector<int> mapping(dimension, -1);
	for (int i = index1; i <= index2; ++i) {
		child.permutation[i] = parent1.permutation[i];
		mapping[parent1.permutation[i]] = parent2.permutation[i];
	}

	for (int i = 0; i < dimension; ++i) {
		if (i >= index1 && i <= index2) {
			continue;
		}
		int allele = parent2.permutation[i];
		while (mapping[allele] != -1) {
			allele = mapping[allele];
		}
		child.permutation[i] = allele;
	}

	return child;
}

GASearch::Individual GASearch::tournamentSelection(const std::vector<Individual>& populations)
{
	std::uniform_int_distribution<int> indexDist(0, populations.size() - 1);

	Individual bestIndividual;

	for (int i = 0; i < tournamentSize; i++)
	{
		int index = indexDist(gen);
		const Individual& condidate = populations[index];

		if (bestIndividual.fitness == 0 || condidate.fitness < bestIndividual.fitness)
		{
			bestIndividual = condidate;
		}
	}

	return bestIndividual;
}

std::vector<GASearch::Individual> GASearch::updatePopulation(const std::vector<Individual>& populations)
{
	//定义新的种群群
	std::vector<Individual> newPoulations;

	while (newPoulations.size() < popSize)
	{
		Individual parent1 = tournamentSelection(populations);

		if (rand01() < crossoverRate)
		{
			Individual parent2 = tournamentSelection(populations);

			Individual child = crossover(parent1, parent2);

			mutation(child);

			child.fitness = calculateCost(child.permutation);

			newPoulations.push_back(child);
		}
		else
		{
			newPoulations.push_back(parent1);
		}

		return newPoulations;
	}
}

运行结果