1
$\begingroup$

I wrote a code that implements a simple genetic algorithm to maximize:

f(x) = 15x - x^2

The function has its maximum at 7.5, so the code output should be 7 or 8 since the population are integers. When I run the code 10 times I get 7 or 8 around three times out of 10.I chose mating probability of 0.7 and mutation probability of 0.001. What modification should I make to further improve the algorithm and what are different types of genetic algorithms?

Here is the code:

from random import *
import numpy as np

#fitness function
def fit(x):
    return 15*x -x**2
#covert binary list to decimal number
def to_dec(x):
    return int("".join(str(e) for e in x), 2)

#picks pairs from the original population
def gen_pairs(populationl, prob):
    pairsl = []
    test = [0, 1, 2, 3, 4, 5]
    for i in range(3):
        pair = []
        for j in range(2):
            temp = np.random.choice(test, p=prob)
            pair.append(populationl[temp].copy())
        pairsl.append(pair)

    return pairsl

#mating function
def cross_over(prs, mp):
    new = []
    for pr in prs:
        if mp[prs.index(pr)] == 1:
            index = np.random.choice([1,2,3], p=[1/3, 1/3, 1/3])
            pr[0][:index], pr[1][:index] = pr[1][:index], pr[0][:index]

    for pr in prs:
        new.append(pr[0])
        new.append(pr[1])

    return new

#mutation
def mutation(x):
    for chromosome in x:
        for gene in chromosome:
            mutation_prob = np.random.choice([0, 1], p=[0.999, .001])
            if mutation_prob == 1:
                #m_index = np.random.choice([0,1,2,3])
                if gene == 0:
                    gene = 1
                else:
                    gene = 0
    #generate initial population
    randlist = lambda n:[randint(0,1) for b in range(1, n+1)]
for j in range(10):
    population = [randlist(4) for i in range(6)]
    for _ in range(20):
        fittness = [fit(to_dec(y)) for y in population]

        s = sum(fittness)
        prob = [e/s for e in fittness]
        pairsg = gen_pairs(population.copy(), prob)

        mating_prob = []
        for i in pairsg:
            mating_prob.append(np.random.choice([0,1], p=[0.4,0.6]))

        new_population = cross_over(pairsg, mating_prob)
        mutated = mutation(new_population)
        decimal_p = [to_dec(i)for i in population]
        decimal_new = [to_dec(i)for i in new_population]
        # print(decimal_p)
        # print(decimal_new)
        population = new_population
    print(decimal_new)
$\endgroup$
1
$\begingroup$

Without paying much attention to your code, your crossover rate is maybe a touch low, your mutation rate is orders of magnitude too low, your population is tiny, and you're only running 20 generations. You're just not doing enough search for anything to work. If your initial population had a 6 or 7, you find it. Otherwise, you get a handful of crossovers to hope to get lucky and then you're done.

You have 4 bits * 6 individuals = 24 bits per generation * 20 generations. At best, you have 480 bits of information here, and your mutation operator expects one flip per thousand bits.

You also select parents using fitness proportionate selection, which has pretty severe issues with selection pressure, made even worse with such a small population. Look at it this way, suppose you generate the following six individuals for your initial population (6, 0, 15, 13, 11, 2). f(6) is quite a bit better than every other choice -- the selection probabilities are roughly (0.36, 0, 0, 0.17, 0.29, 0.17). So you'd expect the parent pool to look something like (6, 13, 6, 11, 11, 2). Obviously the exact choices are random, but that fits the distribution. Now if you pair a 6 with a 6 or an 11 with an 11, you're guaranteed to produce another copy of those, as crossover of identical parents can't flip any bit. And you have no mutation at all (practically speaking). So your population just rapidly converges to the best thing you found in your initial random population.

Crossover does have some chance of producing better individuals, which is why you see the optimum 30% of the time instead of ~10% that you'd expect just by sampling for the initial population. But that's about it. You just don't have enough search happening to reliably do any better.

Again, there may also be bugs -- I didn't look carefully.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.