Geekly Articles each Day
📜 ⬆️ ⬇️

Selfish gene

Picture to attract attention (http://xkcd.com/534/) It all started one summer evening, while reading the book of evolutionary biologist Richard Dawkins "God as an illusion." This book is about religion, faith, and atheism, but the author briefly refers to another book, The Selfish Gene, and introduces the concept of the same name. For a long time, I was fascinated by the elegance of genetic algorithms. And now, a month later, once again trying to come up with some mini-project, it suddenly dawned on me - what if, with the help of genetic algorithms, to simulate evolution and see what will evolve. The task is difficult and at this stage of development of IT, I think, unsolvable, so I had to do something simpler. Namely, test the hypothesis of the selfish gene. Interested, please under the cat ...

To begin with, we will define the standard representation of evolution. According to Wikipedia : "Biological evolution is a natural process of the development of wildlife, accompanied by a change in the genetic composition of populations, the formation of adaptations, speciation and extinction of species, the transformation of ecosystems and the biosphere as a whole." And what is important, the unit of evolution is the population. Richard Dawkins put forward the theory that the unit of evolution is not the population of individuals of any species, but the gene itself (therefore, it is called selfish). And the “purpose” of a gene is not to adapt an individual to environmental conditions (so that it survives and gives birth to offspring), but to do everything so that the gene itself “survives”. Another view on this issue is genetic algorithms in programming - in them the "unit of evolution" is recognized as a separate individual.

Denial of responsibility
I want to note that my knowledge of biology and evolution is limited to the school course and popular science films, so that if there are errors in the text, please unsubscribe in the comments or in the PM.

Thus, it is possible to investigate (and model) which genes will prevail in the gene pool of any population:

  1. Those that benefit the whole population;
  2. Those [genes] that benefit the relatives of the current individual (since it is relatives who are more likely to “store” the same genes);
  3. Those that benefit only the current individual.


For the simulation developed a program on C # 6 and. NET 4.6.
')
The data model in the program is quite simple. We have the World and Creature classes and a couple of Relation and Gene auxiliary enumerations. There is also a class Statistic, encapsulating in itself the necessary data on the state of the world at a certain iteration.

World
Hereinafter, only basic code cuts are given. All the code is laid out on the githab by the link at the end of the article.

public class World { public readonly List<Creature>[] Species = new List<Creature>[8]; public void Run(int generations) { for (int i = 0; i < generations; i++, this.age = this.Age + 1) { this.SelectBest(); this.MakeChildren(); this.Mutate(); Debug.Print("Age: {0}", i); } } private void SelectBest() { var allCreatures = new List<Creature>(this.Species.Sum(kind => kind.Count)); allCreatures.AddRange(this.Species.SelectMany(kind => kind)); allCreatures = allCreatures.OrderByDescending(creature => creature.SummaryStrength).Take(allCreatures.Count >> 1).ToList(); for (int i = 0; i < this.Species.Length; i++) { this.Species[i].ForEach(creature => creature.BreakRedundantConnections()); this.Species[i].Clear(); this.Species[i].AddRange(allCreatures.Where(creature => creature.IdOfSpecies == i)); } } private void MakeChildren() { Parallel.For( 0, this.Species.Length, i => { var temp = new List<Creature>(this.Species[i].Count << 1); // Random parents (of same species) - for supporting different genes this.Species[i].Shuffle(); Random rnd = RandomProvider.GetThreadRandom(); for (int j = 1; j < this.Species[i].Count; j += 2) { double value = rnd.NextDouble(); if (value < 0.33) { temp.Add(new Creature(this.Species[i][j - 1], this.Species[i][j])); temp.Add(new Creature(this.Species[i][j - 1], this.Species[i][j])); temp.Add(new Creature(this.Species[i][j - 1], this.Species[i][j])); } else if (value < 0.665) { temp.Add(new Creature(this.Species[i][j - 1], this.Species[i][j])); temp.Add(new Creature(this.Species[i][j - 1], this.Species[i][j])); temp.Add(new Creature(this.Species[i][j - 1], this.Species[i][j])); temp.Add(new Creature(this.Species[i][j - 1], this.Species[i][j])); } else { temp.Add(new Creature(this.Species[i][j - 1], this.Species[i][j])); temp.Add(new Creature(this.Species[i][j - 1], this.Species[i][j])); temp.Add(new Creature(this.Species[i][j - 1], this.Species[i][j])); temp.Add(new Creature(this.Species[i][j - 1], this.Species[i][j])); temp.Add(new Creature(this.Species[i][j - 1], this.Species[i][j])); } } this.Species[i].ForEach(creature => creature.BreakRedundantConnections()); this.Species[i].Clear(); this.Species[i] = temp; }); } private void Mutate() { Parallel.ForEach(this.Species, list => list.ForEach(creature => creature.Mutate())); } }


World contains only one public Run method, which performs a specified number of iterations of the “modeling the world”, which includes selecting the best individuals, creating their offspring and then introducing mutations into their [offspring] genes. In the world there are 8 species. Initially, in each of them 1024 individuals. Several species are present in order: first, to simulate a race between species (a battle for survival); secondly, to reduce the probability of finding a local maximum.

The fitness function in this experiment is simple - each creature has a certain “Strength” parameter; the higher it is, the more adapted the creature to survive in a simulated world. The world ("environment") is static. Of all the creatures selected 50% of the fittest.
The child generation is created on the basis of the “surviving” individuals of the parent generation. Individuals of the parent generation are selected by random pairs (from the same species), on the basis of whose genes daughters are created. At the same time, with a probability of 33%, 3 individuals will be created, 33.5% - 4 individuals and 33.5% - 5 individuals. Thus, the number of individuals will slowly grow from generation to generation. In my simulation, the number of individuals in the world increased from 8.192 to ~ 30.000 in 1024 iterations.

Mutations are simply applied to all newly created individuals.

Enums
  public enum Gene : byte { SelfishGene = 1, AltruisticGene = 2, CreatureLevelGene = 4 } public enum Relation { Child, BrotherOrSister, GrandChild, NephewOrNiece, Cousin }


Genes are simply represented by listing three values.

Relatives influenced by genes are represented by five values. The limitations were as follows: the similarity of genes with the genes of a relative should not be less than 10%, individuals of older generations can help individuals of this or younger generations (since each individual (generation) participates in the selection in this simulation only once), individuals of generation n can help individuals of a generation not larger than n + 2 (I suppose this is some average real assumption for humans and some other mammals).

Creature
  public class Creature { private const int GeneStrength = 128; private readonly Gene[] genes = new Gene[128]; private readonly List<Creature> childs = new List<Creature>(8); private Creature mother; private Creature father; public Creature(int idOfSpecies, World world) { Contract.Requires<ArgumentNullException>(world != null); Contract.Ensures(this.IdOfSpecies == idOfSpecies); this.IdOfSpecies = idOfSpecies; this.world = world; for (int i = 0; i < this.genes.Length; i++) { this.genes[i] = EnumHelper.CreateRandomGene(); } } public Creature(Creature mommy, Creature daddy) { Debug.Assert(mommy.IdOfSpecies == daddy.IdOfSpecies, "Interspecies relation are FORBIDDEN!!!"); this.mother = mommy; this.father = daddy; mommy.childs.Add(this); daddy.childs.Add(this); this.world = mommy.world; this.IdOfSpecies = mommy.IdOfSpecies; for (int i = 0; i < this.genes.Length; i++) { this.genes[i] = EnumHelper.ChooseRandomGene(mommy.genes[i], daddy.genes[i]); } } public int SummaryStrength { get { double sum = 0.0; World world = this.world; string cacheKey = $"AltruisticGenesOutStrength{this.IdOfSpecies}"; object cachedValue = Cache.Get(cacheKey, world.Age); if (cachedValue != null) { sum = (double)cachedValue; } else { for (int i = 0; i < world.Species[this.IdOfSpecies].Count; i++) { if (world.Species[this.IdOfSpecies][i] != this) { sum += world.Species[this.IdOfSpecies][i].AltruisticGenesOutStrength; } } Cache.Put(cacheKey, world.Age, sum); } return this.ThisCreatureGenesStrength + (int)sum + (int)this.HelpFromRelations; } } private int ThisCreatureGenesStrength => this.genes.Sum(g => g == Gene.CreatureLevelGene ? GeneStrength : GeneStrength >> 1); private double AltruisticGenesOutStrength { get { int sum = 0; for (int i = 0; i < this.genes.Length; i++) { Gene gene = this.genes[i]; if (gene == Gene.AltruisticGene) { sum += GeneStrength >> 1; } } return (double)sum / (this.world.Species[this.IdOfSpecies].Count - 1); } } private double HelpFromRelations { get { Creature mommy = this.mother; Creature daddy = this.father; if (mommy == null) { return 0; } if (mommy.mother == null) { return mommy.GetSelfishGenesOutStrength(Relation.Child) + daddy.GetSelfishGenesOutStrength(Relation.Child) + mommy.childs.Sum( brother => brother == this ? 0 : brother.GetSelfishGenesOutStrength(Relation.BrotherOrSister)); } return mommy.GetSelfishGenesOutStrength(Relation.Child) + daddy.GetSelfishGenesOutStrength(Relation.Child) + mommy.childs.Sum( brother => brother == this ? 0 : brother.GetSelfishGenesOutStrength(Relation.BrotherOrSister)) + mommy.mother.GetSelfishGenesOutStrength(Relation.GrandChild) + mommy.father.GetSelfishGenesOutStrength(Relation.GrandChild) + daddy.mother.GetSelfishGenesOutStrength(Relation.GrandChild) + daddy.father.GetSelfishGenesOutStrength(Relation.GrandChild) + mommy.mother.childs.Sum( aunt => aunt == mommy ? 0 : aunt.GetSelfishGenesOutStrength(Relation.NephewOrNiece)) + daddy.mother.childs.Sum( uncle => uncle == daddy ? 0 : uncle.GetSelfishGenesOutStrength(Relation.NephewOrNiece)) + mommy.mother.childs.Sum( aunt => aunt == mommy ? 0 : aunt.childs.Sum(cousin => cousin.GetSelfishGenesOutStrength(Relation.Cousin))) + daddy.mother.childs.Sum( uncle => uncle == daddy ? 0 : uncle.childs.Sum(cousin => cousin.GetSelfishGenesOutStrength(Relation.Cousin))); } } public void Mutate() { // Tries to change 6 genes with 50% probability int length = this.genes.Length; int rnd = RandomProvider.GetThreadRandom().Next(length << 1); int limit = Math.Min(length, rnd + 6); for (; rnd < limit; rnd++) { this.genes[rnd] = EnumHelper.CreateRandomGene(); } } public void BreakRedundantConnections() { Creature mommy = this.mother; Creature daddy = this.father; if (mommy?.mother?.mother != null) { mommy.mother.mother?.childs.Clear(); mommy.mother.mother = null; mommy.mother.father?.childs.Clear(); mommy.mother.father = null; mommy.father.mother?.childs.Clear(); mommy.father.mother = null; mommy.father.father?.childs.Clear(); mommy.father.father = null; daddy.mother.mother?.childs.Clear(); daddy.mother.mother = null; daddy.mother.father?.childs.Clear(); daddy.mother.father = null; daddy.father.mother?.childs.Clear(); daddy.father.mother = null; daddy.father.father?.childs.Clear(); daddy.father.father = null; } } private double GetSelfishGenesOutStrength(Relation whoAreYou) { Creature mommy = this.mother; Creature daddy = this.father; int summarySelfishStrength = this.genes.Sum(g => g == Gene.SelfishGene ? GeneStrength >> 1 : 0); switch (whoAreYou) { case Relation.Child: return summarySelfishStrength / this.childs.Count * 30.78; case Relation.BrotherOrSister: Debug.Assert(mommy.childs.Count > 1, "LIER! He is not our brother!"); return summarySelfishStrength / (mommy.childs.Count - 1) * 30.78; case Relation.GrandChild: return summarySelfishStrength / this.childs.Sum(creature => creature.childs.Count) * 15.38; case Relation.NephewOrNiece: Debug.Assert(mommy.childs.Count > 1, "LIER! We don't have any brothers!"); return summarySelfishStrength / mommy.childs.Sum(brother => brother == this ? 0 : brother.childs.Count) * 15.38; case Relation.Cousin: return summarySelfishStrength / (mommy.mother.childs.Sum(aunt => aunt == mommy ? 0 : aunt.childs.Count) + daddy.mother.childs.Sum(uncle => uncle == daddy ? 0 : uncle.childs.Count)) * 7.68; default: throw new NotImplementedException("Unknown enum value"); } } }


Each individual contains exactly 128 genes. For individuals of the zero generation, genes are selected randomly. Individuals of each next generation take random genes from their parents. Each gene has a basic power of 128. The genes act as follows:
  1. AltruisticGene - 50% of the gene's strength goes “in the piggy bank” of a gene carrier, the remaining 50% is divided equally among all creatures of this species;
  2. CreatureLevelGene - all 100% of the gene's power goes “to the piggy bank” of the creature carrier;
  3. SelfishGene - 50% of the gene's strength goes “to the piggy bank” of the gene carrier, the remaining 50% is divided between the relatives of this individual in the following ratio: children receive 15.39% of power, siblings and sisters - the same amount, grandchildren - 7.69%, nephews - 7.69 % and cousins ​​- 3.84% of gene power.

The ratios are related to the likelihood of the presence of the same genes in relatives:
probabilities

A mutation with a probability of 50% changes 4 genes.

The last interesting method is BreakRedundantConnections. To allow the garbage collector to collect memory, it is necessary to remove references to parents when they are no longer needed (the difference in generations is more than two).

Memory leak
At this stage a funny memory leak was obtained. In theory, the GC should collect all the objects in the heap that it cannot reach, since it works according to the algorithm for traversing the object graph. For this, it was enough for the child generations to set in null the links to the parents (since this is the only place where the links to the (outdated) creatures are stored). However, this did not work, and I also had to clear the array of references to the children of the parents. I can not say what is the reason for this behavior: I do not want to believe that this is a .NET bug. Most likely, I don’t know something or I’ve been naughty with LINQ and the helper classes it creates.


The program runs 1024 iterations in ~ 20 minutes (on a laptop with an Intel Core i7 2.4 GHz processor), consuming up to 50 MB of RAM. On average, one iteration takes 1 second. The number of individuals at each iteration ranges from ~ 10,000 to ~ 30,000. For the entire simulation, about 20,000,000 individuals and 2,500,000,000 gene are calculated.

68% of existing genes are selfish genes. Equally (16% each) of absolutely good genes and genes that benefit only carrier individuals. To this ratio came on the 89th generation. At the 201st generation, only one species remained (which took the lead only in the 9th generation (the first from which statistics were taken)).

Awful unaesthetic screenshots

...



...


Which can from this try to draw conclusions:

  1. We are genetically programmed to help relatives;
  2. One of the properties of evolution is that it is not accidental. This is the law. On any planet in the universe on which there is a simple life and the carrier of genetic information will evolve as well as on Earth. No matter how much we run the simulation, we get the same results. That is a small confirmation of this. In fact, this is a confirmation that an optimized brute force (called the genetic algorithm) finds some maximum of a certain function. But evolution does the same thing!
  3. Perhaps, it is worthwhile to think about the future, when using genetic algorithms for solving real problems, to take into account this feature of evolution.


Sources are available (under the free CC 4.0 license) on github .

I will be glad to constructive criticism. If you have questions - please ask in the comments.

Thank you all for your attention!

If you are interested in this article
PS In anticipation of the delivery of the book “The Selfish Gene”, the next version is planned (programs and / or articles) with the following changes: increased productivity (at the moment there are several highly non-optimized sections in the code, as well as furious memory traffic), removal of more statistical data and their visualization, perhaps the release of a (probably next) mini-framework for simulating processes using genetic algorithms and a more precise determination of how good we are. Also, if you have any wishes (more accurate modeling of natural selection, genetic algorithms applied to memes, but not genes, a study of the advantages / disadvantages of polygamy / monogamy, genetic modeling of the parameters of another genetic modeling ...), please unsubscribe in comments.

Source: https://habr.com/ru/post/267399/

More articles:


All Articles