How to eliminate duplicates; Genetic Algorithm

Question

I was writing my thesis and got to a problem that i can't solve. I am writing about Genetic Algorithms with steady-state selection.
The problem is that after some iteration duplicates shows up; my question is how to remove these duplicates.
How can i compare some specific elements from an object? I tried with the function Equals() but didn't figured out how to set her up.

Example: i want that this repeats until the new object isn't the same as existing objects in class population:

public void permutationRecombination(Chromosome parent1, Chromosome parent2, Chromosome child1, Chromosome child2)
{
int cLen = parent1.genes.Length;

do{
int recomPoint = ga.rng.Next(cLen - 1);
int poc1 = 0, poc2 = 0;
bool nadjen;

// prvi dio (kopiranje gena)
for (int i = 0; i <= recomPoint; i++)
{
child1.genes[i] = parent1.genes[i].Clone();
child2.genes[i] = parent2.genes[i].Clone();
}
// drugi dio (umetanje gena koji nedostaju redoslijedom iz drugog roditelja)
for (int i = recomPoint + 1; i < cLen; i++)
{
// prvo dijete
nadjen = false;
for (int j = poc1; j < cLen; j++) // trazi preostale gene iz jednog u drugom
{
for (int k = recomPoint + 1; k < cLen; k++)
{
if (parent2.genes[j].ToInteger() == parent1.genes[k].ToInteger()) //trazi
{
child1.genes[i] = parent2.genes[j].Clone();
poc1 = j + 1;
nadjen = true;
}
}
if (nadjen) break;
}
//drugo dijete;
nadjen = false;
for (int j = poc2; j < cLen; j++) // trazi preostale gene iz jednog u drugom
{
for (int k = recomPoint + 1; k < cLen; k++)
{
if (parent1.genes[j].ToInteger() == parent2.genes[k].ToInteger()) //trazi
{
child2.genes[i] = parent1.genes[j].Clone();
poc2 = j + 1;
nadjen = true;
}
}
if (nadjen) break;
}
}
if(child1.genes==parent1.genes) MessageBox.Show("postoje jednaki");
} while (child1.Equals(parent1) || child2.Equals(parent2) || child1.Equals(parent2) || child2.Equals(parent1));
}

Attachment: eliminationgeneticalgorithm.rar

Vulpes · Answer

OK let me see if I've understood this correctly: 1. You have a variable 'population' which is an array of 10 Chromosomes 2. Each Chromosome object has a field 'genes' which contains an array of 18 Genes 3. Each Gene object has a field of type IntegerGene 4. Gene has a method ToInteger() which returns the value of IntegerGene as an ordinary integer and you're wanting to say that two Chromosomes are equal if they have the same integers (as described in 4) in the same order. If my understanding is correct then I'd suggest you override the Equals and GetHashCode methods inherited by the Chromosome class as follows: public override bool Equals(object obj) { //Check for null and compare run-time types. if (obj == null || GetType() != obj.GetType()) return false; Chromosome c = (Chromosome)obj; for(int i = 0; i { // if any pair of corresponding genes are unequal the chromosomes are unequal if (this.genes[i].ToInteger() != c.genes[i].ToInteger()) return false; } return true; // all corresponding genes equal } } public override int GetHashCode() { int hash = genes[0].ToInteger(); for(int i = 1; i { hash ^= this.genes[i].ToInteger(); } return hash; }

Vulpes · Answer

I've been running it some more times (the changes you made shouldn't have affected anything) and I can't find anything wrong with it at all! The cases I thought were hanging the machine do in fact (eventually) work and the UI is simply locking up because the calculations are so CPU intensive and are running on the UI thread itself rather than a background thread. Can you still find a particular setting where the chromosomes are all becoming null?

Mato Milic · Answer

