4° Entrega - Subasta Inglesa

Determinación del ganador 

Subasta inglesa 

Introducción

En esta práctica realizaremos una subasta, esta es la forma más sencilla de llegar a un mutuo acuerdo entre el agente y el subastador.

Objetivos

Asignar bienes a los agentes, generando una subasta la cual es un mecanismo convencional a grito abierto, ascendente, con la cual el que oferte una cantidad más alta es el que se lleva el objeto subastado. 

Justificación 
En un inicio pensamos realizar el protocolo Contract net, en el cual tuvimos muchas dificultades, así que decidimos cambiar a Subasta Inglesa, el cual también es un tema interesante y aplicable a la vida diaria. 

Desarrollo 

Desarrollamos una subasta inglesa, consiste en comenzar con un precio a grito abierto por lo cual el agente sabe cuanto ofrecen sus contrincantes, debido a esto su estrategia dominante es incrementar un poco más la oferta, la  determinación  del ganador sera quien ofrece más y pagara la cantidad ofrecida. 

Código Subasta Inglesa

#! usr/bin/python

import pygame
import time
from random import randint
from pygame.locals import *
pygame.init()

def subasta():
    print ("\nEl artiulo en venta es: %s - Precio inicial: $%d") % (articulo[0], articulo[1])
    cantidad = input("\nCuantas ofertas se van a hacer: ")
    pantalla.blit(fondo2, (0, 0))
    pygame.display.update()
        
    for i in range (cantidad):
        if i == 0:
            nombre = raw_input("Nombre: ")
            x = input("Primera oferta: ")
            while x <= articulo[1]:
                print "Error, ingrese una oferta mayor a $%d" % (articulo[1])
                x = input("Primera oferta: ")
            arr.append(x)
            precios.append(x)
            nombres.append(nombre)
            
      
        
        else:
            nombre = raw_input("Nombre: ")
            x = input("Siguiente oferta: ")
            while precios[i-1] >= x:
                print "Error, ingrese una oferta mayor a $%d" % (precios[i-1])
                x = input("Siguiente oferta: ")
            precios.append(x)
            nombres.append(nombre)
            while precios[i] < precios[i-1]:
                print "Error, ingrese una oferta mayor a $%d" % (precios[i-1])
                x = input("Siguiente oferta: ")
            arr.append(x)
            precios.append(x)
               
        x = str(x)
        pantalla.blit(fondo2, (0, 0))
        pantalla.blit(fuente.render(x, True, (0, 0, 0)), (190, 90))
        pygame.display.update()
        x = int(x)     
   
    gana = max(arr)
    pos = arr.index(gana)
    ganador = nombres[pos]
    print "El ganador es %s, ofrecio $%d" % (ganador, gana)
    time.sleep(1)
    pantalla.blit(fondo, (0, 0))
    pantalla.blit(fuente.render("Ganador: %s" % (ganador), True, (255, 255, 255)), (80, 20))
    pantalla.blit(fuente1.render("Ofrecio $%d" % (gana), True, (255, 255, 255)), (230, 65))
    pygame.display.update()
     
       

    while True:
            for event in pygame.event.get():
                if event.type == pygame.QUIT:
                    exit()

if __name__ == "__main__":
    arr = []
    nombres = []
    precios = []
    a1 = "Tazo de Will Smith"
    p1 = 1500
    a2 = "Disco de los Beatles"
    p2 = 300
    a3 = "Playera de los tigres"
    p3 = 600
    a4 = "Chevy seminuevo 2008"
    p4 = 30000
    a5 = "Laptop Sony"
    p5 = 7000
    articulo = 0

    articulos = randint(0, 4)
    if articulos == 0:
        articulo = [a1, p1]
    elif articulos == 1:
        articulo = [a2, p2]
    elif articulos == 2:
        articulo = [a3, p3]
    elif articulos == 3:
        articulo = [a4, p4]
    else:
        articulo = [a5, p5]
    pantalla = pygame.display.set_mode((576, 350))
    pygame.display.set_caption("Subasta Inglesa")
    fondo = pygame.image.load("subasta1.png")
    fondo2 = pygame.image.load("subasta2.png")
    pantalla.blit(fondo, (0, 0))
    pygame.display.update()
    fuente = pygame.font.Font(None, 50)
    fuente1 = pygame.font.Font(None, 40)
    pantalla.blit(fuente.render(articulo[0], True, (250, 250, 250)), (80, 20))
    pantalla.blit(fuente1.render("Precio inicial: $%d" % (articulo[1]), True, (250, 250, 250)), (210, 65))
    pygame.display.update()
    subasta()
    
    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                exit()
    

