C++builder中的人工智能（24）：遗传算法Genetic Algorithms的C++使用人工智能技术实现优化

最新推荐文章于 2025-02-21 15:33:21 发布

caridle

最新推荐文章于 2025-02-21 15:33:21 发布

阅读量792

点赞数 27

分类专栏： C++与人工智能文章标签： c++ 人工智能开发语言

本文链接：https://blog.csdn.net/caridle/article/details/143722500

版权

C++与人工智能专栏收录该内容

33 篇文章

订阅专栏

解决C++优化问题涉及社会科学、经济学到计算机科学等工程领域的所有定量学科。遗传算法Genetic Algorithm (GA) 是一种机器学习过程，它依赖于突变、交叉和选择等受生物启发的操作符，用于生成优化和搜索问题的高质量解决方案。本文将解释如何使用人工智能技术实现优化。

我们下面使用的遗传算法最初由Željko Kovačević（Embarcadero MVP）提出。Željko拥有令人惊叹的VCL示例和关于C++ Builder的博客文章。他给了我下面这个关于GA的控制台应用程序示例，可以免费发布，但代码的版权归他所有，如需使用可能需要联系他。这是使用了C++builder 对代码进行了改进和简化，可以帮助了解科学应用。

什么是遗传算法？

在计算机科学和研究中，遗传算法（GA）是一种通过进化来解决优化问题的算法，就像自然界中的生物一样。遗传算法是一种受自然选择过程启发的元启发式算法，属于更广泛的进化算法类别。遗传算法通常用于生成优化和搜索问题的高质量解决方案，依赖于突变、交叉和选择等受生物启发的操作符。在遗传算法中，首先创建一个初始种群，然后通过循环迭代，通过计算适应度值、选择、交叉和突变步骤，如下所示：

遗传算法是最早开发的AI/ML方法之一，用于解决一些问题，如解决数独谜题。遗传算法和模糊逻辑在20世纪90年代非常流行。一个典型的遗传算法需要：

解决方案领域的遗传表示，
用于评估解决方案领域的适应度函数。

如何使用C++ Builder开发遗传算法？

在我们的C++优化示例中，我们开发了一个关于我们选择领域的优化算法，例如遗传算法。现在让我们快速解释一下这意味着什么。首先，我们有一个全局的输入值，它代表遗传算法（GA）试图找到其二进制表示的值（数字）。

我们有个体用于评估遗传算法，因此我们可以创建下面的类。

class Individual
{
	public:
		std::vector<bool> gene = std::vector<bool>(32); // number of bits
		unsigned int fitness{ std::numeric_limits<int>::max() };
 
		void evaluate()
		{
			unsigned int number = toNumber();
			if (number < inputValue)	fitness = inputValue - number;	else	fitness = number - inputValue;
		}
 
		unsigned int toNumber() const
		{
			unsigned int sum = 0;
			for (unsigned int i = 0; i < gene.size(); i++)
				sum += (gene[i]) * (int)std::pow(2, gene.size() - i - 1);
			return sum;
		}
};

在这种情况下，对于输入值1234567890，GA试图找到一个正确的解决方案，即0100.1001.1001.0110.0000.0010.1101.0010。为了做到这一点，它首先会创建一个随机（初始）种群（第1代），然后通过选择、交叉和突变操作优化当前最佳解决方案。因此，我们首先需要一个如下所示的种群类。

我们需要以二进制模式显示代的值，因此需要将我们的值（例如InputValue）转换为二进制字符串，如下所示，

 
class Population
{
	public:
		std::vector<Individual> individual;
 
		void generateRandom(int size)
		{
			for (int i = 0; i < size; i++)
			{
				Individual pom;
				for (unsigned int j = 0; j < pom.gene.size(); j++)	pom.gene[j] = rand() % 2;
				individual.push_back(pom);
			}
		}
 
		// evaluating population
		void evaluate()
		{
			for (unsigned int i = 0; i < individual.size(); i++) individual[i].evaluate();
		}
 
