Practica 1 ACO

Algoritmo ACO

Introducción

El problema del viajero consiste en una persona que tiene como objetivo pasar por “n” lugares sin repetir alguno y regresar a su origen además de encontrar la ruta óptima ya sea en tiempo, recorrido y dinero sea cual sea su situación.

Es muy importante para conseguir rutas de optimización y  obtener la solución a problemas donde se tenga que encontrar los caminos mas adecuados.

Algunas aplicaciones que podría tener serian en el traslado de mercancía a ciertas rutas de entrega que tienen que seguir para dejar su producto. El problema del viajero es difícil debido que se tienen muchas series de opciones o rutas que pueden ser elegidas.

ACO es un algoritmo de optimización basado en la colonia de hormigas, esto se trata de que cierta cantidad de hormigas salen a buscar alimento dejando una feromona ya que son ciegas las hormigas rastrean esta feromona optan por tomar la que esta impregnada con mas fuerza ya que esta ya siguió un recorrido y volvió a su origen. ACO sirve para resolver problemas de este tipo es decir en donde se tenga cierta cantidad de caminos opcionales y sean los más factibles y fáciles a usar.

Se puede usar para darte una ruta de acceso especifica optimizada  y dejando atrás la fuerza bruta.

Las secciones en las que se dividirá la entrada serán Introducción, Marco teórico, Desarrollo y Conclusión.

Marco Teórico

El problema del viajero es un problema NP-completo ya que cuenta con muchas combinaciones de caminos y se tiene que encontrar el más óptimo o el más corto.

Este problema se trata de encontrar el camino más corto en un mapa con diferentes ciudades conectadas entre sí y el viajero tiene que comenzar y terminar en la misma ciudad. EL mapa se representa mediante un grafo.

Las instancias de este problema consisten en darle pesos o valores a las aristas y encontrar el más óptimo por ejemplo:

Debe pasar por 4 ciudades diferentes y regresar a la misma.

Por fuerza bruta:

MTGCM= 29                                                     

MCGTM= 29                                                     

MGCTM= 28*                                                   

MGTCM= 39

MTCGM= 28*

MCTGM= 39

CMTGC=  29

CGTMC= 29

CTGMC= 39

CTMGC= 28*

CGMTC= 28*

CMGTC= 39

GTMCG= 28*   

GCMTG= 28*

GMTCG= 28*

GMCTG= 39

GTCMG= 39

GCTMG= 28*

TMCGT= 29

TGCMT= 29

TCMGT= 39

TCGMT= 28*

TGMCT= 39

TMGCT= 28*

ACO significa optimización basado en colonia de hormigas, es un tipo de técnica metauristica que se basa en el comportamiento natural de las hormigas para resolver un problema de optimización, esta técnica fue inventada por Dorigo etal en 1991, esta técnica se inspiró en el comportamiento de las colonias de hormigas.

El proceso a seguir en esta técnica es la siguiente como se muestra en el siguiente pseudocódigo:

1.       Inicio

Hacer (Do)

2.       Comienzo de recorrido de hormigas

3.       Camino más corto para el regreso

4.       Búsqueda de objetivo

5.       Si se encontró el objetivo(if)

6.       Dejar rastro de feromona

7.       Regresar al origen

8.       Hormigas escogen camino con más feromona

9.       Se eliminan rastros de feromona

10.   Se cumple el objetivo(while)

11.   Fin

Las fórmulas más importantes para esta técnica son:

Selección de camino

Donde Ti es la cantidad de feromona y n es la distancia o costo

Actualización de feromona:

En donde p es el coeficiente de evaporación de feromonas.

Código

Conclusión

De la práctica desarrollada nos dejó de aprendizaje que el algoritmo basado en colonias de hormigas (ACO) puede tener diferentes aplicaciones como optimizar algún proceso, en la teoría y explicación de cómo funcionaba el algoritmo lo entendimos bien pero en lo que se batallo fue en el comprender las formulas y también un poco en la codificación, para entender mejor el algoritmo se pueden buscar libros o videos para poder tener más en claro y afianzar lo hecho en esta practica.

Referencias

http://www.slideshare.net/Slidemora/optimizacin-basada-en-colonias-de-hormigas

http://elisa.dyndns-web.com/~saraelena/material/sistadap/dorigo_aco_2006.pdf

http://es.wikipedia.org/wiki/Algoritmo_colonia_de_hormigas

Un video de la funcion de ACO

