Genetic Algorithm Selection and Crossover

Question

I did some research on genetic algorithms for a project in the ai class, but I got a little confused about what looks like a traditional algorithm.

Basically, I wonder why they use different options, such as a roulette wheel, to choose their parents to play. Why not choose parents with the best fitness score and call it a day?

Also, the crossover bothers me. He randomly selects points each time to merge parent information. But it seems that for crossovers, a change based on previous information would be more reasonable. If the chromosome string is well known to the point, the crossover can still be random, but not in the range of the good part in the string.

Any thoughts?

Answer 1

The choice

If you only choose the best parent, then you get Hill climbing . Climbing the hill works great, but the more difficult the problem, the more likely you are to get stuck in a position from which you can’t move further.

Generally, the more complex the problem, the more such local optima . The choice of other people in addition to the best of them supports the diversity of the population: decisions are distributed further in the search space, and if part of the population gets stuck in a local optimum, another part of the population can still make progress.

Modern genetic algorithms usually work hard to preserve population diversity in order to prevent premature convergence . One of the methods for this is fitness sharing. Another simple way to do this is to divide the population into different species so that individuals cannot (or only rarely) reproduce with each other.

Crossover

The crossover is trying to spread the good parts of the genome among people who have arisen due to a mutation. It would be great if you could just swap the good parts of the genome, and that was done; for example, you can look at each gene and measure the average fitness of individuals with this gene.

There are two main problems with this:

• It is computationally expensive.

• There may be interdependencies in the genome. Maybe A gene looks really good according to your metric, but B gene doesn't do it, so you don't leave it. In reality, however, it may be that gene A does not actually work without the presence of the gene.

Answer 2

Choosing only two parents and challenging him a day converges to a decision too quickly. You want to set up several different variables at the same time. Imagine a two-variable scenario in which you use a genetic algorithm to find the lowest point in a room. Your approach can quickly find the lowest place in one local tray, but if there is a lot of unrest on the plane, you risk not finding the tray with the lowest point.

Answer 3

Without choosing best =>, because otherwise you are likely to be stuck at a local optimum. For a similar reason, choosing roulette is a thing of the past, and cool children use rank-based selection (sorting offspring for fitness and preserving, say, the 1/10 best, checking "evolution strategies"). The choice of roulette, as well as the proportional choice for fitness, does not work well if the fitness scale is not very correct, and in practice it is never regular.

Crossover => Evolution strategies just use a mutation and are completely perfect without a crossover. Crossover suggests that your target function can be neatly decomposed into several bits, which will find the crossover. In most genotypes, different parts of the genotype are connected in a very non-linear fashion. This is very naive and true only on toy issues. If you do not have serious excuses for using the crossover operator, just do without it, Occam's razor and all.

Answer 4

I think DataWraith answered the question very well. As for the crossover, I’ll just add that John Holland claims that GA works by implicitly calculating the suitability of each chromosome substring (“scheme”) using a randomized crossover and selection, instead of calculating it explicitly, which would be extremely time-consuming (like said DataWraith). Holland calls this process "implicit parallelism".

-Ted

Answer 5

How about replacing views after a crossover?

I select species to breed using the roulette wheel selection method. My crossover speed is 0.7 (70%), but I really don't know what that means. Does this mean that I select 70 pairs of parents, cross them and replace the worst two in the pool with new two? Or does this mean that I choose 70/2 = 35 pairs of parents, cross them and replace them with worse ones?

I really don’t know with what types you are replacing new children? What if children's fitness is worse than the fitness of the worst two in the pool? Please explain the replacement process in proportional selection mode by the roulette wheel.