用遗传算法求解Ackley函数

技术2024-08-07 60

第一部分讲解了遗传算法的基本原理和框架，对遗传算法的主要工作流程和操作算子作了整体分析。第二部分结合Ackley函数优化问题，讲解了遗传算法中个体编码方式、适应函数的选取、父体选择策略、杂交算子、变异算子、参数设置以及演化终止条件等的具体实现过程。

1.遗传算法的基本原理和框架

遗传算法(Genetic Algorithm)是基于"适者生存"的一种高度并行、随机和自适应的优化算法，它将问题的求解表示成"染色体"的适者生存过程，通过"染色体"群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到"最适应环境"的个体，从而求得问题的最优解或满意解。

在遗传算法中，选择、杂交和变异是三个主要操作算子。从图1.1中的算法框架可知，遗传算法的主要操作步骤如下：1.在一定的编码方案下，随机产生一个初始种群(第3行)；2.用相应的解码方法将编码后的个体转换成问题空间的决策变量，并计算初始种群中个体的适应值(第4行)；3.按照个体适应值的大小，从种群中选出适应值较大的一些个体(第6行)；4.由杂交和变异算子对挑选出的个体进行操作，并产生新一代的种群(第7-8行)；5.对新产生的种群进行评估，计算适应值(第9行)；6.反复执行步骤3-5，直至满足收敛判据为止。遗传算法是一种通用的优化算法，其编码技术和遗传操作比较简单，优化不受限制性条件的约束，其搜索过程从问题解的一个集合开始，而不是从单个个体开始，具有隐含并行搜索特性，减小了陷入局部极值的可能。遗传算法主要应用在函数优化和组合优化问题中，在生产调度、自动控制、机器学习、图像处理、人工生命和遗传编码等方面也有着广泛应用。

2.遗传算法的设计与实现

在设计和实现遗传算法时，必须要考虑以下几个问题：个体编码方式、适应函数、父体选择策略、杂交算子、变异算子、参数设置以及终止条件。本文结合Ackley 函数优化问题，实例讲解了遗传算法的整个设计流程和实现过程，并在最后研究分析了目标函数的维数对遗传算法性能的影响。本算法采用C++实现，使用了C++中的类来表示个体和种群，用容器vector来存储和管理数据。

2.1. 问题实例

考虑下面的Ackley 函数优化问题，用遗传算法求解该函数的最小值，并分析维数对算法性能的影响。

2.2. 个体编码方式

采用实数向量编码。对于n维的目标函数，解的编码表示为。

2.3. 适应函数

由于该问题是求解最小值问题，因此，不能直接用目标函数作为适应函数，必须要对目标函数做变换，以保证计算出的适应值为正值，并且越好的个体所对应的适应值越大。在此采用了如下的简单变换：

其中，表示目标函数的上界，是适应函数。通过对目标函数的分析发现，它的最大值不超过30，因此，取的值为30。

2.4. 父体选择策略

父体选择策略采用随机通用采样(Stochastic Universal Sampling)的方法，该方法只用一次随机选择就可确定N 个父体，其实现步骤如下： (1) 根据个体的适应值计算出每个个体的选择概率，计算公式如下：

其中，表示第i 个个体的适应值，表示计算出的第i个个体的选择概率。

(2) 计算每个个体被选择的期望个数，计算公式如下：

其中，表示每个个体被选择的期望个数，N 表示种群的规模。

(3) 构造一个轮盘，该轮盘被划分为N 个扇形区域，每个扇形区域的面积分别与个体被选择的期望个数成正比，N 个指针平均分布在轮盘的中轴上(见图2.1)。将轮盘转动一次，当轮盘停止转动后，N 个指针所指向的个体被选中作为父体参与下一代的演化。

实现通用随机采样的算法代码如算法2.1 所示。

2.5. 杂交算子

杂交算子采用的是整体算术杂交的方式。先依据杂交概率从种群中挑选出偶数个待杂交的个体，这些个体中的每两个个体再随机配对进行杂交。未被挑选出的个体直接进入到下一代中。

假设待杂交的两个个体为：，先随机生成[0, 1]上的N 个随机数，经杂交后得到两个后代为：

同样地，也可以取，在这种情况下，只用随机生成一个随机数，代码在实现时采用的是这种方式。杂交产生的两个个体将会直接取代父体进入到下一代种群中。

实现杂交算子的代码如算法2.2 所示。形参sg 和coPro 分别表示种群和杂交概率。首先依据杂交概率从种群中随机挑选出待杂交的个体构成待杂交个体群(算法第2-7 行)，如果挑选出的个体数目为奇数个，则去掉挑选出的最后一个个体(算法第8-10 行)；对挑选出的个体两两随机配对杂交(算法第11-19 行)，该步骤在实现时，首先随机挑选出第一个杂交父体(算法第12-13 行)，并将该父体从待杂交个体群中剔除掉(算法第14 行)，同样地，再随机挑选出第二个杂交父体(算法第15-17 行)，最后将这两个父体按照整体算术杂交的方式进行杂交，产生的两个新个体替换掉原来的父体进入种群中。

