C++ implements genetic algorithm
- 2020-05-05 11:42:32
- OfStack
In this paper, a simple genetic algorithm is implemented by C++. Share with you for your reference. The specific implementation method is as follows:
// CMVSOGA.h : main header file for the CMVSOGA.cpp
////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////
#if !defined(AFX_CMVSOGA_H__45BECA_61EB_4A0E_9746_9A94D1CCF767__INCLUDED_)
#define AFX_CMVSOGA_H__45BECA_61EB_4A0E_9746_9A94D1CCF767__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include "Afxtempl.h"
#define variablenum 14
class CMVSOGA
{
public:
CMVSOGA();
~CMVSOGA();
void selectionoperator();
void crossoveroperator();
void mutationoperator();
void initialpopulation(int, int ,double ,double,double *,double *); // Population initialization
void generatenextpopulation(); // Generation of next generation population
void evaluatepopulation(); // Evaluate the individual, find the best individual
void calculateobjectvalue(); // Calculate the value of the target function
void calculatefitnessvalue(); // Calculate the fitness function
void findbestandworstindividual(); // Look for the best and the worst
void performevolution();
void GetResult(double *);
void GetPopData(CList <double,double>&);
void SetFitnessData(CList <double,double>&,CList <double,double>&,CList <double,double>&);
private:
struct individual
{
double chromosome[variablenum]; // The length of the chromosome code should be the number of variables
double value;
double fitness; // fitness
};
double variabletop[variablenum]; // A variable's value
double variablebottom[variablenum]; // A variable's value
int popsize; // The population size
// int generation; // generations
int best_index;
int worst_index;
double crossoverrate; // Crossover rate
double mutationrate; // The mutation rate
int maxgeneration; // Maximum generation number
struct individual bestindividual; // The best individual
struct individual worstindividual; // The worst individual
struct individual current; // The current individual
struct individual current1; // The current individual
struct individual currentbest; // Current best
CList <struct individual,struct individual &> population; // population
CList <struct individual,struct individual &> newpopulation; // A new species
CList <double,double> cfitness; // Store the fitness value
// How to make the linked list data a structure ???? The idea is to make a linked list of populations. Save space.
};
#endif
Execution file:
// CMVSOGA.cpp : implementation file
//
#include "stdafx.h"
//#include "vld.h"
#include "CMVSOGA.h"
#include "math.h"
#include "stdlib.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
/////////////////////////////////////////////////////////////////////////////
// CMVSOGA.cpp
CMVSOGA::CMVSOGA()
{
best_index=0;
worst_index=0;
crossoverrate=0; // Crossover rate
mutationrate=0; // The mutation rate
maxgeneration=0;
}
CMVSOGA::~CMVSOGA()
{
best_index=0;
worst_index=0;
crossoverrate=0; // Crossover rate
mutationrate=0; // The mutation rate
maxgeneration=0;
population.RemoveAll(); // population
newpopulation.RemoveAll(); // A new species
cfitness.RemoveAll();
}
void CMVSOGA::initialpopulation(int ps, int gen ,double cr ,double mr,double *xtop,double *xbottom) // The first step is initialization.
{
// Some strategy should be adopted to ensure that the initialization of genetic algorithm is reasonable. What is the selected center point?
int i,j;
popsize=ps;
maxgeneration=gen;
crossoverrate=cr;
mutationrate =mr;
for (i=0;i<variablenum;i++)
{
variabletop[i] =xtop[i];
variablebottom[i] =xbottom[i];
}
//srand( (unsigned)time( NULL ) ); // Find a true random number generation function.
for(i=0;i<popsize;i++)
{
for (j=0;j<variablenum ;j++)
{
current.chromosome[j]=double(rand()%10000)/10000*(variabletop[j]-variablebottom[j])+variablebottom[j];
}
current.fitness=0;
current.value=0;
population.InsertAfter(population.FindIndex(i),current);// Except for initial use insertafter outside , Other use setat Command.
}
}
void CMVSOGA::generatenextpopulation()// Third, generate the next generation.
{
//srand( (unsigned)time( NULL ) );
selectionoperator();
crossoveroperator();
mutationoperator();
}
//void CMVSOGA::evaluatepopulation() // The second step is to evaluate the individual and find the best one
//{
// calculateobjectvalue();
// calculatefitnessvalue(); // Sort by fitness value in this step . Sort of linked lists .
// findbestandworstindividual();
//}
void CMVSOGA:: calculateobjectvalue() // Calculate the function value, should be implemented by the external function. Mainly because the target function is complicated.
{
int i,j;
double x[variablenum];
for (i=0; i<popsize; i++)
{
current=population.GetAt(population.FindIndex(i));
current.value=0;
// Using an external function, where only the result is passed.
for (j=0;j<variablenum;j++)
{
x[j]=current.chromosome[j];
current.value=current.value+(j+1)*pow(x[j],4);
}
//// Using an external function, where only the result is passed.
population.SetAt(population.FindIndex(i),current);
}
}
void CMVSOGA::mutationoperator() // The selection of mutation operator is of decisive significance for floating point number coding.
// Need to be guass The normal distribution function generates a variance of sigma , the mean is the coded value of a floating point number c .
{
// srand((unsigned int) time (NULL));
int i,j;
double r1,r2,p,sigma;//sigma Gaussian variation parameter
for (i=0;i<popsize;i++)
{
current=population.GetAt(population.FindIndex(i));
// The generated mean is current.chromosome , the variance of sigma Of the gaussian distribution
for(j=0; j<variablenum; j++)
{
r1 = double(rand()%10001)/10000;
r2 = double(rand()%10001)/10000;
p = double(rand()%10000)/10000;
if(p<mutationrate)
{
double sign;
sign=rand()%2;
sigma=0.01*(variabletop[j]-variablebottom [j]);
// Gauss mutation
if(sign)
{
current.chromosome[j] = (current.chromosome[j]
+ sigma*sqrt(-2*log(r1)/0.4323)*sin(2*3.1415926*r2));
}
else
{
current.chromosome[j] = (current.chromosome[j]
- sigma*sqrt(-2*log(r1)/0.4323)*sin(2*3.1415926*r2));
}
if (current.chromosome[j]>variabletop[j])
{
current.chromosome[j]=double(rand()%10000)/10000*(variabletop[j]-variablebottom[j])+variablebottom[j];
}
if (current.chromosome[j]<variablebottom [j])
{
current.chromosome[j]=double(rand()%10000)/10000*(variabletop[j]-variablebottom[j])+variablebottom[j];
}
}
}
population.SetAt(population.FindIndex(i),current);
}
}
void CMVSOGA::selectionoperator() // The new population is selected probabilistically from the current population , A copy selection should be added , Increase the average fitness of the population
{
int i,j,pindex=0;
double p,pc,sum;
i=0;
j=0;
pindex=0;
p=0;
pc=0;
sum=0.001;
newpopulation.RemoveAll();
cfitness.RemoveAll();
// List order
// population.SetAt (population.FindIndex(0),current); // Redundant code
for (i=1;i<popsize;i++)
{
current=population.GetAt(population.FindIndex(i));
for(j=0;j<i;j++) // Growing up before Alignment.
{
current1=population.GetAt(population.FindIndex(j));// Temporary borrowing variable
if(current.fitness<=current1.fitness)
{
population.InsertBefore(population.FindIndex(j),current);
population.RemoveAt(population.FindIndex(i+1));
break;
}
}
// m=population.GetCount();
}
// List order
for(i=0;i<popsize;i++)// Seek the total value of fitness for normalization , It's a sorted chain.
{
current=population.GetAt(population.FindIndex(i)); // There is a problem with the value being fetched .
sum+=current.fitness;
}
for(i=0;i<popsize; i++)// The normalized
{
current=population.GetAt(population.FindIndex(i)); //population Have a value , Why didn't it come out right ??
current.fitness=current.fitness/sum;
cfitness.InsertAfter (cfitness .FindIndex(i),current.fitness);
}
for(i=1;i<popsize; i++)// The probability value goes from small to large ;
{
current.fitness=cfitness.GetAt (cfitness.FindIndex(i-1))
+cfitness.GetAt(cfitness.FindIndex(i)); // The normalized
cfitness.SetAt (cfitness .FindIndex(i),current.fitness);
population.SetAt(population.FindIndex(i),current);
}
for (i=0;i<popsize;)// Roulette odds. There are questions in this paragraph.
{
p=double(rand()%999)/1000+0.0001; // Probability of random generation
pindex=0; // Traverse index
pc=cfitness.GetAt(cfitness.FindIndex(1)); // Why can't I get the value ???20060910
while(p>=pc&&pindex<popsize) // The problem.
{
pc=cfitness.GetAt(cfitness .FindIndex(pindex));
pindex++;
}
// Must be from index~popsize Choose the number with high probability. Greater than probability p The number of should be selected, select the dissatisfaction for the next selection.
for (j=popsize-1;j<pindex&&i<popsize;j--)
{
newpopulation.InsertAfter (newpopulation.FindIndex(0),
population.GetAt (population.FindIndex(j)));
i++;
}
}
for(i=0;i<popsize; i++)
{
population.SetAt (population.FindIndex(i),
newpopulation.GetAt (newpopulation.FindIndex(i)));
}
// j=newpopulation.GetCount();
// j=population.GetCount();
newpopulation.RemoveAll();
}
//current After the change, there is no problem.
void CMVSOGA:: crossoveroperator() // Nonuniform arithmetic linear crossing, floating point Numbers apply ,alpha ,beta is (0 . 1) Random number between
// The selection of pairs of intersecting individuals in the population was also random. Also desirable beta=1-alpha;
//current There will be some changes.
{
int i,j;
double alpha,beta;
CList <int,int> index;
int point,temp;
double p;
// srand( (unsigned)time( NULL ) );
for (i=0;i<popsize;i++)// Generate a sequence number
{
index.InsertAfter (index.FindIndex(i),i);
}
for (i=0;i<popsize;i++)// Disturb the serial number
{
point=rand()%(popsize-1);
temp=index.GetAt(index.FindIndex(i));
index.SetAt(index.FindIndex(i),
index.GetAt(index.FindIndex(point)));
index.SetAt(index.FindIndex(point),temp);
}
for (i=0;i<popsize-1;i+=2)
{// Number in order , According to the sequence number to select two maternal crossover operation.
p=double(rand()%10000)/10000.0;
if (p<crossoverrate)
{
alpha=double(rand()%10000)/10000.0;
beta=double(rand()%10000)/10000.0;
current=population.GetAt(population.FindIndex(index.GetAt(index.FindIndex(i))));
current1=population.GetAt(population.FindIndex(index.GetAt(index.FindIndex(i+1))));// For the temporary use current1 Instead of
for(j=0;j<variablenum;j++)
{
// cross
double sign;
sign=rand()%2;
if(sign)
{
current.chromosome[j]=(1-alpha)*current.chromosome[j]+
beta*current1.chromosome[j];
}
else
{
current.chromosome[j]=(1-alpha)*current.chromosome[j]-
beta*current1.chromosome[j];
}
if (current.chromosome[j]>variabletop[j]) // Determine whether or not the bounds are crossed .
{
current.chromosome[j]=double(rand()%10000)/10000*(variabletop[j]-variablebottom[j])+variablebottom[j];
}
if (current.chromosome[j]<variablebottom [j])
{
current.chromosome[j]=double(rand()%10000)/10000*(variabletop[j]-variablebottom[j])+variablebottom[j];
}
if(sign)
{
current1.chromosome[j]=alpha*current.chromosome[j]+
(1- beta)*current1.chromosome[j];
}
else
{
current1.chromosome[j]=alpha*current.chromosome[j]-
(1- beta)*current1.chromosome[j];
}
if (current1.chromosome[j]>variabletop[j])
{
current1.chromosome[j]=double(rand()%10000)/10000*(variabletop[j]-variablebottom[j])+variablebottom[j];
}
if (current1.chromosome[j]<variablebottom [j])
{
current1.chromosome[j]=double(rand()%10000)/10000*(variabletop[j]-variablebottom[j])+variablebottom[j];
}
}
// Back to the generation of
}
newpopulation.InsertAfter (newpopulation.FindIndex(i),current);
newpopulation.InsertAfter (newpopulation.FindIndex(i),current1);
}
ASSERT(newpopulation.GetCount()==popsize);
for (i=0;i<popsize;i++)
{
population.SetAt (population.FindIndex(i),
newpopulation.GetAt (newpopulation.FindIndex(i)));
}
newpopulation.RemoveAll();
index.RemoveAll();
}
void CMVSOGA:: findbestandworstindividual( )
{
int i;
bestindividual=population.GetAt(population.FindIndex(best_index));
worstindividual=population.GetAt(population.FindIndex(worst_index));
for (i=1;i<popsize; i++)
{
current=population.GetAt(population.FindIndex(i));
if (current.fitness>bestindividual.fitness)
{
bestindividual=current;
best_index=i;
}
else if (current.fitness<worstindividual.fitness)
{
worstindividual=current;
worst_index=i;
}
}
population.SetAt(population.FindIndex(worst_index),
population.GetAt(population.FindIndex(best_index)));
// Replace the worst with the best.
if (maxgeneration==0)
{
currentbest=bestindividual;
}
else
{
if(bestindividual.fitness>=currentbest.fitness)
{
currentbest=bestindividual;
}
}
}
void CMVSOGA:: calculatefitnessvalue() // Fitness function value calculation, the key is the design of fitness function
//current Change, this program changes a lot, especially sort.
{
int i;
double temp;//alpha,beta;// Scale variation coefficient of fitness function
double cmax=100;
for(i=0;i<popsize;i++)
{
current=population.GetAt(population.FindIndex(i));
if(current.value<cmax)
{
temp=cmax-current.value;
}
else
{
temp=0.0;
}
/*
if((population[i].value+cmin)>0.0)
{temp=cmin+population[i].value;}
else
{temp=0.0;
}
*/
current.fitness=temp;
population.SetAt(population.FindIndex(i),current);
}
}
void CMVSOGA:: performevolution() // Demonstrate evaluation results , There is redundant code ,current Change, the program should change more
{
if (bestindividual.fitness>currentbest.fitness)
{
currentbest=population.GetAt(population.FindIndex(best_index));
}
else
{
population.SetAt(population.FindIndex(worst_index),currentbest);
}
}
void CMVSOGA::GetResult(double *Result)
{
int i;
for (i=0;i<variablenum;i++)
{
Result[i]=currentbest.chromosome[i];
}
Result[i]=currentbest.value;
}
void CMVSOGA::GetPopData(CList <double,double>&PopData)
{
PopData.RemoveAll();
int i,j;
for (i=0;i<popsize;i++)
{
current=population.GetAt(population.FindIndex(i));
for (j=0;j<variablenum;j++)
{
PopData.AddTail(current.chromosome[j]);
}
}
}
void CMVSOGA::SetFitnessData(CList <double,double>&PopData,CList <double,double>&FitnessData,CList <double,double>&ValueData)
{
int i,j;
for (i=0;i<popsize;i++)
{
current=population.GetAt(population.FindIndex(i)); // Because of this sentence, there is a big problem.
for (j=0;j<variablenum;j++)
{
current.chromosome[j]=PopData.GetAt(PopData.FindIndex(i*variablenum+j));
}
current.fitness=FitnessData.GetAt(FitnessData.FindIndex(i));
current.value=ValueData.GetAt(ValueData.FindIndex(i));
population.SetAt(population.FindIndex(i),current);
}
FitnessData.RemoveAll();
PopData.RemoveAll();
ValueData.RemoveAll();
}
# re: C++ Genetic algorithm source program
/********************************************************************
Filename: aiWorld.h
Purpose: Genetic algorithm, flower evolution.
Id:
Copyright:
Licence:
*********************************************************************/
#ifndef AIWORLD_H_
#define AIWORLD_H_
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cmath>
#define kMaxFlowers 10
using std::cout;
using std::endl;
class ai_World
{
public:
ai_World()
{
srand(time(0));
}
~ai_World() {}
int temperature[kMaxFlowers]; // The temperature
int water[kMaxFlowers]; // The water quality
int sunlight[kMaxFlowers]; // The sun
int nutrient[kMaxFlowers]; // nutrient
int beneficialInsect[kMaxFlowers]; // Beneficial insects
int harmfulInsect[kMaxFlowers]; // pests
int currentTemperature;
int currentWater;
int currentSunlight;
int currentNutrient;
int currentBeneficialInsect;
int currentHarmfulInsect;
/**
First generation flower
*/
void Encode();
/**
Flower fit function
*/
int Fitness(int flower);
/**
Flower evolution
*/
void Evolve();
/**
Returns the interval [start, end] The random number
*/
inline int tb_Rnd(int start, int end)
{
if (start > end)
return 0;
else
{
//srand(time(0));
return (rand() % (end + 1) + start);
}
}
/**
According to the numerical
*/
void show();
};
// ----------------------------------------------------------------- //
void ai_World::Encode()
// ----------------------------------------------------------------- //
{
int i;
for (i=0;i<kMaxFlowers;i++)
{
temperature[i]=tb_Rnd(1,75);
water[i]=tb_Rnd(1,75);
sunlight[i]=tb_Rnd(1,75);
nutrient[i]=tb_Rnd(1,75);
beneficialInsect[i]=tb_Rnd(1,75);
harmfulInsect[i]=tb_Rnd(1,75);
}
currentTemperature=tb_Rnd(1,75);
currentWater=tb_Rnd(1,75);
currentSunlight=tb_Rnd(1,75);
currentNutrient=tb_Rnd(1,75);
currentBeneficialInsect=tb_Rnd(1,75);
currentHarmfulInsect=tb_Rnd(1,75);
currentTemperature=tb_Rnd(1,75);
currentWater=tb_Rnd(1,75);
currentSunlight=tb_Rnd(1,75);
currentNutrient=tb_Rnd(1,75);
currentBeneficialInsect=tb_Rnd(1,75);
currentHarmfulInsect=tb_Rnd(1,75);
}
// ----------------------------------------------------------------- //
int ai_World::Fitness(int flower)
// ----------------------------------------------------------------- //
{
int theFitness;
theFitness=abs(temperature[flower]-currentTemperature);
theFitness=theFitness+abs(water[flower]-currentWater);
theFitness=theFitness+abs(sunlight[flower]-currentSunlight);
theFitness=theFitness+abs(nutrient[flower]-currentNutrient);
theFitness=theFitness+abs(beneficialInsect[flower]-currentBeneficialInsect);
theFitness=theFitness+abs(harmfulInsect[flower]-currentHarmfulInsect);
return (theFitness);
}
// ----------------------------------------------------------------- //
void ai_World::Evolve()
// ----------------------------------------------------------------- //
{
int fitTemperature[kMaxFlowers];
int fitWater[kMaxFlowers];
int fitSunlight[kMaxFlowers];
int fitNutrient[kMaxFlowers];
int fitBeneficialInsect[kMaxFlowers];
int fitHarmfulInsect[kMaxFlowers];
int fitness[kMaxFlowers];
int i;
int leastFit=0;
int leastFitIndex;
for (i=0;i<kMaxFlowers;i++)
if (Fitness(i)>leastFit)
{
leastFit=Fitness(i);
leastFitIndex=i;
}
temperature[leastFitIndex]=temperature[tb_Rnd(0,kMaxFlowers - 1)];
water[leastFitIndex]=water[tb_Rnd(0,kMaxFlowers - 1)];
sunlight[leastFitIndex]=sunlight[tb_Rnd(0,kMaxFlowers - 1)];
nutrient[leastFitIndex]=nutrient[tb_Rnd(0,kMaxFlowers - 1)];
beneficialInsect[leastFitIndex]=beneficialInsect[tb_Rnd(0,kMaxFlowers - 1)];
harmfulInsect[leastFitIndex]=harmfulInsect[tb_Rnd(0,kMaxFlowers - 1)];
for (i=0;i<kMaxFlowers;i++)
{
fitTemperature[i]=temperature[tb_Rnd(0,kMaxFlowers - 1)];
fitWater[i]=water[tb_Rnd(0,kMaxFlowers - 1)];
fitSunlight[i]=sunlight[tb_Rnd(0,kMaxFlowers - 1)];
fitNutrient[i]=nutrient[tb_Rnd(0,kMaxFlowers - 1)];
fitBeneficialInsect[i]=beneficialInsect[tb_Rnd(0,kMaxFlowers - 1)];
fitHarmfulInsect[i]=harmfulInsect[tb_Rnd(0,kMaxFlowers - 1)];
}
for (i=0;i<kMaxFlowers;i++)
{
temperature[i]=fitTemperature[i];
water[i]=fitWater[i];
sunlight[i]=fitSunlight[i];
nutrient[i]=fitNutrient[i];
beneficialInsect[i]=fitBeneficialInsect[i];
harmfulInsect[i]=fitHarmfulInsect[i];
}
for (i=0;i<kMaxFlowers;i++)
{
if (tb_Rnd(1,100)==1)
temperature[i]=tb_Rnd(1,75);
if (tb_Rnd(1,100)==1)
water[i]=tb_Rnd(1,75);
if (tb_Rnd(1,100)==1)
sunlight[i]=tb_Rnd(1,75);
if (tb_Rnd(1,100)==1)
nutrient[i]=tb_Rnd(1,75);
if (tb_Rnd(1,100)==1)
beneficialInsect[i]=tb_Rnd(1,75);
if (tb_Rnd(1,100)==1)
harmfulInsect[i]=tb_Rnd(1,75);
}
}
void ai_World::show()
{
// cout << "/t temperature water sunlight nutrient beneficialInsect harmfulInsect/n";
cout << "current/t " << currentTemperature << "/t " << currentWater << "/t ";
cout << currentSunlight << "/t " << currentNutrient << "/t ";
cout << currentBeneficialInsect << "/t " << currentHarmfulInsect << "/n";
for (int i=0;i<kMaxFlowers;i++)
{
cout << "Flower " << i << ": ";
cout << temperature[i] << "/t ";
cout << water[i] << "/t ";
cout << sunlight[i] << "/t ";
cout << nutrient[i] << "/t ";
cout << beneficialInsect[i] << "/t ";
cout << harmfulInsect[i] << "/t ";
cout << endl;
}
}
#endif // AIWORLD_H_
//test.cpp
#include <iostream>
#include "ai_World.h"
using namespace std;
int main()
{
ai_World a;
a.Encode();
// a.show();
for (int i = 0; i < 10; i++)
{
cout << "Generation " << i << endl;
a.Evolve();
a.show();
}
system("PAUSE");
return 0;
}
I hope this article is helpful for your C++ programming.