Evolutionary algorithm python optimization problem

Question

I have an assignment about evolutionary algorithm to find the value of x to maximize 𝑓(𝑥) = sin(𝑥𝜋/256) over the interval 0 ≤ 𝑥 ≤ 255. Step 1 in the algorithm is to choose an alphabet to represent solutions to the problem. Because candidate solutions are integers in the range 0 to 255, my professor suggested using 8-bit binary encodings for each individual. Also, he suggested to use a simple array.

However, I am not sure what he meant about 8-bit binary encodings and how to initialize it. Is it just simple solution=[]? Thanks in advance. Also, if you happen to have any resources related to this problem, please let me know. I am really lost on this.

Answer 1

Even though I know this question has been raised quite some time ago, I think it is worth providing some more details of how to solve such a problem. A genetic algorithm needs evolutionary operators in order to work. The hint in the assignment is to us a binary genotype which is used for sampling, crossover and mutation in each generation. The phenotype, however, is the value which has been converted to an integer value. Based on the phenotype the objective value shall be calculated.

One possible setup for a genetic algorithm operating on binary values is to use random binary sampling, uniform crossover and bit flip mutation. In the example below, I have implemented the problem stated in your question this way. I have used the evolutionary (multi-objective) optimization framework pymoo for this purpose because it provides already everything which is needed to implement a genetic algorithm out of the box (Disclaimer: I am the main developer of pymoo). More information and a getting started guide of pymoo can be found here.

The optimum for your problem lies where the sin function has its maximum. Considering the sin function only from 0 to pi the maximum is pi/2. This corresponds to 128 as an integer value and 10000000 in binary representation.

The following source code using pymoo (0.4.1) solves your test problem rather quickly.

Binary Variable

import numpy as np

from pymoo.algorithms.so_genetic_algorithm import GA
from pymoo.factory import get_sampling, get_crossover, get_mutation
from pymoo.model.problem import Problem
from pymoo.optimize import minimize


class MyProblem(Problem):
    def __init__(self):
        super().__init__(n_var=8,
                         n_obj=1,
                         n_constr=0,
                         xl=0,
                         xu=1)

    def _evaluate(self, x, out, *args, **kwargs):

        # get the number of variables to be used
        n = self.n_var

        # create the value of each binary value, e.g. 128, 64, 32, 16, 8, 4, 2, 1
        val = np.full(n, 2) ** np.arange(n)[::-1]

        # convert the input to the corresponding integer value
        x_as_int = (x * val).sum(axis=1)

        # calculate the objective (multiplied by -1 because minimization is assumed)
        out["F"] = - np.sin(x_as_int * np.pi / (2 ** n))


problem = MyProblem()

# initialize the genetic algorithm with binary operators
algorithm = GA(
    pop_size=10,
    sampling=get_sampling("bin_random"),
    crossover=get_crossover("bin_ux"),
    mutation=get_mutation("bin_bitflip"))

res = minimize(problem,
               algorithm,
               seed=1,
               verbose=True)

print(res.X.astype(np.int))
print(- res.F)

The output:

[1 0 0 0 0 0 0 0]
[1.]

You can also formulate the problem to optimize a discrete value directly.

Integer Variable

import numpy as np

from pymoo.algorithms.so_genetic_algorithm import GA
from pymoo.factory import get_sampling, get_crossover, get_mutation
from pymoo.model.problem import Problem
from pymoo.optimize import minimize


class MyProblem(Problem):
    def __init__(self):
        super().__init__(n_var=1,
                         n_obj=1,
                         n_constr=0,
                         xl=0,
                         xu=256)

    def _evaluate(self, x, out, *args, **kwargs):
        out["F"] = - np.sin(x * np.pi / 256)


problem = MyProblem()

# initialize the genetic algorithm with binary operators
algorithm = GA(pop_size=15,
               sampling=get_sampling("int_random"),
               crossover=get_crossover("int_sbx", prob=1.0, eta=3.0),
               mutation=get_mutation("int_pm", eta=3.0),
               )

res = minimize(problem,
               algorithm,
               seed=1,
               verbose=True)

print(res.X.astype(np.int))
print(- res.F)

In genetic algorithms the variable representation is essential and comes directly along with the evolutionary operators being used.

Answer 2

Any integer can be converted into binary representation, e.g.

0 = 00000000
1 = 00000001
2 = 00000010
...
254 = 11111110
255 = 11111111

If you need a zero initialization, the initialization is as simple as

solution = [0]*8

Similarly if you want to initialize with 1s:

solution = [1]*8

And if you need a random initialization:

import numpy as np
solution = list(np.random.randint(0, 2, size=8))