this algorithm is a implementation of Traveling Salesman problem and genes are citys and each Chromosome is a potential solution. the algorithm goes something like this random creates first population then it calculates the fitness (for each chromosome; it represents the length of the tour) it selects 2 parents and 2 EliminationChromosome (the parents recombinate and create 2 childs these childs take the position of EliminationChromosome) the population mutates than (random selects some cromosomes and changes theyr 2 genes postion just not to the best chromosome) calculates the fitness again checks if the number of iteration has reached maximum (breaking criterium if maximum then it writes the cyti order to be visited of the best Chromosome i changed your Method a little bit: public override bool Equals(object obj) { if (object.ReferenceEquals(obj null)) return false; Chromosome chromosome = obj as Chromosome; if (object.ReferenceEquals(chromosome null)) return false; for (int index = 0; index { if (this.genes[index].ToInteger() != chromosome.genes[index].ToInteger()) return false; } return true; // all coresponding genes equal } i also added my final solution as attachement it is not an expected behavior for chromosomes to become null dont know why that is happening and when.

Vulpes · Answer

Well I've tried running the program with the initial default values and also with iterations of 100000 and population size of 10 but I wasn't able to reproduce the problem. On both occasions it gave me a list of 18 towns - one for each gene I imagine. I tried some other combinations and sometimes the programming stopped responding without actually throw an exception. It's difficult for me to figure this out without knowing much about the subject matter. Is it in fact 'expected behavior' for all the chromosomes to sometimes become null before the iterations have completed? If it is then you'll need to put in a 'null test' to stop the program from hanging though doing so will of course slow things down.

Mato Milic · Answer

@Vulpes thanks you helped me to get closer to the final solution i added your code to the chromosome class (just copied it there) but i removed the while statemant from permutationRecombination and changed in Population class the Elimincija method public void Eliminacija(Population oldPopulation) { Chromosome parent1 parent2 eliminationChromosome1 eliminationChromosome2; { parent1 = oldPopulation.rouletteWheel(); do { parent2 = oldPopulation.rouletteWheel(); } while (parent1 == parent2); do { eliminationChromosome1 = oldPopulation.eliminacijaJedinke(); } while (eliminationChromosome1 == parent1 || eliminationChromosome1 == parent2); do { eliminationChromosome2 = oldPopulation.eliminacijaJedinke(); } while (eliminationChromosome2 == parent1 || eliminationChromosome2 == parent2 || eliminationChromosome2 == eliminationChromosome1); //recombination recombination(parent1 parent2 eliminationChromosome1 eliminationChromosome2); //i added this; if the eliminationChromosome equals to any other chromosome in population foreach (Chromosome c in population) { if (eliminationChromosome1.Equals(c)&&eliminationChromosome1.fitness!=c.fitness) { Gene tmpGene; int gene1 gene2; gene1 = ga.rng.Next(chromosomeSize); do { gene2 = ga.rng.Next(chromosomeSize); } while (gene1 == gene2); tmpGene = eliminationChromosome1.genes[gene1]; eliminationChromosome1.genes[gene1] = eliminationChromosome1.genes[gene2]; eliminationChromosome1.genes[gene2] = tmpGene; } if (eliminationChromosome2.Equals(c)&&eliminationChromosome2.fitness!=c.fitness) { Gene tmpGene; int gene1 gene2; gene1 = ga.rng.Next(chromosomeSize); do { gene2 = ga.rng.Next(chromosomeSize); } while (gene1 == gene2); tmpGene = eliminationChromosome2.genes[gene1]; eliminationChromosome2.genes[gene1] = eliminationChromosome2.genes[gene2]; eliminationChromosome2.genes[gene2] = tmpGene; } } //mutation oldPopulation.mutation(); //Calculate Fitness oldPopulation.fitness(); oldPopulation.kumulativnaKazna(); } but after some iterations al my Chromosomes get the value null ( for example when i set iterations to 100000 and Velicina populacije(this is croatian-->that means population size) to 10 the algorithm stops because all chromosomes are null can you please help me to figure out why that is happening?!

Mato Milic · Answer

but my problem is that i dont know how to compare the right objects i.e. this picture shows the structure of my classes... and the genes are value int so if these values are the same for two chromosomes; it should generate again new childs: i meen if child.genes = { 123456789} and parent parent.genes={12345678}---> they have the same order of numbers so i need to avoid this http://img843.imageshack.us/i/capturezo.png/ [ ^ ]

Vulpes · Answer

Assuming Chromosome is a reference type (i.e. a class) then the Equals method will only return true if you are comparing exactly the same objects. If you want two different objects whose fields have the same value to be regarded as equal then you'll need to override Chromosome's Equals method and also its GetHashCode method as well. See the notes and example in the MSDN docs ( http://msdn.microsoft.com/en-us/library/bsc2ak47.aspx ).