Pulsa aquípara volver a sección de Informática de Cyberfisica

Algoritmos genéticos

Los algoritmos genéticos son técnicas para obtener soluciones aproximadas a problemas en los que evaluar la solución exacta resultaría muy costoso en tiempo. Un algoritmo es una secuencia de operaciones que efectúa alguna función, y se le llama genético porque “simula” la reproducción y mutación de código genético como se hace en otras ciencias (biología, genética, etc). Pero sólamente simula, es decir lo que se va a explicar es un procedimiento puramente informático para resolver problemas de todo tipo y no es una parte de la biología o un conjunto de métodos informáticos para aplicarlo a esa ciencia, como se puede pensar al escuchar el nombre.
 

El problema del viajante

Consideremos el ejemplo de un viajante que parte de una ciudad ”origen” y tiene que pasar por un número determinado de ciudades, digamos 20.La ruta a escoger resulta diferente según el orden en que se visiten las ciudades. Si vamos visitando ciudades en un orden en que cada una está lo más cerca  posible de la próxima entoces el viaje nos resultará más rentable que si visitamos primero una ciudad que esté muy lejos de la “origen”, luego volvemos a otra cerca de ésta, luego nos volvemos a ir al otro extremo etc. Por eso nos puede interesar visitar  las ciudades en un orden en que la distancia total  sea la más corta posible.
Ahora intentamos desarrollar un programa que consista en lo siguiente: dadas las coordenadas (x,y) de las ciudades origen y de las demás ciudades a visitar, que éste evalue todas las maneras posibles de efectuar el recorrido y vaya calculando sus respectivas distancias una a una, dándonos al final como resultado la más pequeña.
Pero esto sin duda tiene un problema. En nuestro ejemplo con 20 ciudades el número de maneras diferentes de recorrerlas es 2.432.902.008.176.640.000 (que es 20!) que es un número aun astronómico para los ordenadores de hoy en día. Está claro que si diseñamos un programa que nos intente calcular la solución exacta por evaluación de todas las rutas posibles, el programa no será rentable en tiempo. Pensemos que si el número de ciudades en lugar de ser 20 fuese 40 el número de maneras distintas de recorrerlas nos sale del orden de 8e47 (un 8 con 47 ceros detrás). Es decir, hemos de descartar este método por ser demasiado costoso en tiempo, incluso irrealizable en muchos casos.
 

Solución de este problema mediante algoritmos genéticos

Los algoritmos genéticos nos permitirán encontrar una solución aproximada a este problema, una solución que puede ser (y la mayoría de veces lo es) muy cercana a la mejor.
Identificamos a cada ciudad con un número (1,2,3...20) y generamos 20 ristras (el número 20 es arbitrario) con los 20 numeros de las ciudades ordenados de manera aleatoria, de manera que tengamos 20 rutas diferentes que hemos generado por azar. Ahora vamos a reproducir esas ristras; esto es que a partir de cada una generaremos 10 más: la primera de ellas la dejamos igual que la ristra “padre” (o sea la que hemos usado para generar esta) y en cada una de las otras 9  permutamos dos ciudades al azar. Por ejemplo, si una de las 20 ristras generadas aleatoriamente que contienen un orden concreto de visita de las ciudades es

20 3 4 1 15 16 18 2 5 6 7 11 12 8 9 10 19 17 14 13

entonces la primera de las 10 ristras que llamaremos “hijas” será ella misma y la segunda será la misma, excepto que habremos permutado 2 elementos (por ejemplo la posición del 20 por la del 4), obteniendo así una ristra diferente que implica una nueva manera de recorrer las ciudades. Y las demás análogamente a esta segunda.
Teníamos 20 ristras “padres”, de cada una hemos generado 10 ristras hijas diferentes, por tanto tendremos 200 ristras diferentes. Ahora podemos calcular la distancia que supondría recorrer las ciudades en cada una de estas 200 rutas en que las tenemos ordenadas. Notemos que ahora habremos de hacer solamente 200 operaciones frente a las 2.432.902.008.176.640.000 que habíamos de hacer si evaluávamos todas las posibilidades. Ahora de estas 200 nos quedamos con las 20  mejores, esto es, con las ristras que generaban las 20 maneras más rentables (en distancia) de realizar el viaje. Con estas 20 repetiremos el proceso de generar otras 200, de ellas calcularemos de nuevo sus 20 mejores y podemos repetir toda esta operación (es lo que se llama el algoritmo genetico) todas las veces que queramos. Se puede comprobar cómo en cada “reproducción” y selección de las 20 mejores ristras van apareciendo mejores resultados que en la anterior reproducción. Al terminar del programa, de esas 20 mejores ristras solamente nos quedamos con la mejor, dándola como resultado final. Ésa será nuestra aproximación a la solución.
Por qué se le llama aproximación? Esto es porque hemos ido tanteando soluciones que al principio eran malas pero que cada vez iban generando otras soluciones mejores, así que después de un cierto número de repeticiones del algoritmo genético obtenemos una solución razonablemente buena.
 

