Hosting por dinahosting.

Desenvolvemento da ferramenta informática

Descrición do algoritmo desenvolvido

Os algoritmos xenéticos son un tipo de algoritmos iterativos baseados en poboacións empregados habitualmente para a resolución de problemas de optimización. A iteración consiste en pasar dunha poboación (conxunto de individuos) a outra (evolución) buscando que os individuos teñan mellores cualidades para o problema que se quere resolver. No caso dos algoritmos xenéticos, para a evolución úsanse operacións inspiradas na evolución biolóxica (mutación, cruce, selección…).

Neste problema de agrupación de parcelas, un individuo modelouse como un conxunto de pares formados por parcelas e explotacións, no que cada par representa a explotación que se faría cargo da parcela. É dicir, un individuo representa unha posible asignación das explotacións de cada parcela, e é, polo tanto, unha posible solución do problema.

Fases

Validación dos individuos (restricións)

Resulta practicamente imposible que o algoritmo manteña exactamente a superficie xestionada por cada explotación. Hai que permitir un certo marxe de variación entre a superficie inicial e a superficie asignada despois da agrupación. Nas probas realizadas traballouse normalmente cun 10% de marxe de variación. Canta maior variación se permita, mellor será o resultado global da agrupación, pero maior será tamén a mingua da superficie dalgunhas explotacións, polo que non debe ser demasiado grande. En lugar de comparar a superficie inicial coa final, o algoritmo tamén permite comparar a valoración das parcelas de cada explotación. A valoración individual de cada parcela é un proceso previo á execución do algoritmo.

Inclusión de parcelas de terceiros

Poden darse situacións nas que a maiores das parcelas xa traballadas por cada explotación, existan outros propietarios que queiran ceder, mediante arrendamento ou outros mecanismos, as súas parcelas non traballadas para que sexan aproveitadas polas explotacións. (Tamén poderían incluírse, por exemplo, masas comúns xestionadas polo Banco de Terras). Nestes casos, as explotacións pasarían a ter, en media, mais superficie da que dispoñían inicialmente. O algoritmo permite contemplar estes casos de dúas maneiras:

  • Non limitando o crecemento dunha explotación (aplicación da variación máxima só para os decrecementos).
  • Establecendo a priori unha superficie/valoración desexada para cada explotación, que pode ser proporcional á superficie/valoración inicial de cada unha, ou ben, un valor acordado entre todos os participantes no proceso.

Xeración da poboación inicial

Para obter unha poboación con diversidade e boas propiedades de cara á execución do algoritmo, implementaronse varios mecanismos de xeración da poboación inicial:

  • Asignación das parcelas á explotación máis próxima, ordenando a asignación polo valor da parcela.
  • Asignación das parcelas á explotación máis próxima, ordenando a asignación aleatoriamente.
  • Asignación das parcelas en función da relación valor/(distancia á explotación)
  • Forza bruta
  • Combinación de varios métodos de xeració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

Avaliación dos individuos (fitness)

Á hora de medir a agrupación dun conxunto de parcelas dunha explotación existen distintas posibilidades. Neste caso tivéronse en conta fundamentalmente tres tipos de funcións de medida, con varias variantes e combinacións sobre elas. En todos os casos, canto menor sexa o valor, mellor é a solución (modelase como un problema de minimización). As funcións son estas:

  • Distancia das parcelas ás explotacións: consisten en medir a distancia, en liña recta, de cada parcela á súa explotación (en lugar de distancia á explotación pode ser calquera distancia a calquera outro punto que indique o interesado).
  • Distancia entre as parcelas de cada explotación: consisten en medir a distancia, en liña recta, entre cada dúas parcelas dunha explotación (sen repeticións).
  • Número de parcelas: é o número total de parcelas. Só ten sentido aplicar esta función cando se realiza a unión das parcelas confinantes dun mesmo propietario, tal e como se explica a continuación.

Unión de parcelas confinantes

Aínda que este algoritmo non fai variar a forma das parcelas (como si ocorre tradicionalmente nas concentracións parcelarias), si que se soe ocorrer que dúas parcelas confinantes inicialmente de distintas explotacións pasen a ser da mesma explotación. Nestes casos, teoricamente, pasarían a ser unha única parcela. Para favorecer estes casos, durante a execución do algoritmo permítese a opción de realizar a unión xeometrica das parcelas confinantes da mesma a explotación antes de avaliar un individuo mediante algunha das funcións comentadas anteriormente. Así, aplicando esta unión e empregando funcións como o número de parcelas ou total de distancias, favorecese reducir o número de parcelas de cada explotación. A parte negativa da realización da unión de parcelas é que fai que a evolución do algoritmo sexa moito máis lenta.

Combinacións de varias funcións. O algoritmo tamén permite combinar varias das funcións comentadas, e aplicar distintos pesos a cada unha delas.

Detección de estancamento

Durante a execución deste tipo de algoritmos é frecuente que se chegue a un punto onde a evolución se estanca durante un período de tempo indefinido (o fitness non mellora). Aínda que isto pode usarse como criterio para a finalización do algoritmo, para tentar mellor un pouco máis a solución, implementouse unha opción que no caso de estancamento, rexera unha parte da poboación actual do algoritmo e continúa a súa execución. Esta xeración de novos individuos faise do mesmo modo que a xeración da poboación inicial.

Parcelas fixas

Algunhas explotacións poden ter pacelas xa suficientemente próximas que queren conservar sen cambios. O algoritmo permite fixar estas parcelas, de modo que sigan pertencendo a mesma explotación, pero, ao mesmo tempo, permite telas en conta á de calcular o fitness da solución (para que as novas parcelas asignadas tendan a aproximarse tamén a estas parcelas prefixadas).

Paralelización

Aínda que depende do problema concreto, é habitual que os algoritmos xenéticos teñan un alto custe computacional. Neste caso, para acurtar o tempo de execución (reducir o tempo que o algoritmo tarda en acadar os seus mellores valores) e mellorar os valores acadados, realizouse unha implementación paralela que permite aproveitar ao mesmo tempo todos os núcleos e fíos de execución dos que dispoñen os procesadores actuais. Realizáronse dous tipos de paralelización:

  • Paralelización da propia execución do algoritmo.
  • Execución de varios algoritmos en paralelo con sincronización periódica.

Deseño extensible

Todo o algoritmo esta deseñado para poder incorporar sen demasiada complicación novas estratexias de xeración, mutación, avaliación…

Execución do algoritmo

O algoritmo está programado en Java, sendo, polo tanto, multiplataforma. Para a súa execución empregase a liña de comandos, indicando o ficheiro de configuración coas distintas opcións a empregar durante a execución do algoritmo. Trátase dun ficheiro de texto de tipo properties . Un dos parámetros configurables é o tempo de execución do algoritmo. Nas execucións realizadas sobre as zonas de proba (as probas realizáronse en varios equipos procesador Intel Core TM de catro cores con hyperthreading), observouse que, en media, o algoritmo, tenden a estancarse tras varias horas de execución (4-5 horas), aínda que a desviación sobre esta media é bastante alta. Por exemplo, cando se usa a unión de parcelas a execución é varios ordes de magnitude máis lenta.

Durante a execución, o usuario pode ver no log do algoritmo como vai evolucionando o valor do fitness. O algoritmo soporta varias ordes, comandos ou peticións: xerar un shape do mellor individuo obtido ata a momento para consultar as súas características, e facer unha parada controlada, conservando o mellor individuo obtido ata ese momento.