时间戳

首页 > 解决方案 > How could I use a Genetic Algorithm to solve this placement optimization problem?

genetic-algorithm - How could I use a Genetic Algorithm to solve this placement optimization problem?

问题描述

I would like to use GA to solve the following problem:

How can I find which set of 50 pixels is approximately the best one (without having to try all possible combinations)? I am new to GA and I would like to ask how should I approach/implement such an optimization?

标签： genetic-algorithmevolutionary-algorithmgenetic-programming

解决方案

除了基于 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]

编辑：

在了解到应用程序是射频传播之后，我想说唯一需要的大改变是变异函数绝对应该只是随机移动坐标而不是生成新点（因为选择已经完成了这一点）。假设某种渐变，它通常也可能更好。下面是一个基于 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)

考虑到这是射频传播，您可能可以在执行遗传操作后进行一些优化以避免浪费计算时间。将显然太靠近的点合并为一个点（平均），然后生成一个新点。

推荐阅读