http://www.youtube.com/watch?v=SMc6UR5blS0

Sistema adaptativo para bien estar social

Sistema de estacionamiento para personas con alguna discapacidad Algo que comúnmente en México no se respeta desde hace años es el de lugar para discapacitados o lugares exclusivos para estacionarse, la idea es a estas personas ya sea discapacitadas o de uso exclusivo de estacionamiento se les daría una código de barras o o algún tipo de código reconocible por un sensor si este vehículo tiene el código no hará nada de lo contrario activaría una alarma o daría alguna señal indicando que no es discapacitado o no tiene permitido estacionarse en este lugar para cierto lector el cual dirá si pueden estacionarse en ese lugar o no

Algoritmos Geneticos

Equipo

1527268 Victor Emanuel Ríos Martínez

1483821 Juan Carlos Guzmán Pinales

1511137 Eduardo Alberto Briones Hernández
1522790 Ricardo Alberto Morales Ramos

Introducción

Para este algoritmo utilizaremos el problema de la mochila, que se trata de un un ladrón que intenta robar cierta cantidad de objetos que se ven limitados por la capacidad de transporte de la mochila, el debe escoger que tipo de objetos pueden ser los mas valiosos y ademas de eso poder transportar la mayor cantidad de ellos.

El problema de la mochila es una de las cosas que vivimos día a día aun sin darnos cuenta e ahí su importancia. Este tipo de problemas se presentan en la vida real para mi forma de verlo por ejemplo cuando vas de paseo y necesitas llevarte cosas tienes un limite de objetos que puedes llevar o también al momento de comprar comida tienes cierta cantidad de dinero y cada platillo cuesta tanto porcentaje de el.

El dilema del problema de la mochila se ve reflejado mas que nada en que la mayoría de nosotros somos tan codiciosos o aborasados que nos vamos siempre por lo mas factible o el el así mero.

Marco teorico

EL problema de la mochila está en una categoría de NP completo ya que es difícil por que es relevante y cuenta con demasiadas instancias.
Una instancia de este problema consiste en darle diferentes valores a los a las variables involucradas ósea parámetros dentro del problema, por ejemplo:

Objeto O1 O2 O3 O4 O5 O6 O7

Ganancia 8 16 45 2 11 22 7
Peso 5 7 15 8 24 20 18

Capacidad total = 95
El algoritmo genético es una técnica que busca una solución de algún problema influenciado por la evolución humana. Estos algoritmos genéticos fueron inventados por John Henry Holland, este tipo se basó en la evolución biológica usando términos como genes, cromosomas y mutaciones.
Esta información se representa de la siguiente manera:
La población es el conjunto de cromosomas que hay dentro del problema estos cromosomas se representan por medio de una cadena binaria y cada elemento de la cadena se le llama gen.
¿Cuál es el proceso (general) que se sigue con un AG simple? Puedes incluir un diagrama de flujo o pseudocódigo para explicar este punto.
Se trabaja con una población de individuos donde cada uno representa una solución al problema.  Cada 1 tiene un valor o puntación, relacionada con la solución al problema. Entre más se adapte un individuo al problema más probabilidad tendrá a reproducirse y este cruce creara nuevos individuos que se adaptaran mejor al problema.
Si el algoritmo genético fue bien diseñado cada vez se harán mejores individuos con mejores características para encontrar la solución.
Entonces resumiendo el AG simple es:

> Se genera una población inicial
> Se evalúa cada individuo
> Se seleccionan 2 de los mejores individuos para una cruza.
> Se cruzan y mutan
> Se evalúa su función de los descendientes mutados
> Estos se agregan a una nueva generación

