Cualquier persona que no tenga idea de informática y aquellos que la tengan pero no hayan tenido la oportunidad de conocer esta técnica se preguntarán, ¿Qué es un algoritmo genético?. Según Wikipedia "Un algoritmo es una serie de pasos organizados que describe el proceso que se debe seguir, para dar solución a un problema específico. Son llamados así porque se inspiran en la evolución biológica y su base genético-molecular. Estos algoritmos hacen evolucionar una población de individuos sometiéndola a acciones aleatorias semejantes a las que actúan en la evolución biológica (mutaciones y recombinaciones genéticas), así como también a una Selección de acuerdo con algún criterio, en función del cual se decide cuáles son los individuos más adaptados, que sobreviven, y cuáles los menos aptos, que son descartados". Según yo diría que son unos algoritmos que buscan una solución a un problema de optimización en un espacio de soluciones más o menos aleatorio, consiguiendo en algunos casos la solución óptima en un tiempo de ejecución bastante reducido.
En comparación con otras técnicas como Backtracking el tiempo en encontrar soluciones ambos algoritmos puede llegar a tener una grandísima diferencia.
La primera toma de contacto que tuvimos con estos algoritmos fue para la reslocuión del problema de las n reinas, y tal y como observamos el tiempo que empleaba el algoritmo para unos tamaños de problema considerables era bastante aceptable.
Estos algoritmos tienen las siguientes características:
Los algoritmos genéticos se representan mediante una cadena sobre un alfabeto finito (una posible codificación sería una cadena de 0s y 1s). Dicha codificación define el tamaño del espacio de búsqueda y el tipo de operadores de combinación necesarios.
Cada elemento de un estado (también llamado individuo o cromosoma) es denominado gen.
Se utilizan unos operadores denominados "Selección, Cruce y Mutación" que explicaremos más adelante.
Estos algoritmos hacen uso de funciones heurísticas, y el valor heurístico de un estado se denomina fitness. La función de idoneidad o fitness mide la calidad de los estados.
Se basan en la afirmación de que combinando buenos estados se obtienen estados mejores.
Ahora pasamos a explicar de manera breve los distintos operadores:
Selección: Escoge qué individuos tendrán la oportunidad de reproducirse. Habrán individuos que aparezcan más de una vez y habrán individuos que no aparezcan. Principalmente hay dos técnicas para realizar esta función: Ruleta y Torneo. La primera técnica elige individuos con probabilidad proporcional a su función de idoneidad. La segunda establece k torneos aleatorios entre parejas de individuos y selecciona aquellos que ganen cada torneo.
Cruce: Los individuos seleccionados son recombinados para producir la descendencia que formará la siguiente generación. La técnica más común y básica es el operador de cruce por un punto.
La función de idoneidad asigna un medida de calidad a cada estado (individuo). Cuando mejor sea dicho estado mayor será el valor de la función idoneidad.
De esta forma queda definido más o menos qué es un algoritmo genético.
El problema que nos tocó resolver era el problema de la mochila 0/1 (el cual ya hicimos también con otras técnicas de programación el curso anterior). Está resuelto en C++ haciendo uso de la librería Galib (no hemos tenido que hacer ningún tipo de implementación de individuos y demás). La única función que hemos tenido que realizar ha sido modificar los operadores de inicialización, cruce, mutación y la función objetivo (la que calcula el fitness de un individuo).
El problema que debíamos resolver es el siguiente:
Una empresa de publicidad necesita sacar al mercado un cierto producto. Para ello, debe elegir los avisos (anuncios publicitarios) en los medios de comunicación con el objetivo de maximizar el número de personas (audiencia) a los que alcanzan. La empresa cuenta de un presupuesto para ello y existe una cota superior para el número de avisos de cada tipo. Además, de acuerdo a ciertos estudios, se conoce la audiencia de cada medio de comunicación. El costo por aviso en cada medio de comunicación también es fijo y conocido.
Este problema puede modelarse mediante el modelo knapsack 0/1:
Tenemos n objetos. El problema knapsack 0/1 consiste en llenar una mochila con objetos. Cada objeto i tiene un peso determinado pi siempre positivo y una utilidad o valor asociado, también positivo, bi. Se ha de considerar además que la mochila tiene una capacidad máxima limitada C, por tanto, se han de escoger aquellos objetos xi para llenar la mochila que maximicen la utilidad sin exceder su capacidad”.
Diseñar e implementar en GALib, este problema utilizando un algoritmo genético simple.
Tener en cuenta los siguientes elementos o cuestiones:
Como los individuos que se obtienen en la inicialización de la población y al aplicar los operadores genéticos pueden ser individuos inválidos (individuos que no verifican las restricciones, es decir, sobrepasan la capacidad de la mochila), necesitamos modificar la inicialización y operadores genéticos para que comprueben la validez de los individuos generados. Para ello, vamos a partir de la inicialización, operador de cruce y mutación disponibles en GALib para string binarios.
Las modificaciones deben realizarse en el siguiente sentido:
- Inicialización: Ir creando el individuo gen a gen. Ir introduciendo elementos en los genes de forma aleatoria siempre que sea un individuo válido.
- Operador de cruce: supongamos que tenemos los cromosomas padre P11+P12 y P21+P22, cortados por el punto de corte x.
El operador de cruce empieza a crear los individuos hijos como sigue:
Tomar P11+P’, donde P’ es el trozo de cromosoma e inicialmente está a cero (no incluye ningún objeto). Ir recorriendo P22 gen a gen. Si al introducir el valor de un gen en P’ produce un P11+P’ válido, se introduce copiando sus valor en P’. En caso contrario, pasar al siguiente gen.
Tomar P21+P’, donde P’ es el trozo de cromosoma e inicialmente está a cero (no incluye ningún objeto). Ir recorriendo P12 gen a gen. Si al introducir el valor de un gen en P’ produce un P21+P’ válido, se introduce. En caso contrario, pasar al siguiente gen.
- Operador de mutación: si al mutar un gen provoca un individuo inválido, está mutación no se realiza. Se sigue con el siguiente gen candidato a ser mutado. Una vez diseñado el algoritmo genético, probarlo para el caso siguiente:
a) Si suponemos que disponemos de 5.000 euros para la publicidad, que como máximo podríamos poner 20 anuncios en paneles estáticos, 20 anuncios en paneles móviles, 40 anuncios en prensa, 50 anuncios en radio y 50 en televisión. Además, cada anuncio tiene un costo de 15, 15, 25, 45 y 90 euros, y una audiencia de 35, 40, 90, 135 y 220, respectivamente. ¿Cuántos anuncios podríamos poner en total en cada medio?
b) Cambiar los datos del problema para hacerlo más complejo. Además, del caso anterior, definir cuatro casos distintos del problema con complejidad distinta. Comparar los resultados en tiempo y solución del algoritmo genético en los 5 casos distintos.
A continuación expondré la solución propuesta para la implementación:
Para la implementación del algoritmo genético que resolviese el problema de la mochila 0/1 hemos optado por hacer uso de la clase GA1DArrayAlleleGenome, la cual, a su vez, hace uso de un array de conjuntos de alelos: GAAlleleSetArray.
El primer paso importante en la realización del algoritmo es la inicialización del array de conjuntos de alelos. Este array almacenará conjuntos de valores que representarán el número de cada tipo de anuncios que disponemos. Más adelante veremos que esto nos sirve para establecer el número de anuncios de un tipo concreto que hemos metido en la mochila. Por tanto, dichos valores estarán en el rango [0 – anunciosTipoi].
La inicialización de este array se hace de la siguiente manera:
1) Declaramos el array de conjuntos de alelos.
2) Creamos un conjunto de alelos y añadimos los valores deseados con la función add.
3) Añadimos el conjunto creado al array de alelos mediante la función add.
Cabe destacar que ,debido a que estas dos clases están parametrizadas, se han declarado para que almacene tipo de dato entero, ya que no tiene sentido tener valores reales de la cantidad de anuncios.
Una vez realizada la inicialización del array de conjuntos de alelos que usaremos para resolver este problema, pasamos ahora a la declaración de la clase que usaremos para crear posteriormente el algoritmo genético simple.
Dicha clase es la mencionada anteriormente, GA1DArrayAlleleGenome. Para la creación de esta clase usamos las ya definidas anteriormente que nos representan los conjuntos de alelos que emplearemos en el problema. Esta clase además nos sirve para especificar los operadores de inicialización, cruce y mutación que emplearemos para nuestra población de genomas. Dichas operaciones se detallan a continuación:
•Operador de Inicialización: El objetivo de esta función es el de inicializar la población con valores válidos. Valores válidos son aquellos que no superen la capacidad máxima de la mochila y, además, cada valor individual no supere el número de anuncios máximo del tipo que representa.
El hecho que motiva que tengamos que definir nosotros mismos este operador, es que debemos controlar que el incializado de los individuos de nuestra población sea correcto ya que, si lo hiciésemos con valores aleatorios, podríamos tener individuos inválidos.
Para realizar este control realizamos los siguientes pasos:
1) Recorremos el genoma.
2) Para cada gen del genoma generamos un valor aleatorio dentro de los limites especificados por el conjunto al que pertenece.
3) Comprobamos si al insertar dicho valor superamos la capacidad máxima de la mochila. En caso afirmativo vamos reduciendo dicho valor hasta que consigamos meterlo o el valor sea 0. En caso negativo lo metemos sin más.
De esta forma conseguiríamos tener toda la población inicializada con valores 3aleatorios y afirmar que son válidos.
•Operador de Cruce: El operador de cruce nos sirve para generar individuos nuevos a partir de dos individuos que tomaremos como progenitores. De nuevo debemos definirnos nuestro propio operador para asegurar que se cumplan las restricciones impuestas por el problema.
El operador de cruce que hemos implementado es el de cruce por un punto. Dicho punto de cruce es establecido por un valor aleatorio entre 0 y la longitud del genoma.
Una vez establecido este punto recorremos todos los genes del genoma hasta dicho punto y copiamos los genes de la madre en el primer hijo y los del padre en el segundo, y posteriormente se copian el resto de genes del padre para el primero y el resto de la madre para el segundo.
Al realizar la copia, de la primera parte de cualquiera de los dos progenitores no debemos realizar ninguna comprobación, ya que si partimos de individuos válidos, una parte de ellos también es válida. Por tanto las comprobaciones debemos hacerlas al copiar la segunda parte. La comprobación a realizar es ver si al copiar el gen en el hijo excedemos la capacidad de la mochila, en caso afirmativo optamos por establecer dicho gen a 0. Una alternativa podría ser ir reduciendo el valor del gen del progenitor e insertarlo.
•Operador de Mutación: Este operador ha sido modificado para que nos cambie el valor de un gen por un valor aleatorio. La única consideración es comprobar si al realizar la mutación el individuo generado es válido. Si es válido seguimos con los siguientes genes, si por el contrario generamos uno inválido entonces establecemos su valor como 0. Una posible alternativa es ir reduciendo el valor del número aleatorio generado hasta que sea posible asignárselo al gen.
•Función objetivo: La función objetivo será usada por el algoritmo genético para conocer el valor de fitness de un individuo. Este valor es calculado de la siguiente manera:
1) Recorremos los genes del individuos
2) Por cada gen multiplicamos su valor por el beneficio
3) Vamos llevando la suma y la devolvemos.
Los valores asignados para el tamaño de la población y el número de generaciones ha sido 100 y 1000 respectivamente. Además la probabilidad de mutación y de cruce son de 0.1 y 0.9 respectivamente.
Cabe destacar que hemos optado por leer los datos del problema por teclado. El realizarlo de esta manera nos beneficia en cuanto a que podemos insertar los valores del problema que queramos ejecutar a mano, o mediante un fichero redireccionando la entrada desde consola.
/*Declaracion y creacion del array de conjuntos de alelos */
GAAlleleSetArray arrayAlelos;
cin>>maximo_dinero>>num_publicidad;
datos.capacidadMaxima = maximo_dinero;
for(int i=0;i>aux;
datos.pesos.push_back(aux);
cin>>aux;
datos.beneficio.push_back(aux);
cin>>aux;
GAAlleleSet alelos;
for(int j = 0;j<=aux;j++)
alelos.add(j);
arrayAlelos.add(alelos);
}
// Creamos el GA. Primero creamos el genoma y creamos una poblacion de genomas
GA1DArrayAlleleGenome genome(arrayAlelos, Objective, &datos);
// Inicializamos -minimizar la funcion objetivo, tamaño de la poblacion, no.
// generaciones, prob. mutacion, prob. Cruce, y le indicamos que evolucione.
genome.initializer(inicializar); //Establecemos funcion operadores de inicializacion, cruce y mutacion
genome.mutator(mutador);
genome.crossover(cruzador);
GASimpleGA ga(genome);
ga.minimaxi(1);
ga.populationSize(popsize);
ga.nGenerations(ngen);
ga.pMutation(pmut);
ga.pCrossover(pcross);
ga.solve(); //Resuelve problema
// Ahora imprimimos el mejor individuo que encuentra el GA y su valor fitness
GA1DArrayAlleleGenome & g = (GA1DArrayAlleleGenome &)ga.statistics().bestIndividual();
int pesoTotal = capacidadMochila(g, g.length());
cout << "El GA encuentra:\n\t" << ga.statistics().bestIndividual() << "\n\n";
cout << "Mejor valor fitness es " << ga.statistics().maxEver() << "\n";
cout << "El peso alcanzado es " << pesoTotal << endl;
La funciones de inicializar, mutador, cruzador las dejo para que aquél que le interese las realice.Me ha quedado una publicación bastante extensa, pero quién sabe, a lo mejor a alguien le sirve.
Espero haberme explicado con claridad y haber creado algo de interés a aquella persona que lea esta entrada.
Saludos y ¡hasta la próxima!
