resueltos - codigo fuente de un algoritmo genetico python

¿Cómo puedo entrenar un algoritmo de programación genética en una secuencia variable de descriptores?

Question

Actualmente estoy intentando diseñar un algoritmo de programación genética que analice una secuencia de caracteres y asigne un valor a esos caracteres . A continuación he realizado un conjunto de ejemplos. Cada línea representa un punto de datos. Los valores que se entrenan son de valor real. Ejemplo: Para la palabra ABCDE el algoritmo debe devolver 1.0.

Ejemplo de conjunto de datos:

ABCDE : 1

ABCDEF : 10

ABCDEGH : 3

ABCDELKA : 50

AASD : 3

El conjunto de datos podría ser tan grande como sea necesario, ya que todo está hecho. Supongamos que la regla que el GP debe resolver no es demasiado complicada y que está explicada por los datos.

Lo que me gustaría que hiciera el algoritmo es aproximar los valores de mi conjunto de datos cuando se me da la secuencia de entrada. Mi problema ahora es que cada secuencia puede consistir en un número diferente de caracteres. Preferiría no necesitar escribir algunos descriptores de fantasía, si es posible.

¿Cómo puedo entrenar a mi médico de cabecera (preferiblemente usando tinyGP o python) para construir este modelo?

Como hubo tanta discusión aquí, un diagrama dice más que mil palabras: Lo que quiero hacer es poner un punto de datos y ponerlo en una función. Entonces obtengo un valor, que es mi resultado. Desafortunadamente, no conozco esta función, solo tengo un conjunto de datos que tiene algunos ejemplos (quizás 1000 ejemplos solo un ejemplo). Ahora utilizo el algoritmo de programación genética para encontrar un algoritmo que pueda convertir mi punto de datos en un resultado. Este es mi modelo. El problema que tengo en este caso es que los puntos de datos son de diferentes longitudes. Para una longitud establecida, solo podría especificar cada uno de los caracteres en la cadena como un parámetro de entrada. Pero me gana lo que debo hacer si tengo un número variable de parámetros de entrada.

Descargo de responsabilidad: he abordado este problema varias veces durante mis estudios, pero nunca podríamos encontrar una solución que funcionara bien (como usar una ventana, descriptores, etc.). Me gustaría usar un médico de cabecera, porque me gusta la tecnología y me gustaría probarlo, pero durante la Uni también probamos esto con ANN, etc., pero sin éxito. El problema del tamaño de entrada variable permanece.

Answer 1

Como no tiene una función de aptitud física, deberá tratar el algoritmo genético ya que era un clasificador. Por lo tanto, tendrá que encontrar una manera de evaluar un solo cromosoma. Como otros lo sugirieron, este es un problema de clasificación pura, no de optimización, pero, si aún desea seguir adelante con GA, aquí tiene algunos pasos para intentar un enfoque inicial:

Necesitará:

1. Descripción de (cómo codificar) un cromosoma válido

Para trabajar con algoritmos genéticos, todas las soluciones deben tener la misma longitud (hay un enfoque más avanzado con un límite de longitud variable, pero no ingresaré allí). Entonces, teniendo eso, necesitarás encontrar un método de codificación óptimo. Sabiendo que su entrada es una cadena de longitud variable, puede codificar su cromosoma como una tabla de búsqueda (diccionario en python) para su alfabeto. Sin embargo, un diccionario le dará algunos problemas cuando intente realizar operaciones de cruce o mutación, por lo que es mejor tener el alfabeto y la codificación del cromosoma divididos. Con referencia a los modelos de lenguaje, puede verificar los n-gramas, y su cromosoma tendrá la misma longitud que la longitud de su alfabeto:

.. 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]

.. Trigramas

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

2. Decodifica un cromosoma para evaluar una sola entrada.

Su cromosoma representará valores enteros para cada elemento de su alfabeto. Entonces, si desea saber el valor de una de sus entradas (cadena de longitud variable) que tiene un cromosoma, deberá probar algunas funciones de evaluación, la más simple es la suma de cada valor de letra.

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. función de la aptitud

Su función de fitness es simplemente una función de error simple. Puede usar suma de errores simple, error cuadrado ... Una función de evaluación simple para una sola generación:

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

Ahora, utilizando cualquier operador de cruce y mutación que desee (por ejemplo: un punto de mutación y mutación de cambio de bit), encuentre el cromosoma que minimiza ese error.

Cosas que puedes intentar para mejorar el modelo de algoritmo:

• Utilizando bigramas o trigramas
• Cambiar el método de evaluación (actualmente es una suma de valores de tabla de búsqueda, puede ser un producto o algo más complejo)
• Intente usar valores reales en los cromosomas, en lugar de solo enteros

Answer 2

La programación genética tradicional no es adecuada para entradas de longitud variable.

Se me ocurre que en la pregunta se presupone algún modelo de evaluación.

Considere, por ejemplo, que codifica su entrada de longitud variable a un solo valor de precisión arbitrario, por ejemplo para un alfabeto de 10 símbolos:

ABCD = 1234; ABCDEF = 123456

o

ABCD = 0.1234; ABCDEF = 0.123456

Sin embargo, si esta codificación no es natural para el dominio del problema, será bastante difícil desarrollar un programa que se ocupe de tal entrada.

También podría suponer que un problema puede ser representado adecuadamente por una máquina de estado finito derivada genéticamente:

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

Ese es un campo de estudio separado de la programación genética, busca en Google, lee artículos de investigación, quizás puedas encontrar un paquete que haga lo que quieras por ti.

Entonces, nuevamente, su problema puede estar mejor representado por otra transformación, por ejemplo, la frecuencia de los bigramas, tal transformación es de longitud finita:

# 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

Bigrams, trigrams, etc. son predictores sorprendentemente buenos:

• capturar información de Markov ("ab" vs "ac")
• posición relativa de captura ("ab" && "bc" vs "ed" && "bc")
• capturar semántica no lineal ("abab"! = "ab" * 2)
• Resistente a la entrada aleatoria ("comprar nuevo spam" vs "comprar spam es nuevo")

Estos se utilizan a menudo en problemas de lenguaje natural, como la detección de temas de texto, la detección de autores, la protección contra correo no deseado; biotecnología, como las secuencias de ADN y ARN, etc.

Sin embargo, no hay garantía de que este enfoque sea aplicable a su problema. Realmente depende de su dominio de problemas, por ejemplo, considere el alfabeto 10+ en el dominio de aritmética, las siguientes dos entradas se vuelven indistinguibles y, sin embargo, producen resultados diferentes:

10000+10000 = 20000
1000+100000 = 101000

En este caso necesitas algo como una máquina de registro:

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