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.
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.
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:
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:
Para a realización das mutacións tamén se implementaron varios mecanismos:
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:
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.
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.
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).
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:
Todo el algoritmo está diseñado para poder incorporar sin demasiada complicación nuevas estrategias de generación, mutación, evaluación…
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.