Resultados

Estamos satisfechos con los resultados obtenidos al realizar esta práctica, en un principio iniciamos la pŕactica con la idea de realizar el protocolo Contract Net, pero al no tener muy clara la idea, decidimos cambiarlo ya que el código no realizaba lo debido. Al cambiar a Subasta Inglesa pensamos que sería algo muy sencillo, pero al final resulto ser un poco complicado.

A continuación presentamos el video de la ejecución.

Video

Conclusiones 

Con esta práctica concluimos que este mecanismo es muy utilizado en la vida diaria,podría ayudar a cualquier persona que desee realizar una subasta, en el código se mostró el objeto a subastar, posteriormente se realizaron varias ofertas, y al final se escogió la oferta con el precio mayor. Tuvimos menor dificultad en desarrollar la subasta a comparación del contract net. 

3° Entrega - Agrupamiento

Introducción 
En esta práctica realizaremos un sistema adaptativo el cual relacionaremos con técnicas de sistemas inteligentes, hemos elegido la técnica de agrupamiento, la cual consiste en separar los elementos en grupos, los elementos de esos grupos deben de ser lo más similares posibles entre ellos.
Realizaremos un algoritmo clásico de agrupamiento, el algoritmo K-means. 

Objetivo 
Nuestro objetivo es aprender a utilizar la técnica de agrupamiento del algoritmo K-means, en el cual la idea principal es dar a el centroide de cada grupo ciertos vectores, los cuales serán comparados con los vectores de los animales que usaremos en esta práctica. Analizaremos cuales son los animales que son idénticos o similares a los centroides y ese centroide agrupará a los animales de la misma especie. El resultado que pretendemos obtener es que al analizar cada punto (animal) y compararlos con los centroides, se pueda agrupar cada especie con su centroide correspondiente, teniendo este las mismas características de la especie. 

Justificación 
En clase se vio este tema y llamó nuestra atención. A los integrantes del equipo se nos facilitó el aprendizaje de este algoritmo, por consiguiente decidimos realizar esta técnica en nuestra práctica.
Estuvimos investigando y nos pareció interesante conocer más sobre este tema ya que hay muchas áreas en las cuales se puede aplicar esta técnica.
La única diferencia en nuestro programa a lo visto en clase es que las especies de animales y centroides tienen ciertos vectores (características) ya establecidos, así que el centroide agrupará a la especie que tenga las mismas características que él, no como lo visto en clase que el centroide agrupaba a los puntos más cercanos a él.

Desarrollo
En un inicio estábamos confundidos con respecto al agrupamiento de las especies que queríamos realizar, pero pudimos aclarar las dudas. Empezamos en primer lugar a generar ideas, anotar lo que se nos ocurría que podía servir para el programa, después de tener la idea algo clara de como sería el código, pensamos en que animales usaríamos para agrupar, decidimos que serían cuyos, perros y serpientes, buscamos algunas imágenes que pudieran servir, las convertimos a .png y cambiamos su tamaño para que se viera bien en el programa. Seguido de esto empezamos con la codificación, primero poniendo cada imagen con un botón o tecla distinta, los cuyos se insertan con el mouse (click izquierdo), los perros con la tecla "P" y las serpientes con la letra "S". A cada animal le dimos sus características basadas en 0's y 1's, al igual que los centroides.
Tuvimos que hacer modificaciones en el código debido a que las listas en las cuales estaban incluidas las coordenadas de los animales y sus vectores, causaban ciertos problemas, pero con un poco de paciencia se pudieron resolver.
Aplicamos la formula del k-means que es la sumatoria de los puntos que son iguales al centroide, sumamos las x's y las dividimos entre el total de estas, hicimos lo mismo con las y's, así pudimos agrupar a las distintas especies.
Al final se nos ocurrió unir el centroide con las especies agrupadas para poder apreciar mejor cual era el grupo que se había formado con el centroide.

Código

# usr/bin/python

import pygame
import time
import random

ancho = 1000
alto = 700

#         Mamifero - Domestico - Carnivoro - Grande - Cola - Colmillos
# Cuyo       1           1           0          0       0        0        [1, 1, 0, 0, 0, 0]
# Perro      1           1           1          1       1        1        [1, 1, 1, 1, 1, 1]
# Serpientes 0           0           1          0       1        1        [0, 0, 1, 0, 1, 1]

