Генетический алгоритм с использованием вектора фиксированной длины

Я пытаюсь реализовать генетический алгоритм, используя векторы фиксированной длины действительных чисел. Я нашел простую реализацию в Интернете с использованием двоичных закодированных значений. Мое замешательство возникает, когда я пытаюсь найти способ инициализировать массив и установить границы для этого алгоритма.

Ниже приведен фрагмент кода с двоичным декодированным кодом:

def decode(bounds, n_bits, bitstring):
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)
return decoded

Можно ли это переписать как массив действительных чисел для кодирования решения, а не битовой строки?

Полный код взят из следующей статьи: Простой генетический алгоритм с нуля на Python

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


# objective function
def objective(x):
    return x[0] ** 2.0 + x[1] ** 2.0


# decode bitstring to numbers
def decode(bounds, n_bits, bitstring):
    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)
    return decoded


# tournament selection
def selection(pop, scores, k=3):
    # 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):
    # 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
        c1 = p1[:pt] + p2[pt:]
        c2 = p2[:pt] + p1[pt:]
    return [c1, c2]


# mutation operator
def mutation(bitstring, r_mut):
    for i in range(len(bitstring)):
        # check for a mutation
        if rand() < r_mut:
            # flip the bit
            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)]
    # 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)]
        # 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 input
bounds = [[-5.0, 5.0], [-5.0, 5.0]]
# define the total iterations
n_iter = 100
# bits per variable
n_bits = 16
# define the population size
n_pop = 100
# crossover rate
r_cross = 0.9
# mutation rate
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)
print('Done!')
decoded = decode(bounds, n_bits, best)
print('f(%s) = %f' % (decoded, score))
14 Задание: Типы данных и структуры данных Python для DevOps
14 Задание: Типы данных и структуры данных Python для DevOps
проверить тип данных используемой переменной, мы можем просто написать: your_variable=100
Python PyPDF2 - запись метаданных PDF
Python PyPDF2 - запись метаданных PDF
Python скрипт, который будет записывать метаданные в PDF файл, для этого мы будем использовать PDF ридер из библиотеки PyPDF2 . PyPDF2 - это...
Переменные, типы данных и операторы в Python
Переменные, типы данных и операторы в Python
В Python переменные используются как место для хранения значений. Пример переменной формы:
Почему Python - идеальный выбор для проекта AI и ML
Почему Python - идеальный выбор для проекта AI и ML
Блог, которым поделился Harikrishna Kundariya в нашем сообществе Developer Nation Community.
Как автоматически добавлять котировки в заголовки запросов с помощью PyCharm
Как автоматически добавлять котировки в заголовки запросов с помощью PyCharm
Как автоматически добавлять котировки в заголовки запросов с помощью PyCharm
Анализ продукта магазина на Tokopedia
Анализ продукта магазина на Tokopedia
Tokopedia - это место, где продавцы могут продавать свои товары. Товар должен быть размещен на витрине, чтобы покупателям было легче найти товар...
0
0
83
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Похоже, вы ссылаетесь на код в этой статье: Простой генетический алгоритм с нуля в Python.

Бит-векторное представление отдельных лиц, используемое в исходном коде, представляет собой кодирование вектора с действительным знаком. Если вы хотите, чтобы ваше представление человека было вектором с действительным знаком, это означает, что вам вообще не нужно выполнять какое-либо декодирование или кодирование.

Инициализируйте свою популяцию, чтобы она была вектором случайных действительных значений в пределах границ

def genetic_algorithm(objective, bounds, n_iter, n_pop, r_cross, r_mut):
    # initial population of random real-valued vectors
    pop = [[random.uniform(bound[0], bound[1]) for bound in bounds] for _ in range(n_pop)]
...

Тогда в самом генетическом алгоритме нет необходимости декодировать популяцию, так как они уже являются вещественнозначными векторами.

# genetic algorithm
def genetic_algorithm(objective, bounds, n_iter, n_pop, r_cross, r_mut):
    # initial population of random real-valued vectors
    pop = [[random.uniform(bound[0], bound[1]) for bound in bounds] for _ in range(n_pop)]
    # keep track of best solution
    best, best_eval = 0, objective(pop[0])
    # enumerate generations
    for gen in range(n_iter):
        # evaluate all candidates in the population
        scores = [objective(d) for d in pop]
        # 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, pop[i], scores[i]))
        # select parents
        selected = [selection(pop, scores) for _ in range(n_pop)]
        # 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]

Единственное, что осталось решить, — изменить функции мутации и кроссовера, чтобы они работали с векторами с действительными значениями, а не с битовыми строками. Существует множество подходов к реализации мутации и скрещивания для векторов с действительными значениями; некоторые примеры перечислены в этом сообщении StackOverflow.

У вас есть геном с определенными генами:

genome = { GeneA: value, GeneB: value, GeneC: value }

Так возьмем, например:

genome = { GeneA: 1, GeneB: 2.5, GeneC: 3.4 }

Вот несколько примеров мутации:

  • Поменяйте местами два гена: { GeneA: 1, GeneB: 3.4, GeneC: 2.5 }
  • Добавить/вычесть случайное значение из гена: { GeneA: 0.9, GeneB: 2.5, GeneC: 3.4 }

Предположим, у вас есть два генома:

genome1 = { GeneA: 1, GeneB: 2.5, GeneC: 3.4 }
genome2 = { GeneA: 0.4, GeneB: 3.5, GeneC: 3.2 }

Вот несколько примеров кроссовера:

  • Принимая среднее значение: { GeneA: 0.7, GeneB: 3.0, GeneC: 3.3 }
  • Униформа (шанс 50%): { GeneA: 0.4, GeneB: 2.5, GeneC: 3.2 }
  • Кроссовер N-точки: { GeneA: 1, | CROSSOVER POINT | GeneB: 3.5, GeneC: 3.2 }

У меня было еще одно сомнение относительно этого кода, разве функция мутации уже не подходит для кодирования значения? Как указано в статье.

No_Name 19.11.2022 18:57

Функция мутации, приведенная в статье, принимает битовую строку. Он перебирает каждый бит в строке битов (которая представляет собой список 1 и 0) и случайным образом переворачивает некоторые биты. В векторном представлении с действительным знаком функция мутации должна принимать одно действительное значение и возвращать новое действительное значение, которое каким-то образом было случайно изменено.

Jonny 19.11.2022 22:16

Другие вопросы по теме