salga

SALGA significa System for Automated Learning based in Genetics Algorithms, y es un programa desarrollado en python para el simular la evolución por selección natural de los individuos de una población de soluciones a un problema. Está orientado tanto a docencia como a desarrollo de proyectos en este campo.

Primeros pasos

Instalación

  • Descomprimir el archivo salga-xxx.zip.
  • Los usuarios de Windows deberán descargar también el runtime de python 2.7.x, disponible aquí,

Ejecutar el programa Salga

  • En windows, hay que instalar previamente python y ejecutar salga.pyo con doble click.
  • En MacOSX y en linux, abrir un terminal y teclear “python salga.pyo”. Dependiendo de la distribución de linux puede ser necesario instalar el paquete “python-tk”.

Definición del fitness, alfabeto y tipo de GA

Por su propia naturaleza, los Algoritmos Genéticos requieren, para ser adaptados a un problema concreto, que se defina una función de fitness (o función de calidad) que indica cómo de bueno es un individuo particular de cara a resolver un determinado problema. Éste fitness es la parte dependiente del dominio y debe programarse previamente para que el sistema pueda aplicarse al problema concreto.

Adicionalmente puede definirse una función phenotype que permita obtener el individuo a evaluar a partir del cromosoma que lo describe. Por otro lado debemos seleccionar el tipo de algoritmo genético a utilizar (classic, floating o permutation) e indicar el alfabeto a utilizar en el problema.

Sobre el tipo de Algoritmo Genético

El tipo de Algoritmo Genético a utilizar puede ser:

  • Classic
    • El alfabeto es un conjunto finito de símbolos.
    • La mutación se realiza a nivel de gen, eligiendo un nuevo valor del alfabeto.
    • El emparejamiento se realiza cortando las cadenas de los padres en un punto aleatorio y pegándolas cruzadas.
  • Floating
    • El alfabeto se forma con todos los posibles valores flotantes en un intervalo [a,b] definido en el campo alfabeto.
    • La mutación se realiza un salto aleatorio desde el valor actual con distribución gausiana y temple simulado.
    • El emparejamiento se realiza combinando los genes de los padres mediante la ecuación αG1+(1-α)G2, con α∈[0,1], eligiendo α aleatoriamente para cada emparejamiento.
  • Permutation
    • El alfabeto es un conjunto finito de símbolos.
    • Un cromosoma se forma por una permutación concreta del alfabeto, es decir, la longitud del cromosoma es la longitud del alfabeto.
    • La mutación consiste en intercambiar dos genes de posición.
    • El emparejamiento se construye copiando una subsecuencia del padre A y rellenando el resto con los valores que no están, tomándolos del padre B y manteniendo el orden parcial, aunque no la posición.
  • Variable
    • El alfabeto es un conjunto finito de símbolos.
    • La longitud del cromosoma es variable.
    • Mutación y emparejamiento son similares al classic.

Sobre el alfabeto

Dependiendo del tipo de Algoritmo Genético elegido, el alfabeto se especifica de diferente modo:

  • En ‘classic’, el alfabeto se representa por una lista de símbolos separados por comas y entre corchetes. Ejemplo: [0, 1] ➜ alfabeto binario.
  • En ‘floating’, el alfabeto se especifica por el par de valores que definen el intervalo, entre corchetes. Ejemplo: [0, 10] ➜ todos los valores flotantes en el intervalo [0, 10].
  • En permutation, el alfabeto se representa por una lista de símbolos separados por comas y entre corchetes, igual que en el modo ‘classic’. Ejemplo: [1, 2, 3, 4, 5] ➜ permutaciones de los números naturales del 1 al 5.

Sobre el fitness

La definición del fitness se realizará en un archivo python independiente que se cargará posteriormente desde el programa salga. Veamos un ejemplo sencillo cuyo objetivo es encontrar el número x tal que x^2 sea 488670902500:

import math
target = 488670902500

def phenotype (chromosome): # computes the decimal number represented by the chromosome
	res = 0
	l = len(chromosome)
	for v in range(l):
		if chromosome[l-v-1] != 0:
			res += 2**v
	return res

def fitness (chromosome): # aproximates x^2 = target
	fen = phenotype(chromosome)
	return 1.0 / (1.0 + abs(target - fen**2)) # maximum value when fen**2 == target!

Es este código, la función phenotype recibe un cromosoma y devuelve el número decimal obtenido a partir del genotipo, es decir, transforma, por ejemplo, “1 0 0 1” en el valor decimal 5. Si no se especifica, el fenotipo es el propio cromosoma.