if __name__ == "__main__":
    # Declaramos la pantalla con todas sus imagenes y agregamos la imagen
    pantalla = pygame.display.set_mode((ancho, alto))
    pygame.display.set_caption("Agrupamiento")
    zacate = pygame.image.load("Zacate.jpg")
    casa_cuyo = pygame.image.load("puntoazul.png")
    casa_perro = pygame.image.load("puntorojo.png")
    casa_serpiente = pygame.image.load("puntoamarillo.png")
    pantalla.blit(zacate, (0, 0))
    pygame.display.update()
    # Declaramos los vectores de los cuyos y de los perros
    vector_cuyo = [1, 1, 0, 0, 0, 0] # Centroide cuyo
    vector_perro = [1, 1, 1, 1, 1, 1] # Centroide perro
    vector_serpiente = [0, 0, 1, 0, 1, 1] # Centroide serpiente
    posicion = []
    lista = []
    vector = []
    coordenadas = []
    cuyos_x = []
    cuyos_y = []
    perros_x = []
    perros_y = []
    serpientes_x = []
    serpientes_y = []
    x = 0

    #Pedimos cual es la cantidad de los animales que se van a agregar
    cantidad = input("Cuantos animales en total desea agregar? ")
    print cantidad
    i = cantidad 
    
    # Ciclo para poner los animalitos en su posicion
    while i > 0:
        time.sleep(0.1)
        
        # La imagen de los cuyos, de los perros y de las serpientes es aleatoria
        cuyos = random.randint(1, 6)
        if cuyos == 1:
            cuyo = pygame.image.load("cuyo1.png")
        elif cuyos == 2:
            cuyo = pygame.image.load("cuyo2.png")
        elif cuyos == 3:
            cuyo = pygame.image.load("cuyo3.png")
        elif cuyos == 4:
            cuyo = pygame.image.load("cuyo4.png")
        elif cuyos == 5:
            cuyo = pygame.image.load("cuyo5.png")
        else:
            cuyo = pygame.image.load("cuyo6.png")

        perros = random.randint(1, 6)
        #Aquí van las imagenes de los perros

        serpiente = random.randint(1, 5)
        #Aquí van las imagenes de las serpientes

       # Actividad del mouse o los botones del teclado
        for event in pygame.event.get():
            # Mouse
            if event.type == pygame.MOUSEBUTTONDOWN:
                vector = [1, 1, 0, 0, 0, 0]
                pos_x, pos_y = pygame.mouse.get_pos()
                print "presionando"
                coordenada_x = [pos_x]
                coordenada_y = [pos_y]
                # Se comparan los vectores para saber que animal es y se agregan a una lista
                if vector == vector_cuyo:
                    lista.append(vector)
                    lista.append(coordenada_x)
                    lista.append(coordenada_y)
                # Se agrega la imagen
                pantalla.blit(cuyo, (pos_x - 25, pos_y - 15))
                pygame.display.update()
                i -= 1
                print i
                print lista
                x += 1

            # Teclado 
            if event.type == pygame.KEYDOWN:

                #Perros
                if event.key == pygame.K_p:
                    vector = [1, 1, 1, 1, 1, 1]
                    pos_x, pos_y = pygame.mouse.get_pos()
                    #Se hace lo mismo que con los cuyos

                #Serpientes
                if event.key == pygame.K_s:
                    vector = [0, 0, 1, 0, 1, 1]
                    pos_x, pos_y = pygame.mouse.get_pos()
                    #Se hace lo mismo que con los cuyos 

            if event.type == pygame.QUIT:
                exit()
    
    # Separamos los diferentes valores guardados en la lista, aqui se encuentran los vectores y las coordenadas
    vectores = lista[0::3]
    coordenada_x = lista[1::3]
    coordenada_y = lista[2::3]
    print "Vectores: ", vectores
    print "Coordenada x: ", coordenada_x
    print "Coordenada y: ", coordenada_y

    an = 0
    en = 0
    iin = 0
    largo = len(vectores)
    for i in range (largo):
        if vectores[i] == vector_cuyo:
            #print "Cuyos x: ", coordenada_x[i]
            a = coordenada_x[i]
            cuyos_x.append(a)
            b = coordenada_y[i]
            cuyos_y.append(b)
            #print "Cuyos x: ", a
            #print "Cuyos y: ", coordenada_y[i]
            cuyos_x[en] = int("".join(str(x) for x in a))
            print "Cuyos_x: ", cuyos_x # Se guardan las coordenadas de x de cada uno de los cuyos
            cuyos_y[en] = int("".join(str(x) for x in b))
            print "Cuyos_y: ", cuyos_y # Se guardan las coordenadas de y de cada uno de los cuyos
            print en
            en += 1
        if vectores[i] == vector_perro:
            #Lo mismo que con los cuyos

        if vectores[i] == vector_serpiente:
            #Lo mismo que con los cuyos

    suma_cuyos_x = 0
    suma_cuyos_y = 0
    promedio_cuyo_x = 0
    promedio_cuyo_y = 0
   
    
    # Calculamos el promedio de las coordenadas en x y en y para los cuyos
    for i in range (len(cuyos_x)):
        suma_cuyos_x = suma_cuyos_x + cuyos_x[i]
        promedio_cuyo_x = suma_cuyos_x / len(cuyos_x)
        suma_cuyos_y = suma_cuyos_y + cuyos_y[i]
        promedio_cuyo_y = suma_cuyos_y / len(cuyos_y)
        
    print "Promedio cuyos x: ", promedio_cuyo_x
    print "Promedio cuyos y: ", promedio_cuyo_y

    # Calculamos el promedio de las coordenadas en x y en y para los perros
    
    
    # Calculamos el promedio de las coordenadas en x y en y para las serpientes
    
    # Se agregan las lineas que unen a los cuyos
    linea1 = []
    for j in range (len(cuyos_x)):
        linea1 = [cuyos_x[j], cuyos_y[j]]
        linea = pygame.draw.line(pantalla, (0, 5, 250), linea1, (promedio_cuyo_x, promedio_cuyo_y), 3)

    # Se agregan las lineas que unen a los perros
    
    # Se agregan las lineas que unen a las serpientes     

    # Se agregan los centroides
    pantalla.blit(casa_cuyo, (promedio_cuyo_x - 10, promedio_cuyo_y - 10))
    pantalla.blit(casa_perro, (promedio_perros_x - 10, promedio_perros_y - 10))
    pantalla.blit(casa_serpiente, (promedio_serpientes_x - 10, promedio_serpientes_y - 10))
    pygame.display.update()

    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                exit()

