Descubrimiento de reglas de asociación en bases de datos grandes mediante técnicas metaheurísticas distribuidas

El 5/9/2016 en el SIO (Simposio de Investigación Operativa) de las 45 JAIIO tuve el gusto de exponer este trabajo sobre ARM/KDD con algoritmos genéticos distribuidos basado en Scala, Apache Spark, Apache Drill y Apache Parquet.

Dejo la exposición disponible aquí:Descubrimiento de reglas de asociación

 

Anuncios

44 JAIIO 2015

El martes 01/09/2015 pudimos exponer en el marco del simposio SIO (Simposio Argentino de Investigación Operativa) de las JAIIO 2015, tal como se refleja en el programa, un extracto de nuestro trabajo: hadoop.

El congreso se llevó a cabo en la ciudad de Rosario, en la llamada “Siberia” (Ciudad Universitaria de la UNR), en donde hubo muy buenas ponencias, cursos, seminarios, etc.

IMG-20150901-WA0000

 

¿Cómo es el control de un sistema de potencia?

Esta pregunta puede sonar básica para un ingeniero del área eléctrica… Pero no para el resto (de los ingenieros y de los mortales). Es por eso que conviene revisar los conceptos básicos.

La representación de la potencia demandada por un sistema eléctrico en función de la hora del día (dentro de un día calendario) es llamada curva de carga diaria. Independientemente del sistema, la región y la época, hay una característica común en todas las curvas de carga diaria: sus puntas, llanos y valles, tal cómo se ve a continuación:

Curva de Carga diaria de un sistema convencional de potencia.

Curva de Carga diaria de un sistema convencional de potencia.

Presentada esta disposición horaria de la demanda, conviene recordar ciertas características de las centrales generadoras, o más bien, de la tecnología de las centrales generadoras:

  • Las grandes centrales generadoras son poco regulables1.
  • Los grupos generadores térmicos más importantes, así como, las centrales nucleares son centrales grandes.
  • Por tanto las grandes centrales térmicas y nucleares (que son térmicas, claro) son poco regulables y no pueden seguir la evolución de la curva de carga diaria.
  • No existe una tecnología económicamente viable para almacenar gran capacidad de energía para ser utilizada en otro momento.
  • Estas restricciones obligan al estudio de la previsión de la demanda, a largo plazo y a corto plazo.
  • Siempre es necesario contar con generación de reserva, para determinar cuáles son los márgenes seguros de reserva primaria y secundaria se encaran estudios de vulnerabilidad del sistema.
  • La selección de las máquinas que trabajan juntas en un momento del tiempo va a depender de:
    • Factores Económicos:
      • Costo de Combustibles
      • Costo de Mantenimiento
      • Costo de Arranque
      • Costo de Parada
    • Aspectos técnicos
      • Características de regulación
      • Limites de estabilidad

Un estudio más minucioso de la situación, arroja como conclusión que cada tipo de tecnología tendrá una zona o régimen de carga dentro de la curva de carga en donde será más útil:

  • Base: Será atendida por máquinas de regulación lenta, cuya potencia será relativamente constante y que produce grandes cantidades de energía eléctrica (nucleares y grandes grupos térmicos)
  • Exceso de demanda sobre la carga base: Atendido por máquinas más regulables como las hidroeléctricas, o las centrales térmicas de potencia media, como las TG (gas) o TV (vapor).
  • Punta: Máquinas cuya regulación y arranque sean muy rápidos como las pequeñas hidroeléctricas y algunas TG. La potencia que entregan estas suele ser menor a las anteriores.

Notas:

1 – El término “regulables” se refiere a la capacidad que tiene una máquina generadora independientemente de su tecnología para colocarse en sincronismo con el sistema de generación. Son más regulables mientras menos tiempo tardan en acoplarse al sistema.

Bibliografía:

“Tecnología Eléctrica” – 2da Edición ampliada y revisada – Ramón María Mujal Rosas

“Operación del sistema de generación” – Francisco D. Gagliana y Antonio J. Conejo

El problema del Despacho Económico Básico en un sistema de Energía Eléctrica

Se trata de uno de los problemas fundamentales de la operación de un sistema de energía eléctrica. Visto desde muy arriba, un sistema eléctrico es un sube y baja en donde en una punta están los consumidores de energía eléctrica y, en la otra punta, están los generadores de la misma. Por tanto, este problema consiste en repartir la demanda de energía eléctrica entre los generadores disponibles con un costo total de generación mínimo. Se trata de un problema de optimización, en particular de minimización.

