BSA & Bee

-

Lo siento, pero estos algoritmos ya están cogidos II

En la segunda ronda de Técnicas Evolutivas os presentamos el algoritmo Backtracking Search y el algoritmo de las abejas.

Algoritmo Backtracking Search - BSA

El algoritmo BSA se basa en una mutación de retroceso, esto es, se creará una población mutada utilizando las poblaciones de la iteración actual y la anterior.

Vamos a ser prácticos. Este algoritmo es muy parecido al algoritmo DE. La diferencia: la fórmula de la población mutada. La fórmula esta vez será la siguiente:

Yi = Xactual + F*(Xanterior - Xactual)

Donde F es el rango de mutación y puede tomar cualquier valor de 0 a 3. Los pasos del BSA son los mismos del algoritmo DE:

  • Generar una población de agentes X.
  • En la primera generación/iteración, la población anterior (Xanterior) será igual que Xactual.
  • Crear una población mutada Y, usando las poblaciones Xactual y Xanterior.
  • Crear una cuarta población de agentes descendientes (T) con la población mutada Y y la población Xactual.
  • Selección de los candidatos más aptos entre las poblaciones T y Xactual.
  • Xactual pasa a ser Xanterior.
  • Los agentes supervivientes a la selección pasan a ser la población Xactual.
Imagen: crossover.

Y así, generación tras generación se irá mejorando el resultado de los agentes hasta conseguir el agente que proporcione la solución óptima.

Algoritmo de las Abejas

Este algoritmo se basa en la división de las abejas en tres clases según su aptitud en la comparación de las abejas de las clases excelentes y buenas con su versión mutada.

Sí, incluso las abejas son clasistas. Esta vez, las abejas/agentes se ordenarán según su aptitud/capacidad de solucionar el problema. Las abejas más aptas, serán el grupo de abejas excelentes, las siguientes, las abejas buenas, y las sobrantes, las del montón. La cantidad de abejas pertenecientes a cada grupo dependerá de la cantidad total de agentes, del problema a resolver, de la cantidad de características que tiene cada abeja, ...

Una vez se han clasificado, se dará comienzo a los septuagésimo cuartos Juegos del Hambre la mutación y selección de agentes. Cada abeja del grupo excelente atraerá a (por ejemplo) 10 abejas mutadas, y el grupo bueno a (por ejemplo) 5. La cantidad de abejas atraídas, al igual que la cantidad de abejas de cada grupo dependerá del tipo de problema y otros factores. Las abejas atraídas serán mutaciones aleatorias de las abejas originales. Para entendernos mejor, supongamos que se ha de diseñar la forma que debería de tener una rueda de coche para que esta fuera óptima (buena sujeción a la calzada, gastos mínimos de energía, aerodinámico, ...):

  • Abeja original, características:
    • Radio = 0.5m
    • Anchura = 0.3m
    • ...
  • Abeja mutada 1, características:
    • Radio*0.1
    • Anchura*0.35
    • ...
  • Abeja mutada 2, características:
    • Radio*1.005
    • Anchura*0.8726
    • ...
  • ...

Y por último solo queda que cada abeja se enfrente a las abejas que ha atraído. La abeja más apta ocupará el lugar de la original.

Después del proceso de selección de abejas excelentes y buenas, el grupo de agentes común se eliminará y se creará una nueva población de abejas con el grupo excelente, el grupo bueno y un grupo nuevo aleatorio de abejas. Ha tener en cuenta, al final de cada iteración/generación, la cantidad de agentes en la población tiene que ser la misma.

Comentarios

Publicar un comentario

Entradas populares de este blog

Proyecto Estación Meteorológica 4: Visualización de Resultados Mediante HTML y D3.js

-
Imagen
Visualización de Resultados Mediante HTML y D3.js Una vez se han subido los datos a ThingSpeak, tal y como se describe en el post anterior , se quiere visualizar el contenido que se ha subido. Para ello, se diseña una página web utilizando HTML, JavaScript, CSS y D3.js. El código de la página consiste principalmente en 3 partes: la importación de datos y su tratamiento, la visualización de estos en una gráfica y la visualización en una tabla. Primero, la importación de datos. Para ello, se debe conseguir una URI desde ThingSpeak, la cual se puede conseguir entrando en la pestaña “ Data Import/Export ” de los canales que se han creado, en la sección “ Get a Channel Feed ”. Se decide que se quieren recuperar 5 sets de datos desde cada canal, por lo que esto se tiene en cuenta a la hora de codificar las URIs. Se cargan los datos llamando a estas con JavaScript, las cuales, tras ser llamadas, ejecutan unas funciones previamente definidas. El cometido de
Leer más

Diferentes técnicas de las redes neuronales

-
Imagen
DIFERENTES TÉCNICAS DE LAS REDES NEURONALES En la entrada anterior hemos visto, un poco por encima, lo que son las redes neuronales artificiales y de que se componen. La explicación de como se consigue  la salida de las neuronas y de la red en su totalidad, encaja con una técnica de las redes neuronales: Forward Propagation. La primera técnica que se va a explicar en esta entrada. Forward propagation El Forward propagation  es una implementación vectorial de las funciones de las redes neuronales, es decir, explica como pasan los valores de entrada (x) a ser los valores de salida, como se transforman.  Aunque ya se haya explicado este proceso en la entrada anterior, vemos necesario volver a explicarlo, para entender correctamente las demás técnicas (si lo habéis entendido bien, podéis saltar un poco más hacia adelante). Bien pues, primero las entradas (x) se multiplican con una  matriz de pesos ( θ )  que controla la función de mapeo de una capa a otra. Después, una
Leer más

Proyecto Estación Meteorológica 3: Obtención y Envío de Datos Mediante Python

-
Imagen
Obtención y Envío de Datos Mediante Python Una vez se ha configurado la Raspberry como es debido, se comienza la codificación. Lo primero que se codifica es el programa de Python. La función de este programa es el de crear automáticamente los canales necesarios en ThingSpeak, recoger datos del sensor y subir estos a los canales previamente mencionados. Para ello, primero se observan las especificaciones del usuario para definir la problemática. Haciendo esto, se observa que hay que subir datos con una frecuencia de 10 segundos, pero los canales de ThingSpeak solo aceptan datos cada 15 segundos. Para solucionar este problema, se crean dos canales, a los cuales se suben datos alternamente. En cuanto al código, lo primero es importar las librerías. Ya que la comunicación con ThingSpeak se hace mediante peticiones http, se importan las librerías urllib y httplib , además de json , la cual será necesaria para interpretar las respuestas. También se
Leer más