Resultados
Pudimos hacer que el programa mostrara una unión entre los animales similares y su respectivo centroide, cada grupo con un diferente color en las líneas que los unen al centroide. También teníamos la simple idea de usar puntos en una gráfica, pero vimos que podíamos hacerlo más atractivo y empleamos imágenes de los distintos animales.
Nos sentimos muy conformes con el programa ya que resultó ser más de lo que esperábamos.

Video

Conclusiones
Aprendimos sobre las diferentes aplicaciones donde se puede usar la técnica del agrupamiento. Gracias a las bases del agrupamiento se pueden realizar programas los cuales puedan detectar el cáncer, agrupar y clasificar diferentes elementos por sus características, entre otras.

Referencias
Página de la Dra. Sara Elena
Dibujar líneas con Pygame

2° Entrega - Autómatas Celulares

Introducción

Definido con nuestras palabras, un autómata celular es un conjunto de elementos que evolucionan mediante reglas o condiciones previamente definidas.

Se utilizan para representar los cambios en un sistema (natural o artificial).

Objetivo

Representar los cambios o generaciones de un conjunto de células (en nuestro caso las llamamos "genes"), implementando todas las reglas de los autómatas celulares (0-255).

Justificación

En un inicio nos interesó el tema de Swarm Intelligence y pensamos en desarrollar un código que simulara el comportamiento de una comunidad de roedores, pero debido al corto tiempo que teníamos, cambiamos de idea y decidimos cambiar a autómatas celulares.

 

Desarrollo

Al tener el tema definido comenzamos a generar una lluvia de ideas entre los integrantes del equipo para tener clara la lógica del programa y nos dimos cuenta que era posible inlcuir todas las reglas y no sólo limitarnos a 4.

Después de mucho pensar, anotar nuestras ideas en la libreta y tener bien clara la idea del algoritmo que se implementaría en el código, empezamos con la codificación, haciendolo paso a paso para no cometer errores.

