En esta oportunidad voy a desarrollar la idea de cómo podemos valernos de un algoritmo genético para calcular distintos horarios a partir de una serie de cursos disponibles.
Los objetivos son:
- Obtener uno o más horarios válidos
- Llevar todos los cursos posibles
- Cada curso puede dictarse mas de un dia a la semana
- Cada curso puede tener varios horarios para escoger
Primero vamos a repasar rápidamente lo que es un algoritmo genético.
Un algoritmo genético es aquel en el que los datos se representan por genes. A su vez los genes se organizan en estructuras llamadas genomas, que le dan cierto sentido a los datos. Los genomas interactúan entre sí para buscar la solución a un cierto problema dado.
En este ejemplo vamos a hacer uso de un algoritmo genético y evolutivo. En otras palabras, los genomas irán evolucionando para llegar a la solución buscada.
La parte principal de nuestro algoritmo es la siguiente:
public void EjecutarCiclo()
{
List<CGenoma> nuevaPoblacion = new List<CGenoma>();
while (nuevaPoblacion.Count < LongitudPoblacion)
{
CGenoma padre = Seleccionar();
CGenoma madre = Seleccionar();
CGenoma hijo1;
CGenoma hijo2;
RealizarCruce(padre, madre, out hijo1, out hijo2);
hijo1 = Mutacion(hijo1);
hijo2 = Mutacion(hijo2);
nuevaPoblacion.Add(hijo1);
nuevaPoblacion.Add(hijo2);
}
ListaPoblacion = nuevaPoblacion;
ActualizarFitness();
}
Si podemos entender esa pequeña sección de código, lo tendremos casi todo.
El algoritmo se basa en la creación de nuevas poblaciones a partir de los genomas existentes. Para obtener nuevos “hijos”, se selecciona un padre, una madre y se realiza el cruce. El padre y la madre deben ser cuidadosamente seleccionados: no es una selección al azar. Una vez que tenemos dos nuevos hijos, se da paso a la mutación (aunque procuraremos que su efecto sea mínimo). Esto se repite una y otra vez, hasta obtener una solución.
La mala noticia es que no se puede garantizar una solución. La buena es que este algoritmo puede obtener soluciones que normalmente escapan a los cálculos humanos.
Ya hemos visto la parte principal. Pero para poderla utilizar, antes necesitamos una población inicial:
public void GenerarPoblacionInicial()
{
ListaPoblacion = new List<CGenoma>();
while (ListaPoblacion.Count < LongitudPoblacion)
{
CGenoma genoma = new CGenoma();
foreach (CCurso curso in Data.ListaCursos)
{
genoma.ListaGenes.Add(new CGen(curso.Id, curso.ObtenerIdHorarioAlAzar()));
}
ListaPoblacion.Add(genoma);
}
ActualizarFitness();
}
Ahora se hace evidente que existe una relación entre nuestros datos y los genes cada genoma. Los genes son muy dependientes de cada problema analizado. Para el presente caso, un gen representa la información: Curso-Horario.
Los genomas son siempre listas de genes. En este caso un genoma tendrá la estructura:
- genoma: gen1, gen2, gen3…, genN
O, lo que es lo mismo:
- genoma: Curso1-Horario1, Curso2-Horario2, Curso3-Horario3…, CursoN-HorarioN
La estructura de la clase genoma es la siguiente:
public class CGenoma
{
public List<CGen> ListaGenes;
public double Fitness;
public CGenoma()
{
ListaGenes = new List<CGen>();
Fitness = 0;
}
internal void CalculaFitness(int PeorPuntaje, CTestData pData)
{
int total = 0;
Fitness = 1 - ((double)total / (double)PeorPuntaje);
}
public void Render(Graphics Canvas, int x, int y, CTestData pData)
{
}
}
La clase genoma se compone simplemente de una lista de genes, una función para calcular el Fitness y un método para representar al genoma de forma gráfica (dibujar el horario en pantalla, vamos).
Probablemente esto del Fitness sea lo más difícil de entender, y también lo mas delicado, por lo que le dedicaré mayor espacio en la siguiente publicación. Sólo adelanto que el fitness de un genoma es un valor float entre 0 y 1 y sirve para indicar la “utilidad” de un genoma. Si el fitness se acerca a 1, el genoma es “bueno”, si se acerca a 0, es “malo”.
Por ahora veamos que contiene cada gen dentro de nuestro genoma:
public class CGen
{
public int Curso;
public int Horario;
public CGen(int pCurso, int pHorario)
{
Curso = pCurso;
Horario = pHorario;
}
}
Como podemos ver, el gen es bastante simple para este problema.
En la mayoría de implementaciones de algoritmos genéticos que se pueden encontrar por la web, pareciera ser necesario que tanto el gen, como el genoma, sean representaciones de cadenas con ceros y unos. Eso no es necesario y no lo verán en este ejemplo. La ventaja de utilizar ceros y unos es que con ellos es más fácil realizar operaciones genéticas (cruces, mutaciones, selecciones). Pero presentan la desventaja de que hay que codificar y decodificar los genes para poder llegar a los datos.
Próximamente continuaremos con la implementación de este algoritmo.
¡Hasta pronto!
Posted on febrero 20, 2011
0