进化算法python优化问题

Question

我有一个关于进化算法的任务，该算法在区间0 ≤ 𝑥 ≤ 255上找到x的值以最大化𝑓(𝑥) = sin(𝑥𝜋/256)。算法的第一步是选择一个字母表来表示问题的解决方案。因为候选解是0到255范围内的整数，所以我的教授建议对每个个体使用8位二进制编码。此外，他还建议使用一个简单的数组。

然而，我不知道他对8位二进制编码的意思以及如何初始化它。它只是简单的solution=[]吗？提前谢谢。此外，如果你碰巧有任何与这个问题有关的资源，请告诉我。我真的很失落。

Answer 1

任何整数都可以转换为二进制表示，例如

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

如果您需要零初始化，初始化就像一样简单

solution = [0]*8

类似地，如果你想用1s初始化：

solution = [1]*8

如果你需要随机初始化：

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

Answer 2

尽管我知道这个问题早就提出了，但我认为值得提供更多关于如何解决这样一个问题的细节。遗传算法需要进化算子才能工作。分配中的提示是给我们一个二进制基因型，用于每一代的采样、交叉和突变。然而，表型是已转换为整数值的值。应根据表型计算目标值。

对二进制值进行操作的遗传算法的一种可能设置是使用随机二进制采样、均匀交叉和位翻转突变。在下面的例子中，我以这种方式实现了您问题中所述的问题。为此，我使用了进化(多目标(优化框架pymoo，因为它已经提供了开箱即用实现遗传算法所需的一切(免责声明：我是pymoo的主要开发人员(。更多信息和pymoo入门指南可以在这里找到。

对于您的问题，最佳情况是sin函数的最大值。考虑sin函数仅从0到pi，最大值为pi/2。这对应于作为整数值的128和二进制表示中的10000000。

以下使用pymoo(0.4.1(的源代码很快解决了您的测试问题。

二进制变量

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)

输出：

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

您也可以直接公式化问题以优化离散值。

整数变量

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)

在遗传算法中，变量表示是必不可少的，它直接与所使用的进化算子一起出现。