参考博客:
轮盘赌
https://blog.csdn/weixin_45274629/article/details/103480900
随机数产生1
随机数产生2
https://blog.csdn/weixin_43666945/article/details/90287775
一、实验目的
1.掌握遗传算法的基本原理和步骤。
2.熟练使用VC、Java等编程语言编写遗传算法程序。
3.上机编写程序,解决以下函数优化问题:
二、实验设备
Windows 10 , Visual Studio 2019
三、实验原理
1. 遗传算法(Genetic Algorithm):
遗传算法的思想来源于生物进化过程, 它是一种基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法。遗传算法以字符串表示状态空间,用概率搜索过程在该状态空间中搜索,产生新的样本。该算法简单、通用,鲁棒性强,适于并行处理。
2. 基本遗传算法(Simple Genetic Algorithm):
仅使用选择算子、交叉算子、变异算子来产生新种群。
2.1 SGA构成要素
(1)染色体编码方法:对问题解空间的编码,例如二进制编码。
(2)适应度函数(fitness function):评价染色体的好坏。
(3)遗传算子
选择算子:也称为复制算子,指使用某种策略从父代种群中挑选染色体放入下一代种群中策略常用有比例选择与轮盘式方法。
交叉算子:从父代种群中选择两个染色体,使用某种策略使两个染色体交换部分基因,形成两个新染色体放入下一种群中,常用方法有单点一致交叉。
变异算子:按照一定概率,改变父代种群中染色体的基因,得到的新个体加入下一代种群。
(4)运行参数:
N: 种群中个体数量;
T :GA终止进化的代数;
Pc:交叉概率,一般取0.4 ~ 0.99;
Pm:变异概率,一般取0.0001~0.1。
2.2 SGA算法流程
(1)随机产生一个由固定长度字符串组成的初始群体。
(2)对于此群体,迭代执行下述操作,直到满足选种标准。
1)计算群体中每个个体字符串的适应值;
2)应用以下三种操作产生新群体:
·复制:选择个体复制到下一代;
·杂交:选择两个个体,杂交产生新个体;
·变异:选择一个个体,随机选择一位进行变异。
(3)把后代中适应度最高的个体作为结果。
四、实验过程
1、编码
由题目知函数的定义域为 x∈[-10, 10],因为在函数f(x)内x均为平方形式,所以可把函数定义域看为x∈[0, 10]。再根据函数形式,将个体设计为(x1, x2),其中x1与x2为染色体,均由4位基因组成,对应的二进制编码范围是 0000 ~ 1010,个体的结构体设计如下:
typedef struct individual //个体结构体
{
bool chromo1[len]; //染色体x1
bool chromo2[len]; //染色体x2
double fit; //适应度
double prob; //选中概率
}individual;
2、适应度与选择概率的计算
题目要求得到函数的最小值,所以使用f(x)的倒数作为个体对应的适应度,这样可以满足f(x)越小,适应度越大的需求。将种群内的个体适应度相加得到总适应度,每个个体的适应度除以种群总适应度则得到个体的选择概率。
适应度计算的具体代码如下:
//获取个体适应度
double getFitness(individual in)
{
double x1, x2;
double fit = 0;
x1 = getXValue(in.chromo1);
x2 = getXValue(in.chromo2);
if (x1 == 0 && x2 == 0)
return 0;
else
fit = 1 / (pow(x1, 2) + pow(x2, 2)); //f(x)值越小,适应度越高,用1/f(x)表示适应度函数
return fit;
}
3、初始群体的产生
初始种群中每个个体中的两个染色体为(0, 10)的随机数,再将随机数换算为二进制代码形式,作为染色体的基因值。
获得初始种群的代码如下:
//随机获取x的值(0 ~ 10)
int getRanChromo()
{
int ch = 0;
ch = rand() % 10; //获取0~10之间的随机数
return ch;
}
//获取初始种群
void getInitPop(struct individual pop[])
{
int ch1, ch2;
ch1 = ch2 = 0;
totalFit = 0;
for (int i = 0; i < popSize; i++)
{
ch1 = getRanChromo();
ch2 = getRanChromo();
for (int j = len; j > 0; j--)
{
pop[i].chromo1[len - j] = floor(ch1 / pow(2, j - 1));
ch1 = ch1 % (int)pow(2, j - 1);
pop[i].chromo2[len - j] = floor(ch2 / pow(2, j - 1));
ch2 = ch2 % (int)pow(2, j - 1);
}
pop[i].fit = getFitness(pop[i]);
}
totalFit = getTotalFit(pop);
for (int i = 0; i < popSize; i++)
{
pop[i].prob = getProb(pop[i]);
}
//打印初始种群
cout << "第1代种群:" << endl;
popPrintf(pop);
}
4、选择算子
这次实验的选择策略为轮盘式选择,轮盘式选择需要先计算每个个体的选择概率,再按概率的大小将轮盘划分为popSize(种群中个体数)个扇形,选择时转动轮盘,根据参考点落入的区域选则个体。在代码实现过程中,通过将选择概率累加来达到轮盘分区的效果,相当于将轮盘线性化,当产生一个(0, 1)的随机数时,根据随机数所属的累加概率区间,来选择个体。
具体代码实现如下:
//选择(轮盘式)
void selection(struct individual pop[])
{
cout << " 选择一次" << endl;
lineProb[0] = pop[0].prob;
for (int i = 1; i < popSize; i++)//累计概率,使种群内个体的概率线性化
{
lineProb[i] = lineProb[i-1] + pop[i].prob;
}
double r = rand() / double(RAND_MAX);//获取0~1之间随机数
for (int j = 0; j < popSize; j++)//查寻随机数对应的轮盘上的个体
{
if ( r <= lineProb[j])
{
nextPop[nextPopNum] = pop[j];
nextPopNum++;
break;
}
}
}
5、杂交算子
执行杂交操作时,选择单点一致交叉的方法。这种方法先随机选取两个个体,再随机选取一个数i作为交叉点,将两个个体对的应染色体,其第i个及之后的基因进行互换,来达到杂交的目的。在代码实现过程中,先产生随机数来判断是否执行杂交操作,此次实验中杂交概率Pc设置为0.7。由于一次交叉操作会产生两个新个体,所以需要在放入下一代种群前判断是否还有足够空位,若只剩一个空位,则只有一个新个体加入下一代种群,另一个新个体则舍去。除此之外,将杂交得到的新个体加入下一代种群后,需要更新适应度,以便之后选择概率的计算。
具体代码实现如下:
//交叉
void crossover(struct individual pop[])
{
double r1;
int r2, r3, r4;
bool a, b;
r1 = rand() / double(RAND_MAX);//获取0~1之间随机数
//cout << "交叉概率随机数:" << r1 << endl;
if (r1 <= Pc)
{
r2 = (rand() % (popSize));
r3 = (rand() % (popSize));
r4 = (rand() % (len));
cout << " " << r2 << " " << r3 << " " << r4 <<" ";
if (nextPopNum + 1 > popSize - 1)//当前新种群只剩一个位置
{
cout << " 交叉一次,产生一个新个体" << endl;
nextPop[nextPopNum] = pop[r2];
for (int i = r4; i < len; i++)
{
nextPop[nextPopNum].chromo1[i] = pop[r3].chromo1[i];
nextPop[nextPopNum].chromo2[i] = pop[r3].chromo2[i];
}
nextPop[nextPopNum].fit = getFitness(nextPop[nextPopNum]);//更新个体适应度
if (inLegality(nextPop[nextPopNum]))//判断新个体值是否合法
nextPopNum++;
else
nextPopNum--;
}
else //新种群中剩余空位大于等于2
{
cout << " 交叉一次,产生二个新个体" << endl;
nextPop[nextPopNum] = pop[r2];
nextPopNum++;
nextPop[nextPopNum] = pop[r3];
//两个个体进行杂交
for (int i = r4; i < len; i++)
{
a = nextPop[nextPopNum - 1].chromo1[i];
nextPop[nextPopNum - 1].chromo1[i] = nextPop[nextPopNum].chromo1[i];
nextPop[nextPopNum].chromo1[i] = a;
b = nextPop[nextPopNum - 1].chromo2[i];
nextPop[nextPopNum - 1].chromo2[i] = nextPop[nextPopNum].chromo2[i];
nextPop[nextPopNum].chromo2[i] = b;
}
nextPop[nextPopNum - 1].fit = getFitness(nextPop[nextPopNum - 1]);
nextPop[nextPopNum].fit = getFitness(nextPop[nextPopNum]);
//判断新个体值是否合法
if (!inLegality(nextPop[nextPopNum - 1]))
{
if(!inLegality(nextPop[nextPopNum]))
nextPopNum --;
else
nextPop[nextPopNum - 1] = nextPop[nextPopNum];
}
else
{
if (inLegality(nextPop[nextPopNum]))
nextPopNum++;
}
}
//popPrintf(nextPop);
}
else
cout << " 此次未进行交叉" << endl;
}
6、变异算子
变异操作使用一致变异的方法。在代码实现过程中,先产生随机数,判断是否进行变异,这次实验中变异概率Pm设置为0.001。当进行变异时,先随机选取一个个体,再随机选取一个变异位,对个体包含的两个染色体指定位点进行取反,最后再计算新个体的适应度。
具体代码实现如下:
//变异
void mutataion(struct individual pop[])
{
double m1;
int m2, m3;
m1 = rand() / double(RAND_MAX);//获取0~1之间随机数
//cout << "变异概率随机数:" << m1 << endl;
if (m1 < Pm)
{
cout << " 变异一次,产生一个新个体" << endl;
m2 = (rand() % (popSize));
m3 = (rand() % (len));
nextPop[nextPopNum] = pop[m2];
//取反
if (nextPop[nextPopNum].chromo1[m3] == 1)
nextPop[nextPopNum].chromo1[m3] = 0;
else
nextPop[nextPopNum].chromo1[m3] = 1;
//判断新个体值是否合法
if (inLegality(nextPop[nextPopNum]))
nextPopNum++;
else
nextPopNum--;
}
else
cout << " 此次未进行变异" << endl;
}
注:在使用杂交和变异的方法产生新个体后,要对新个体进行检查判断,防止产生超出定义域的无效个体。
五、算法分析与结果讨论
1、算法流程图
2、结果分析
2.1运行时参数设置如下:
const int popSize = 20; //种群大小
const int len = 4; //染色体长度
const double Pc = 0.7; //交叉概率
const double Pm = 0.001; //变异概率
const int generation = 20; //迭代次数(终止条件)
2.2得到运行结果如下:
六、实验分析
此次实验算法的实现,主要依靠老师ppt的原理讲解部分与例题部分以及一些网上的博客,其中算法流程与编码方式参考的是例题。
在算法实现的过程中,遇到了一些问题,主要有有编码设计、轮盘式方法实现和杂交过程实现这几处。其中编码设计是以(x1, x2)为核心的结构体,用四位二进制码表示x,实现了遗传算法的基础操作,但从结果上看有较大的缺陷。这种编码方式没有考虑x取小数的情形,使得最终得到的优化结果也十分粗略,不够接近最小值。对于轮盘式方法的实现,关键是如何用代码模拟随机点落在轮盘对应区域的情形,此次试验通过将选择概率累加的方式,使轮盘面积转化为线性区间,从而根据随机数所属区间来得到轮盘赌结果。最后是杂交过程,杂交的特点是一次性产生两个新个体,这就需注意不要超出下一代种群限制的大小。此次实验在个体杂交之前,先判断下一代种群中所余空间,若剩余一个空间时,则仅有一个新个体传入下一代种群,另一个新个体则舍弃。
此次实验完成过程中,发现自己许多C++基础的知识不清楚或遗忘,写代码过程较为费力,代码总体十分臃肿,还需要花更多时间去修改代码、学习基础知识与算法实践。
七、源代码清单
#include <iostream>
#include <iomanip>
#include <math.h>
#include <ctime>
using namespace std;
/*
*Author:yuzewei
*email:salanderyzw@163
*Date:2020/10/24
*/
const int popSize = 20; //种群大小
const int len = 4; //染色体长度
const double Pc = 0.7; //交叉概率
const double Pm = 0.001; //变异概率
const int generation = 20; //迭代次数(终止条件)
typedef struct individual //个体结构体
{
bool chromo1[len]; //染色体x1
bool chromo2[len]; //染色体x2
double fit; //适应度
double prob; //选中概率
}individual;
struct individual pop[popSize]; //种群
struct individual nextPop[popSize]; //下一代种群
int nextPopNum = 0; //记录当前下一代种群中个体数
double lineProb[popSize]; //线性选择概率(用于轮盘赌)
double totalFit; //总适应度
int gen = 1; //当前代数
double getXValue(bool[]);
double getFitness(individual);
double getProb(individual);
int getRanChromo();
void getInitPop(struct individual []);
bool inLegality(individual);
void selection(struct individual[]);
void crossover(struct individual[]);
void evolution();
void popPrintf(struct individual[]);
int main()
{
srand((unsigned)time(NULL));
getInitPop(pop);
while (gen < generation)
evolution();
cout << "最优解为:f(" << getXValue(pop[0].chromo1) << "," << getXValue(pop[0].chromo2) << ")="
<< pow(getXValue(pop[0].chromo1),2) + pow(getXValue(pop[0].chromo2), 2) <<endl;
return 0;
}
/*获取二进制编码对应的x值*/
double getXValue(bool ch[len])
{
double x;
x = ch[0] * 8.0 + ch[1] * 4.0 + ch[2] * 2.0 + ch[3] * 1.0;
return x;
}
/*获取个体适应度*/
double getFitness(individual in)
{
double x1, x2;
double fit = 0;
x1 = getXValue(in.chromo1);
x2 = getXValue(in.chromo2);
if (x1 == 0 && x2 == 0)
return 0;
else
fit = 1 / (pow(x1, 2) + pow(x2, 2)); //值越小,适应度越高,用1/f(x)表示适应度
return fit;
}
/*获取个体选择概率*/
double getProb(individual in)
{
double prob = 0;
prob = in.fit / totalFit;
return prob;
}
/*随机获取x的值(0 ~ 10)*/
int getRanChromo()
{
int ch = 0;
ch = rand() % 10; //获取0~10之间的随机数
return ch;
}
/*获取总适应度*/
double getTotalFit(struct individual pop[])
{
double totalFit = 0;
for (int i = 0; i < popSize; i++)
totalFit += pop[i].fit;
return totalFit;
}
/*获取初始种群*/
void getInitPop(struct individual pop[])
{
int ch1, ch2;
ch1 = ch2 = 0;
totalFit = 0;
for (int i = 0; i < popSize; i++)
{
ch1 = getRanChromo();
ch2 = getRanChromo();
for (int j = len; j > 0; j--)
{
pop[i].chromo1[len - j] = floor(ch1 / pow(2, j - 1));
ch1 = ch1 % (int)pow(2, j - 1);
pop[i].chromo2[len - j] = floor(ch2 / pow(2, j - 1));
ch2 = ch2 % (int)pow(2, j - 1);
}
pop[i].fit = getFitness(pop[i]);
}
totalFit = getTotalFit(pop);
for (int i = 0; i < popSize; i++)
{
pop[i].prob = getProb(pop[i]);
}
//打印初始种群
cout << "第1代种群:" << endl;
popPrintf(pop);
}
/*判断(杂交与变异所得)个体值是否符合要求*/
bool inLegality(individual in)
{
double x1, x2;
x1 = getXValue(in.chromo1);
x2 = getXValue(in.chromo2);
if (x1 > 10 || x2 > 10)
return 0;
else
return 1;
}
/*选择(轮盘式)*/
void selection(struct individual pop[])
{
cout << " 选择一次" << endl;
lineProb[0] = pop[0].prob;
for (int i = 1; i < popSize; i++)//累计概率,使种群内个体的概率线性化
{
lineProb[i] = lineProb[i-1] + pop[i].prob;
}
double r = rand() / double(RAND_MAX);//获取0~1之间随机数
//cout << "轮盘赌随机数:" << r << endl;
for (int j = 0; j < popSize; j++)//查询随机数对应的轮盘上的个体
{
if ( r <= lineProb[j])
{
nextPop[nextPopNum] = pop[j];
nextPopNum++;
break;
}
}
}
/*交叉*/
void crossover(struct individual pop[])
{
double r1;
int r2, r3, r4;
bool a, b;
r1 = rand() / double(RAND_MAX);//获取0~1之间随机数
if (r1 <= Pc)
{
r2 = (rand() % (popSize));
r3 = (rand() % (popSize));
r4 = (rand() % (len));
if (nextPopNum + 1 > popSize - 1)//当前新种群只剩一个位置
{
cout << " 交叉一次,产生一个新个体" << endl;
nextPop[nextPopNum] = pop[r2];
for (int i = r4; i < len; i++)
{
nextPop[nextPopNum].chromo1[i] = pop[r3].chromo1[i];
nextPop[nextPopNum].chromo2[i] = pop[r3].chromo2[i];
}
nextPop[nextPopNum].fit = getFitness(nextPop[nextPopNum]); //更新个体适应度
if (inLegality(nextPop[nextPopNum])) //判断新个体值是否合法
nextPopNum++;
else
nextPopNum--;
}
else //新种群中剩余空位大于等于2
{
cout << " 交叉一次,产生二个新个体" << endl;
nextPop[nextPopNum] = pop[r2];
nextPopNum++;
nextPop[nextPopNum] = pop[r3];
//两个个体进行杂交
for (int i = r4; i < len; i++)
{
a = nextPop[nextPopNum - 1].chromo1[i];
nextPop[nextPopNum - 1].chromo1[i] = nextPop[nextPopNum].chromo1[i];
nextPop[nextPopNum].chromo1[i] = a;
b = nextPop[nextPopNum - 1].chromo2[i];
nextPop[nextPopNum - 1].chromo2[i] = nextPop[nextPopNum].chromo2[i];
nextPop[nextPopNum].chromo2[i] = b;
}
//更新适应度
nextPop[nextPopNum - 1].fit = getFitness(nextPop[nextPopNum - 1]);
nextPop[nextPopNum].fit = getFitness(nextPop[nextPopNum]);
//判断新个体值是否合法
if (!inLegality(nextPop[nextPopNum - 1]))
{
if(!inLegality(nextPop[nextPopNum]))
nextPopNum --;
else
nextPop[nextPopNum - 1] = nextPop[nextPopNum];
}
else
{
if (inLegality(nextPop[nextPopNum]))
nextPopNum++;
}
}
}
else
cout << " 此次未进行交叉" << endl;
}
/*变异*/
void mutataion(struct individual pop[])
{
double m1;
int m2, m3;
m1 = rand() / double(RAND_MAX);//获取0~1之间随机数
if (m1 < Pm)
{
cout << " 变异一次,产生一个新个体" << endl;
m2 = (rand() % (popSize));
m3 = (rand() % (len));
nextPop[nextPopNum] = pop[m2];
//取反
if (nextPop[nextPopNum].chromo1[m3] == 1)
nextPop[nextPopNum].chromo1[m3] = 0;
else
nextPop[nextPopNum].chromo1[m3] = 1;
//判断新个体值是否合法
if (inLegality(nextPop[nextPopNum]))
nextPopNum++;
else
nextPopNum--;
}
else
cout << " 此次未进行变异" << endl;
}
/*进化*/
void evolution()
{
gen++;
cout << "第" << gen << "代种群:" << endl;
//遗传操作
while (nextPopNum < popSize)
{
selection(pop);
if (nextPopNum == popSize) break;
crossover(pop);
if (nextPopNum == popSize) break;
mutataion(pop);
if (nextPopNum == popSize) break;
}
//更新选择概率
totalFit = getTotalFit(nextPop);
for (int i = 0; i < popSize; i++)
nextPop[i].prob = getProb(nextPop[i]);
//打印新种群
popPrintf(nextPop);
//更新种群存储空间
for (int i = 0; i < popSize; i++)
pop[i] = nextPop[i];
nextPopNum = 0;
}
/*打印种群*/
void popPrintf(struct individual pop[])
{
for (int i = 0; i < popSize; i++)
{
for (int j = 0; j < len; j++)
cout << pop[i].chromo1[j];
cout << " ";
for (int j = 0; j < len; j++)
cout << pop[i].chromo2[j];
cout << " ";
cout << setw(10) << left<< pop[i].fit;
cout << " ";
cout << pop[i].prob;
cout << endl;
}
}
更多推荐
遗传算法及c++实现
发布评论