Por qué es buena la solución y el por qué de hacerlo de esta manera

¿Cómo saber si esa aproximación es buena, si lo único que hemos hecho ha sido evaluar un cierto númerode ristras que es mucho menor que el número de maneras posibles de visitar todas las ciudades? Y si hemos repetido el algoritmo digamos, 50 veces, no sería menos complicado coger 50x200=10000 ristras y evaluar las distancias de cada una de ellas prescindiendo de lo que hemos llamado mutación y reproducción? Contestaremos a estas preguntas simultáneamente.
Las dos preguntas son razonables. Es chocante que si repetimos el algoritmo genético 50 veces y por lo tanto habremos analizado 50x200=10.000 ristras aleatorias,pues que la más óptima de todas ellas pueda no acercarse nada a la manera de recorrer las ciudades por el camino más corto, ya que el número de maneras distintas era 2.432.902.008.176.640.000 y solamente estamos mirando 10.000 de ellas!!!! Por otra parte, tambien nos preguntamos el por qué de la evaluación “genética” de esas 10.000 ristras y no las evaluamos secuencialmente, cosa que nos ahorraría tiempo (y tiempo de pensar también).
Pues aquí llega la comparación genética. Al igual que un padre se parace (normalmente) a su hijo, las ristras generadas se parecen a las ristras “padres” que usamos para generarlas. Cuando  generamos las 20 primeras ristras,  éstas pueden ser buenas o malas aleatoriamente, pero las ristras “hijas” que genera una ristras buena tienen tendencia a ser en su mayoría buenas, y así al ir seleccionando las mejores cada vamos moviéndonos más por el espacio de las soluciones buenas  y no es para nada lo mismo que generar 10.000 ristras aleatoriamente y dar como resultado la mejor.
Pues con este ejemplo se permite ilustrar en lo que  consisten principalmente los algoritmos genéticos. La eficiencia de éstos depende de la a a priori desconocida elección correcta de número de iteraciones, ristras seleccionadas inicialmente, ristras hijas que genera cada ristra padre, etc. Cabe decir que estos algoritmos genéticos resuelven a diario un problema muy similar al del viajante y que es el de las empresas de logística que han de distribuir mercancías en varios puntos de una ciudad y han de hacerlo por varios motivos por la distancia más corta (tiempo, dinero, etc.).
 

Otros tipos de problemas resolubles con algoritmos genéticos

