Я пытаюсь реализовать генетический алгоритм, используя векторы фиксированной длины действительных чисел. Я нашел простую реализацию в Интернете с использованием двоичных закодированных значений. Мое замешательство возникает, когда я пытаюсь найти способ инициализировать массив и установить границы для этого алгоритма.
Ниже приведен фрагмент кода с двоичным декодированным кодом:
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))
Похоже, вы ссылаетесь на код в этой статье: Простой генетический алгоритм с нуля в 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 }
Функция мутации, приведенная в статье, принимает битовую строку. Он перебирает каждый бит в строке битов (которая представляет собой список 1 и 0) и случайным образом переворачивает некоторые биты. В векторном представлении с действительным знаком функция мутации должна принимать одно действительное значение и возвращать новое действительное значение, которое каким-то образом было случайно изменено.
У меня было еще одно сомнение относительно этого кода, разве функция мутации уже не подходит для кодирования значения? Как указано в статье.