Genetic algorithm initial seed diversity usage value encoding C #

public Chromosome(Random rand) 
 {
 Alele = new List();
 for (int i = 0; i  {
 Alele.Add(rand.NextDouble () * 2000-1000);
 }
 }

private bool CheckSimilarFitnes(List chromosome, Chromosome newCandidate) 
 {
 Boolean flag=false;
 double fitFromList, fitFromCandidate;
 double fitBigger,fitSmaller;

 foreach (var listElement in chromosome)
 {
 fitFromList = listElement.CalculateChromosomeFitness(listElement.Alele); 
 fitFromCandidate = newCandidate.CalculateChromosomeFitness( newCandidate.Alele);
 fitBigger = fitFromList >= fitFromCandidate? fitFromList: fitFromCandidate;
 fitSmaller = fitFromList 
 if ((fitFromList / fitFromCandidate) < 1.5) 
 return false
 }

 else return true;

 }

GEN: fitness (allele, ...) 
 0: 375.47460 (583.640, -4.215, -78.418, 164.228, -243.982, -250.237, 354.559, 374.306, 709.859, 115.323)

100: 68.11683 (-154.818, -173.378, -170.846, -193.750, -198.722, -396.502, -464.710, -450.014, -422.194, -407.162)
 ...
10000: 6.01724 (-269.681, -267.947, -273.282, -281.582, -287.407, -293.622, -302.050, -307.582 , -308.198, -308.648)
 ...
99999: 0.67262 (-294.746, -293.906, -293.114, -292.632, -292.596, -292.911, -292.808, -292.039, -291.112,- 290.928)

// try to pack the aleles together spaced apart by 1.0
// returns the standard deviation of the samples from 1.0
static float Eval_OrderedDistance(Chromosome c) {
 float sum = 0;
 int n = c.alele.Length;
 for(int i=1; i float diff = (c.alele[i]-c.alele[i-1])-1.0 f; 
 sum += diff*diff; // variance from 1.0
 }

 return (float)Math.Sqrt(sum/n);
}< /pre> 
And mutation. I used a simple crossover and "completely change one allele":
 
 
Chromosome ChangeOne(Chromosome c) {
 Chromosome d = c.Clone();
 int i = rand.Next()% d.alele.Length;
 d.alele[i] = (float)(rand.NextDouble()* 2000-1000);
 return d;
}
I use elitism to maintain an exact copy of the best chromosomes. Then use mutation and crossover to generate 100 new chromosomes .
This sounds like calculating the variance of fitness, which of course will tell you that the fitness in your population is about the same. I find it very important for you to define fitness functions. The finer the fitness function , The more you can distinguish your chromosomes. Obviously, your fitness function returns similar values ​​for completely different chromosomes, because your gen 0 returns a fitness variance of 68e-19.
You can Share your health calculations? Or what problem do you ask GA to solve? I think this can help us help you.
[Edit: add clear fitness sharing/Niching]
I reconsidered this and updated my code. If you want to remain unique You have to compare their contents (as others have mentioned). One way is to calculate the standard deviation between them. If it is below a certain threshold, you can consider them to be the same. From the class chromosome :

// compute the population standard deviation
public float StdDev(Chromosome other) {
 float sum = 0.0f;
 for( int i=0; i float diff = other.alele[i]-alele[i];
 sum += diff*diff;
 }< br /> return (float)Math.Sqrt(sum);
}
I think Niching will give you what you want. It compares all the chromosomes in the population to determine them And assign a “niche” value to each chromosome. Then use a technique called Explicit Fitness Sharing to “punish” the chromosomes as belonging to a niche. The fitness value is divided by the number of chromosomes in each niche. Therefore, if you have three niche A groups (A, A, A) instead of the niche that may be selected 3 times, it is treated as a single entity.
I will take my sample Compared with Explicit Fitness Sharing. The maximum STDDEV is 500 and Niching is off, there are about 18-20 niches (so in 100 people, each item is basically repeated 5). With the opening of Niching, there are about 85 Niche. This is 85% of the unique chromosomes in the population. In my test output, you can see the diversity after 17000 generations.
This is the niching code:
 
// returns: total number of niches in this population
// max_stddev - any two chromosomes with p opulation stddev less than this max
// will be grouped together
int ComputeNiches(float max_stddev) {
 List niches = new List();
< br /> // clear niches
 foreach(var c in population) {
 c.niche = -1;
 }

 // calculate niches
 for(int i=0; i var c = population[i];
 if( c.niche != -1) continue; // niche already set 

 // compute the niche by finding the stddev between the two chromosomes 
 c.niche = niches.Count;
 int count_in_niche = 1; // includes the curent Chromosome
 for(int j=i+1; j var d = population[j];
 float stddev = c.StdDev(d);
 if(stddev  d.niche = c.niche; // same niche
 ++count_in_niche;
 }
 }
 niches.Add(coun t_in_niche);
 }

 // penalize Chromosomes by their niche size
 foreach(var c in population) {
 c.niche_scaled_fitness = c.scaled_fitness / niches[ c.niche];
 }

 return niches.Count;
}
[Edit: post analysis and update of Anton code]
I know this may not be the right forum for solving homework problems, but because I made a lot of effort before knowing this, and I had a lot of fun doing this, I think it will only help Anton. < /p> 
Genotip.cs, Kromosom.cs, KromoMain.cs
This code maintains a good diversity. I was able to reduce the "original fitness" to 47 in one run. This is the average error in your case. That's very close! 
As stated in my comment, I want to try to help you complete programming, not just help you complete your homework. Please read these analyses of your work.
>As As we expected, there is no need to build a "more diverse" population from the beginning. Just generate some completely random Kromosomes.
>Your mutations and crossovers are very destructive, you only have a few I have added a few new operators that seem to be more suitable for this problem.
>You lost the best solution. When my code runs with only the tournament option, there will be a Kromo that is better than the rest 99%. When choosing a tournament, the most valuable things are likely to be forgotten. I added some "elitism", which retains a copy of that value for the next generation. 
>Consider object-oriented technology. Will me Compare the rewrite sent to you with the original code.
>Don’t repeat the code. You have two different types of sampling parameters.
>Keep the code clean. There are several unused parts of the code. Especially in When submitting questions to SO, please try to narrow down, delete unused code, and do some cleanup.
>Comment your code! I have made a lot of comments on the reassessment. I know it is Serbian, but even some comments will help others understand what you are doing and what you intend to do. 
>Overall, well done Some more complicated things, such as tournament selection
>prefer double[] array instead of List. Less overhead. In addition, you don’t even need a few temporary List variables. Your structure
List temp = new List();
for(...){
 temp.add(value);
}
for(each value in temp){
 sum = value
 }
average = sum / temp.Count
It is easy to write:

sum = 0
for(...) { 
 sum += value;
}
average = sum / count;
>In a few places you forgot to initialize a loop variable, which may be easy to add to Your problem. Things like this can cause serious problems, and there are one or two other places in your fitness code
double fit = 0;
for(each chromosome){
 // You should initialize in LOOP
 for (each allele) {
 fit = ...;
 fit / = count;
}
Good luck! 

I want to know the following:
How to use value coding to efficiently generate the initial generation of highly diverse chromosomes?
One method is grid initialization, but it is too slow.

So far, I have been using the Random class in .NET to select random values ​​in value encoding, but , Although the values ​​are uniformly distributed, the fitness function value calculated from these chromosomes is not. This is the code for chromosome initialization:

public Chromosome(Random rand) 
 {
 Alele = new List();
 for (int i = 0; i  {
 Alele.Add(rand.NextDouble () * 2000-1000);
 }
 }

So, I developed a function to calculate the fitness from a new, randomly made chromosome (upper code), If the fitness is similar to any other existing in the chromosome list, randomly make a new chromosome and calculate its fitness and repeat this process until his health status is different from the fitness status in the list.

Following This part of the code:

private bool CheckSimilarFitnes(List chromosome, Chromosome newCandidate) 
 {
 Boolean flag=false;
 double fitFromList, fitFromCandidate;
 double fitBigger,fitSmaller;

 foreach (var listElement in chromosome)
 {
 fitFromList = listElement.CalculateChromosomeFitness(listElement.Alele); 
 fitFromCandidate = newCandidate.CalculateChromosomeFitness(newCandi date.Alele);
 fitBigger = fitFromList >= fitFromCandidate? fitFromList: fitFromCandidate;
 fitSmaller = fitFromList 
 if ((fitFromList / fitFromCandidate) < 1.5) 
 return false
 }

 else return true;

 }

However, the more chromosomes I have in the list More, it takes longer to add a new chromosome, and its health is comparable to other chromosomes that already exist.

Then, is there a way to make this grid initialization faster, like this to make 80 chromosomes How many days will it take?

Here is some potentially useful code (I just wrote): GA for ordering 10 values ​​spaced by 1.0. It is 100 completely random etc. This is exactly how your code starts.

The goal I solve for GA is to sort the values ​​in ascending order with an interval of 1.0. It calculates the standard of each pair of samples in 1.0 pairs Deviation, perform this operation in the fitness function Eval_OrderedDistance. When the fitness tends to 0.0, the alleles should begin to appear in order.

The 0th generation is best for chromosomes to be completely random, as are other chromosomes. You can see that the fitness value is very high (ie not good):

GEN: fitness (allele, ...)
 0: 375.47460 (583.640, -4.215) , -78.418, 164.228, -243.982, -250.237, 354.559, 374.306, 709.859, 115.323)

As the generations continue, the fitness (standard deviation of 1.0) decreases until it is almost in 100,000 generations Perfect:

100: 68.11683 (-154.818, -173.378, -170.846, -193.750, -198.722, -396.502, -464.710, -450.014, -422.194, -407.162) 
 ...
10000: 6.01724 (-269.681, -267.947, -273.282, -281.582, -287.407, -293.622, -302.050, -307.582, -308.198, -308.648)
. ..
99999: 0.67262 (-294.746, -293.906, -293.114, -292.632, -292.596, -292.911, -292.808, -292.039, -291.112, -290.928)

The interesting part is the fitness function:

// try to pack the aleles together spaced apart by 1.0
// returns the s tandard deviation of the samples from 1.0
static float Eval_OrderedDistance(Chromosome c) {
 float sum = 0;
 int n = c.alele.Length;
 for(int i= 1; i float diff = (c.alele[i]-c.alele[i-1])-1.0f; 
 sum += diff*diff; // variance from 1.0
 }

 return (float)Math.Sqrt(sum/n);
}

And mutation. I used a simple Crossover and "completely change one allele":

Chromosome ChangeOne(Chromosome c) {
 Chromosome d = c.Clone();
 int i = rand.Next()% d.alele.Length;
 d.alele[i] = (float)(rand.NextDouble()*2000-1000);
 return d;
}

I use elitism to maintain an exact copy of the best chromosomes. Then use mutation and crossover to generate 100 new chromosomes.

This sounds like a calculation The variance of fitness, which of course will tell you that the fitness in your population is roughly the same. I find that it is very important for you to define fitness functions. The finer the fitness function, the more you can distinguish your chromosomes. Obviously, you The fitness function returns the similarity value of completely different chromosomes, because your gen 0 returns the fitness variance of 68e-19.

Can you share your health calculations? Or what problem do you ask GA to solve? I think this can help us help you.

[Edit: add clear fitness sharing/Niching]

I reconsidered this and updated my code. If you want to remain unique You have to compare their contents (as others have mentioned). One way is to calculate the standard deviation between them. If it is below a certain threshold, you can consider them to be the same. From the class chromosome :

// compute the population standard deviation
public float StdDev(Chromosome other) {
 float sum = 0.0f;
 for( int i=0; i float diff = other.alele[i]-alele[i];
 sum += diff*diff;
 }< br /> return (float)Math.Sqrt(sum);
}

I think Niching will give you what you want. It compares all the chromosomes in the population to determine them And assign a “niche” value to each chromosome. Then use a technique called Explicit Fitness Sharing to “punish” the chromosomes as belonging to a niche. The fitness value is divided by the number of chromosomes in each niche. Therefore, if you have three niche A groups (A, A, A) instead of the niche that may be selected 3 times, it is treated as a single entity.

I will take my sample Compared with Explicit Fitness Sharing. The maximum STDDEV is 500 and Niching is off, there are about 18-20 niches (so in 100 people, each item is basically repeated 5). With the opening of Niching, there are about 85 Niche. This is 85% of the unique chromosomes in the population. In my test output, you can see the diversity after 17000 generations.

This is the niching code:

// returns: total number of niches in this population
// max_stddev - any two chromosomes with population stddev less than this max
// will be grouped together
int ComputeNiches(float max_stddev) {
 List niches = new List();

 // clear niches
 foreach(var c in population) {
 c.niche = -1;
 }

 // calculate niches
 for(int i=0; i var c = population[i];
 if( c.niche != -1) continue; // niche already set< br />
 // compute the niche by finding the stddev between the two chromosomes 
 c.niche = niches.Count;
 int count_in_niche = 1; // includes the curent Chromosome
 for(int j=i+1; j var d = population[j];
 float stddev = c.StdDev(d);
 if (stddev  d.niche = c.niche; // same niche
 ++count_in_niche;
 }
 }
 niches.Add(count_in_nich e);
 }

 // penalize Chromosomes by their niche size
 foreach(var c in population) {
 c.niche_scaled_fitness = c.scaled_fitness / niches[ c.niche];
 }

 return niches.Count;
}

[Edit: post analysis and update of Anton code]

I know this may not be the right forum for solving homework problems, but because I made a lot of effort before knowing this, and I had a lot of fun doing this, I think it will only help Anton. < /p>

Genotip.cs, Kromosom.cs, KromoMain.cs

This code maintains a good diversity. I was able to reduce the "original fitness" to 47 in one run. This is the average error in your case. That's very close!

As stated in my comment, I want to try to help you complete programming, not just help you complete your homework. Please read these analyses of your work.

>As As we expected, there is no need to build a "more diverse" population from the beginning. Just generate some completely random Kromosomes.
>Your mutations and crossovers are very destructive, you only have a few I have added a few new operators that seem to be more suitable for this problem.
>You lost the best solution. When my code runs with only the tournament option, there will be a Kromo that is better than the rest 99%. When choosing a tournament, the most valuable things are likely to be forgotten. I added some "elitism", which retains a copy of that value for the next generation.
>Consider object-oriented technology. Will me Compare the rewrite sent to you with the original code.
>Don’t repeat the code. You have two different types of sampling parameters.
>Keep the code clean. There are several unused parts of the code. Especially in When submitting questions to SO, please try to narrow down, delete unused code, and do some cleanup.
>Comment your code! I have made a lot of comments on the reassessment. I know it is Serbian, but even some comments will help others understand what you are doing and what you intend to do.
>Overall, well done Some more complicated things, such as tournament selection
>prefer double[] array instead of List. Less overhead. In addition, you don’t even need a few temporary List variables. Your structure

List temp = new List();
for(...){
temp.add(value);
}
for(each value in temp){
sum = value
}
average = sum / temp.Count

It is easy to write:

sum = 0
for(...) { 
 sum += value;
}
average = sum / count;

>In a few places you forgot to initialize a loop variable, which may be easy to add to Your problem. Things like this can cause serious problems, and there are one or two other places in your fitness code

double fit = 0;
for(each chromosome){
// You should initialize in LOOP
for (each allele) {
fit = ...;
fit / = count;
}

Good luck!