		// best fitness in the population
		void getBestFitness(unsigned int* bestFitness, unsigned int* closestValue)
		{
			*bestFitness = individual[0].fitness;
			*closestValue = individual[0].toNumber();
			for (unsigned int i = 1; i < individual.size(); i++)
			{
				if (individual[i].fitness < *bestFitness)
				{
					*bestFitness = individual[i].fitness;
					*closestValue = individual[i].toNumber();
				}
			}
		}
 
		// adding elite members of previous generation
		void addElite(Population* previousGen, int elitism)
		{
			// sort individuals in current population
			sort(individual.begin(), individual.end(),
				[](Individual I1, Individual I2) {
					return I1.fitness < I2.fitness;
				});
 
			// sort individuals from the previous generation
			sort(previousGen->individual.begin(), previousGen->individual.end(),
				[](Individual I1, Individual I2) {
					return I1.fitness < I2.fitness;
				});
			// replace the worst individuals in current population with elite individuals from the previous generation
			int eliteCount = (int)std::ceil((elitism * individual.size()) / 100.);
			for (int i = 0; i < eliteCount; i++) {
				individual[individual.size() - i - 1] = previousGen->individual[i];
			}
			// sort individuals in current population
			sort(individual.begin(), individual.end(),
				[](Individual I1, Individual I2) {
					return I1.fitness < I2.fitness;
				});
		}
};

为了在二进制模式下显示我们的代的值，我们需要将我们的值（例如 InputValue）转换为二进制字符串。这通常涉及到将一个整数转换为其二进制表示形式的字符串。下面是一个简单的C++函数，用于将整数转换为二进制字符串：

#include <vector>
#include <string>
#include <algorithm>

std::string numberToBin(int n, int minBits = 16) {
   std::vector<int> pom;
	while (n != 0) {
		pom.push_back(n % 2);
		n /= 2;
	}
	// fill zeros
	for (int i = pom.size(); i < minBits; i++)
		pom.push_back(0);
	// binary representation
	std::string res;
	int counter = 0;
	for (auto it = pom.rbegin(); it != pom.rend(); it++) {
		if (counter++ % 4 == 0)
			res += '.';
		res += ('0' + *it);
	}
	std::string rets= res.substr(1);
	return rets;
}

这个函数numberToBin接受两个参数：n是要转换的整数，minBits是二进制字符串应该有的最小位数。如果转换后的二进制字符串位数少于minBits，函数会在前面补零，以确保字符串至少有minBits位长。

函数的工作原理如下：

使用一个循环将整数n除以2，并将余数（0或1）存储在bits向量中。这将生成一个从最低位到最高位的位序列。
如果需要，用前导零填充bits向量，以确保它至少有minBits位长。
反转bits向量，并将每位追加到binaryString字符串中，从而生成正确的二进制表示。

使用这个函数，你可以将任何整数转换为其二进制字符串表示，这对于显示遗传算法中的代值非常有用。

如何在C++中迭代遗传算法？

在遗传迭代循环中，我们需要一个锦标赛选择方法tournamentSelection()，如下所示。

 
// tournament selection
Population tournamentSelection(const Population& P0, int tournamentSize) {
	Population P1;
	// repeat tournament until population is full
	for (unsigned int i = 0; i < P0.individual.size(); i++) {
		// choose N random contenders in the tournament
		std::vector<int> randomContender;
		for (int j = 0; j < tournamentSize; j++)
			randomContender.push_back(rand() % P0.individual.size());
		// who is the winner?
		int winner = 0;
		for (unsigned int j = 1; j < randomContender.size(); j++)
			if (P0.individual[randomContender[j]].fitness < P0.individual[randomContender[winner]].fitness) // !
				winner = j;
		// add winner in the next generation
		P1.individual.push_back(P0.individual[randomContender[winner]]);
	}
	return P1;
}

我们需要通过crossPair()方法交叉基因对，如下所示：

 
void crossoverPair(const Individual& parent1, const Individual& parent2, Individual* offspring1, Individual* offspring2) {
	Individual offspring[2];
	for (int i_crossoverTimes = 0; i_crossoverTimes < 2; i_crossoverTimes++) {
		for (unsigned int i_gene = 0; i_gene < parent1.gene.size(); i_gene++) {
			int dice = rand() % 100 + 1;
			// child takes a gene from the 1st parent
			if (dice <= 50) // 50 - 50 probability
				offspring[i_crossoverTimes].gene[i_gene] = parent1.gene[i_gene];
			else
				// child takes a gene from the 2st parent
				offspring[i_crossoverTimes].gene[i_gene] = parent2.gene[i_gene];
		}
	}
	*offspring1 = offspring[0];
	*offspring2 = offspring[1];
}