2.6. 变异算子

变异算子采用的是非均匀变异的方式。先依据变异概率从父体中随机挑选出待变异的个体，再对该个体进行变异操作。假设待变异的个体为，其中，非均匀变异按照如下的方式产生一个后代：首先产生[1, n]之间的随机整数k，然后产生变异后代如下：

对于函数，y)，t表示当前演化代数；该函数返回[0, y]之间的值，并且随着代数的增加，该值趋于0 的概率增加。其具体的表达式有以下两种：

其中，r 是[0, 1]上的随机数，T 是最大演化代数，b 是确定非均匀度的参数，取值通常为2~5。

2.7. 参数设置、初始化种群以及终止条件

该算法中种群规模为20(即种群中个体的数目为20)，并且在演化过程中种群的规模保持不变。杂交概率和变异概率分别取0.3 和0.1，即每一代种群中有30%的个体被随机挑选出进行杂交，10%的个体进行变异。最大演化代数是1000，当演化代数达到1000 时，停止演化。在初始化种群时，假设目标函数的维数为n，对于每个个体要随机生成n 个[-30, 30]的随机数，生成方法为：value = -30.0 + 60 * (rand() / RNAD_MAX)。

初始化种群的实现代码如算法2.3 所示，其中SGS 和FD 分别表示种群规模和目标函数的维数。在该问题中SGS 取值为20，FD 可根据需要进行设置，默认取值为2。

代码：