Cada problema posee un planteamiento diferente, y en el problema del viajante se trataba de evaluar posibles caminos y sus distancias. Tomábamos como criterio que una ruta era mejor si la distancia total en recorrerla era mínima, pero hay otro tipo de problemas que en lugar de minimizar o maximizar alguna cantidad física, matemática económica, etc funcionan por puntuaciones. A cada uno de los sucesos posibles se le da una puntuación según lo favorable que sea, y entonces generaremos conjuntos de sucesos aleatoriamente (igual que lo habíamos hecho con las ciudades) y tomaremos como criterio que el mejor es aquél con puntuación máxima. Por ejemplo, consideremos el problema de un grupo de estudiantes en viaje de fin de curso. Hay 100 estudiantes y 4 destinos, cada uno con 25 plazas, pero naturalmente habrá un destino más atractivo que otro y probablemente más de 25 personas quieran ir a ese mientras que tan sólo un par quieran ir a otro de ellos. Los alumnos deben escribir en su papel los 4 destinos  por orden de preferencias, y el jefe de estudios tratará de que todos estén lo más contentos posibles.
Es posible resolver este problema por algoritmos genéticos. Primero hemos de entrar en el ordenador las preferencias de los estudiantes. Asignamos a cada uno de ellos un número entre 1 y 100, por ejemplo su posición en una lista de ellos ordenada alfabéticamente. Generaremos esta vez una ristra de valores que contenga 100 números aleatorios sin repetición distribuidos entre 1 y 100, por ejemplo 56 76 43 23 1 98 72 .... que no son más que los estrudiantes ordenados. Tomamos el criterio de que en una de estas listas, los 25 primeros irán al destino 1, los 25 siguientes al 2, etc. Así una ristra es una permutación de las números 1,2,..100 que tiene el significado de una manera determinada de repartir los destinos a los estudiantes.
Ahora evaluemos lo "contentos" que están los estudiantes con sus destinos. Evaluamos los 25 primeros elementos de la ristra, a los que les toca el destino 1, y asignamos una puntuación de 2 si el destino 1 era el que ese estudiante quería, un 1 si era su segunda opción y un cero en cualquier otro caso. Sumamos las “puntuaciones” y realizamos la misma operación con los tres grupos restantes de 25. Así una puntuación muy alta significará que la repartición se ha realizado mejor, que los estudiantes están más contentos. Ahora nos podemos construir un algoritmo genético basado en esta ristra, mutarlas y  reproducirlas de manera que nos quedamos sólamente con las de puntuación más elevada, y después de unas cuantas iteraciones encontraremos resultados sorprendentes.
Antes de concluir con este ejemplo diremos unas palabras sobre la elección de las “puntuaciones”, es decir, como la manera de darlas puede cambiar ligeramente el significado de lo que estamos haciendo. El hecho de dar 2 puntos si el destino coincide con el primero y 1 si es la segunda opción es un criterio cualquiera. Podríamos haber dado más importancia al hecho de que haya más estudiantes que vayan a donde escogieron, y así habríamos de dar mayor peso cuando el destino coincida con su primera preferencia (por ejemplo 3 y 1, en lugar de 2 y uno). O podríamos ser más cautelosos y evitar que haya muchos estudiantes que vayan al destino que eligieron como cuarto, es decir, a donde menos querían ir, y podríamos dar puntauciones de 2 y 1 como antes, pero además –1 si el destino en la ristra de un estudiante es su última opción, y así podríamos inventar muy diferentes criterios que nos darán diferentes resultados.
 

Algoritmos genéticos y redes neuronales

Los algoritmos genéticos también pueden utilizarse para entrenar a redes neuronales. Los que poseen conocimientos en este sector saben de sobras que en una red neuronal una de las tereas más difíciles es encontar las matrices de pesos que según sean diferentes harán que la red funcione mejor o peor. Se puede construir un algoritmo que genere unos pesos aleatorios, y pruebe a ver si la red devuelve una salida aproximadamente esperada. Si podemos evaluar el error cometido, entoces podemos entrar varios patrones y hacer actuar el algoritmo genético sobre las matrices de pesos para minimizar la suma de errores.
 

Ejercicios

- Modificar el algoritmo genético de las ciudades imponiendo bloqueos entre algunas de ellas (por ejemplo que no se pueda ir directamente de la ciudad 8 a la 5 ni de la 2 a la 12 porque sus carreteras suelen estar muy frecuentadas y se tarda más).

- Crear un algoritmo genético que reparta los asientos de los invitados  de una boda según sus preferencias, es decir cada invitado dará una lista de personas al lado de las que querría estar sentado y otra lista con las personas que no quiere que se sienten a su lado. Hay que conseguir que se cumplan en su mayoría sus preferencias

- Repartición de asignaturas y profesores: tenemos una lista de profesores, cada uno puede impartir una(s)determinada(s) asignatura(s), y una lista de clases con el nº de horas que debe recibir cada asignatura cada una de las clases y se pide diseñar un algoritmo genético que reparta el horario de las asignaturas y asigne a ellas  profesores de manera que no se solapen clases del mismo profesor. El probema se puede complicar si imponemos restricciones como que un profesor no puede dar clase a una cierta hora, que uno de los días una asignatura de dos horas debe darse en dos horas consecutivas, etc.