CODEWITHSUNDEEP
artificial-intelligencegenetic-algorithm
user3273345
user3273345

Reputation: 127

Difference of using different population size and different crossover method

I have couple of general questions on genetic algorithm. In selection step where you pick up chromosomes from the population, is there an ideal number of chromosomes to be picked up? What difference does it make if I pick, say 10 chromosomes instead of 20? Does it have any effect on final result? At mutation stage, I've learnt there are different ways to mutate - Single point crossover, two points crossover, uniform crossover and arithmetic crossover. When should I choose one over the other? I know they sound very basic, but I couldn't find answer anywhere. So I thought I should ask in Stackoverflow. Thanks

Upvotes: 0

Views: 186

Answers (1)

zegkljan
zegkljan

Reputation: 8419

It seems to me that your terminology and concepts are a little bit messed up. Let me clarify.

First of all - there are many ways people call the members of the population: genotype, genome, chromosome, individual, solution... I will use solution for now as it is, in my opinion, the most general term, it is what we are eventually evolve, and also I'm not a biologist so I don't know whether genotype, genome and chromosome somehow differ and if they do what is the difference...

Population

Genetic Algorithms are population-based evolutionary algorithms. The algorithms have (usually) a fixed-sized population of solutions of the problem it is solving.

Genetic operators

There are two principal genetic operators - crossover and mutation. The goal of crossover is to take two (or more in some cases) solutions and combine them to create a solution that has some properties of both, optimally the best of both. The goal of mutation is to create new genetic material that was not previously present in the population by doing a small random change.

The choice of the particular operators, i.e. whether a single-point or multi-point crossover..., is totally problem-dependent. For example, if your solutions are composed of some logical blocks of bits that work together in each block, it might not be a good idea to use uniform crossover because it will destroy these blocks. In such case a single- or multi-point crossover is a better choice and the best choice is probably to restrict the crossover points to be on the boundaries of the blocks only.

You have to try what works best for your problem. Also, you can always use all of them, i.e. by randomly choosing which crossover operator is going to be used each time the crossover is about to be performed. Similarly for mutation.

Modes of operation

Now to your first question about the number of selected solutions. Genetic Algorithms can run in two basic modes - generational mode and steady-state mode.

Generational mode

In generational mode, the whole population is replaced in every generation (iteration) of the algorithm. A simple python-like pseudo-code for a generational-mode GA could look like this:

P = [...]  # initial population
while not stopping_condition():
    Pc = []  # empty population of children
    while len(Pc) < len(P):
        a = select(P)  # select a solution from P using some selection strategy
        b = select(P)
        if rand() < crossover_probability:
            a, b = crossover(a, b)
        if rand() < mutation_probability:
            a - mutation(a)
        if rand() < mutation_probability:
            b = mutation(b)
        Pc.append(a)
        Pc.append(b)
    P = Pc  # replace the population with the population of children

Evaluation of the solutions was omitted.

Steady-state mode

In steady-state mode, the population persists and only a few solutions are replaced in each iteration. Again, a simple steady-state GA could look like this:

P = [...]  # initial population
while not stopping_condition():
    a = select(P)  # select a solution from P using some selection strategy
    b = select(P)
    if rand() < crossover_probability:
        a, b = crossover(a, b)
    if rand() < mutation_probability:
        a - mutation(a)
    if rand() < mutation_probability:
        b = mutation(b)
    replace(P, a)  # put a child back into P based on some replacement strategy
    replace(P, b)

Evaluation of the solutions was omitted.

So, the number of selected solutions depends on how do you want your algorithm to operate.

Upvotes: 2

Related Questions