遗传算法解决简单优化问题的实例

//: 本程序用遗传算法求函数 F(x) = x * x 在区间[0, 255]上的最大值
//：遗传算法用到了轮盘赌选择算法、单点交叉算法、单点变异算法
//: 欢迎批评指正！Email：523192573@ 关同学

#include
#include
#include
#include
using namespace std;

#define DEBUG
//#undef DEBUG

const int CHROMOSOME_LENGTH = 8; // 染色体长度是8位（8bit）

typedef struct INDIVIDUAL
{
int chromosome[CHROMOSOME_LENGTH]; // 基因型
int fitness; // 适应度
} Individual;

void GenerateInitialPopulation(void);
void Select(void);
void Crossover(void);
void Mutate(void);
void Encode(int x, int *chromosome);
int Decode(const int *chromosome);
void CalculateFitness(void);
void CopyIndividual(Individual *dest, const Individual *source);
void SwapIndividual(Individual *a, Individual *b);
int FindBestIndividual(void);
int FindWorstIndividual(void);
double CalculateAverageFitness(void);
void PrintOutlineInfo(int generationCount);
void PrintPopulation(int generationCount);

// 全局变量
int populationSize = 30; // 种群规模
int maxGeneration = populationSize / 2; // 最大世代数
double pc = 0.6; // 交叉概率
double pm = 0.08; // 变异概率
Individual *population; // 种群

// 主函数
int main(void)
{
GenerateInitialPopulation();

#ifdef DEBUG
CalculateFitness();
// PrintPopulation(0);
PrintOutlineInfo(0);
#endif // DEBUG

for (int i=1; i<=maxGeneration; i++)
{
CalculateFitness();
Select();
Crossover();
Mutate();
#ifdef DEBUG
// PrintPopulation(i);
PrintOutlineInfo(i);
#endif // DEBUG
}

CalculateFitness();
int best = FindBestIndividual();
cout << population[best].fitness << endl;

delete population;
}

// 产生初始种群
void GenerateInitialPopulation(void)
{
population = new Individual[populationSize];
if (population == NULL)
{
cout << "Allocate memory failed!" << endl;
exit(0);
}
srand((unsigned)time(NULL)); // 时间作为随机数的种子
for (int i=0; i{
int t = rand() % 256;
Encode(t, population[i].chromosome);
// population[i].fitness = t * t;
}
}

// 计算种群中所有个体的适应度
void CalculateFitness(void)
{
for (int i=0; i{
int t = Decode(population[i].chromosome);
population[i].fitness = t * t;
}
}

// 选择操作
void Select(void)
{
// 求出种群所有个体的适应度之和
double fitnessSum = 0.0;
for (int i=0; ifitnessSum += population[i].fitness;

// 计算累积概率
double *cumulativeProbability = new double[populationSize];
cumulativeProbability[0] = population[0].fitness / fitnessSum;
for (int i=1; icumulativeProbability[i] = cumulativeProbability[i-1] + population[i].fitness / fitnessSum;

// 申请新的内存空间以便

用来存放选择出来的个体
Individual * newPopulation = new Individual[populationSize];
if (newPopulation == NULL)
{
cout << "Allocate memory failed!" << endl;
exit(0);
}

// 用轮盘赌算法从当前种群中选择个体并copy到newPopulation中
srand((unsigned)time(NULL));
for (int i=0; i{
double pointer = rand() % 1001 / (double)1000;
int k = 0;
while (pointer > cumulativeProbability[k])
k++;
CopyIndividual(&newPopulation[i], &population[k]);
}

// 删除旧的population，把选择出的个体组成新的种群
delete population;
population = newPopulation;

// 删除存放累积概率的数组cumulativeProbability
delete cumulativeProbability;
}

// 交叉操作
void Crossover(void)
{
srand((unsigned)time(NULL));

// 重排种群中个体的顺序，模拟随机配对过程
for (int k=0; k{
int i = rand() % populationSize;
int j = rand() % populationSize;
if (i != j)
{
SwapIndividual(&population[i], &population[j]);
}
} // for

// 相邻两个个体以交叉概率pc进行单点交叉
for (int i=0; i{
double p = (double)(rand() % 100) / 100;
if (p <= pc)
{
int pos = rand() % CHROMOSOME_LENGTH;
for (; pos{
int t = population[i].chromosome[pos];
population[i].chromosome[pos] = population[i+1].chromosome[pos];
population[i+1].chromosome[pos] = t;
} // for
} // if
} // for
}

// 变异操作
void Mutate(void)
{
srand((unsigned)time(NULL));

for (int i=0; i{
double p = rand() % 1000 / (double)1000;
if (p <= pm)
{
int pos = rand() % CHROMOSOME_LENGTH;
population[i].chromosome[pos] ^= 1; // 异或可以使特定位翻转
}
}
}

// 编码染色体
void Encode(int x, int *chromosome)
{
for (int i=CHROMOSOME_LENGTH-1; i>=0; i--)
{
chromosome[i] = x % 2;
x /= 2;
}
}

// 解码染色体
int Decode(const int *chromosome)
{
int result = 0;

int t = 1;
for (int i=CHROMOSOME_LENGTH-1; i>=0; i--)
{
result += chromosome[i] * t;
t <<= 1;
}
return result;
}

// 复制个体
void CopyIndividual(Individual *dest, const Individual *source)
{
for (int p=0; p{
dest->chromosome[p] = source->chromosome[p];
}
dest->fitness = source->fitness;
}

// 交换两个个体
void SwapIndividual(Individual *a, Individual *b)
{
int t;

for (int p=0; p{
t = a->chromosome[p];
a->chromosome[p] = b->chromosome[p];
b->chromosome[p] = t;
}
t = a->fitness;
a->fitness = b->fitness;
b->fitness = t;
}

// 找到最好的个体，返回它的下标
int FindBestIndividual(void)
{
int bestIndex = 0;

for (int i=1; iif (population[i].fitness > population[bestIndex].fitness)
bestIndex

= i;
return bestIndex;
}

// 找到最差个体
int FindWorstIndividual(void)
{
int worstIndex = 0;

for (int i=1; iif (population[i].fitness < population[worstIndex].fitness)
worstIndex = i;
return worstIndex;
}

// 计算种群的平均适应度
double CalculateAverageFitness(void)
{
double sum = 0;

for (int i=0; isum += population[i].fitness;

return sum / populationSize;
}

// 打印种群的概要信息（最佳个体适应度、最差个体适应度和平均适应度）
void PrintOutlineInfo(int generationCount)
{
cout << "The -- " << setw(2) << generationCount << " -- generation:" << endl;
cout << "Best individual fitness = " << population[FindBestIndividual()].fitness << endl
<< "Worst individual fitness = " << population[FindWorstIndividual()].fitness << endl
<< "Average fitness = " << CalculateAverageFitness() << endl;
}

// 打印种群中的所有个体
void PrintPopulation(int generationCount)
{
cout << "The -- " << setw(2) << generationCount << " -- generation:" << endl;
for (int i=0; i{
cout << "chromosome = ";
for (int k=0; kcout << population[i].chromosome[k] << ' ';
cout << "; ";
cout << "value = " << setw(3) << Decode(population[i].chromosome) << "; ";
cout << "fitness = " << setw(7) << population[i].fitness << endl;
}
}