Resumen:
El comportamiento que muestra un algoritmo evolutivo depende del balance entre la explotación local y la exploración global del espacio de búsqueda. Con el objetivo de mantener un equilibrio adecuado implementamos un algoritmo genético básico, analizamos métodos elitistas para mejorar el desempeño del algoritmo genético e incluimos un procedimiento para controlar automáticamente la diversidad poblacional. Para llevar a cabo este control proponemos una medida de dispersión poblacional que nos permite detectar prematuramente el problema de homogeneización en un óptimo local. Para obtener el valor de dispersión, y de esta manera conocer la diversidad poblacional, utilizamos el método de Sidaner, Bailleux y Chabrier que utiliza las distancias en torno a un punto medio, y le agregamos nuestra propuesta de disminuir el valor de dispersión ante la presencia de individuos repetidos. Luego desarrollamos un método para obtener la cota que le permite al algoritmo decidir y tomar acción automáticamente en caso de que se deba agregar diversidad. Cuando se decide aumentar la diversidad, se incrementa la tasa de mutación, lo cual hace más probable la aparición de nuevos individuos en la población. Presentamos un desarrollo teórico y los resultados de las ejecuciones del algoritmo genético binario básico y con control de diversidad programados en C++. Las corridas en problemas de prueba muestran que el número de generaciones para alcanzar el óptimo global es menor con control de diversidad. Finalmente demostramos que el algoritmo con control de diversidad converge con probabilidad 1 a un óptimo global.
Abstract:
The behavior of an evolutionary algorithm depends on the balance between local exploitation and global exploration of the search space. In order to keep the balance adequate we implemented a basic genetic algorithm, analyzed elitist methods to improve the genetic algorithm’s performance and included a procedure for automatic population diversity control. To perform this control we propose a population dispersion measure that allows early detection of the homogenization problem at a local optimum. In order to obtain the dispersion value and this way know the population diversity we use the method of Sidaner, Bailleux and Chabrier that uses the distances to a middle point and incorporate our proposal of lowering the dispersion in the presence of repeated individuals. Then we develop a method to obtain the bound that allows the algorithm to decide and automatically take action in case diversity must be increased. When this decision is made, the mutation rate is incremented, making it more probable that new individuals appear in the population. We introduce a theoretical development and the results of the basic binary genetic algorithm runs and those of the algorithm with diversity control implemented in C++. Test problems run show that the number of generations to reach a global optimum is lower with diversity control. Finally we prove that the algorithm with diversity control converges with probability 1 to a global optimum.
Citación:
---------- APA ----------
Di Rado, Alejandra; Podestá, Gabriela Laura. (2014). Algoritmos genéticos binarios con control de diversidad. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000719_DiRadoPodesta
---------- CHICAGO ----------
Di Rado, Alejandra; Podestá, Gabriela Laura. "Algoritmos genéticos binarios con control de diversidad". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2014.https://hdl.handle.net/20.500.12110/seminario_nCOM000719_DiRadoPodesta
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000719_DiRadoPodesta.pdf
Distrubución geográfica
