Canvas de HTML5 y KineticJS

Hace unas semanas empecé a leer cosas sobre HTML5 y JavaScript (JS) para algo que tenía que desarrollar. Comencé a buscar documentación por la red sobre HTML5, información sobre la etiqueta <canvas> y más documentación sobre JavaScript.

Al empezar no tenía ni idea de por donde "meterle mano" al asunto, así que empecé por leer sobre la sintaxis de JS. Encontré esta página W3Schools, en dicha página se explicaba todo muy detalladamente y con ejemplos que además puedes modificar tú mismo y ver que cambios produce. Me vino muy bien, pero solo para adquirir los conocimientos básicos sobre este lenguaje interpretado. A continuación empecé a buscar información sobre como manipular el canvas que ofrece la última versión del lenguaje básico de la web, HTML5 (en el enlace podéis encontrar algo de información interesante) y me encontré con una API bastante simple y reducida (aquí podéis encontrarla), así que seguí buscando un poco más por la web en busca de algun entorno de desarrollo gráfico que automatizase un poco más el desarrollo del código.

Finalmente encontré una librería JS bastante interesante. KineticJS se hace llamar y proporciona un manejo del canvas mucho más fluido, dinámico y comprensible a posibles futuros lectores del código. Esta librería es gratuita y se puede descargar desde la propia página principal. Actualmente su creador, Eric Rowell, sigue actualizando de manera regular la librería añadiendo nueva funcionalidad y eliminando los bugs reportados.

Voy a dar una pequeña pincelada sobre esta librería que la verdad a mi me ha venido genial, por si a otras personas en el futuro les pudiese venir bien la información. En la página hay varios tutoriales donde se explica bastante bien las funcionalidades básicas de la librería.

Para comenzar a usarla debemos descargarnosla para añadirla como source en nuestro fichero .html o podríamos usar la URL. Yo recomiendo descargarla. Una vez descargada debemos añadir a nuestro fichero html una etiqueta <div id="nuestroID"> y colocarlo donde queramos que aparezca el canvas. Cabe destacar que nuestroID es importante ya que posteriormente en el código JS necesitaremos dicho ID para añadir el canvas en su interior. Una vez hecho esto pasamos a lo que viene siendo la programación en JS.

Lo más interesante de KineticJS es la abstracción que proporciona de escenario, capas, grupos y formas/elementos. Esto es muy práctico ya que podemos distribuir funcionalidades y manejar las capas de formas diferente.

Para crear el canvas debemos hacer lo siguiente:

var ancho = 1042;
var alto = 576;
var stage = new Kinetic.Stage("nuestroID", ancho, alto);

De esta forma tenemos declarado un nuevo escenario en el que podemos añadir capas, grupos y/o elementos. Como podemos observar la definición es bien sencilla. El primer parámetro es la cadena que representa el ID que tenía la etiqueta DIV mencionada anteriormente, ancho y alto... creo que no es necesario decir que son.

A continuación podríamos declarar una capa en la que introduciremos varios elementos. Para declarar una capa simplemente debemos hacer:

var layer = new Kinetic.Layer();

Cabe destacar que podemos pasarle como parámetro a esta función una configuración. Los elementos más destacables de la configuración serían si queremos o no mostrar la capa (visible: true, por ejemplo) o si queremos que la capa sea draggable (draggable: true). Para ver más sobre la configuración en la página web HTML5canvastutorials podemos encontrar información. La principal diferencia entre grupos y capas es que los primeros pueden contener grupos y formas (circulos, imagenes, etc) y las capas pueden contener grupos o cosas además de que cada capa está asociada a su propia etiqueta <canvas>. Yo, siguiendo los tutoriales que he encontrado en la página mencionada, he usado los grupos cuando quiero agrupar una serie de elementos con propiedades comunes (por ejemplo para poder hacer drag con muchos elementos de manera uniforme).

Por último podríamos declarar una forma/elemento. Estas formas pueden ser Circulos, Imagenes, Poligonos,  Rectangulos, Poligonos regulares, Estrellas o Texto. Todos los elementos mencionados están documentados en la API oficial y además en la página se pueden encontrar tutoriales de uso además de los distintos elementos de la configuración. Vamos a suponer que queremos añadir un circulo. Simplemente deberíamos hacer lo siguiente:

var circulo = new Kinetic.Circle({
 x: stage.width / 2,
 y: stage.height / 2,
 radius: 40,
 fill: "#AABBCC"
 stroke: "black",
 strokewidth: 4
});


//Podriamos declarar eventos, tanto de escritorio como de movil asi:

circulo.on("mouseover touchstart", function(){
 alert("Sorpresa!!");
});

//Anyadimos el circulo a la capa
layer.add(circulo);

//Anyadimo la capa al escenario
stage.add(layer);

Quizás al principio sea algo lioso, pero encuanto le dedicas un tiempo se convierte en algo muy intuitivo y muy muy sencillo de manejar. En el ejemplo podemos ver la facilidad con la que se gestionan los eventos sobre el circulo. Los eventos disponibles, tanto para PC de escritorio como para móvil, son los siguientes:

Escritorio: mouseover, mouseout, mousemove, mousedown, mouseup, click,dblclick, dragstart, and dragend
Móvil:  touchstart, touchmove, touchend, dbltap, dragstart, dragmove, and dragend


Por último en el ejemplo vemos como se añaden los elementos a la capa y por último como se añade la capa al escenario.


Además podemos crear aplicaciones interactivas, haciendo uso de los métodos para eliminar, mostrar, dibujar y ocultar objetos.


Algo que me pareció curioso es que si le ponemos nombre a los elementos, este nombre debe ser único, ya que si no, al eliminar un elemento de una capa, cuando intentásemos eliminar el siguiente con el mismo nombre nos daría un error.


También me gustaría destacar que normalmente se suele comenzar a manipular la página con las sentencias JS cuando se ha cargado completamente, para ello simplemente debemos hacer lo siguiente:

window.onload = function(){
 //Creacion de escenario, capas, elementos, etc...
};

Por el momento aquí dejo la pequeña introducción a esta gran librería, en caso de estimarlo oportuno, añadiré más entradas en el futuro. Un saludo y espero que os animéis a usar esta librería porque está genial.

Algoritmos Genéticos, mochila 0/1

Hace muchísimo tiempo que no escribo una entrada. Prácticas, exámenes, y tener un poco de vida han hecho que no pueda escribir nada por aquí últimamente. Tal y como mencioné en mi ultima entrada, por aquél entonces estábamos haciendo trabajos con algoritmos genéticos y programando un Shell. Desde aquella fecha ha pasado ya bastante tiempo, y, como es lógico, ya terminé aquellos trabajos y empecé otros nuevos. Pero lo prometido es deuda, así que primero voy a tratar el tema de los algoritmos genéticos que es algo más corto y en mi próxima entrada comentare y daré algunas pinceladas sobre el Shell que programamos mi compañero y yo.

Cualquier persona que no tenga idea de informática y aquellos que la tengan pero no hayan tenido la oportunidad de conocer esta técnica se preguntarán, ¿Qué es un algoritmo genético?. Según Wikipedia "Un algoritmo es una serie de pasos organizados que describe el proceso que se debe seguir, para dar solución a un problema específico. Son llamados así porque se inspiran en la evolución biológica y su base genético-molecular. Estos algoritmos hacen evolucionar una población de individuos sometiéndola a acciones aleatorias semejantes a las que actúan en la evolución biológica (mutaciones y recombinaciones genéticas), así como también a una Selección de acuerdo con algún criterio, en función del cual se decide cuáles son los individuos más adaptados, que sobreviven, y cuáles los menos aptos, que son descartados". Según yo diría que son unos algoritmos que buscan una solución a un problema de optimización en un espacio de soluciones más o menos aleatorio, consiguiendo en algunos casos la solución óptima en un tiempo de ejecución bastante reducido.

En comparación con otras técnicas como Backtracking el tiempo en encontrar soluciones ambos algoritmos puede llegar a tener una grandísima diferencia.

La primera toma de contacto que tuvimos con estos algoritmos fue para la reslocuión del problema de las n reinas, y tal y como observamos el tiempo que empleaba el algoritmo para unos tamaños de problema considerables era bastante aceptable.

Estos algoritmos tienen las siguientes características:

Los algoritmos genéticos se representan mediante una cadena sobre un alfabeto finito (una posible codificación sería una cadena de 0s y 1s). Dicha codificación define el tamaño del espacio de búsqueda y el tipo de operadores de combinación necesarios.
Cada elemento de un estado (también llamado individuo o cromosoma) es denominado gen.
Se utilizan unos operadores denominados "Selección, Cruce y Mutación" que explicaremos más adelante.
Estos algoritmos hacen uso de funciones heurísticas, y el valor heurístico de un estado se denomina fitness. La función de idoneidad o fitness mide la calidad de los estados.
Se basan en la afirmación de que combinando buenos estados se obtienen estados mejores.

Ahora pasamos a explicar de manera breve los distintos operadores:

Selección: Escoge qué individuos tendrán la oportunidad de reproducirse. Habrán individuos que aparezcan más de una vez y habrán individuos que no aparezcan. Principalmente hay dos técnicas para realizar esta función: Ruleta y Torneo. La primera técnica elige individuos con probabilidad proporcional a su función de idoneidad. La segunda establece k torneos aleatorios entre parejas de individuos y selecciona aquellos que ganen cada torneo.

Cruce: Los individuos seleccionados son recombinados para producir la descendencia que formará la siguiente generación. La técnica más común y básica es el operador de cruce por un punto.

Mutación: El operador de mutación cambia aleatoriamente el valor de algunos genes.

La función de idoneidad asigna un medida de calidad a cada estado (individuo). Cuando mejor sea dicho estado mayor será el valor de la función idoneidad.

De esta forma queda definido más o menos qué es un algoritmo genético.

El problema que nos tocó resolver era el problema de la mochila 0/1 (el cual ya hicimos también con otras técnicas de programación el curso anterior). Está resuelto en C++ haciendo uso de la librería Galib (no hemos tenido que hacer ningún tipo de implementación de individuos y demás). La única función que hemos tenido que realizar ha sido modificar los operadores de inicialización, cruce, mutación y la función objetivo (la que calcula el fitness de un individuo).

El problema que debíamos resolver es el siguiente:

Una empresa de publicidad necesita sacar al mercado un cierto producto. Para ello, debe elegir los avisos (anuncios publicitarios) en los medios de comunicación con el objetivo de maximizar el número de personas (audiencia) a los que alcanzan. La empresa cuenta de un presupuesto para ello y existe una cota superior para el número de avisos de cada tipo. Además, de acuerdo a ciertos estudios, se conoce la audiencia de cada medio de comunicación. El costo por aviso en cada medio de comunicación también es fijo y conocido.

Este problema puede modelarse mediante el modelo knapsack 0/1:

Tenemos n objetos. El problema knapsack 0/1 consiste en llenar una mochila con objetos. Cada objeto i tiene un peso determinado pi siempre positivo y una utilidad o valor asociado, también positivo, bi. Se ha de considerar además que la mochila tiene una capacidad máxima limitada C, por tanto, se han de escoger aquellos objetos xi para llenar la mochila que maximicen la utilidad sin exceder su capacidad”.

Diseñar e implementar en GALib, este problema utilizando un algoritmo genético simple.
Tener en cuenta los siguientes elementos o cuestiones:

Como los individuos que se obtienen en la inicialización de la población y al aplicar los operadores genéticos pueden ser individuos inválidos (individuos que no verifican las restricciones, es decir, sobrepasan la capacidad de la mochila), necesitamos modificar la inicialización y operadores genéticos para que comprueben la validez de los individuos generados. Para ello, vamos a partir de la inicialización, operador de cruce y mutación disponibles en GALib para string binarios.

Las modificaciones deben realizarse en el siguiente sentido:

- Inicialización: Ir creando el individuo gen a gen. Ir introduciendo elementos en los genes de forma aleatoria siempre que sea un individuo válido.

- Operador de cruce: supongamos que tenemos los cromosomas padre P11+P12 y P21+P22, cortados por el punto de corte x.

El operador de cruce empieza a crear los individuos hijos como sigue:

Tomar P11+P’, donde P’ es el trozo de cromosoma e inicialmente está a cero (no incluye ningún objeto). Ir recorriendo P22 gen a gen. Si al introducir el valor de un gen en P’ produce un P11+P’ válido, se introduce copiando sus valor en P’. En caso contrario, pasar al siguiente gen.