Claro está que este es el problema básico, y que el enfoque puede ser muy superficial, ya que la minimización de un costo (el adjetivo “económico” en el título) alude un criterio económico exclusivamente. Pero la economía no puede estar desconectada de la política, y hablamos de una ciencia social, no de una ciencia exacta… Probablemente si optimizáramos el costo a como diere lugar, probablemente llegaríamos a la conclusión de que nos conviene inundar ciudades, emitir dióxido de carbono a la atmósfera de manera descontrolada y otros desmanes que están fuera del alcance de este artículo.

Supongamos que cada generador, cada máquina en particular, tiene asociada una función Costo que vincula la cantidad de potencia (generalmente medida en MW) y el costo de producción de dicha potencia por unidad de tiempo (en $/h).

En generación térmica, la función Costo se deriva de la curva de consumo específico asociada a cada máquina. En el caso de la generación hidroeléctrica se deriva de una función que relaciona el caudal de agua turbinada con la potencia generada.

Por tanto el costo general de producción de un sistema de energía eléctrica se expresa de la siguiente manera:

C(P_g) = \sum\limits_{i=1}^n C_i(P_{gi})

Dado que el sistema físicamente está en equilibrio (un sube y baja muy aburrido), la potencia total generada debe ser igual a la demanda total más las pérdidas (por transporte y distribución):

\sum\limits_{i=1}^n P_gi = P_d + P_p

Finalmente la minimización de C(P_g) debe estar sujeta al equilibrio de potencias descripto arriba, y a los límites de producción de cada máquina:

P_{gi}^{min} \le P_{gi} \le P_{gi}^{max}

Conclusiones de Paralelizar GA con MPI

Habiendo implementado un algoritmo genético simple (en particular una minimización de la función valle de Rosenbrock) con el fin de utilizarlo como benchmark, puedo destacar ciertas conclusiones.

El método de paralelización utilizado fue el básico para estos casos, es decir, el monolítico en términos de algoritmos genéticos, o sea, es decir existirá una sola población global que evoluciona. Este mecanismo no es el mejor desde el punto de vista del paralelismo, pero la intención es utilizarlo como benchmark, por lo que pude relajar la exigencia.

Las operaciones que se paralelizaron fueron:

  • Evaluación del Fitness
  • Crossover y Mutación

Mientras que las operaciones que quedaron seriales fueron:

  • Inicialización
  • Selección

No se utilizó una condición de optimalidad, ya que la idea fue implementar algo comparativo, por lo que se forzó siempre la ejecución de 100.000 generaciones, aunque en la mayoría de los casos, antes de las 2.000 generaciones se había alcanzado un valor más que aceptable.

Por otro lado, dado que la representación para los cromosomas fue la clásica tira de bits, no se representó un contínuo, sino una discretización del mismo, quedando excluido el punto en donde se halla el mínimo global de la función (1,1). De esta manera el algoritmo explora una franja con forma de banana que se da en la representación tridimensional de la función donde se encuentran los valores mínimos de la misma.

Por tanto debe quedar claro que el objetivo no fue optimizar la función de Rosenbrock, sino implementar un algoritmo genético paralelo comparable con fines de benchmark.

La parametrización de las corridas ha sido la siguiente:

POBLACION_SIZE 200
MAX_GENERACIONES 100000
CROSSOVER_PROBABILITY 0,65
MUTATION_PROBABILITY 0,035

El resultado arrojado por la versión serial en un dual core (2Ghz) con 2Gb RAM fue:

Operación Tiempo en ms %
Inicializacion 0 0,00%
Computo del Fitness 728085 78,69%
Operaciones Geneticas (Cross+Mut+Reempl) 191311 20,68%
Seleccion 5880 0,64%
925276

Cabe destacar que una corrida serial en un procesador i7 con 8Gb de RAM toma 70 segundos (aproximadamente el 8% respecto a la corrida descripta).

Las corridas paralelas han arrojado los siguientes resultados:

Nodos Workers Tiempo Total Inicializacion Computo del Fitness Operaciones Geneticas Seleccion
1 0 925276 0 728085 191311 5880
2 1 457484 0,077 347019 104263 6085
3 2 548708 0,082 349236 192929 6432
4 3 502676 0,082 318536 177568 6458
5 4 489597 0,081 288175 194847 6445
6 5 494720 0,116 281966 206180 6464
7 6 349025 0,082 206147 136326 6432
8 7 349025 0,082 206147 136326 6432
9 8 294204 0,077 171204 116748 6137
10 9 286247 0,077 162048 117613 6471
11 10 407975 0,078 236078 165234 6494
12 11 468207 0,078 267160 194435 6449
13 12 582009 0,078 340445 234938 6439

TiemposPorWorker

