Как я могу обучать алгоритм генетического программирования на переменную последовательность дескрипторов?

Ответ 1

Традиционное генетическое программирование не подходит для ввода переменной длины.

Мне кажется, что в вопросе предполагается какая-то модель оценки.

Рассмотрим, например, что вы кодируете ввод переменной длины в одно произвольное значение точности, например, для алфавита из 10 символов:

ABCD = 1234; ABCDEF = 123456

или

ABCD = 0.1234; ABCDEF = 0.123456

Однако, если эта кодировка не является естественной для проблемной области, будет довольно сложно разработать программу, которая хорошо подходит для такого ввода.

Вы также можете предположить, что проблема может быть адекватно представлена ​​генетически выведенной машиной конечного состояния:

F(F(F(F(init(), A), B), C), D) = 1234

Что отдельная область изучения генетического программирования, google вокруг, читайте исследовательские статьи, возможно, вы можете найти пакет, который делает то, что вы хотите для вас.

Затем снова ваша проблема может быть лучше всего представлена ​​еще одним преобразованием, например. частота биграмм - такое преобразование конечной длины:

# bigrams
# ABCDE => 1
"AA": 0
"AB": 0.25
"AC": 0
"AD": 0
"AE": 0
"BA": 0
"BC": 0.25
"BD": 0
#... up to end of alphabet ...

(0, 0.25, 0, 0, 0, 0, 0.25, 0, ...., 0, ...) => 1      # ABCDE
(0, 0.20, 0, 0, 0, 0, 0.20, 0, ...., 0.20, ...) => 10  # ABCDEF
# input length N^2

# trigrams
(0, 0.33, 0, 0, ..., 0, ...) => 1      # ABCDE
(0, 0.25, 0, 0, ..., 0.25, ...) => 10  # ABCDEF
# input length N^3

Биграммы, триграммы и т.д. являются на удивление хорошими предикторами:

• информация о захвате марков ( "ab" vs "ac" )
• захватить относительное положение ( "ab" & "bc" vs "ed" & "bc" )
• захватить нелинейную семантику ( "abab"!= "ab" * 2)
• устойчивый к перетасованному вводу ( "купить новый спам" против "купить спам он новый" )

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

Однако нет гарантии, что этот подход применим к вашей проблеме. Это действительно зависит от вашей проблемной области, например, рассмотрите алфавит 10+ в области арифметики, следующие два входа становятся неразличимыми, но при этом дают разные результаты:

10000+10000 = 20000
1000+100000 = 101000

В этом случае вам нужно что-то вроде машины регистрации:

init: tmp = 0; res = 0
"0": tmp *= 10
"1": tmp *= 10; tmp += 1
"+": res += tmp; tmp = 0
end: res += tmp

Ответ 2

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

Вам понадобится:

• Описание (как кодировать) действительную хромосому

Чтобы работать с генетическими алгоритмами, все решения должны иметь одинаковую длину (существует более продвинутый подход с переменной длиной, поддерживающей, но я не вхожу туда). Итак, имея это, вам нужно будет найти оптимальный метод кодирования. Зная, что ваш ввод является строкой переменной длины, вы можете кодировать свою хромосому в качестве таблицы поиска (словарь на языке python) для вашего алфавита. Тем не менее, словарь даст вам некоторые проблемы при попытке применить операции кроссовера или мутации, поэтому лучше иметь разделение алфавита и хромосомы. Ссылаясь на языковые модели, вы можете проверить наличие n-граммов, а ваша хромосома будет иметь такую ​​же длину, как длина вашего алфавита:

.. Unigrams

alphabet = "ABCDE"
chromosome1 = [1, 2, 3, 4, 5]
chromosome2 = [1, 1, 2, 1, 0]

.. Bigrams

alphabet = ["AB", "AC", "AD", "AE", "BC", "BD", "BE", "CD", "CE", "DE"]
chromosome = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

.. Триграммы

alphabet = ["ABC", "ABD", "ABE"...]
chromosome = as above, a value for each combination

2.   Декодировать хромосому для оценки одного входа

Ваша хромосома будет представлять собой целочисленные значения для каждого элемента вашего алфавита. Поэтому, если вы хотите знать значение одного из ваших вводов (строка переменной длины), имеющего хромосому, вам нужно будет попробовать некоторые оценочные функции, а простейшая - это сумма каждого значения букв.

alphabet = "ABC"
chromosome = [1, 2, 1]
input = "ABBBC"

# acc = accumulated value
value = reduce(lambda acc, x: acc + chromosme[alphabet.index(x)], input, 0)
# Will return ABBBC = 1+2+2+2+1 = 8

3.   Фитнес-функция

Ваша функция фитнеса - просто простая функция ошибки. Вы можете использовать простую сумму ошибки, квадратную ошибку... Простая функция оценки для одного генератора:

def fitnessFunction(inputs, results, alphabet, chromosome):
    error = 0

    for i in range(len(inputs)):
        value = reduce(lambda acc, x: acc + chromosome[alphabet.index(x)], inputs[i], 0) 
        diff = abs(results[i] - value)
        error += diff # or diff**2 if you want squared error

    return error

# A simple call -> INPUTS, EXPECTED RESULTS, ALPHABET, CURRENT CHROMOSOME
fitnessFunction(["ABC", "ABB", "ABBC"], [1,2,3], "ABC", [1, 1, 0])
# returned error will be:
# A+B+C = 1 + 1 + 0 -- expected value = 1 --> error += 1
# A+B+B = 1 + 1 + 1 -- expected value = 2 --> error += 1
# A+B+C = 1 + 1 + 1 + 0 -- expected value = 3 --> error += 0
# This chromosome has error of 2

Теперь, используя любой оператор кроссовера и мутации, который вы хотите (например: одноточечный кроссовер и мутация бит-флип), найдите хромосому, которая минимизирует эту ошибку.

Вещи, которые вы можете попытаться улучшить модель алгоритма:

• Использование биграмм или триграмм
• Измените метод оценки (в настоящее время это сумма значений таблицы поиска, это может быть продукт или что-то более сложное)
• Попробуйте использовать реальные значения в хромосомах вместо целых чисел