Convirtiendo cada regla a binario y haciendo un chequeo del conjunto de genes pudimos crear la siguiente generación y cambiando la nueva generación por la anterior pudimos generar las iteraciones deseadas por el equipo.

Nos pareció adecuado dar la opción al usuario de crear genes aleatorios o que él mismo incluyera la cantidad de genes que desee y la posición de cada uno.

Cada vez que se corre el programa se aplican colores diferentes (random) a los genes.

Se uso el lenguaje de programación Python con su libreria Pygame para la interfaz gráfica.

Código

#! usr/bin/python/

# Importamos las librerías necesarias para correr el programa
import pygame
import random

# Declaramos las variables globales que son el alto y el ancho
de la ventana y los valores iniciales de X y Y
ancho = 1360
alto = 710
x = 5
y = 5

# Funcion automata
def automata(regla, i, genesNuevos, genes, opcion):
    if i == 0:
        if opcion != 2:
            for i in range (272):
                generarGenes = random.randint(0, 1)
                if generarGenes == 0:
                    genes[i] = 0
                else:
                    genes[i] = 1

        for i in range (272):
            if genes[i] == 1:
                screen.blit(cuadro, ((x*i) -5, 0))
        print
        print genes
        
    else:
        for i in range (272):
            genes[i] = genesNuevos[i]

    # Aqui se evaluan la ultima y las primeras dos posiciones de la cadena 
    lista1 = genes[i],genes[i-271],genes[i-270]
    cadena1 = "".join(str(x) for x in lista1)
    binario1 = int(cadena1, 2)
    genesNuevos[0] = int(regla[(binario1 + 1) * -1])
    
    # Si la cadena contiene un elemento se coloca el cuadrito en la posicion
    if genesNuevos[0] == 1:
        screen.blit(cuadro, (x*i, y))
        pygame.display.update()

    for i in range (270):
         # Aqui se evaluan todas las posiciones, a excepcion de la primera y la ultima

    # Aqui se evaluan las ultimas dos posiciones y la primera

    print genesNuevos

# Funcion principal
if __name__ == "__main__":
    # Se declaran la cadena de genes por defecto (llena de ceros)

    # Hacemos un pequeño menu para que el usuario eliga entre la opcion de generar una cadena de valores aleatoria o ingresar la cantidad y posicion de genes manualmente
    print "Generar genes de manera aleatoria -> 1"
    print "Agregar genes manualmente         -> 2"
    opcion = input("Opcion: ")
    if opcion == 2:
        opcion2 = input("Cuantos desea agregar? ")
        for i in range (opcion2):
            opcion3 = input("Posicion: ")
            genes[opcion3] = 1
    else:
        for i in range (272):
            generarGenes = random.randint(0, 1)
            if generarGenes == 0:
                genes[i] = 0
            else:
                genes[i] = 1
    
    # El usuario ingresa la regla deseada y si es mayor que 255 o menor que 0 el programa manda un aviso de error y se cierra
    regla = input('Regla: ')
    if (regla > 255) or (regla < 0):
        print 'Solo se pueden reglas de la 0 a la 255'
        exit()
    
    # Convertimos la regla en un numero binario
    print regla
    
    # Creamos la pantalla
    screen = pygame.display.set_mode((ancho, alto))
    pygame.display.set_caption("Automatas celulares")
    
    # Se elige el color de los cuadritos de manera aleatoria (tenemos 8 imagenes, con 8 colores diferentes)
    colores = random.randint(1, 8)
    if colores == 1:
        cuadro = pygame.image.load("1a.png")
    # Aqui van las demas condiciones de los cuadritos
    
    # Se crean las nuevas generaciones    
    for i in range (143):
        automata(regla, i, genesNuevos, genes, opcion)
        pygame.display.update()
        y += 5
    
    # Funcion para cerrar la ventana
    while True:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                exit()

 

Resultados

Tuvimos resultados muy satisfactorios a comparación con las expectativas que teníamos a un inicio. Nuestro código tiene mucho menos líneas que las que hubiera tenido con nuestra idea inicial de implementar sólo 4 reglas.
Regla 99:

 Regla 90:

Video

Conclusiones

Nos pareció excelente el cambio del tema y la solución que le dimos a nuestro programa de autómatas celulares, estamos muy conformes con el resultado.

Aprendimos nuevos métodos en el lenguaje de programación que utilizamos.

Referencias

Autómatas Celulares - Wikipedia
Algunas reglas de los Autómatas Celulares