La función fitness devuelve un valor tanto más alto cuanto más cercano es el número representado por un cromosoma a nuestro objetivo. Se ha construido además de modo que su máximo valor posible es 1.0, lo cual es bastante conveniente para la representación gráfica y para detener automáticamente el proceso evolutivo cuando el fitness del mejor individuo sea 1.

Es posible forzar valores para otros parámetros cuando se realiza la carga del fitness, tales como el alfabeto, las probabilidades de mutación y emparejamiento, la longitud del cromosoma y el método a utilizar, entre otros.

Significado/Uso de las distintas opciones del programa

Controles

  1. ‘Selección del tipo de genético a utilizar’ ➜ puede ser classic, floating o permutation. Cada tipo tiene sus propia interpretación del alfabeto y sus propios operadores de emparejamiento y mutación.
  2. ‘Load Fitness Function’ ➜ carga el código python que define el fitness y en su caso el fenotype.
  3. ‘Init’ ➜ crea la población inicia con valores aleatorios.
  4. ‘Learn’ ➜ inicia el proceso evolutivo.
  5. ‘Pmut’ ➜ probabilidad de mutación de un gen.
  6. ‘Pcross’ ➜ probabilidad de emparejar dos individuos una vez seleccionados.
  7. ‘Elitism’ ➜ indica si hay que usar elitismo. Si es el caso, el mejor individuo de cada generación se guarda para la generación siguiente, previniendo su desaparición.
  8. ‘Norm’ ➜ indica si hay que utilizar el método del rango para la selección, interesante para evitar que la evolución se estanque si los valores de fitness de los individuos son muy parecidos.
  9. ‘Norm. Factor’ ➜ cuando se usa el método del rango, indica cómo de intenso es el escalado de los valores con respecto a la calidad relativa de los individuos. Valores cercanos a 1 indican un escalado pequeño (la probabilidad de selección de los individuos es similar), mientras que valores menores haces que el escalado sea más intenso.
  10. ‘Chrom. size’ ➜ longitud de cromosoma a utilizar.
  11. ‘Population’ ➜ tamaño de la población.
  12. ‘Ω’ ➜ alfabeto a utilizar.
  13. ‘Target fit.’ ➜ fitness objetivo para finalizar el proceso. Se recomienda definir el fitness para que el máximo target posible sea 1.
  14. ‘Stalled in’ ➜ indica que el entrenamiento debe detenerse si en ese número de generaciones la calidad del mejor individuo no ha mejorado. Si es -1 la detención automática se desactiva.
  15. ‘Trace period’ ➜ cada cuántas generaciones actualiza la gráfica y la información presentada.
  16. ‘Load’ ➜ carga una población previamente almacenada.
  17. ‘Save’ ➜ graba la población actual.
  18. ‘Export’ ➜ exporta la población actual en un formato de texto que puede ser importado por otros programas.
  19. ‘Help’ ➜ abre esta ayuda.
  20. ‘About’ ➜ muestra créditos del programa.
  21. ‘Quit’ ➜ finaliza el programa.

Información presentada

  1. ‘Best fitness’ ➜ fitness del mejor individuo de la población
  2. ‘Mean fitness’ ➜ fitness medio de la población.
  3. ‘Diversity ➜ diversidad de la población.
  4. ‘Epoch’ ➜ generaciones transcurridas en la evolución en marcha.
  5. ‘Bst’ ➜ genotipo del mejor individuo en la generación actual, es decir, mejor solución al problema hasta el momento.
  6. ‘En la parte inferior’  fenotipo del mejor individuo en la generación actual.

Procedimiento para generar una solución

  1. Seleecionar tipo de Algoritmo Genético a utilizar.
  2. Cargar la función de fitness con ‘Load fitness’.
  3. Definir el alfabeto a utilizar.
  4. Ajustar los diferentes parámetros (Pmut, Pemp, etc.) o dejar los valores por defecto.
  5. Click en ‘Learn’.
  6. El entrenamiento puede pararse a mano dando click en la opción ‘Stop’ o automáticamente cuando el mejor individuo de la población tenga un fitness igual o mayor a ‘Target fit.‘ o cuando el mejor individuo no haya mejorado tantas generaciones como indique ‘Stalled in‘.

Interpretación de los valores de entrenamiento

salga

Colores de las líneas

  1. Blanco: fitness medio de la población.
  2. Verde: fitness del mejor individuo.
  3. Rojo: diversidad de la población.
  4. Gris: subdivisiones del error en pasos del 10% del “target fitness”, es decir, el punto en que se detendrá la evolución.

Comments are closed.