генетический алгоритм двоичное кодирование отрицательные целые числа

Question

Я пытаюсь реализовать генетический алгоритм для максимизации функции из n целочисленных переменных x1..xn, где каждая переменная принадлежит диапазону [-n, n]. Я имею в виду использование двоичной кодировки для представления хромосомы, но я не уверен, как кодировать отрицательные целые числа. Я искал довольно долгое время, но у меня не встречалась общая формула для двоичной кодировки. Каков наиболее распространенный способ кодирования целых чисел в диапазоне [-n, n] для генетических алгоритмов? Я хочу, чтобы кроссовер и мутация имели меньшую сложность (меньше проверки состояния). Будет ли он работать, если для начальной совокупности вместо генерации чисел между -n и n я генерирую числа от 0 до 2n и кодируя их в двоичном формате, а затем, при декодировании, каждый раз вычитаю n (для каждого последующего поколения)?

Answer 1

Ответ пользователя1765444 имеет смысл ... и я только что прочитал предложение sashkello (использование смещения бинарного кода устранило бы необходимость обмануть с подписанными ints внутри GA). Выполнение кроссовера и мутаций и т. Д. Было бы легко таким образом - используя комбо и ответов shashkello и user1765444. Проблема в том, что ваш тип данных имеет большую ширину, чем ваш диапазон, тогда кроссовер может привести к недействительным дочерним элементам.

Предположим, что int32 имеет требуемую ширину. Затем массив int32 [n]. Вы знаете, что есть 32n бит, поэтому вы можете взять точку пересечения в случайном порядке m, где m> = 0 и m < 32n. Вы знаете, что бит m встречается в массиве [m/n], положение бита m% n, начинающееся с msb (представление массива как одной длинной двоичной строки).

Тогда скажите, что у вас есть 2 родителя int32 parent1 [n] и int32 parent2 [n]. Что-то вроде следующего псевдоисшего кода? В этом кроссовере строка - это просто двоичная строка для креста (т. Е. Знак бит обрабатывается как еще один бит).

Отказ от ответственности: Извините, код ниже грубый n готов, не скомпилирован, поэтому может содержать ошибки ... просто мысль!

int child1[n]; 
uint32 m = rand_like_func(); // random cross over point, a bit position 
          // in the binary string of length n*32; 
uint32 arraySlotForCrossOvr = (uint32)(m/n); 
uint32 bitInSlotForCrossOvr = 31 - m % n; 
uint32 maskForCrossOvrP2 = (1 << bitInSlotForCrossOvr) - 1; 
uint32 maskForCrossOvrP1 = ~maskForCrossOvrP2; 

// crossover to create child 1 
memcpy(child1, parent1, arraySlotForCrossOvr); 
child1[arraySlotForCrossOvr] = 
    (int32)(((uint32)parent1[arraySlotForCrossOvr] & maskForCrossOverP1) | 
      ((uint32)parent2[arraySlotForCrossOvr] & maskForCrossOvrP2)) 
memcpy(
    child1, 
    parent2 + arraySlotForCrossOvr + 1, 
    total_num_slots - arraySlotForCrossOvr); 

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

Надеюсь, что это помогло?

Кроме того, я нашел «Как это решить: Современные эвристики З. Michalewicz и D Фогель» очень полезно при попытке понять кодирование проблем и т.д. :)