Tomar P21+P’, donde P’ es el trozo de cromosoma e inicialmente está a cero (no incluye ningún objeto). Ir recorriendo P12 gen a gen. Si al introducir el valor de un gen en P’ produce un P21+P’ válido, se introduce. En caso contrario, pasar al siguiente gen.

- Operador de mutación: si al mutar un gen provoca un individuo inválido, está mutación no se realiza. Se sigue con el siguiente gen candidato a ser mutado. Una vez diseñado el algoritmo genético, probarlo para el caso siguiente:

a) Si suponemos que disponemos de 5.000 euros para la publicidad, que como máximo podríamos poner 20 anuncios en paneles estáticos, 20 anuncios en paneles móviles, 40 anuncios en prensa, 50 anuncios en radio y 50 en televisión. Además, cada anuncio tiene un costo de 15, 15, 25, 45 y 90 euros, y una audiencia de 35, 40, 90, 135 y 220, respectivamente. ¿Cuántos anuncios podríamos poner en total en cada medio?

b) Cambiar los datos del problema para hacerlo más complejo. Además, del caso anterior, definir cuatro casos distintos del problema con complejidad distinta. Comparar los resultados en tiempo y solución del algoritmo genético en los 5 casos distintos.

A continuación expondré la solución propuesta para la implementación:

Para la implementación del algoritmo genético que resolviese el problema de la mochila 0/1 hemos optado por hacer uso de la clase GA1DArrayAlleleGenome, la cual, a su vez, hace uso de un array de conjuntos de alelos: GAAlleleSetArray.

El primer paso importante en la realización del algoritmo es la inicialización del array de conjuntos de alelos. Este array almacenará conjuntos de valores que representarán el número de cada tipo de anuncios que disponemos. Más adelante veremos que esto nos sirve para establecer el número de anuncios de un tipo concreto que hemos metido en la mochila. Por tanto, dichos valores estarán en el rango [0 – anunciosTipoi].

La inicialización de este array se hace de la siguiente manera:
1) Declaramos el array de conjuntos de alelos.
2) Creamos un conjunto de alelos y añadimos los valores deseados con la función add.
3) Añadimos el conjunto creado al array de alelos mediante la función add.

Cabe destacar que ,debido a que estas dos clases están parametrizadas, se han declarado para que almacene tipo de dato entero, ya que no tiene sentido tener valores reales de la cantidad de anuncios.

Una vez realizada la inicialización del array de conjuntos de alelos que usaremos para resolver este problema, pasamos ahora a la declaración de la clase que usaremos para crear posteriormente el algoritmo genético simple.

Dicha clase es la mencionada anteriormente, GA1DArrayAlleleGenome. Para la creación de esta clase usamos las ya definidas anteriormente que nos representan los conjuntos de alelos que emplearemos en el problema. Esta clase además nos sirve para especificar los operadores de inicialización, cruce y mutación que emplearemos para nuestra población de genomas. Dichas operaciones se detallan a continuación:

•Operador de Inicialización: El objetivo de esta función es el de inicializar la población con valores válidos. Valores válidos son aquellos que no superen la capacidad máxima de la mochila y, además, cada valor individual no supere el número de anuncios máximo del tipo que representa.
El hecho que motiva que tengamos que definir nosotros mismos este operador, es que debemos controlar que el incializado de los individuos de nuestra población sea correcto ya que, si lo hiciésemos con valores aleatorios, podríamos tener individuos inválidos.

Para realizar este control realizamos los siguientes pasos:

1) Recorremos el genoma.
2) Para cada gen del genoma generamos un valor aleatorio dentro de los limites especificados por el conjunto al que pertenece.
3) Comprobamos si al insertar dicho valor superamos la capacidad máxima de la mochila. En caso afirmativo vamos reduciendo dicho valor hasta que consigamos meterlo o el valor sea 0. En caso negativo lo metemos sin más.

De esta forma conseguiríamos tener toda la población inicializada con valores 3aleatorios y afirmar que son válidos.

•Operador de Cruce: El operador de cruce nos sirve para generar individuos nuevos a partir de dos individuos que tomaremos como progenitores. De nuevo debemos definirnos nuestro propio operador para asegurar que se cumplan las restricciones impuestas por el problema.