/*------------------------------------------------------------------------------------------------------------- * Genetic Algorithm * min f(x1, x2, ..., xn) = -20 * exp(-0.2 * sqrt((pow(x1, 2) + pow(x2, 2) + ... + pow(xn, 2)) / n)) - * exp((cos(2 * pi * x1) + cos(2 * pi * x2) + ... + cos(2 * pi * xn)) / n) + 20 + e * -30 <= xi <= 30, i = 1, 2, ..., n; e = 2.71282 * Filename : ga.cpp * Date : 2009-10-23 * *------------------------------------------------------------------------------------------------------------- */ #include <iostream> #include <cmath> #include <ctime> #include <fstream> #include "ga.h" ofstream fout; Individual::Individual() { funcValue = 0.0; fitness = 0.0; selectPro = 0.0; } Individual::~Individual() { } SpeciesGroup::SpeciesGroup(int _speciesGroupSize, int _funDim, double _crossoverPro, double _mutatePro, int _maxGen) { crossoverPro = _crossoverPro; mutatePro = _mutatePro; maxGen = _maxGen; funDim = _funDim; bestIndiv = NULL; //初始化种群 species = initializeSpeciesGroup(_speciesGroupSize); //计算初始种群的适应值 bestIndiv = computeFitness(species, bestIndiv); #ifdef PRINT_DETAIL fout << "初始种群:" << endl; outputInfo(species); #endif int i = 0, indiv_sn = 0; while(i++ < maxGen) { //选择父体 species = selectAnstors(species); //杂交 crossover(species, crossoverPro); //变异 mutate(species, i, maxGen, mutatePro); //计算适应值 bestIndiv = computeFitness(species, bestIndiv); #ifdef PRINT_DETAIL fout << "第" << i << "代:" << endl; outputInfo(species); #endif } } SpeciesGroup::~SpeciesGroup() { // 释放掉种群所占用的内存空间 if (species) { while (species->size() != 0) { delete species->back(); species->pop_back(); } delete species; } // 释放掉最优个体所占用的内存空间 if (bestIndiv) { delete bestIndiv; } } vector<Individual *> * SpeciesGroup::initializeSpeciesGroup(int speciesGroupSize) { int i =0, j = 0; vector<Individual *> * species = new vector<Individual *>; for (i = 0; i < speciesGroupSize; i++) { Individual * indiv = new Individual(); for (j = 0; j < funDim; j++) { indiv->value.push_back(X_MIN + (X_MAX - X_MIN) * ((double)rand() / RAND_MAX)); } species->push_back(indiv); } return species; } Individual * SpeciesGroup::computeFitness(vector<Individual *> * species, Individual * bestIndiv) { vector<Individual *>::iterator iteIndiv; vector<double>::iterator iteX; Individual * bestIndivInCurGen = NULL; for (iteIndiv = species->begin(); iteIndiv != species->end(); iteIndiv++) { double part1 = 0.0, part2 = 0.0; for (iteX = (*iteIndiv)->value.begin(); iteX != (*iteIndiv)->value.end(); iteX++) { part1 += (*iteX) * (*iteX); part2 += cos(2 * PI * (*iteX)); } part1 = -0.2 * sqrt(part1 / (*iteIndiv)->value.size()); part2 = part2 / (*iteIndiv)->value.size(); (*iteIndiv)->funcValue = (-20 * exp(part1) - exp(part2) + 20 + 2.71282); (*iteIndiv)->fitness = FUNC_UPPERBOUND - (*iteIndiv)->funcValue; if (bestIndivInCurGen != NULL) { if (bestIndivInCurGen->fitness < (*iteIndiv)->fitness) { bestIndivInCurGen = *iteIndiv; } }else { bestIndivInCurGen = *iteIndiv; } } if (bestIndiv != NULL) { if (bestIndiv->fitness < bestIndivInCurGen->fitness) { delete bestIndiv; bestIndiv = bestIndivInCurGen; } }else { bestIndiv = bestIndivInCurGen; } return bestIndiv; } vector<Individual *> * SpeciesGroup::selectAnstors(vector<Individual *> * species) { // 计算选择概率 double sum_fitness = 0.0; vector<Individual *>::iterator iteIndiv = species->begin(); for (; iteIndiv != species->end(); iteIndiv++) { sum_fitness += (*iteIndiv)->fitness; } for (iteIndiv = species->begin(); iteIndiv != species->end(); iteIndiv++) { (*iteIndiv)->selectPro = (*iteIndiv)->fitness / sum_fitness; } // 采用"随机通用采样"的方式选择个体 vector<Individual *> * newSpecies = new vector<Individual *>; double pro = (double)rand() / RAND_MAX, sum = 0.0; for (iteIndiv = species->begin(); iteIndiv != species->end(); iteIndiv++) { sum += ((*iteIndiv)->selectPro * species->size()); while (pro < sum) { Individual * indiv = new Individual(); vector<double>::iterator iteX = (*iteIndiv)->value.begin(); while(iteX != ((*iteIndiv)->value.end())) { indiv->value.push_back(*iteX); iteX++; } newSpecies->push_back(indiv); pro += 1.0; } } //释放掉原先个体的内存空间 for (iteIndiv = species->begin(); iteIndiv != species->end(); iteIndiv++) { if (*iteIndiv != bestIndiv) { delete (*iteIndiv); } } delete species; return newSpecies; } void SpeciesGroup::crossover(vector<Individual *> * species, double coPro) { vector<Individual *>::iterator iteIndiv = species->begin(); double pro = 0.0; //杂交个体 vector<Individual *> * crossoverSG = new vector<Individual *>; //选择杂交个体 for (iteIndiv = species->begin(); iteIndiv != species->end(); iteIndiv++) { pro = (double)rand() / RAND_MAX; if (pro < coPro) { crossoverSG->push_back(*iteIndiv); } } //杂交个体为奇数个,去掉最后一个 if ((crossoverSG->size()) % 2 == 1) { crossoverSG->pop_back(); } //杂交 while(crossoverSG->size() != 0) { vector<Individual *>::iterator iteIndiv = crossoverSG->begin(); Individual * indiv1 = NULL, * indiv2 = NULL; //获取第一个杂交个体 iteIndiv = (crossoverSG->begin() + rand() % crossoverSG->size()); indiv1 = *iteIndiv; crossoverSG->erase(iteIndiv); //获取第二个杂交个体 iteIndiv = (crossoverSG->begin() + rand() % crossoverSG->size()); indiv2 = *iteIndiv; crossoverSG->erase(iteIndiv); //整体算术杂交 pro = (double)rand() / RAND_MAX; vector<double>::iterator iteX1 = indiv1->value.begin(), iteX2 = indiv2->value.begin(); while((iteX1 != indiv1->value.end()) && (iteX1 != indiv1->value.end())) { double u = *iteX1, v = *iteX2; *iteX1 = pro * u + (1.0 - pro) * v; *iteX2 = pro * v + (1.0 - pro) * u; iteX1++; iteX2++; } } delete crossoverSG; return ; } void SpeciesGroup::mutate(vector<Individual *> * species, int curGen, int maxGen, double mutatePro) { vector<Individual *>::iterator iteIndiv = species->begin(); vector<double>::iterator iteX = (*iteIndiv)->value.begin(); int x_sn = 0; double l = X_MIN, u = X_MAX, r = (double)rand() / RAND_MAX, b = 4.0; // 非均匀变异 for (iteIndiv = species->begin(); iteIndiv != species->end(); iteIndiv++) { if (((double)rand() / RAND_MAX) < mutatePro) { iteX = ((*iteIndiv)->value.begin() + rand() % funDim); r = (double)rand() /RAND_MAX; if ((rand() % 2) == 0) { (*iteX) += (u - (*iteX)) * r * pow(1.0 - curGen / maxGen, b); }else { (*iteX) -= ((*iteX) - l) * r * pow(1.0 - curGen / maxGen, b); } } } } void SpeciesGroup::outputInfo(vector<Individual *> * species) { int indiv_sn = 0; vector<Individual *>::iterator iteIndiv = species->begin(); vector<double>::iterator iteX; for (iteIndiv = species->begin(); iteIndiv != species->end(); iteIndiv++) { fout << "个体" << indiv_sn++ <<"/t:/t适应值 = " << (*iteIndiv)->fitness << "/tX = ("; for (iteX = (*iteIndiv)->value.begin(); iteX != ((*iteIndiv)->value.end() - 1); iteX++) { fout << *iteX << ", "; } fout << *iteX << ")" << endl; } fout << "演化到当前代找到的最优个体:/t适应值 = " << bestIndiv->fitness << "/t函数值" << bestIndiv->funcValue << "/tX = ("; iteX = bestIndiv->value.begin(); for (; iteX != (bestIndiv->value.end() - 1); iteX++) { fout << *iteX << ", "; } fout << *iteX << ")/n" << endl; } int main(int argc, char * argv[]) { SpeciesGroup * sg = NULL; //种群 const int expTimes = EXPERIMENT_TIMES; // 实验次数 const int minFunDim = MIN_FUN_DIM, // 目标函数的维数范围 maxFunDim = MAX_FUN_DIM; vector<double> avgDepartDis; //平均偏离距 vector<double> departDisVariance; //偏离距标准差 vector<Individual *> expBestIndiv; // 每维中多次实验计算的最好个体 srand((unsigned)time(NULL)); fout.open("test.txt"); fout.precision(8); cout << "正在计算......" << endl; #ifdef PRINT_SPEND_TIME clock_t begin = clock(); #endif for (int funDim = minFunDim; funDim <= maxFunDim; funDim++) { // ||ri - r* ||, r_norms[0] is the sum of r_norms[1] to r_norms[expTimes] vector<double> r_norms; r_norms.push_back(0.0); // the minmum avgrage departure distance used to // record the best individual in experiments double expMinADD = -1.0; expBestIndiv.push_back(new Individual()); for (int j = 0; j < expTimes; j++) { double r_norm_temp = 0.0; sg = new SpeciesGroup(SPECIESGROUPSIZE, funDim, CROSSOVER_PRO, MUTATE_PRO, MAX_GEN); //compute the 2-norm vector<double>::iterator iteX = sg->bestIndiv->value.begin(); for (; iteX != sg->bestIndiv->value.end(); iteX++) { r_norm_temp += pow(*iteX, 2.0); } r_norms.push_back(sqrt(r_norm_temp)); //compute the sum of all 2-norm r_norms.front() += r_norms.back(); // get the experiments' best individual if ((expMinADD < 0) || (expMinADD > r_norms.back())) { expMinADD = r_norms.back(); expBestIndiv.back()->value.assign(sg->bestIndiv->value.begin(), sg->bestIndiv->value.end()); expBestIndiv.back()->funcValue = sg->bestIndiv->funcValue; expBestIndiv.back()->fitness = sg->bestIndiv->fitness; expBestIndiv.back()->selectPro = sg->bestIndiv->selectPro; } delete sg; } //compute average departure distance avgDepartDis.push_back(r_norms.front() / expTimes); //compute departure distance varriance departDisVariance.push_back(0.0); vector<double>::iterator ite = r_norms.begin(); for (ite++; ite != r_norms.end(); ite++) { departDisVariance.back() += pow(*ite - avgDepartDis.back(), 2.0); } departDisVariance.back() = sqrt(departDisVariance.back() / expTimes); // print the infomation // fout << "维数/t/t平均偏离距/t/t偏离距方差/t/t函数值/t/t" << endl; fout << funDim << "/t/t" << avgDepartDis.back()<< "/t/t" << departDisVariance.back() << "/t/t" << expBestIndiv.back()->funcValue << endl; #ifdef PRINT_BEST_INDIV fout << "当前维数下计算的最优个体:/t适应值 = " << expBestIndiv.back()->fitness << "/tX = ("; vector<double>::iterator iteX = expBestIndiv.back()->value.begin(); for (; iteX != (expBestIndiv.back()->value.end() - 1); iteX++) { fout << *iteX << ", "; } fout << *iteX << ")/n" << endl; #endif } #ifdef PRINT_SPEND_TIME clock_t end = clock(); fout << "时间花费:" << (double)(end - begin)/CLK_TCK << "s" << endl; #endif fout.close(); while (expBestIndiv.size() != 0) { delete expBestIndiv.back(); expBestIndiv.pop_back(); } return 0; }

最新回复(0)