BEGIN AG
{
Iniciar población
EVALUAR adap
{
SELECCIONAR padres
CRUZA entre los padres
{
MUTACION de los hijos
}
EVALUAR hijos
If adap hijos < padres
{
“Está mal implementado el AG”
Else
{
AGREGAR hijos ngeneracion
END
END AG
*ngeneracion = nueva generación de hijos

¿Qué son los operadores genéticos y para qué sirven? Explica cada uno de ellos y la implementación específica que estás utilizando (ej. rueda de ruleta, punto de cruce,...).
Son métodos para crear nuevos mejores individuos que los anteriores, sirven para crear una mejor población.
Existen los algoritmos de selección, se eligen cuales individuos se van a reproducir y cuáles no.

  - Punto de cruce
Si se tienen dos individuos digamos:
1010 y
0101

Entonces para hacer un cruce y crear un nuevo individuo supuestamente más apto se toma las primeras dos partes del primer individuo osèase: 10 y en el segundo se toman sus últimas dos partes osèase: 01
Y ya con esto tenemos un nuevo individuo que sería chan chan chaan!:

1001

  -Mutación
   Los genes de un individuo variaran su valor a una forma aleatoria. Si se tiene un cruce con éxito el individuo muta con algo de probabilidad.
Si anteriormente se obtuvo al individuo:
1001 al mutar este seria
0110

- Selección por torneo
En esta selección se realizan comparaciones directas entre individuos como si pelearan entre sí. Existen dos versiones de hacer esto
- Deterministica: Aquí dentro de la población se seleccionan un número de individuos y se selecciona el más adaptable.
- Probabilística: Se genera un numero aleatorio y si es mayor  que un parámetro se escoge al individuo más alto y en caso contrario al menos alto.
¿Cuáles son los parámetros involucrados en un AG?
El tamaño de la población, probabilidad de cruce, probabilidad de mutacion.

Cálculos y resultados de experimentos

Calculo de optimo por fuerza bruta

Instancia 1:




















instancia 2:

Parámetro	Valor
Poblaciones	8	8	8	8
P. mutación	0.2	0.3	0.4	0.3

Código generador de instancias
Conclusiones

Resolver los problemas que se nos presentan cuando estos tiene un número muy alto de combinaciones por fuerza bruta  toma demasiado tiempo, en cambio el algoritmo genético simple es más rápido en su arrojamiento de resultado. El algoritmo genético tiene como base las mutaciones entre cromosomas y por cada iteración se va escogiendo el más óptimo y de esa forma al mismo tiempo se acerca al óptimo de toda la generación.

El algoritmo genético sirve para encontrar soluciones óptimas dentro de una población de n individuos. Una de las ventajas es que se puede encontrar una solución en un tiempo más corto que por fuerza bruta y una de las desventajas puede ser que se no siempre se llega a la más óptima y se tiene que dar mas iteraciones.

Clase Programa de Auto-ajuste

Equipo

1527268 Victor Emanuel Ríos Martínez

1483821 Juan Carlos Guzmán Pinales

1511137 Eduardo Alberto Briones Hernández

Para este proyecto del programa auto ajuste decidimos diseñar un programa de una lavadora con una capacidad de 12 kg  apartir de cierta cantidad de peso este decidiera la manera correcta de suministrar el agua y el jabon exactos que esta nesecitaria en cada carga de ropa sin pasarse y sin faltar.

Para esto tomamos encuenta ciertos parámetros de la vida real que nos ayudaron mucho en la resolución de este programa  

A partir de este dato encontramos nuestra formula base para establecer las condiciones que serian utilizadas y en si la formula mas importante para nuestro proyecto litrosdeagua=103.0*pesototal/6.0, donde litros de agua serian igual a el peso total de la ropa introducida en la lavadora entre 6 como instancia principal.

El siguiente codigo arroja de manera manual la cantidad de ropa y definidos pesos que ya estan incluidos en ella ademas de dar la opcion de determinar que tanto se pondrá en la lavadora.

#include

float menudeprendas();

main(){
 int res;

float pesototal,litrosdeagua, detergente;
  pesototal=0.0;res=1;
  do{
      pesototal=pesototal+menudeprendas();
      printf("Agregar tipo de prenda? 1. Si - 2. No");
      scanf("%d",&res);
      printf("\n");
  }while(res==1);
   litrosdeagua=103.0*pesototal/6.0; //La cantidad de agua se relaciona con el peso de esta forma
   printf("Peso añadido (Kg): %.3f\n", pesototal);
   printf("Agua (Litros): %.3f\n", litrosdeagua);
   if(litrosdeagua>0&&litrosdeagua<=25.75) detergente=.016; //muy bajo
   else if(litrosdeagua>25.75&&litrosdeagua<=51.50) detergente=.024; //bajo
   else if(litrosdeagua>51.50&&litrosdeagua<=77.25) detergente=.034; //medio
   else if(litrosdeagua>77.25&&litrosdeagua<=103.0) detergente=.050; //alto
   printf("Detergente (Gramos): %.3f\n", detergente);
   system("pause");
}

float menudeprendas(){
 system("cls");
 printf("Seleccionetipo de prenda a agregar\n");
 printf("1. Interior (100g)\n");
 printf("2. Camisa (300g)\n");
 printf("3. Pantalon de mezclilla (900)\n");
 printf("4. Blusa (250g)\n");
 printf("5. Camiseta (300g)\n");
 printf("6. Falda (200g)\n");
 printf("7. Cobertor (1100g)\n");
 printf("8. Toalla (450g)\n");

 int opcion;
 float peso,n;
 scanf("%d", &opcion);
 printf("Cuantas?");scanf("%f",&n);
 switch(opcion){
  case 1: peso=0.300*n; break;
  case 2: peso=0.100*n; break;
  case 3: peso=0.900*n; break;
  case 4: peso=0.250*n; break;
  case 5: peso=0.300*n; break;
  case 6: peso=0.200*n; break;
  case 7: peso=1.100*n; break;
  case 8: peso=0.450*n; break;


default: printf("Opcion no valida"); break;
 }
 return peso;


}

Capturas de pantalla de la ejecución

A continuacion se ejecuto el mismo codigo con algunos cambios para ver los resultados de manera random y ver que tan optimo era el ajuste realizado

#include

#include


loat menudeprendas();

f
main(){
 int res,i;

(unsigned int) time (NULL);
 srand (iseed);
 floa
unsigned int iseed =
 t pesototal, litrosdeagua, detergente;
 while(1){

oducidas:\n");
  do{ pesot
pesototal=0.0;res=1;i=0;
  printf("\nPrendas Int
rotal=pesototal+menudeprendas();

da? 1. Si - 2. No");
   res=rand()%2+1;
   i++;
  }wh
//printf("Agregar tipo de pre

nile(res==1&&i<3 data-blogger-escaped-a="" data-blogger-escaped-agua="" data-blogger-escaped-anadido="" data-blogger-escaped-cantidad="" data-blogger-escaped-con="" data-blogger-escaped-de="" data-blogger-escaped-el="" data-blogger-escaped-eso="" data-blogger-escaped-esta="" data-blogger-escaped-f="" data-blogger-escaped-forma="" data-blogger-escaped-g="" data-blogger-escaped-gua="" data-blogger-escaped-if="" data-blogger-escaped-itros="" data-blogger-escaped-litrosdeagua="" data-blogger-escaped-n="" data-blogger-escaped-peso="" data-blogger-escaped-pesototal="" data-blogger-escaped-printf="" data-blogger-escaped-relaciona="" data-blogger-escaped-se="">0&&litrosdeagua<=25.75) detergente=.016; //muy bajo
else if(litrosdeagua>25.75&&litrosdeagua<=51.50) detergente=.024; //bajo
  else if(litrosdeagua>51.50&&litrosdeagua<=77.25) detergente=.034; //medio
  else if(litrosdeagua>77.25) detergente=.050; //alto
  printf("Detergente (Gramos): %.3f\n", detergente);
  usleep(900000);
 }
}

float menudeprendas(){
 int opcion;
 float peso=0.0,n;
 opcion=rand()%8+1;
 //printf("Cuantas?");
 if(opcion==7||opcion==3) n=rand()%6+1; //aunque es probable un exceso, esto nos ayudará a limitarlo
 else n=rand()%10+1;
 switch(opcion){
  case 1: peso=0.100*n; printf("Interior (100g)------------- X %.0f\n", n); break;
  case 2: peso=0.300*n; printf("Camisa (300g)--------------- X %.0f\n", n); break;


case 3: peso=0.900*n; printf("Pantalon de mezclilla (900)- X %.0f\n", n); break;
  case 4: peso=0.250*n; printf("Blusa (250g)---------------- X %.0f\n", n); break;
  case 5: peso=0.300*n; printf("Camiseta (300g)------------- X %.0f\n", n); break;
  case 6: peso=0.200*n; printf("Falda (200g)---------------- X %.0f\n", n); break;
  case 7: peso=1.100*n; printf("Cobertor (1100g)------------ X %.0f\n", n); break;
  case 8: peso=0.450*n; printf("Toalla (450g)--------------- X %.0f\n", n); break;
  //default: printf("Opcion no valida"); break;
 }


return peso;}

Capturas de pantalla de su ejecucion

Bibliografias

http://www.electrolux.com.ve/files/manuales/EWLI066OFDIWT.pdf

http://www.ehowenespanol.com/instrucciones-lavadora-whirlpool-como_85135/

laboratorio 1 parte 2 ACO

Introduccion