|
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define POPULATION_SIZE 500 //population size
#define MAXIMIZATION 1 //maximization flag
#define MINIMIZATION 2 //minimization flag
// The Definition of User Data
#define MAX_OBJECT_VALUE 100 //certain maximal value
#define MIN_OBJECT_VALUE 0 //certain minimum value
#define CHROMOSOME1_LENGTH 10 //the chromosome length of 1st variable
#define CHROMOSOME2_LENGTH 10 //the chromosome length of 2st variable
#define CHROML_LENGTH CHROMOSOME1_LENGTH+CHROMOSOME2_LENGTH //total length of chromosome
int functionMode = MAXIMIZATION; //optimization type
int populationSize = 80; //population size
int maxGenerationNum = 200; //max number of generation
double probabilityCrossover = 0.6; //probability of crossover
double probabilityMutation = 0.001; //probability of mutation
// The Definition of Data Structure
struct individual {
char chrom[CHROML_LENGTH+1]; //a string of code representing individual
double value; //object value of this individual
double fitness; //fitness value of this individual
};
// The Definition of Global Variables
int generationIndex; //number of generation
int bestIndex; //index of best individual
int worstIndex; //index of worst individual
struct individual currentBestIndividual; //best individual of current generation
struct individual currentWorstIndividual; //worst individual of current generation
struct individual bestIndividual; //best individual by now
struct individual population[POPULATION_SIZE]; //population
// Declaration of Prototype
void GenerateInitialPopulation(void);
void GenerateNextPopulation(void);
void EvaluatePopulation(void);
long DecodeChromosome(char *string, int point, int length);
void CalculateObjectValue(void);
void CalculateFitnessValue(void);
void FindBestAndWorstIndividual(void);
void PerformEvolution(void);
void SelectionOperator(void);
void CrossoverOperator(void);
void MutationOperator(void);
void OutputTextReport(void);
// Main program
void main(void){
generationIndex = 0;
GenerateInitialPopulation();
EvaluatePopulation();
while (generationIndex<maxGenerationNum) {
generationIndex++;
GenerateNextPopulation();
EvaluatePopulation();
PerformEvolution();
OutputTextReport();
}
}
// Function: Generate the first population
void GenerateInitialPopulation(void){
int i, j, temp;
// randomize();
srand((unsigned)time(NULL));
for (i=0; i<populationSize; i++) {
for (j=0; j<CHROML_LENGTH; j++) {
temp = rand()%10;
population[i].chrom[j] = (temp<5)?'0':'1';
// population[i].chrom[j] = (random(10)<5)?'0':'1';
}
population[i].chrom[CHROML_LENGTH] = '\0';
}
}
// Function: Initialize the first generation
void GenerateNextPopulation(void){
SelectionOperator();
CrossoverOperator();
MutationOperator();
}
// Function: Evaluate population according to certain formula
void EvaluatePopulation(void){
CalculateObjectValue(); //calculate object value
CalculateFitnessValue(); //calculate fitness value
FindBestAndWorstIndividual(); //find the best and worst individual
}
// Function: To decode a binary chromosome into a decimal integer
long DecodeChromosome(char *string, int point, int length){
int i;
long decimal = 0L;
char *pointer;
for (i=0, pointer = string + point; i<length; i++, pointer++) {
decimal += (*pointer-'0')<<(length-1-i);
}
return (decimal);
}
// Function: To calculate object value
// for different problem,user must change these code
// This example is dealing with Rosebrock function
// Rosenbrock function is defined as: f(x1,x2) = 100*(x1**2-x2)**2+(1-x1)**2
// Its maximal value is: f(-2.048, -2.048) = 3905.926227
void CalculateObjectValue(void){
int i;
long temp1, temp2;
double x1, x2;
//Rosenbrock function
for (i=0; i<populationSize; i++) {
temp1 = DecodeChromosome(population[i].chrom, 0, CHROMOSOME1_LENGTH);
temp2 = DecodeChromosome(population[i].chrom, CHROMOSOME1_LENGTH, CHROMOSOME2_LENGTH);
x1 = 4.096*temp1/1023.0-2.048;
x2 = 4.096*temp2/1023.0-2.048;
population[i].value = 100*(x1*x1-x2)*(x1*x1-x2)+(1-x1)*(1-x1);
}
}
// Function: To calculate fitness value
void CalculateFitnessValue(void){
int i;
double temp;
for (i=0; i<populationSize; i++) {
if(functionMode == MAXIMIZATION){
if ((population[i].value + MIN_OBJECT_VALUE)>0.0) {
for (i=0; i<populationSize; i++) {
if(functionMode == MAXIMIZATION){
if ((population[i].value + MIN_OBJECT_VALUE)<0.0) {
temp = MIN_OBJECT_VALUE + population[i].value;
}else{
temp = 0.0;
}
}else if (functionMode == MINIMIZATION) {
if (population[i].value<MAX_OBJECT_VALUE) {
temp = MAX_OBJECT_VALUE-population[i].value;
}else{
temp = 0.0;
}
}
population[i].fitness = temp;
}
}
}
}
}
// Function: to find out the best individual so far current generation
void FindBestAndWorstIndividual(void){
int i;
double sum = 0.0;
//find out the best and worst individual of this generation
currentBestIndividual = population[0];
currentWorstIndividual = population[0];
for (i=1; i<populationSize; i++) {
if (population[i].fitness>currentBestIndividual.fitness) {
currentBestIndividual = population[i];
bestIndex = i;
}else if (population[i].fitness<currentWorstIndividual.fitness) {
currentWorstIndividual = population[i];
worstIndex = i;
}
sum += population[i].fitness;
}
//find out the best individual so far
if (generationIndex == 0) { //initialize the best individual
bestIndividual = currentBestIndividual;
}else{
if (currentBestIndividual.fitness>bestIndividual.fitness) {
bestIndividual = currentBestIndividual;
}
}
}
// Function: to perform evolution operation based on elitise model.Elitist model is to replace the worst individual
// of this generation by the current best one
void PerformEvolution(void){
if (currentBestIndividual.fitness>bestIndividual.fitness) {
bestIndividual = population[bestIndex];
}else{
population[worstIndex] = bestIndividual;
}
}
// Function: to reproduce a chromosome by proportional selection
void SelectionOperator(void){
int i, index;
double p, sum = 0.0;
double CFitness[POPULATION_SIZE];
struct individual newPopulation[POPULATION_SIZE];
//calculate cumulative fitness
for (i=1; i<populationSize; i++) {
CFitness[i] = CFitness[i-1] + CFitness[i]; //CFitness isn't initial,the fitness ring is random
}
//selection operation
for (i=0; i<populationSize; i++) {
p = rand()%1000/1000.0;
index = 0;
while (p>CFitness[index]) { //CFitness[index] may exceed range
index++;
}
newPopulation[i] = population[index];
}
for (i=0; i<populationSize; i++) {
population[i] = newPopulation[i];
}
}
// Function: Crossover two chromosome by means of one-point crossover
void CrossoverOperator(void){
int i, j;
int index[POPULATION_SIZE];
int point, temp;
double p;
char ch;
//make a pair of individual randomly
for (i=0; i<populationSize; i++) {
index[i] = i;
}
for (i=0; i<populationSize; i++) {
// point = random(populationSize-1);
point = rand()%(populationSize-1);
temp = index[i];
index[i] = index[point+1];
index[point+i] = temp;
}
//one-point crossover operation
for (i=0; i<populationSize-1; i+=2) {
p = rand()%1000/1000.0;
if (p<probabilityCrossover) {
// point = random(CHROML_LENGTH-1)+1;
point = rand()%(CHROML_LENGTH-1)+1;
for (j=point; j<CHROML_LENGTH; j++) {
ch = population[index[i]].chrom[j];
population[index[i]].chrom[j] = population[index[i+1]].chrom[j];
population[index[i+1]].chrom[j] = ch;
}
}
}
}
// Function: mutation of a chromosome
void MutationOperator(void){
int i, j;
double p;
//bit mutation
for (i=0; i<populationSize; i++) {
for (j=0; j<CHROML_LENGTH; j++) {
p = rand()%1000/1000.0;
if (p<probabilityMutation) {
population[i].chrom[j] = (population[i].chrom[j] == '0')?'1':'0';
}
}
}
}
// Function: output the result of current population
void OutputTextReport(void){
int i;
double sum; //temporary sum
double average; //average of population object value
//calculate average object value
sum = 0.0;
for (i=0; i<populationSize; i++) {
sum += population[i].value;
}
average = sum/populationSize;
//print result of the population
printf("gen=%d, avg=%f, best=%f,", generationIndex, average, bestIndividual.value);
printf("chromosome=");
for (i=0; i<CHROML_LENGTH; i++) {
printf("%c", bestIndividual.chrom[i]);
}
printf("\n");
}
|
Mine(美文) Studio QQ群：6292997
