我想用GA来解决以下问题：
- 我有一个分辨率为100 * 100的白色图像，始终具有50个黑色像素。
- 我可以选择这 50 个像素。
- 我已经有一个函数 f(image)，根据这 50 个黑色像素的位置，它返回一个分数(我不知道最高分数是多少)。
如何找到哪组 50 像素大约是最好的(无需尝试所有可能的组合)？我是 GA 的新手，我想问我应该如何处理/实施这样的优化？
除了它只是根据 50 分得分之外，您是否还有更多关于适应度函数性质的信息？如果没有，似乎没有任何理由通过尝试在编码上强加高阶抽象来使问题复杂化。这限制了遗传算法的好处，但也大大降低了维度。下面的例子是在 Python 中。
个体只是坐标对的列表：
from random import SystemRandom
X_DIMENSION = 100
Y_DIMENSION = 100
N_PIXELS = 50
rng = SystemRandom()
def create_individual():
return [
(rng.randrange(X_DIMENSION), rng.randrange(Y_DIMENSION))
for i in range(N_PIXELS)
]
朴素交叉可以实现为两个人的直接拼接和连接。
def crossover(a, b):
location = rng.randrange(1, N_PIXELS - 1)
return a[:location] + b[location:], b[:location] + a[location:]
这是另一个随机的幼稚实现，这次是为了突变。它只是用新坐标随机替换坐标。请记住，LOCATION_MUTATION_RATE只是这种突变方法的产物，而不是一般个体的实际突变率(见MUTATION_RATE)。
LOCATION_MUTATION_RATE = .1
def mutate(a):
for i in range(N_PIXELS):
if rng.random() < LOCATION_MUTATION_RATE:
a[i] = (rng.randrange(X_DIMENSION), rng.randrange(Y_DIMENSION))
下面是最终实现的一般概述。这里的一些功能显然被省略了，但你可以得到要点。
POPULATION_SIZE = 10000
SELECTION_RATE = .8
CROSSOVER_RATE = .2
MUTATION_RATE = .03
def main():
population = [create_individual() for i in range(POPULATION_SIZE)]
normalized_fitnesses = normalize_fitnesses(calc_fitnesses(population))
print_stats(normalized_fitnesses)
while not completion_condition(normalized_fitnesses):
select(zip(population, normalized_fitnesses))
replace_dead(population)
crossover_all(population)
mutate_all(population)
normalized_fitnesses = normalize_fitnesses(calc_fitnesses(population))
print_stats(normalized_fitnesses)
def calc_fitnesses(population):
return [calc_fitness(individual) for individual in population]
编辑：
在了解到该应用程序是RF传播之后，我想说唯一需要的大变化是突变函数绝对应该只是随机移动坐标而不是生成新点(因为选择已经完成了这一点)。一般来说，假设某种梯度，它也可能更好。下面是一个基于 x 和 y 维度使用不同移动量的示例。它可能不直观，但想象一下，如果您使用的是 20 x 1000 或类似的东西。此外，我个人会添加除基本量(MUTATION_MOVEMENT_FACTOR)之外的另一个因素，以根据个人相对于其他人的表现不佳(因此标准化健身)来增加运动量。
import math
LOCATION_MUTATION_RATE = .3
MUTATION_MOVEMENT_FACTOR = .05
MOVEMENT_X = math.ceil(X_DIMENSION * MUTATION_MOVEMENT_FACTOR)
MOVEMENT_Y = math.ceil(Y_DIMENSION * MUTATION_MOVEMENT_FACTOR)
def mutate(a):
for i in range(N_PIXELS):
if rng.random() < LOCATION_MUTATION_RATE:
a[i][0] += rng.randrange(-MOVEMENT_X, MOVEMENT_X)
a[i][1] += rng.randrange(-MOVEMENT_Y, MOVEMENT_Y)
考虑到这是射频传播，您可能会在执行遗传操作后进行一些优化，以避免浪费计算时间。将明显靠得太近的点合并为一个点(平均)，然后生成一个新点。
你的问题对SO来说有点太宽泛了。但这里是 GA 工作原理的摘要。关键部分是您已经拥有健身功能。
- 定义总体大小 N。
- 定义您的染色体编码。这可能很棘手。
- 随机生成N条染色体。
- 使用
f(image)计算每条染色体的适应度。 - 生成下一代执行选择(使用先前计算的适应度分数)和突变。
- 从 4 重复一定次数，或者如果满足结束条件。
我希望这有助于作为一个起点。也许你应该检查一些GA示例，开始编码，如果需要，可以在这里问一些更具体的问题。
补充阿尔瓦罗的答案：
为了使人口为 N，这 N 个对象中的每一个都将是一个有效的图像，即分辨率为 100*100 的白色图像，始终具有 50 个黑色像素。
50个黑色像素可以随机放置(如果N很大)或使用任何其他方法。这将设置大小为 N 的初始群体，每个染色体都是 100x100 的数据结构(基本上是您的图像)。
由于您已经拥有健身功能，因此请使用它为下一代找到最佳人才。
现在要增加种群，您需要"交叉函数"和/或"突变函数"。
突变可以通过用白色像素改变一些(比如k，其中k<50)黑色像素的位置来完成，这样染色体就不会失去其基本属性，而只是从原始图像中发生了一点突变。
对于交叉功能，拍摄 2 张图像(染色体)并将它们混合以形成一条新染色体，请记住，每条染色体可以恰好有 50 个黑色像素(以及任何其他约束)。这可以通过从每个父图像中获取 25 个黑色像素来完成，如果它们重叠(来自父 1 的黑色像素和来自父 2 的黑色像素)，您可以将其放在随机的白色位置，或者您可以选择最近的空像素来放置这个黑色像素。
重复生成最佳总体、交叉、突变、生成最佳总体、交叉、突变等步骤。直到收敛，或者为一组没有。的迭代次数。