我们可以创建一个如下所示的Crossover()类：

Population Crossover(const Population& P1, int crossoverProbability) {
	Population P2 = P1;
	// probability crossover table type
	class crossoverIndividualType {
	public:
		Individual individual;
		int indexInPopulation;
		int probability;
		crossoverIndividualType(Individual _individual, int _indexInPopulation, int _probability) : individual(_individual) {
			indexInPopulation = _indexInPopulation;
			probability = _probability;
		}
	};
	// creating crossover probability table
	std::vector<crossoverIndividualType> crossoverProbabilityTable; // 1-100 %
	for (unsigned int i = 0; i < P2.individual.size(); i++) {
		int probability = rand() % 100 + 1; // probability of crossover for i-th individual
		if (probability <= crossoverProbability)
			crossoverProbabilityTable.push_back(crossoverIndividualType(P2.individual[i], i, probability));
	}
	// if having odd number of parents, delete the last one
	if (crossoverProbabilityTable.size() % 2 != 0)
		crossoverProbabilityTable.pop_back();
	// shuffle parents
	if (crossoverProbabilityTable.size() > 1) {
		for (unsigned int i = 0; i < crossoverProbabilityTable.size(); i++) {
			int j = rand() % crossoverProbabilityTable.size();
			crossoverIndividualType temp = crossoverProbabilityTable[j];
			crossoverProbabilityTable[j] = crossoverProbabilityTable[i];
			crossoverProbabilityTable[i] = temp;
		}
	}
	// mate parents
	for (unsigned int i = 0; i < crossoverProbabilityTable.size(); i += 2) {
		Individual parent1 = crossoverProbabilityTable[i].individual;
		Individual parent2 = crossoverProbabilityTable[i + 1].individual;
		Individual offspring1, offspring2;
		crossoverPair(parent1, parent2, &offspring1, &offspring2);
		// replace parents with their children
		P2.individual[crossoverProbabilityTable[i].indexInPopulation] = offspring1;
		P2.individual[crossoverProbabilityTable[i + 1].indexInPopulation] = offspring2;
	}
	return P2;
}

我们可以通过这个Mutation()方法进行一些突变（随机基因变化），如下所示：

// mutation - random gene changes
void Mutation(Population* P2, int mutationProbability) {
	// for every individual in the population...
	for (unsigned int i_individual = 0; i_individual < P2->individual.size(); i_individual++) {
		// for every gene
		for (unsigned int i_gene = 0; i_gene < P2->individual[i_individual].gene.size(); i_gene++) {
			int dice = rand() % 100 + 1;
			// mutate?
			if (dice <= mutationProbability)
				P2->individual[i_individual].gene[i_gene] = rand() % 2;
		}
	}
}

如何在C++ Builder中一键运行遗传算法？

现在我们可以创建我们的C++ Builder FMX应用程序，包含以下组件：

2个编辑框（TEdit），
一个备忘录（TMemo），
一个TeeChart图表，带有y=f(x)系列（TChart）
一个按钮（TButton）

这里，Edit1用于输入输入值，Edit2用于显示种子值，Memo1用于显示结果，TChart1用于图形化显示GA优化，Button1用于一次又一次地运行GA。双击Button1。这个按钮将设置GA并运行GA算法。它将创建一个随机的（初始）种群（第1代），然后通过选择、交叉和突变操作优化当前最佳解决方案。以下是它的工作方式：

