Algoritmos genéticos – demo versión 2

Debo decir dos cosas acerca de los algoritmos genéticos. Primero ¡están buenísimos!, una vez que te metés en tema resulta totalmente atrapante. Segundo: en la diversidad está la solución.

El video muestra una actualización de la demo. Esta actualización tiene cinco diferentes algoritmos de cruce (para crear descendencia) y cinco diferentes algoritmos de mutación. La aplicación permite seleccionar con cuales y cuantos algoritmos se quiere trabajar.

Los resultados son bastante elocuentes: cuanto más algoritmos utilizo, menor población inicial (y por consiguiente menor tiempo) necesitamos para resolver el problema. Cuanto más diversidad, más probabilidad de encontrar mejores soluciones.

En la primer demo, para 20 ciudades necesitábamos una población inicial de 1000 individuos y ahora (utilizando los 10 algoritmos juntos) con sólo 250 llegamos al mismo resultado y en forma mucho más veloz.

Ahora empezó la etapa de optimización y “emprolijamiento” de código, agregar algunas validaciones para los campos y demás.

¡Si se les ocurre alguna problemática para resolver con algoritmos genéticos avisen!

Algoritmos Genéticos – Mi primer demo

Finalmente puedo mostrar avances en mi aprendizaje de Algoritmos Genéticos. Luego de varias semanas de lectura y algunas pruebas me puse a construir mi primera aplicación.

Problema del Viajante

La aplicación busca una solución al problema del viajante. Elegí este problema porque es el más conocido para explicar algoritmos genéticos y además porque tiene características impactantes.

Tiene un enunciado muy simple: un viajante debe recorrer una cantidad dada de ciudades, ¿cuál es la ruta que pasa por todas las ciudades y que recorre la menor distancia?

Tienen una solución muy complicada: deberíamos calcular todas las rutas posibles y seleccionar la más corta. El problema es que para sólo 12 ciudades existen 479.001.600 rutas posibles. Si una computadora pudiera calcular la distancia de una ruta en un microsegundo (millonésima parte de un segundo) tardaría 3 segundos en resolver el problema para 10 ciudades, más de medio minuto para 11 y 777.146 años para 20 ciudades (fuente Wikipedia).

Mi implementación con Algoritmos Genéticos

Para crear descendencia, la aplicación elige un operador de cruce al azar. Hasta ahora sólo incluí tres: PMX (Correspondencia Parcial, Goldberg y Lingle, 1985), CX (Cruce basado en ciclos, Oliver y col., 1987) y OX1 (Cruce basado en orden, Davis, 1985).

Y sólo implementé un algoritmo de mutación: DM (basado en desplazamiento, Michalewizc, 1997).

Para mi sorpresa, los resultados son muy buenos incluso usando un solo algoritmo de cruce (cualquiera de ellos) y sin mutación.

Sobre la Demo

En la demo dispuse 20 ciudades en círculo (ya que es muy evidente cual es la mejor ruta), una población inicial de 1000 individuos, un máximo de 50 generaciones (aunque la solución la encuentra por la generación 35 aprox.), de cada generación se queda con el 25% “mejor adaptado”, y el 10% de la descendencia incluye alguna mutación.

La aplicación está construída en C# .NET 3.5 y la idea es agregar más algoritmos tanto de cruce como de mutación.

Exportar Microsoft Project día por día versión Office 2007 Español

Hace varios años publique un post sobre Exportar Microsoft Project día por día basado en Office 2003.

Este post es creado en respuesta a todos aquellos que me pidieron actualizar la macro para la versión 2007 de Office.

Cambios en las referencias

Esta es la principal diferencia con la versión Office 2003.

Cambios en el formulario de exportación

Aproveché y modifiqué el formulario para que Start Date sea la fecha de inicio configurada en el proyecto y End Date sea la fecha actual.

Descarga y tutorial de uso

Ya pueden descargar el archivos de Project 2007 con la macro para Exportar Microsoft Project día por día versión Office 2007. El mismo archivo explica como instalarla y utilizarla.

Para más datos y explicaciones técnicas pueden ver el post de la versión original.

Mantener viva una aplicación .NET en IIS con Web Scheduler Tasks

Web Scheduled Tasks en ASP.NET nos sirve para ejecutar tareas programadas cada determinado intervalo de tiempo. Está pensado para Aplicaciones Web alojadas en Hostings que no nos permiten acceder al servidor.

Pero para asegurarnos de que las tareas se ejecuten, debemos mantener “viva” la aplicación. Este se convierte entonces en la primer tarea a configurar en Web Scheduled Tasks.

WebRequestTask para Web Scheduled Tasks

Actualicé el sitio demo de Web Scheduled Tasks para incorporar un objeto IScheduleable cuya misión es mantener viva una aplicación a través de un WebRequest.

