Genetic Algorithm Maximization of Non-Linear Function

GA_max.py

# genetic algorithm search for continuous function optimization
from numpy.random import randint
from numpy.random import rand

# objective function
# fitness function
def objective(x):
    """
    # the function to optimize
    >> x**2 - y * y**0.5 + 14
    """
    return (x[0] ** 2.0) - (x[1] * (x[1] ** 0.5)) + 14


# decode bitstring to numbers
def decode(bounds, n_bits, bitstring):
    """
    assume bitstring is in binary, decode into number(s) for the function input(s)
    """
    decoded = list()
    largest = 2 ** n_bits
    for i in range(len(bounds)):
        # extract the substring
        start, end = i * n_bits, (i * n_bits) + n_bits
        substring = bitstring[start:end]
        # convert bitstring to a string of chars
        chars = "".join([str(s) for s in substring])
        # convert string to integer
        integer = int(chars, 2)
        # scale integer to desired range
        value = bounds[i][0] + (integer / largest) * (bounds[i][1] - bounds[i][0])
        # store
        decoded.append(value)
    # will return array of length same as length of bounds
    # ie: decoded values for all variables
    return decoded


# tournament selection
def selection(pop, scores, k=3):
    """
    pick k tournaments and pick the best parent in each call
    best is determined by scores array (fitness scores (based on objective function))
    """
    # first random selection
    selection_ix = randint(len(pop))
    for ix in randint(0, len(pop), k - 1):
        # check if better (e.g. perform a tournament)
        if scores[ix] > scores[selection_ix]:
            selection_ix = ix
    return pop[selection_ix]


# crossover two parents to create two children
def crossover(p1, p2, r_cross):
    """
    r_cross (crossover rate) is a hyperparameter that determines whether crossover is performed or not,
    and if not, the parents are copied into the next generation (default behaviour in this case)

    It is a probability and typically has a large value close to 1.0.
    """
    # children are copies of parents by default
    c1, c2 = p1.copy(), p2.copy()
    # check for recombination
    if rand() < r_cross:
        # select crossover point that is not on the end of the string
        pt = randint(1, len(p1) - 2)
        # perform crossover
        """
        one-point crossover
        """
        c1 = p1[:pt] + p2[pt:]
        c2 = p2[:pt] + p1[pt:]
    return [c1, c2]


# mutation operator
def mutation(bitstring, r_mut):
    """
    mutate bitstring itself, NOT the copy
    """
    for i in range(len(bitstring)):
        # check for a mutation
        if rand() < r_mut:
            # flip the bit
            """
            bit-flip mutation
                1 - (1) => 0
                1 - (0) => 1
            """
            bitstring[i] = 1 - bitstring[i]


# genetic algorithm
def genetic_algorithm(objective, bounds, n_bits, n_iter, n_pop, r_cross, r_mut):
    # initial population of random bitstring
    pop = [randint(0, 2, n_bits * len(bounds)).tolist() for _ in range(n_pop)]
    """
    pop =>
    [
        [1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0]
        ...
        ...
        ...
        (n_pop)th array
    ]
    """

    # keep track of best solution
    best, best_eval = 0, objective(decode(bounds, n_bits, pop[0]))

    # enumerate generations
    for gen in range(n_iter):
        # decode population
        decoded = [decode(bounds, n_bits, p) for p in pop]

        # evaluate all candidates in the population
        scores = [objective(d) for d in decoded]

        # check for new best solution
        for i in range(n_pop):
            if scores[i] > best_eval:
                best, best_eval = pop[i], scores[i]
                print(">%d, new best f(%s) = %f" % (gen, decoded[i], scores[i]))

        # select parents
        selected = [selection(pop, scores) for _ in range(n_pop)]
        # `selected` is a length 100 array of each element being 32 length arrays

        # create the next generation
        children = list()
        for i in range(0, n_pop, 2):
            # get selected parents in pairs
            p1, p2 = selected[i], selected[i + 1]
            # crossover and mutation
            for c in crossover(p1, p2, r_cross):
                # mutation
                mutation(c, r_mut)
                # store for next generation
                children.append(c)

        # replace population
        pop = children

    return [best, best_eval]


# define range for each input variable
bounds = [[0.0, 15.0], [12.0, 17.0]]
# define the total iterations
n_iter = 100
# bits per variable
n_bits = 16
# define the population size
n_pop = 100
# crossover rate: high probability value
r_cross = 0.9
# mutation rate: low probability value
r_mut = 1.0 / (float(n_bits) * len(bounds))
# perform the genetic algorithm search
best, score = genetic_algorithm(
    objective, bounds, n_bits, n_iter, n_pop, r_cross, r_mut
)
# getting the best population and the best score possible
print("Done!")
decoded = decode(bounds, n_bits, best)
# decoding best population to value
print("f(%s) = %f" % (decoded, score))

output.log

>0, new best f([13.878250122070312, 12.493927001953125]) = 162.443856
>0, new best f([14.672012329101562, 15.193283081054688]) = 170.046713
>0, new best f([14.933395385742188, 15.052215576171875]) = 178.607939
>0, new best f([14.680709838867188, 13.609649658203125]) = 179.315531
>1, new best f([14.844589233398438, 13.985702514648438]) = 182.058850
>1, new best f([14.844818115234375, 12.241470336914062]) = 191.538398
>3, new best f([14.926528930664062, 12.517959594726562]) = 192.511813
>4, new best f([14.926300048828125, 12.34820556640625]) = 193.402822
>5, new best f([14.984893798828125, 12.328521728515625]) = 195.259143
>6, new best f([14.939346313476562, 12.006256103515625]) = 195.582337
>8, new best f([14.984893798828125, 12.255279541015625]) = 195.644322
>8, new best f([14.970245361328125, 12.106353759765625]) = 195.985174
>8, new best f([14.984664916992188, 12.103912353515625]) = 196.429852
>9, new best f([14.984664916992188, 12.103759765625]) = 196.430648
>10, new best f([14.984664916992188, 12.028228759765625]) = 196.824196
>10, new best f([14.984893798828125, 12.016403198242188]) = 196.892560
>11, new best f([14.997482299804688, 12.035552978515625]) = 197.170380
>12, new best f([14.999542236328125, 12.035552978515625]) = 197.232172
>13, new best f([14.999542236328125, 12.017013549804688]) = 197.328612
>13, new best f([14.999542236328125, 12.016403198242188]) = 197.331785
>14, new best f([14.997711181640625, 12.001754760742188]) = 197.353003
>15, new best f([14.999771118164062, 12.011749267578125]) = 197.362848
>18, new best f([14.999771118164062, 12.006103515625]) = 197.392195
>22, new best f([14.999542236328125, 12.001373291015625]) = 197.409912
>23, new best f([14.999771118164062, 12.001373291015625]) = 197.416778
>31, new best f([14.999542236328125, 12.0]) = 197.417048
>32, new best f([14.999771118164062, 12.001220703125]) = 197.417571
>36, new best f([14.999771118164062, 12.000152587890625]) = 197.423121
>41, new best f([14.999771118164062, 12.0]) = 197.423914
Done!
f([14.999771118164062, 12.0]) = 197.423914