void __fastcall TForm1::Button1Click(TObject *Sender)
{
	int seed = (unsigned)time(NULL);
	srand(seed);
 
	int popSize = 250;
	int ts = 2;
	int pc = 70; // %
	int pm = 10; // %
	int el = 10; // %
	//bool multithreaded = false;
	unsigned int maxGen = 2500; // maximum number of generations
 
 
	inputValue = Edit1->Text.ToInt();
 
	auto start_t = std::chrono::high_resolution_clock::now();
	std::vector<Population> generation;
 
	Population randomPopulation;
	randomPopulation.generateRandom(popSize);
	randomPopulation.evaluate();
 
	unsigned int bestFitness, currentFitness, closestNumber;
	randomPopulation.getBestFitness(&currentFitness, &closestNumber);
	bestFitness = currentFitness;
	generation.push_back(randomPopulation);
 
	Memo1->Lines->Add( "Seed: "+ IntToStr(seed) );
	Edit2->Text= IntToStr(seed);
 
	std::string sbin= numberToBin(inputValue, generation[0].individual[0].gene.size());
 
	Memo1->Lines->Add( "                          Input value: " + UIntToStr(inputValue)+" bin: "+  sbin.c_str() );
 
	sbin = numberToBin(closestNumber, generation[0].individual[0].gene.size());
 
	UnicodeString ustr;
	ustr.printf( L"Generation:%4u fitness:%10u val:%10u", 
					1,
					currentFitness,
					closestNumber);
	Memo1->Lines->Add(ustr+" bin: "+sbin.c_str() ); 
 
	Series1->Clear();
	Series1->Add( currentFitness , 1 ,clTeeColor );
 
	Application->ProcessMessages();
 
 
	// genetic algorithm
	do {
		// selection
		Population P1 = tournamentSelection(generation[generation.size() - 1], ts);
		// crossover
		Population P2 = Crossover(P1, pc);
		// mutation
		Mutation(&P2, pm);
		// elitism
		P2.addElite(&generation[generation.size() - 1], el);
		generation.push_back(P2);
		generation[generation.size() - 1].evaluate();
 
		generation[generation.size() - 1].getBestFitness(&currentFitness, &closestNumber);
		if (currentFitness < bestFitness)
		{
			bestFitness = currentFitness;
			//output after finding better fitness value
			sbin= numberToBin(closestNumber, generation[0].individual[0].gene.size());
								
			ustr.printf( L"Generation:%4u fitness:%10u val:%10u", 
							generation.size(),	
							currentFitness,
							closestNumber
							);
			Memo1->Lines->Add(ustr+" bin: "+sbin.c_str() );
			Series1->Add( currentFitness , generation.size() ,clTeeColor );
		}
		if (bestFitness == 0)
		{
			/*std::string sbin= numberToBin(inputValue, generation[0].individual[0].gene.size()); 
			Memo1->Lines->Add( "                          Input value: " + UIntToStr(inputValue)+" bin: "+  sbin.c_str() );
			*/
			
			Memo1->Lines->Add( "Solution is found in generation: " + UIntToStr(generation.size()) );
			break;
		}
	} while (bestFitness != 0 && generation.size() <= maxGen); // termination condition
 
	auto end_t = std::chrono::high_resolution_clock::now();
	auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end_t - start_t).count();
	Memo1->Lines->Add( "Duration: " + IntToStr(duration)+ " ms");
}

这句话的意思是，遗传算法将通过选择、交叉和突变操作在一代又一代中优化当前的最佳解决方案。下面是一个运行时的示例：

遗传算法的运行过程通常包括以下几个步骤：

初始化：随机生成初始种群。
评估：计算种群中每个个体的适应度值。
选择：根据适应度值选择个体进行繁殖。
交叉：选中的个体配对并交换基因，产生新的后代。
突变：以一定的概率随机改变某些个体的基因。
新一代：用产生的后代替换当前种群中的一些或全部个体，形成新一代。
终止条件：重复上述过程，直到满足终止条件，如达到最大代数或找到满意的解决方案。

以下是一个遗传算法运行时的示例流程：

初始种群：[种群中的个体]
评估适应度：[计算每个个体的适应度值]
选择操作：[根据适应度选择个体]
交叉操作：[配对并交换基因]
突变操作：[随机改变某些基因]
新一代种群：[形成新一代]
重复上述过程...

每次迭代都旨在改进解决方案，随着代数的增加，种群中个体的适应度值通常会提高，意味着解决方案的质量越来越好。最终，算法将收敛到一个最优或接近最优的解决方案。