"Hello World!" un ejemplo de Algoritmo Genetico (Generation5.org)
- Artículo original: A "Hello World!" Genetic Algorithm Example
- Autor: James Matthews
- Traductor: Year of the Dragon
Alguien en el fórum de Generation5 preguntó por un programa "Hello World!" para algoritmos genéticos. Me lo tomé de forma literal y creé un programa muy simple (138 lineas de código) que evoluciona la frase "Hello World!"
Aquí podéis ver algunos ejemplos de la salida (se muestran el mejor miembro de la población y el número de adecuación):
Best: IQQte=Ygqem# (152)
Best: Crmt`!qrya+6 (148)
Best: 8ufxp+Rigfm* (140)
Best: b`hpf"woljh[ (120)
Best: b`hpf"woljh4 (81)
Best: b`hpf"woljh" (63)
Best: Kdoit!wnsk_! (24)
Best: Kdoit!wnsk_! (24)
Best: Idoit!wnsk_! (22)
Best: Idoit!wnsk_! (22)
Best: Idoit!wnsk_! (22)
Best: Idoit!wnsk_! (22)
Best: Ifknm!vkrlf? (17)
Best: Ifknm!vkrlf? (17)
Best: Gfnio!wnskd$ (14)
Best: Ffnjo!wnskd$ (14)
Best: Hflio!wnskd$ (11)
Best: Hflio!wnskd$ (11)
Best: Kflkn wosld" (8)
Best: Ifmmo workd" (6)
Best: Hfljo wosld" (5)
Best: Hflmo workd" (4)
Best: Hflmo workd" (4)
Best: Hflmo workd" (4)
Best: Iflmo world! (3)
Best: Iflmo world! (3)
Best: Hflmo world! (2)
Best: Hflmo world! (2)
Best: Hflko world! (2)
Best: Hflko world! (2)
Best: Hdllo world! (1)
Best: Hfllo world! (1)
Best: Hfllo world! (1)
Best: Helko world! (1)
Best: Hfllo world! (1)
Best: Hfllo world! (1)
Best: Hfllo world! (1)
Best: Hello world! (0)
Algoritmo Genético
El GA tiene las siguientes características:
| Tamaño población: | 2048 |
| Mutación (%): | 25 |
| Elitismo (%): | 10 |
Hay unas cuantas cosas a comentar sobre el código. Primero, hicimos algo de trampas al establecer el tamaño de las cadenas en la población del GA al hacerlo del mismo tamaño que la cadena buscada. Esto hace el código más fácil de entender. Segundo, la clase STL contenedora vector se usa para almacener los detalles del GA - esto también hace la ordenación muy eficiente y simple de implementar. Finalmente, el programa usa dos arrays para almacenar la población - uno para la población actual, y otro para el buffer que contiene la siguiente generación. Al final de cada generación, los punteros son intercambiados para optimizar la velocidad.
Función de adecuación
Finalmente, un rápido vistazo a la función de adecuación:
void calc_fitness(ga_vector &population)
{
string target = GA_TARGET;
int tsize = target.size();
unsigned int fitness;
for (int i=0; i<GA_POPSIZE; i++) {
fitness = 0;
for (int j=0; j<tsize; j++) {
fitness += abs(int(population[i].str[j] - target[j]));
}
population[i].fitness = fitness;
}
}
Básicamente, todo lo que hace es comparar cada miembro de la población con la cadena buscada. Añade las diferencias entre los caracteres y usa la suma acumulada como el valor de aducación (por lo tanto, a más bajo el valor, mejor).
Conclusión
Con algo de suerte este pequeño programa servirá como un decente ejemplo a como de simple un GA puede ser para un problema de búsqueda. Este GA no es el más eficiente, aunque el uso de STL ayuda. Con algo de suerte el código será compatible con ANSI aunque sólo lo he probado con Visual C++ 6.0.