El operador de cruce que hemos implementado es el de cruce por un punto. Dicho punto de cruce es establecido por un valor aleatorio entre 0 y la longitud del genoma.

Una vez establecido este punto recorremos todos los genes del genoma hasta dicho punto y copiamos los genes de la madre en el primer hijo y los del padre en el segundo, y posteriormente se copian el resto de genes del padre para el primero y el resto de la madre para el segundo.

Al realizar la copia, de la primera parte de cualquiera de los dos progenitores no debemos realizar ninguna comprobación, ya que si partimos de individuos válidos, una parte de ellos también es válida. Por tanto las comprobaciones debemos hacerlas al copiar la segunda parte. La comprobación a realizar es ver si al copiar el gen en el hijo excedemos la capacidad de la mochila, en caso afirmativo optamos por establecer dicho gen a 0. Una alternativa podría ser ir reduciendo el valor del gen del progenitor e insertarlo.

•Operador de Mutación: Este operador ha sido modificado para que nos cambie el valor de un gen por un valor aleatorio. La única consideración es comprobar si al realizar la mutación el individuo generado es válido. Si es válido seguimos con los siguientes genes, si por el contrario generamos uno inválido entonces establecemos su valor como 0. Una posible alternativa es ir reduciendo el valor del número aleatorio generado hasta que sea posible asignárselo al gen.

•Función objetivo: La función objetivo será usada por el algoritmo genético para conocer el valor de fitness de un individuo. Este valor es calculado de la siguiente manera:

1) Recorremos los genes del individuos
2) Por cada gen multiplicamos su valor por el beneficio
3) Vamos llevando la suma y la devolvemos.

Los valores asignados para el tamaño de la población y el número de generaciones ha sido 100 y 1000 respectivamente. Además la probabilidad de mutación y de cruce son de 0.1 y 0.9 respectivamente.

Cabe destacar que hemos optado por leer los datos del problema por teclado. El realizarlo de esta manera nos beneficia en cuanto a que podemos insertar los valores del problema que queramos ejecutar a mano, o mediante un fichero redireccionando la entrada desde consola.

 /*Declaracion y creacion del array de conjuntos de alelos */
    GAAlleleSetArray arrayAlelos;
    cin>>maximo_dinero>>num_publicidad;
    datos.capacidadMaxima = maximo_dinero;
    for(int i=0;i>aux;
            datos.pesos.push_back(aux);
            cin>>aux;
            datos.beneficio.push_back(aux);
            cin>>aux;
            GAAlleleSet alelos;
            for(int j = 0;j<=aux;j++)
                    alelos.add(j);
            arrayAlelos.add(alelos);
    }

// Creamos el GA. Primero creamos el genoma y creamos una poblacion de genomas
    GA1DArrayAlleleGenome genome(arrayAlelos, Objective, &datos);

// Inicializamos -minimizar la funcion objetivo, tamaño de la poblacion, no.
    // generaciones, prob. mutacion, prob. Cruce, y le indicamos que evolucione.
    genome.initializer(inicializar); //Establecemos funcion operadores de inicializacion, cruce y mutacion
    genome.mutator(mutador); 
    genome.crossover(cruzador);
    GASimpleGA ga(genome);
    ga.minimaxi(1);
    ga.populationSize(popsize);
    ga.nGenerations(ngen);
    ga.pMutation(pmut);
    ga.pCrossover(pcross);

    ga.solve(); //Resuelve problema

 // Ahora imprimimos el mejor individuo que encuentra el GA y su valor fitness
    GA1DArrayAlleleGenome & g = (GA1DArrayAlleleGenome &)ga.statistics().bestIndividual();
    int pesoTotal = capacidadMochila(g, g.length());
    cout << "El GA encuentra:\n\t" << ga.statistics().bestIndividual() << "\n\n";
    cout << "Mejor valor fitness es " << ga.statistics().maxEver() << "\n";
    cout << "El peso alcanzado es " << pesoTotal << endl;

La funciones de inicializar, mutador, cruzador las dejo para que aquél que le interese las realice.

Me ha quedado una publicación bastante extensa, pero quién sabe, a lo mejor a alguien le sirve.

Espero haberme explicado con claridad y haber creado algo de interés a aquella persona que lea esta entrada.

Saludos y ¡hasta la próxima!