lunes, 8 de julio de 2013

Adapatación del tamaño de la población

Cuando se habla de algoritmos genéticos, se debe hacer una referencia obligada a la obra de John Holland quien en el año 1975, en el libro titulado “Adaptación en sistemas naturales y artificiales”, asienta las bases para un acelerado desarrollo ulterior hasta llegar a lo que se conoce como algoritmos genéticos. Un algoritmo genético es un método de búsqueda que imita la teoría de la evolución biológica de Darwin para la resolución de problemas. Para ello, se parte de una población inicial de la cual se seleccionan los individuos más capacitados para luego reproducirlos y mutarlos para finalmente obtener la siguiente generación de individuos que estarán más adaptados que la anterior generación. En palabras de los investigadores Arranz de la Peña y Parra Truyol, en el artículo escrito el año 2007 titulado “Algoritmos genéticos”, para el estudio de este tipo de algoritmos se debe tener en cuenta una serie de parámetros: (1) Tamaño de la población. Este parámetro indica el número de cromosomas que se tiene en una población para una generación determinada. En caso de que esta medida sea insuficiente, el algoritmo genético tiene pocas posibilidades de realizar reproducciones con lo que se realizaría una búsqueda de soluciones escasa y poco óptima. Por otro lado si la población es excesiva, el algoritmo genético será excesivamente lento. De hecho estudios revelan que hay un límite a partir del cual es ineficiente elevar el tamaño de la población puesto que no se consigue una mayor velocidad en la resolución del problema. (2) Probabilidad de apareamiento. Indica la frecuencia con la que se producen apareamientos entre los cromosomas padre es decir, que haya probabilidad de reproducción entre ellos. En caso de que no exista probabilidad de reproducción, los hijos serán copias exactas se los padres. En caso de haberla, los hijos tendrán partes de los cromosomas de los padres. Si la probabilidad de cruce es del cien por ciento, el hijo se crea totalmente por apareamiento, no por partes. (3) Probabilidad de mutación. Indica la frecuencia con la que los genes de un cromosoma son mutados. Si no hay mutación, los descendientes son los mismos que había tras la reproducción. En caso de que haya mutaciones, parte del cromosoma descendiente es modificado y si la probabilidad de mutación es del cien por ciento, la totalidad del cromosoma se cambia. En este caso, no se cambian simplemente unos bits del cromosoma sino que se cambian todos, lo que significa que se produce una inversión en el cromosoma y no una mutación por lo que la población degenera muy rápidamente. Como se muestra en el párrafo precedente, el parámetro tamaño de la población es uno de los parámetros necesarios para la ejecución de un algoritmo genético, este parámetro determina el tamaño de la población que el algoritmo utilizará para cada una de sus iteraciones, algunos estudios han demostrado que el utilizar un rango de cincuenta a cien individuos para problemas de baja complejidad es adecuado, pero el tamaño de la población depende de la complejidad del problema, si la población es demasiado pequeña el algoritmo converge hacia pobres soluciones, en caso contrario el algoritmo consume recursos de procesamiento muy altos. Según Cantor, en la tesis de magister escrita el año 2009 titulada “Adaptación del tamaño de la población en los algoritmos genéticos”, el costo computacional de evaluar la función de aptitud de una población es uno de los principales factores a tener en cuenta, cuando se requiere configurar el tamaño de la población. Algunos usuarios de algoritmos genéticos desconocen este factor y configuran tamaños de la población extremadamente elevados sin prestar mayor importancia a este proceso, pero cuando se vean enfrentados a problemas donde la evaluación de la función de aptitud de un individuo es moderadamente alta, se percatan que evaluar en cada iteración la aptitud de una población de gran tamaño, se puede convertir en una tarea de nunca acabar. Por esta razón algunos investigadores evalúan técnicas donde se puedan obtener los beneficios de grandes poblaciones en poblaciones reducidas, uno de los principales beneficios a rescatar es la diversidad de la población.

No hay comentarios:

Publicar un comentario en la entrada