Con respecto a los tiempos de las operaciones genéticas en paralelo vemos que no se evidencia un incremento en la performance que sea beneficioso en términos reales. Esto puede deberse a que las operaciones genéticas, en este caso, son operaciones a nivel de bits, que suelen ser sumamente eficientes a nivel de procesamiento; y que, por otro lado, implican una transferencia de datos importantes: se envían 2 individuos (en este caso cabe recordar que cada individuo consiste en un arreglo de 13 bytes) y se devuelven 2 individuos, por tanto cada operación implica una transferencia de 52 bytes entre master y worker. Por tanto, la mejora en términos de procesamiento no compite con el consumo de recursos de red provocado por esta estrategia.

En cambio, en la evaluación del fitness se da otro escenario, favorable al paralelismo. En este caso, por cada individuo se envían 13 bytes y se reciben 4 bytes. En esta operación, el consumo de CPU tiene un peso más significativo que el overhead provocado por la utilización de la red (hasta cierto punto). Con la presente configuración, se encontró un mínimo tiempo de procesamiento con 10 nodos (9 workers) para la evaluación del fitness, como para el tiempo global, de una magnitud de 4,5 y 3,23 veces respectivamente.

Como conclusión general se puede extraer:

  • En GA simples, las operaciones genéticas consumen poco procesador respecto al consumo de red de enviar 2 individuos y recibir otros dos individuos.
  • La operación que más fácilmente se paraleliza es el cálculo del fitness.
  • La paralelización es muy sensible a los parámetros: Cambiará mucho si el tamaño del individuo se multiplica por 100 (vuelva totalmente inviable la paralelización de las operaciones genéticas), o si el tamaño de la población se multiplica, podríamos empezar a obtener buenos resultados paralelizando las operaciones genéticas. Otro dato sensible es el consumo de procesador durante la evaluación del fitness. Si este consumo se multiplica por 100, el rendimiento del paralelismo incrementará, dado que es la función más fácilmente paralelizable.
  • El ancho de banda es un impedimento para la escalabilidad de la solución en paralelo con MPI (GA simple y monolítico). Más aún si el GA consume o genera datos centralizados.

Implementación Serial de la función de Rosenbrock en ANSI-C

Con el fin de tener un benchmark serial disponible, hice una implementación de un algoritmo genético simple (con algunos parámetros ajustables) de la minimización de la función de Rosenbrock. La dejo subida aquí.

El desempeño es muy bueno, la voy a usar como referencia para estudiar el speed up de las versiones paralelizables, en principio en MPI, más luego en otras plataformas. Acepto sugerencias de optimización del código, ya que la idea para medir speed up es utilizar la mejor versión existente del problema.

Dado que va a ser utilizada como benchmark no utilicé un corte de procesamiento en el caso de llegar a un óptimo global (si es que se puede conocer), ya que no estaría comparando una misma cantidad de iteraciones, cosa que puede ser muy útil.

La salida de una corrida se ve así:

 Fitness del mejor individuo generacion 0 = 4998.768001 [x=1.013442  y=0.916077]
 Fitness del mejor individuo generacion 5 = 4999.850536 [x=1.364238  y=1.874105]
 Fitness del mejor individuo generacion 56 = 4999.945572 [x=0.786639  y=0.609365]
 Fitness del mejor individuo generacion 90 = 4999.993030 [x=1.011555  y=1.014976]
 Fitness del mejor individuo generacion 257 = 4999.995249 [x=1.023401  y=1.040867]
 Fitness del mejor individuo generacion 290 = 4999.996838 [x=1.001817  y=1.009258]
 Fitness del mejor individuo generacion 671 = 4999.997794 [x=1.039652  y=1.078359]
 Fitness del mejor individuo generacion 891 = 4999.999793 [x=0.988134  y=0.975593]
 Fitness del mejor individuo generacion 20930 = 4999.999837 [x=1.002684  y=1.006624]
 Fitness del mejor individuo generacion 21727 = 4999.999890 [x=0.990997  y=0.981535]
 Fitness del mejor individuo generacion 52676 = 4999.999977 [x=1.001246  y=1.002026]
 Fitness del mejor individuo generacion 52678 = 4999.999977 [x=1.001244  y=1.002026]
 Fitness del mejor individuo generacion 128817 = 4999.999993 [x=0.997415  y=0.994781]
 Fitness del mejor individuo generacion 253474 = 4999.999996 [x=0.998250  y=0.996419]
 Fitness del mejor individuo generacion 547343 = 4999.999997 [x=0.998733  y=0.997576]
 Fitness del mejor individuo generacion 959670 = 4999.999999 [x=0.999087  y=0.998105]

Llegó a una diferencia menor a 10-6 en la función objetivo, y a una distancia menor a 10-3 en el plano de la función, lo que es muy positivo en una exploración discreta (la representación es del algoritmo genético simple, es decir, un arreglo de bits).