Descripción del algoritmo desarrollado
Los algoritmos genéticos son un tipo de algoritmos iterativos basados en poblaciones empleados habitualmente para la resolución de problemas de optimización. La iteración consiste en pasar de una población (conjunto de individuos) a otra (evolución) buscando que los individuos tengan mejores cualidades para el problema que se quiere resolver. En el caso de los algoritmos genéticos, para la evolución se usan operaciones inspiradas en la evolución biológica (mutación, cruce, selección…).
En este problema de agrupación de parcelas, un individuo se modeló como un conjunto de pares formados por parcelas y explotaciones, en que cada par representa la explotación que se haría cargo de la parcela. Es decir, un individuo representa una posible asignación de las explotaciones de cada parcela, y es, por lo tanto, una posible solución del problema.
Fases
Validación de los individuos (restricciones)
Resulta prácticamente imposible que el algoritmo mantenga exactamente la superficie gestionada por cada explotación. Hay que permitir un cierto margen de variación entre la superficie inicial y la superficie asignada después de la agrupación. En las pruebas realizadas se trabajó normalmente con un 10% de margen de variación. Cuanta mayor variación se permita, mejor será el resultado global de la agrupación, pero mayor será también la disminución de la superficie de algunas explotaciones, por lo que no debe ser demasiado grande. En lugar de comparar la superficie inicial con la final, el algoritmo también permite comparar la valoración de las parcelas de cada explotación. La valoración individual de cada parcela es un proceso previo a la ejecución del algoritmo.
Inclusión de parcelas de terceros
Pueden darse situaciones en las que a mayores de las parcelas ya trabajadas por cada explotación, existan otros propietarios que quieran ceder, mediante arrendamiento u otros mecanismos, sus parcelas no trabajadas para que sean aprovechadas por las explotaciones. (También podrían incluirse, por ejemplo, masas comunes gestionadas por el Banco de Terras). En estos casos, las explotaciones pasarían a tener, de media, más superficie de la que disponían inicialmente. El algoritmo permite contemplar estos casos de dos maneras:
- No limitando el crecimiento de una explotación (aplicación da variación máxima solo para los decrecimientos).
- Estableciendo a priori una superficie/valoración deseada para cada explotación, que puede ser proporcional a la superficie/valoración inicial de cada una, o bien, un valor acordado entre todos los participantes en el proceso.
Generación de la población inicial
Para obtener una población con diversidad y buenas propiedades de cara a la ejecución del algoritmo, se implementaron varios mecanismos de generación de la población inicial:
- Asignación de las parcelas a la explotación más próxima, ordenando la asignación por el valor de la parcela
- Asignación de las parcelas a la explotación más próxima, ordenando la asignación aleatoriamente
- Asignación de las parcelas en función de la relación valor/(distancia a la explotación)
- Fuerza bruta
- Combinación de varios métodos de generación
Mutación
Para a realización das mutacións tamén se implementaron varios mecanismos:
- Cambio aleatorio de explotación
- Intercambio de parcelas
- Intercambio de varios pares de parcelas
- Combinación de varios métodos de mutación
Evaluación de los individuos (fitness)
A la hora de medir la agrupación de un conjunto de parcelas de una explotación existen distintas posibilidades. En este caso se tuvieron en cuenta fundamentalmente tres tipos de funciones de medida, con varias variantes y combinaciones sobre ellas. En todos los casos, cuanto menor sea el valor, mejor es la solución (se modela como un problema de minimización). Las funciones son estas:
- Distancia de las parcelas a las explotaciones: consisten en medir la distancia, en línea recta, de cada parcela a su explotación (en lugar de distancia a la explotación puede ser cualquiera distancia a cualquiera otro punto que indique el interesado).
- Distancia entre las parcelas de cada explotación: consisten en medir la distancia, en línea recta, entre cada dos parcelas de una explotación (sin repeticiones).
- Número de parcelas: es el número total de parcelas. Solo tiene sentido aplicar esta función cuando se realiza la unión de las parcelas confinantes de un mismo propietario, tal y como se explica a continuación.
Unión de parcelas confinantes
Aunque este algoritmo no hace variar la forma de las parcelas (como si ocurre tradicionalmente en las concentraciones parcelarias), si que se suele ocurrir que dos parcelas confinantes inicialmente de distintas explotaciones pasen a ser de la misma explotación. En estos casos, teóricamente, pasarían a ser una única parcela. Para favorecer estos casos, durante la ejecución del algoritmo se permite la opción de realizar la unión geométrica de las parcelas confinantes de la misma a la explotación antes de evaluar un individuo mediante alguna de las funciones comentadas anteriormente. Así, aplicando esta unión y empleando funciones como el número de parcelas o total de distancias, se favorece reducir el número de parcelas de cada explotación. La parte negativa de la realización de la unión de parcelas es que hace que la evolución del algoritmo sea mucho más lenta.
Combinaciones de varias funciones. El algoritmo también permite combinar varias de las funciones comentadas, y aplicar distintos pesos a cada una delas.
Detección de estancamento
Durante la ejecución de este tipo de algoritmos es frecuente que se llegue a un punto donde la evolución se estanca durante un período de tiempo indefinido (el fitness no mejora). Aunque esto puede usarse como criterio para la finalización del algoritmo, para tentar mejor un poco más la solución, se implementó una opción que en el caso de estancamiento, regenera una parte de la población actual del algoritmo y continúa su ejecución. Esta generación de nuevos individuos se hace del mismo modo que a generación de la población inicial.
Parcelas fijas
Algunas explotaciones pueden tener parcelas ya suficientemente próximas que quieren conservar sin cambios. El algoritmo permite fijar estas parcelas, de modo que sigan perteneciendo a la misma explotación, pero, al mesmo tempo, permite tenerlas en cuenta a la de calcular el fitness de la solución (para que las nuevas parcelas asignadas tiendan a aproximarse también a estas parcelas prefijadas).
Paralelización
Aunque dependiendo del problema concreto, es habitual que los algoritmos genéticos tengan un alto coste computacional. En este caso, para acortar el tiempo de ejecución (reducir el tiempo que el algoritmo tarda en conseguir sus mejores valores) y mejorar los valores conseguidos, se realizó una implementación paralela que permite aprovechar al mismo tiempo todos los núcleos e hilos de ejecución de los que disponen los procesadores actuales. Se realizaron dos tipos de paralelización:
- Paralelización de la propia ejecución del algoritmo.
- Ejecución de varios algoritmos en paralelo con sincronización periódica.
Diseño extensible
Todo el algoritmo está diseñado para poder incorporar sin demasiada complicación nuevas estrategias de generación, mutación, evaluación…
Ejecución del algoritmo
El algoritmo está programado en Java, siendo, por lo tanto, multiplataforma. Para su ejecución se emplea la línea de comandos, indicando el fichero de configuración con las distintas opciones a emplear durante la ejecución del algoritmo. Se trata de un fichero de texto de tipo properties . Uno de los parámetros configurables es el tiempo de ejecución del algoritmo. En las ejecuciones realizadas sobre las zonas de prueba (las pruebas se realizaron en varios equipos procesador Intel Core TM de cuatro cores con hyperthreading), se observó que, en media, el algoritmo, tiende a estancarse tras varias horas de ejecución (4-5 horas), aunque la desviación sobre esta media es bastante alta. Por ejemplo, cuando se usa la unión de parcelas la ejecución es varios órdenes de magnitud más lenta.
Durante la ejecución, el usuario puede ver en el log del algoritmo como va evolucionando el valor do fitness. El algoritmo soporta varias órdenes, comandos o peticiones: generar un shape del mejor individuo obtenido hasta el momento para consultar sus características, y hacer una parada controlada, conservando el mejor individuo obtenido hasta ese momento.