El código es muy sencillo y es el siguiente:

Lo que hace es tomar todas las entradas del Web.config cuyo “name” comience con “webRequest” y hace un request a la URL indicada en “value”. El sitio demo tiene la siguiente entrada en el Web.config:

<add key="webRequest01" value="http://localhost:38652/DemoScheduler/Default.aspx" />

Deberán modificar la URL. En mi PC, el sitio está en el puerto 38652, si el puerto es 80 no hay necesidad de indicarlo.

Web Scheduled Tasks en ASP.NET 2.0, 3.0, 3.5 y MVC

¿Cómo hacer para automatizar tareas en nuestro sitio Web si no tenemos acceso al servidor ni a los Scheduled Tasks?

Omar Al Zabir nos ofrece una solución muy creativa: utilizar el evento que genera un objeto al ser removido del caché. Aquí la solución de Omar.

Tomando la solución propuesta pero intentando convertirla en lo más portable y menos invasiva posible desarrolle el Web Scheduled Tasks para ASP.NET 2.0 o superior. Funciona también con MVC.

Cómo funciona Web Scheduled Tasks

Web Scheduled Tasks se inicia en el Application_Start del global.asax y crea una lista de objetos IScheduleable obteniendo los datos del web.config.

En el web.config se indica cada cuanto tiempo el Web Scheduled Tasks llamará a las tareas y lo único que les proveerá son los objetos Application y Cache ya que de otra forma no estarían disponibles. El Resto depende de la tarea: cuando ejecutarse, cómo controlar si ya se está ejecutando, log de errores, etc.

Las tareas se ejecutarán en un thread que no estará vinculado con un request de un usuario por lo que no se puede utilizar cosas como HttpContext.Current o Server.MapPath.

Implementar Web Scheduled Tasks en 4 pasos

Paso 1: copiar  WebScheduledTasks.dll en la carpeta BIN de nuestra Aplicación Web.

Paso 2: crear las clases que implementen IScheduleable. La interfaz es muy sencilla con un método y dos propiedades.

El método Run recibe el objeto Application y el objeto Cache ya que de otra forma serían inaccesibles.

Paso 3: configurar Web Scheduled Tasks a través del web.config. Para hacer esto utilicé el muy buen tutorial Creating Custom Configuration Sections in Web.config using .NET 2.0.

Son dos bloques. El primero hay que agregarlo dentro de <configSections> y define la nueva sección del Web.config y la clase que lo controla. El segundo va dentro de <configuration> y son los settings propios de Web Secheduled Tasks. El primer seteo es el intervalo que define cada cuantos minutos el sistema revisará las tareas para ejecutarlas.

Dentro de <tasks> están definidos los objetos que deben ejecutarse periódicamente. Debe colocarse el AssemblyQualifiedName, de otra forma no sabrá como instanciarlo. El AssemblyQualifiedName de mi tarea de ejemplo es "ActualizaHoraTask, App_Code.owmojsxy, Version=0.0.0.0, Culture=neutral, PublicKeyToken=null". Si no saben como armarlo, pueden ejecutar esto: Response.Write((new Objeto()).GetType.AssemblyQualifiedName).

Paso 4: modificar el Global.asax. Simplemente debemos agregar la siguiente línea al evento Application_Start: bd.WebScheduledTasks.Scheduler.RunTimer();

Cómo saber el estado de Web Scheduled Tasks

Scheduler expone la propiedad “Status” que devuelve un XML con el estado de Web Scheduled Tasks y las tareas.

En en XML se puede ver:

• StartTime: fecha y hora en que se inicializó Web Scheduled Tasks
• Interval: definido en el Web.config
• LastTickTime: hora a la que se ejecutó por última vez
• CacheTimerExist: muestra si existe el objeto en Cache que permite que todo funcione.
• LastError: en “object” veremos el objeto que generó el último error y en “error” su descripción.
• ScheduledTasks: veremos la lista de los objetos que invocará el sistema.

Además de Status, Scheduler expone el método “ScheduleTick” que nos permite, tal vez desde algún administrador, ejecutar las tareas programadas manualmente. En realidad lo que lograremos es “despertar” a Web Scheduled Tasks para que revise cuales tareas deben ser ejecutadas.

Descargar Web Scheduled Tasks

Pueden descargar:

• WebScheduledTasks.dll para copiarla a la carpeta BIN de sus sitios web.
• El sitio Web demo en ASP.NET 2.0 con Web Scheduled Tasks implementado. En este caso, el objeto IScheduleable simplemente actualiza la hora en una variable de Aplicación que es mostrada en la página inicial. También se ve un link a una página que nos muestra el Status de Web Scheduled Tasks.
• Código fuente de Web Scheduled Tasks.

Espero que les sea útil. Cualquier sugerencia, corrección, o aporte será más que bienvenido.