Python (programación de videojuegos con pygame IV)

Esta será la entrada en la que terminemos nuestro pequeño juego, nuestro remake de Pong, en esta ocasión le añadiremos texto para poner el sistema de puntuación de nuestro juego así como mostraré de manera sencilla la forma de introducir sonido en nuestro juego. Comencemos!!!
Para poder tener un marcador de puntos de nuestro juego, es necesario que modifiquemos nuestra clase Pala que teníamos anteriormente, el método que modificaremos será el método actualizar, al cual le modificaremos su firma de la función para que acepte un parámetro más, el parámetro puntos, el cual nos permitirá poder modificar en pantalla el marcador, así como introducir unas cuantas lineas de código para modificar el valor de la variable puntos, lo cual es muy bueno, ya que no será necesario modificar de manera abrupta el código que ya teníamos, solo modificaremos la firma de la función y añadiremos las siguientes líneas de código:

#cambiamos los parametros del metodo para anadirle los puntos
def actualizar ( self,time,pala ,pala_cpu,puntos):
    #cuando pase de largo aumentamos un punto como corresponda
    if self.rect.left <= 0:
        puntos[1]+=1
    if self.rect.right >= ANCHO:
        puntos[0]+=1
    return puntos

Las líneas anteriores solo las añadimos en la parte intermedia de nuestro método, así como la simple modificación de la firma del método y al final del mismo le añadimos la sentencia "return". 
Ahora crearemos otro método que nos permita manipular el texto que mostraremos en pantalla, así que el código es el siguiente:

#Metodo para manipular el texto que queremos mostrar en pantalla
#el cual creara un sprite y la regresara junto con su imagen recien 
#creada
def texto(texto, posicion_x, posicion_y, color=(255,255,255)):
    #Cargamos la fuente para mostrar en pantalla
    fuente = pygame.font.Font('images/17-years-ago.ttf',25)
    #el texto lo pasamos por la fuente elegida
    salida = pygame.font.Font.render(fuente,texto,1,color)
    #creamos un sprite para mostrarlo en pantalla
    salida_rect = salida.get_rect()
    #al sprite con el texto lo ponemos en una posicion 
    #dentro de la pantalla
    salida_rect.centerx = posicion_x
    salida_rect.centery = posicion_y
    return salida,salida_rect

Este código nos sirve para poder insertar texto en nuestro juego de manera sencilla.
Ahora, procederemos a modificar nuestro Game Loop, el cual nos servirá para poder actualizar en cada momento de la partida nuestra puntuación y así mostrarla en pantalla. Lo que haremos, será crear una lista que nos permitirá almacenar los puntos del jugador, así como el de la máquina, además de crear los sprites necesarios para mostrarlos en pantalla durante cada ciclo del juego, la modificación es muy sencilla, la cual es la siguiente (si quieren ver de manera completa el código, junto con los archivos de la fuente y el sonido,  click aquí):

#anadimos las siguientes lineas al metodo
def game_loop ():
    
    #creamos una lista para almacenar los puntos
 #de ambos jugadores
    puntos = [0,0]
    while True:  
        puntos = bola.actualizar(time,pala,pala_cpu,puntos)
        #creamos los sprites de los puntos del jugador
        puntos_jug, puntos_jug_rect = texto("Jugador Puntos: "+str(puntos[0]), 140, 40)
        #creamos los sprites de los puntos del cpu
        puntos_cpu, puntos_cpu_rect = texto("Maquina Puntos: "+str(puntos[1]), ANCHO-ANCHO/4,40)
        
        #actualizamos los puntos en pantalla
        pantalla.blit(puntos_jug,puntos_jug_rect)
        pantalla.blit(puntos_cpu,puntos_cpu_rect)

y así de sencillo hemos añadido nuestro marcador a pantalla. Ahora solo falta añadir el audio a nuestro juego, este audio será el que suene cuando la bola choque contra alguna de las paletas del juego, la modificación será en la clase Bola, está modificación es muy sencilla, la cual será ilustrada a continuación:

#modificar en las secciones indicadas
class Bola(pygame.sprite.Sprite) :
    def __init__ ( self ):
        #cargamos el audio de choque contra una pared o raqueta
        self.sound = pygame.mixer.Sound('audios/rebote.wav')        
    def actualizar ( self,time,pala ,pala_cpu,puntos):
        if pygame.sprite.collide_rect(self,pala) :
            self.speed[0] = -self.speed[0]
            self.rect.centerx += self.speed[0]*time
            #al chocar con las palas generar sonido
            self.sound.play()
        if pygame.sprite.collide_rect(self,pala_cpu) :
            self.speed[0] = -self.speed[0]
            self.rect.centerx += self.speed[0]*time
            #al chocar con las palas generar sonido
            self.sound.play()

Y así hemos añadido de manera sencilla el audio en nuestro juego, el cual no es fue muy difícil ¿verdad?
Entonces con esto hemos terminado nuestro pequeño remake del Pong, el cual se ve así:

Fue divertido hacer nuestro primer videojuego con python, y muy sencillo, con esto hemos terminado y como en el post anterior, el código desarrollado esta aquí.
¡Hasta la próxima!

Python (programación de videojuegos con pygame III)

Continuamos con el desarrollo de nuestro juego con python y su módulo pygame, en el post anterior creamos nuestro entorno del juego (la ventana), en esta ocasión cargaremos la interfaz gráfica en la pantalla, así como desarrollaremos el entorno del jugador (la pala) y el comportamiento de la bola en nuestro juego.
En nuestro código anterior le modificaremos para tener un método que nos permita maniobrar con imágenes, este soporte nos los brinda de manera parcial pygame, por lo que nuestro código a desarrollar es el siguiente:

#Metodo para cargar una imagen a nuestro juego 
#de manera semiautomatica
def cargar_imagen(nombre, transparent = False):
    """metodo para cargar una imagen dada su 
    ubicacion"""
    try:
        #intentamos cargar la imagen por su ubicacion
        #si no funciona mandamos un error
        imagen = pygame.image.load(nombre)
    except pygame.error, message:
        raise SystemExit, message
    #Optimizamos la calidad de la imagen, para
    #que esta no influya en de manera sustancial
    #en el consumo de recursos
    imagen = imagen.convert()
    if transparent:
        color = imagen.get_at((0,0))
        imagen.set_colorkey(color,RLEACCEL)
    return imagen

este método nos permite maniobrar de manera sencilla con las imágenes, para que veamos como funciona modificaremos nuestro método "Game_loop" para que nos cargue el fondo de pantalla para nuestro remake, antes de mostrar el código modificado, es necesario crear un directorio con el nombre images, donde pondremos los gráficos de nuestro juego (sprites), y la imagen a mostrar en el juego es la siguiente:

Ya que tenemos nuestra imagen base mostraré el código modificado, el cual es el siguiente:

#metodo que contiene a nuestro "Game Loop"
def game_loop ():
    #Creamos la ventana y la asignamos a una variable
    pantalla = pygame.display.set_mode((ANCHO,ALTO))
    #Le ponemos nombre a nuestra ventana
    pygame.display.set_caption("Remake de pong")
    #cargamos la imagen y la almacenamos en una variable
    fondo = cargar_imagen('images/fondo_pong.png')
    while True:  
        for eventos in pygame.event.get():
            if eventos.type == QUIT:
                sys.exit(0)
        #anadimos la imagen a la pantalla
        pantalla.blit(fondo,(0,0))
        #actualizamos la pantalla
        pygame.display.flip()
    return 0

Ya que tenemos modificado a nuestro archivo, lo ejecutamos y vemos el resultado de nuestra modificación, el cual se asemejará a ésta imagen:

¡Bien! Ahora nuestra aplicación se va asemejando cada vez al clásico Pong, por lo que ahora crearemos a la pala del jugador y a la bola de juego, para esto los desarrollaremos como clases que permitirán crear un conjunto de instancias de clases para nuestros propósitos, los cuales son el desarrollar la pala y la bola. Las imágenes de la pala y la bola son las siguientes, de igual forma las almacenaremos en el directorio images.

El código de la clase Pala es la siguiente:

#Clase Pala, esta es usada tanto para el jugador, como 
#por la computadora para poder jugar
class Pala(pygame.sprite.Sprite) :
    """Clase Pala: hereda atributos directamente de la clase 
    Sprite, que se encuentra en el paquete pygame.sprite"""

    #Metodo constructor de la clase, el parametro self es utilizada
    #por todos los metodos de cualquier clase, y el parametro
    #centerx es para indicarle a que altura del eje x iniciaremos a nuestra 
    #pala (esta es una analogia con el plano cartesiano)
    def __init__ ( self, centerx ):

        #inicializamos al metodo constructor de nuestra clase padre
        pygame.sprite.Sprite.__init__(self)
        
        #cargamos la imagen de la pala y la guardamos en una variable
        self.image = cargar_imagen("images/pala.png")
        
        #esta variable nos sirve para poder interactuar con los elementos
        #dentro de nuestro juego
        self.rect = self.image.get_rect()
        
        #indicamos la altura en el eje x
        self.rect.centerx = centerx
        
        #indicamos de manera default donde estara en el eje Y
        self.rect.centery = ALTO / 2
        
        #velocidad usada cuando apretemos una tecla
        self.speed = 0.5

    #metodo que permitira manipular a la pala
    def mover ( self, time, keys ):
        
        #las siguientes condicionales nos permitiran
        #que nuestra pala se mueva y ademas no se salgan
        # de la pantalla
        if self.rect.top >= 0 :
            if keys[K_UP] :
                self.rect.centery -= self.speed * time
        if self.rect.bottom <= ALTO:
            if keys[K_DOWN] :
                self.rect.centery += self.speed * time

    #Metodo que controlara nuestra computadora de manera automatica
    #es decir, la inteligencia artificial de nuestro oponente
    def ia( self, time, ball ):
        #Estas condicionales sirven para detectar el movimiento de 
        #la bola y entonces poder realizar una accion
        if ball.speed[0] >= 0 and ball.rect.centerx >= ANCHO/2 :
            if self.rect.centery < ball.rect.centery :
                self.rect.centery += self.speed*time
            if self.rect.centery > ball.rect.centery :
                self.rect.centery -= self.speed*time

El código anterior es el nuestra pala y como poder moverla en nuestro juego, así como la inteligencia artificial sencilla que nos permite crear un oponente controlado por computadora.
El siguiente código va a ser el de nuestra bola, que se moverá tal y como lo hacía en aquel entrañable juego que era el Pong

#Clase Bola, la cual permite tener una bola que se mueve de manera natural 
#en el juego
class Bola(pygame.sprite.Sprite) :
    """Clase Bola: hereda atributos directamente de la clase 
    Sprite, que se encuentra en el modulo pygame.sprite"""
    
    #Metodo constructor de la bola, no tiene ningun parametro
    def __init__ ( self ):
        #cargamos la imagen y la almacenamos en una variable
        self.image = cargar_imagen("images/ball.png",True)
        #esta variable nos sirve para poder interactuar con los 
        #elementos dentro del juego
        self.rect = self.image.get_rect()
        #lugar de inicio por default
        self.rect.centerx = ANCHO/2
        self.rect.centery =  ALTO/2
        #velocidad utilizada para desplazarse en los dos ejes
        self.speed = [0.5,0.5]

    #Este metodo funciona para actualizar en pantalla los elementos de 
    #de nuestro juego
    def actualizar ( self,time,pala ,pala_cpu):
        #actualizando la posicion de la bola en pantalla
        self.rect.centerx += self.speed[0]*time
        self.rect.centery += self.speed[1]*time
        
        #cambiar la posicion de la bola al chocar con las paredes
        if self.rect.left <= 0 or self.rect.right >=ANCHO :
            self.speed[0] = -self.speed[0]
            self.rect.centerx += self.speed[0] * time   
        if self.rect.top <= 0 or self.rect.bottom >= ALTO :
            self.speed[1] = -self.speed[1]
            self.rect.centery += self.speed[1]*time
            
        #cambiar la posicion de la bola al colisionar con alguna de 
        #de las palas
        if pygame.sprite.collide_rect(self,pala) :
            self.speed[0] = -self.speed[0]
            self.rect.centerx += self.speed[0]*time
        if pygame.sprite.collide_rect(self,pala_cpu) :
            self.speed[0] = -self.speed[0]
            self.rect.centerx += self.speed[0]*time

El código anterior, nos muestra de manera sencilla como se mueve de manera autónoma la bola sin necesidad de interferir el usuario. Y finalmente para poder utilizarlos en nuestro juego, volvemos a modificar el método "Game_loop", la modificación es la siguiente:

#metodo que contiene a nuestro "Game Loop"
def game_loop ():
    #Creamos la ventana y la asignamos a una variable
    pantalla = pygame.display.set_mode((ANCHO,ALTO))
    #Le ponemos nombre a nuestra ventana
    pygame.display.set_caption("Remake de pong")
    #cargamos la imagen y la almacenamos en una variable
    fondo = cargar_imagen('images/fondo_pong.png')
    #creamos una instancia de la clase Bola
    bola = Bola()
    #Ahora creamos dos instancias de la clase pala: una para
    #el usuario y otra para el computador
    pala = Pala(30)
    pala_cpu = Pala(ANCHO-30)
    #creamos una instancia de Clock para evitar que nuestro juego 
    #sobrepase una cantidad de frames preestablecidos
    clock = pygame.time.Clock()
    while True:  
        #igual que la variable clock, creamos otra para la limitacion
        #de los frames en pantalla
        time = clock.tick(60)
        #creamos una variable para almacenar las teclas presionadas
        #en cada momento del juego
        keys = pygame.key.get_pressed()
        for eventos in pygame.event.get():
            if eventos.type == QUIT:
                sys.exit(0)
        #actualizamos los datos del juego en cada uno de los ciclos
        #del juego
        bola.actualizar(time,pala,pala_cpu)
        pala.mover(time,keys)
        pala_cpu.ia(time,bola)
        #anadimos la imagen y demas elementos a la pantalla
        pantalla.blit(fondo,(0,0))
        pantalla.blit(bola.image,bola.rect)
        pantalla.blit(pala.image,pala.rect)
        pantalla.blit(pala_cpu.image,pala_cpu.rect)
        #actualizamos la pantalla
        pygame.display.flip()
    return 0

La apariencia resultante es la siguiente:

Con esto ya tenemos jugable nuestro pequeño programa, pero aún falta introducir texto en pantalla para mostrar la puntuación de cada uno de los jugadores y posiblemente introducirle sonido, por lo que hoy terminamos con esto y en el próximo post le enseñaré como introducir el texto en pantalla y el sonido de manera sencilla para que terminemos nuestro remake del Pong. Hasta la próxima :).

Nota: el código que hoy hicimos, así como las imágenes las podrán descargar desde aquí.

Python (programación de videojuegos con pygame II)

Continuaremos con nuestro pequeño trabajo sobre como desarrollar un videojuego sencillo en python con la ayuda del módulo pygame, entonces el juego que haremos será un remake del clásico pong.
Antes de iniciar es necesario tener instalado pygame en nuestro sistema, si eres usuario linux con una distribución Ubuntu, la forma de instalarlo en nuestro sistema es la siguiente:

sudo apt-get install python-pygame

Y si eres usuario windows puedes darle click aquí, y escoger la versión de pygame de acuerdo con la versión de python que estés utilizando.

Bueno continuando con el desarrollo del videojuego, podemos iniciar de manera sencilla creando un script de python, por ejemplo, "pong.py", el cual contendrá lo siguiente:

#! /usr/bin/env python
import sys, pygame
from pygame.locals import *

#Constantes para nuestra ventana que crearemos
ALTO = 480
ANCHO = 640

#metodo que contiene a nuestro "Game Loop"
def game_loop ():
    #Creamos la ventana y la asignamos a una variable
    screen = pygame.display.set_mode((ANCHO,ALTO))
    #Le ponemos nombre a nuestra ventana
    pygame.display.set_caption("Remake de pong")
    while True:  
        for eventos in pygame.event.get():
            if eventos.type == QUIT:
                sys.exit(0)


if __name__ == '__main__':
    pygame.init()
    game_loop()

Con esto crearemos el entorno del juego (la ventana), la cuál se verá como la siguiente:

y con el sencillo script de arriba hemos creado nuestra ventana que contendrá a nuestro juego.
En el siguiente post les mostraré como añadirle imágenes a nuestro juego y crearemos a nuestros primeros personajes del juego: la pelota y la pala de juego.

Python (programación de videojuegos con pygame)

Bien, hoy programaremos un videojuego sencillo con python, utilizando un módulo que permite la creación de videojuegos en dos dimensiones cuyo nombre es “pygame”. Pygame permite desarrollar y prototipar rápidamente videojuegos en 2 dimensiones, además de ser una interfaz para SDL (Simple Direct Layer) orientada para el dibujado en 2D.

Antes de iniciar a programar nuestro primer videojuego en python, es necesario conocer como está estructurada la anatomía de un videojuego, que nos servirá como referencia para poder desarrollar nuestro videojuego en pygame.
Un videojuego se compone de la siguientes características:

• Entrada:
  Claramente un videojuego necesita comunicarse con el usuario de alguna manera, esto será a través de un dispositivo de entrada como un joystick o un teclado.

• Visualización:
  Esta característica tiene que ver con la capacidad de transmitir el estado interno del videojuego a una salida gráfica. Ya sea que el videojuego sea en 2D o 3D, esta característica es importante, ya que, a partir de ella será fundamental el que sea agradable visualmente al jugador. Para este pequeño tutorial será en 2D, dadas las características de programación con las que trabajamos (el módulo pygame solo trabajo con Sprites en 2 dimensiones).
  
  
• Sonido:
  Esta característica también es muy importante, ya que el audio proporcionado al jugador le transmitirá un conjunto de sensaciones que le permitirán determinar si el juego es agradable o no (pygame proveé un conjunto de herramientas para trabajar con audio de manera sencilla).
  
  
• Comunicaciones:
  Actualmente los juegos en línea y más los juegos sociales van ganando más adeptos dentro del mercado de los videojuegos. Normalmente los videojuegos en línea utilizan comunicación TCP/IP, lo cual permite que juguemos con otras personas en nuestra red local o que se encuentra en otros lugares del globo. Como pygame está basado como una interfaz de SDL, nos permite maniobrar con este tipo de cosas, pero este tema sale de nuestro pequeño tutorial.
  
  
• Game loop:
  Esta característica, tal como su nombre indica, es la que realiza el ciclo del juego y se encarga de realizar las actividades antes mencionadas. En la figura siguiente se muestra de manera sencilla como es que está estructurado el “Game Loop”.

Ya que hemos analizado como es que funciona un videojuego, procederemos a realizar el videojuego prometido. El videojuego que haremos será el clásico pong, el cual realizaremos en python, pero para eso lo empezaremos a hacer en el siguiente post, en el cual ya nos dedicaremos directamente a programar en python junto con el módulo pygame.

El algoritmo genético simple (AGS)

En el libro Mathematical Foundations of Programming, Holland propone una manera de seleccionar individuos y de cruzarlos. Actualmente existen muchas otras propuestas, pero las de Holland constituyen aún hoy la base de muchos desarrollos teóricos y prácticos en el área. Goldberg en "On Computable Numbres with Application to the Entscheidungsproblem" publicado en Proceedings of the London Mathematical Society, retomó el algoritmo de Holland y lo popularizó llamándolo algoritmo genético simple (AGS). En éste se considera que los códigos genéticos están en binario. Explicado con detalle el proceso de un AGS es:

1. Decidir cómo codificar el dominio del problema.
2. Generar un conjunto aleatorio (población inicial) de N posibles soluciones codificadas al problema. A ésta se le llamará la población actual.
3. Calificar cada posible solución (individuo) de la población actual.
4. Seleccionar dos individuos de la población actual con una probabilidad proporcional a su calificación.
5. Lanzar una moneda al aire (con probabilidad pc cae cara).
6. Su cayó cara mezclar los códigos de los dos individuos seleccionados para formar dos híbridos, a los que llamaremos nuevos individuos.
7. Si cayó cruz llamamos a los individuos seleccionados nuevos individuos.
8. Por cada bit de cada nuevo individuo lanzar otra moneda al aire (con probabilidad pm cae cara).
9. Si cae cara cambiar el bit en turno por su complemento.
10. Si cae cruz el bit permanece inalterado.
11. Incluir a los dos nuevos individuos en una nueva población.
12. Si la nueva población tiene ya N individuos, llamarla población actual y regresar al paso 3, a menos que se cumpla alguna condición de terminación.
13. Si no, regresar al paso 4.

En el algoritmo se utiliza el término "lanzar una moneda al aire" para decir un experimento de Bernoulli (aquel en el que pueden ocurrir exclusivamente dos eventos posibles, uno con probabilidad p y otro con probabilidad 1-p). Es decir, el lanzamiento de una moneda "extraña" en la que no necesariamente ambas caras son equiprobables.

La condición de terminación, a la que se hace referencia en el paseo 12, puede definirse de muchas maneras. Se puede fijar un número máximo de generaciones que se pretende ejecutar el algoritmo, o puede decidirse hacer alto cuando la mayoría de la población, digamos el %85, tenga una calificación que este dentro de 0.6 desviaciones estándar de la media. En fin, opciones hay muchas. Generalmente depende del problema o de las preferencias personales la decisión acerca de cuándo es conveniente detenerse.

Algoritmos genéticos parte III

Cruzamiento.

En el contexto de los algoritmos genéticos reproducirse significa que, dados dos individuos seleccionados en función de su grado de adaptación, éstos pasen a formar parte de la siguiente generación o, al menos, mezclen sus códigos genéticos para generar hijos que posean un código híbrido. Es decir, los códigos genéticos de los individuos se cruzan. Existen muchos mecanismos de cruzamiento todos ellos tienen por objeto que el código de un individuo A y el de un individuo B, previamente seleccionados, se mezclen, es decir, se fragmenten y recombinen para formar nuevos individuos con la esperanza de que éstos hereden de sus progenitores las características deseables. El mecanismo de cruzamiento más común es el llamado cruzamiento de un punto.

Mutación.

Algunas veces, muy pocas de hecho, la ADN-polimerasa (la enzima encargada de replicar el código genético), se equivoca y produce una mutación, una alteración accidental en el código genético de los seres vivos.

Ocasionalmente algunos elementos del código de ciertos individuos de un algoritmo genético se alteran a propósito. Éstos se seleccionan aleatoriamente en lo que constituye el símil de una mutación. El objetivo es generar nuevos individuos, que exploren regiones del dominio del problema que probablemente no se han visitado aún. Esta exploración no presupone conocimiento alguno, no es sesgada. Aleatoriamente se buscan nuevas soluciones posibles que quizá superen las encontradas hasta el momento. Esta es una de las características que hacen aplicables los algoritmos genéticos a gran variedad de problemas: no presuponer conocimiento previo acerca del problema a resolver ni de su dominio, no sólo en la mutación sino en el proceso total. De hecho, el problema a resolver sólo determina la función de evaluación y la manera de codificar las soluciones posibles (la semántica de los códigos genéticos de los individuos). El resto de los subprocesos que constituyen el algoritmo son independientes y universalmente aplicables.

Algoritmos genéticos parte II

Evaluación de la población

Al igual que en la naturaleza, en los algoritmos genéticos es necesario establecer algún criterio que permita decidir cuáles de las soluciones propuestas en una población son mejores respecto del resto de las propuestas y cuáles no lo son. Es necesario establecer, para cada individuo, una medida de desempeño relativa a la población a la que pertenece.

Para determinar cuáles de estos individuos corresponden a buenas propuestas de solución y cuáles no, es necesario calificarlos de alguna manera. Cada individuo de cada generación de un algoritmo genético recibe una calificación o, para usar el término biológico, una medida de su grado de adaptación (fitness). Éste es un número real no negativo tanto más grande cuanto mejor sea la solución propuesta por dicho individuo. El objetivo de este número es que permita distinguir propuestas de solución buenas de aquellas que no lo son. Si el problema a resolver consiste en maximizar una función, entonces la calificación asignada a un individuo determinado debe indicar que tan alto es el valor de la función en el elemento de su dominio codificado por el individuo. Si, en cambio, el problema es determinar la ruta más corta entre dos puntos, la calificación deberá ser tanto más alta cuanto más corto sea el camino codificado en el individuo que esté siendo calificado.

Evidentemente, al hablar de que a cada individuo de la población se le asigna una y sólo una calificación, se está hablando de una función que se denomina función de adaptación, cuya evaluación puede no ser sencilla y es, de hecho, lo que en la mayoría de los casos consume más tiempo en la ejecución de un algoritmo genético. Hay que tener en cuenta que se evalúa una vez en cada individuo de cada generación. Si un AG es ejecutado con una población de tamaño 1000 durante 100 generaciones, la función es evaluada 10,000 veces. Además, puede darse el caso de que la función de evaluación no tenga una regla de correspondencia explícita, esto es, una expresión algebraica, y puede ocurrir incluso que la función cambie de generación en generación.

Selección.

Una vez calificados todos los individuos de una generación, el algoritmo debe, al igual que lo hacen la naturaleza y el hombre, seleccionar a los individuos más calificados, mejor adaptados al medio, para que tengan mayor oportunidad de reproducción. De esta forma se incrementa la probabilidad de tener individuos "buenos" (con alta calificación) en el futuro. Si de una determinada generación de individuos se seleccionaran sólo aquellos con una calificación mayor o igual que cierto número c para pasarlos a la siguiente generación, es claro que en ésta la calificación promedio superará c y por tanto al promedio de la generación anterior. La selección ocasiona que haya más individuos buenos, explota el conocimiento que se ha obtenido hasta el momento, procurando elegir lo mejor que se haya encontrado, elevando así el nivel de adaptación de toda la población.

En principio podría parecer que es conveniente tener una estrategia de selección estricta para que mejore rápidamente la población y converja el algoritmo, es decir, que la población se acumule alrededor de una genotipo óptimo. Esto no es cierto. Lo que ocurrirá es que la población se acumulará rápidamente alrededor de algún individuo que sea bueno, comparativamente con el resto de los individuos considerados a lo largo de la ejecución del algoritmo, pero este individuo puede no ser el mejor posible. A esto se le suele llamar convergencia prematura. No se puede asegurar pero sí procurar que lo anterior no ocurra. Además de la explotación es necesario que exista exploración. El AG debe, no sólo seleccionar de entre lo mejor que ha encontrado, sino procurar encontrar mejores individuos. A esto se dedican los operadores que serán descritos a continuación, los que aseguran que en todo momento exista cierto grado de variedad en la población, procurando con ello que no se "vicie".

En la estrategia de selección normalmente se incluye un elemento extra que sirve de "ancla". Si sólo se hace selección forzando que sea más probable elegir al mejor individuo de la población pero sin asegurarlo, es posible que este individuo se pierda y no forme parte de la siguiente generación. Para evitar lo anterior se fuerza la selección de los mejores n individuos de la generación para pasar intactos a la siguiente. A esta estrategia se le denomina elitismo y puede ser generalizada especificando que permanezcan en la población los n mejores individuos de las pasadas k generaciones.

Algoritmos genéticos

Un poco de biología.

Cada individuo de cada una de las especias que habitan en nuestro planeta poseen ciertas características que lo identifican. Si hablamos de seres humanos, cada uno posee cierta estatura, cierto color de ojos y de cabello y cierto tipo sanguíneo, entre otras muchas. Estas características "externas", aunque algunas de ellas no se puedan ver, como el tipo sanguíneo, constituyen lo que se denomina el fenotipo de un individuo. Cada una de estas características es igual a la correspondiente de alguno de los antecesores del individuo, es decir, nos son dadas por herencia, o por lo menos nos es dada cierta predisposición a ella (como la diabetes, por ejemplo). El fenotipo es resultado de la interacción del medio ambiente en que se desarrolla un individuo y la herencia que éste recibe de sus ancestros. La herencia impone ciertos límites o predisposiciones que, al sumarse con el medio, generan el fenotipo. A veces el medio no importa, por ejemplo, no puede intervenir en nuestro color de ojos (hasta donde mi conocimiento sabe), pero en otras influye de manera determinante. Si se posee cierta predisposición a padecer enfermedades cardiovasculares pero se tiene una excelente condición aeróbica desde pequeño, posiblemente éstas nunca se padezcan. El fenotipo de cada individuo está determinado por las proteínas que produce, y esto a su vez está definido en la información genética de cada una de sus células.

La información acerca de cuáles proteínas se producirán está contenida en los cromosomas del individuo. En cada célula somática (aquellas que constituyen el organismo) existen dos juegos de cromosomas que definen las mismas características; un juego es aportado del padre del individuo y el otro lo es de la madre. Un ser humano posee 23 pares de cromosomas.

Hay células especiales llamadas gametos, que intervienen en la reproducción (los espermatozoides y los óvulos humanos pertenecen a esta categoría). Los gametos no se reproducen por mitosis como el resto de las células, el proceso de división se llama en este caso meiosis. En la mitosis las ćelulas producidas son diploides, mientras que en la meiosis el resultado, los gametos, son haploides, sólo tienen un juego de cromosomas.

Partiendo de una célula diploide el proceso meiótico se realiza de la siguiente manera:

1. Se duplica el número de cromosomas en la célula, esto es, se hace una copia de cada cromosoma. Al final quedan dos juegos correspondientes al padre y dos a la madre.
2. Se cruzan un juego de cromosomas del padre con uno de la madre, formándose dos juegos de cromosomas híbridos. El resultado es un juego de cromosomas puros del padre, un juego puro de la madre y dos juegos de cromosomas híbridos.
3. Se divide la célula dos veces y al final del proceso quedan cuatro células haploides: una con cromosomas puros del padre, una con cromosomas puros de la madre y dos con cromosomas híbridos.

Algoritmos genéticos.

En la naturaleza las características de los seres vivos, incluso aquéllas que los hacen óptimos para habitar en su medio, están determinadas por las proteínas que producen. A su vez, como hemos visto, estas proteínas (o más bien, los aminoácidos que las forman) se codifican en el material genético contenido en cada una de las células del individuo. Así pues, la naturaleza ha mapeado cada posible solución al problema de crear un individuo óptimo en una secuencia particular de bases que producirá ciertas proteínas, ha codificado el dominio del problema (todos los posibles individuos) mapeándolo al conjunto de todas las posibles secuencias de nucleótidos.

Así, para un algoritmo genético lo primero que se requiere es determinar en qué espacio se encuentran las posibles soluciones al problema que se pretende resolver. En caso de tener un problema de optimización de una función cuyo dominio es un subconjunto de los números reales, entonces este subconjunto es al que nos referimos. Pero el algoritmo opera sobre "códigos genéticos", sobre genotipos que se deberán mapear al espacio de soluciones. Es decir, es necesario codificar de alguna manera el dominio del problema para obtener estructuras manejables que puedan ser manipuladas por el AG (algoritmo genético). Cada una de estas estructuras constituye el equivalente al genotipo de un individuo en términos biológicos. El elemento del dominio del problema al que se mapea este genotipo es el análogo al fenotipo. Es frecuente que el código de los elementos del dominio del problema utilice un alfabeto binario (0 o 1).

Una vez que se ha definido la manera de codificar los elementos del dominio del problema y se conoce la forma de pasar de un elemento a su código y viceversa, es necesario fijar un punto de partida. Los algoritmos genéticos manipulan conjuntos de códigos en generaciones sucesivas. Nuevamente haciendo una analogía, manipulan poblaciones de códigos. En éstas un código puede aparecer más de una vez. El algoritmo se encargará de favorecer la aparición en la población de códigos que correspondan a elementos del dominio que estén próximos a resolver el problema. En resumen, el algoritmo recibirá como entrada una población de códigos y a partir de ésta generará nuevas poblaciones, donde algunos códigos desaparecerán mientras que otros, que se mapean en mejores soluciones posibles, aparecen con más frecuencia hasta que se encuentra una satisfactoria o hasta que se cumple alguna otra condición de terminación. Para establecer una base nemotécnica, los códigos en una población, es decir, los elementos de ésta serán llamados individuos y a los códigos en general, ya no en el contexto exclusivo de una población, se les denominará indistintamente cromosomas, genotipo, genoma o código genético, por analogía con los términos biológicos de donde surgen.

Computación evolutiva

¡Hola a todos!, esta es mi primera entrada en el blog de este año (ya se que es muy tarde pero no había tenido tiempo para escribir esta entrada), les traigo aquí unas notas que tomé de mi curso de computación evolutiva espero sean de su agrado.

La computación evolutiva constituye un conjunto de técnicas heurísticas utilizadas para resolver problemas de diversos tipos, en los que podemos encontrar comúnmente problemas de búsqueda y optimización. La característica principal de estos problemas es la gran cantidad de variables que pueden estar involucradas junto con un enorme espacio de posibles soluciones, a veces tan grande como el número de átomos que constituyen el universo.

Los mecanismos de estos algoritmos se inspiran en el proceso de la evolución biológica, se retoman conceptos como genotipo y fenotipo, los cuales son los principales componentes de la unidad fundamental "el individuo", y como motor de variabilidad se identifican procesos genéticos como la reproducción y la mutación, así como la adaptabilidad del individuo en su entorno.

Estas técnicas se han aplicado en distintas disciplinas y ramas del conocimiento desde aplicaciones en inteligencia artificial hasta problemas en ingeniería, debido a que es posible encontrar soluciones relativamente buenas en un periodo corto de tiempo.

Aquí les ofrezco una pequeña introducción a la computación evolutiva, donde les mostraré los fundamentos, teoría y aplicaciones de las principales técnicas evolutivas como son: los agoritmos genéticos, estrategias evolutivas, programación evolutiva y programación genética.

Python: trabajando con un entorno gráfico (wxPython)

Anteriormente les hablaba de python y sus ventajas, hoy les mostraré como hacer de manera sencilla una aplicación gráfica con python, solo que en esta ocasión nos le hablaré de la interfaz nativa de python que es el módulo Tkinter que permite realizar interfaces gráficas basadas en la biblioteca Tk, sino de otro binding cuyo nombre es wxPython, que proviene de la biblioteca gráfica wxWidgets; esta elección es porque Tkinter es demasiado básico, además de no utilizar bindings nativos del sistema, cosa que wxPython si hace.
WxPython trabaja muy bien en diversas plataformas generando el aspecto nativo de las GUI realizadas con él. El programa es el siguiente:

#! /usr/bin/python
import  wx, os 
#modulos para trabajar con el entorno 
#grafico y el sistema operativo
from wx.lib.wordwrap import wordwrap

#El mensaje de la licencia de nuestra aplicacion
licenceText = "Este es una muestra del poder de python XD"

#Tipo de archivos de ejemplo, estos son utilizados para
#filtrar por extension al momento de invocar "abrir un archivo"
wildcard = "Archivos de audio mp3 (*.mp3)|*.mp3|" \
     "Documento de Word (*.doc)|*.doc|"\
     "Todos los archivos(*.*)|*.*"


#Clase de nuestra ventana de ejemplo     
class MyFrame(wx.Frame):
 
 def __init__(self):
  """Esta tambien es otra forma de crear comentarios 
  utilizando varias lineas, equivaldria a /** ... */ en Java o C.
  Este es el metodo constructor que permite inicializar a nuestra 
  ventana, es el equivalente al constructor de Java"""
  
  #Llamamos a la clase Frame que construira nuestra ventana
  wx.Frame.__init__(self,None,-1,"Mi Ventana",size=(400,400))
  
  #El panel de nuestra ventana para poner botones y demas artilugios
  panel = wx.Panel(self,-1)
  
  #Un boton que mostrara un dialogo "Sobre..."
  b = wx.Button(panel,-1,"Hola Mundo!",(20,10))
  
  #integramaos el boton en la ventana
  self.Bind(wx.EVT_BUTTON,self.OnButton,b)
  
  #Otro boton que abrira un dialogo de abrir un archivo
  b = wx.Button(panel,-1,"Abrir algun archivo",(20,50))
  
  #igualmente integramos este boton al al panel
  self.Bind(wx.EVT_BUTTON,self.OnButton2,b)
  
 def OnButton(self,evt):
  """Metodo que reaccionara cuando presionemos el boton Hola Mundo!"""
  
  #Creamos el dialogo
  info = wx.AboutDialogInfo()
  
  #le ponemos nombre superior de nuestro dialogo
  info.Name = "Mi Ventana"
  
  #le asignamos la version de nuestra aplicacion
  info.Version = "1.0"
  
  #Un copyright
  info.Copyright = "(C) Copyright Miguel Pinia"
  
  #Una descripcion de nuestra aplicacion
  info.Description = wordwrap("Este es la informacion sobre la aplicacion: "
  "esta aplicacion fue hecha en"
  " python ", 350, wx.ClientDC(self))
  
  #Asignamos la licencia que creamos al principio del documento
  info.License = wordwrap(licenceText,500,wx.ClientDC(self))
  
  #Desarrolladores de la aplicacion
  #Nota: Vypi es una mascota XD
  info.Developers = ["Miguel Pinia","wxPython","Vypi la mascota"]
  
  #la que contendra nuestra informacion
  wx.AboutBox(info)
 def OnButton2(self,evt):
  """Este metodo reaccionara al presionar el boton "abrir" generando 
  un evento que permitira crear un dialogo de apertura a nuestro archivo, 
  claramente este archivo seleccionado no hara nada, ya que no vamos a trabajar
  sobre el, dado que esta es una aplicacion de ejemplo"""
  
  #Creamos el dialogo y lo mostramos
  dlg = wx.FileDialog(self,message="Escoga un archivo",defaultDir = os.getcwd(),defaultFile="",wildcard=wildcard ,style= wx.OPEN | wx.MULTIPLE | wx.CHANGE_DIR)
  
  #Si ya seleccionamos el archivo lo unico que haremos sera destruir el dialogo
  if dlg.ShowModal() == wx.ID_OK:
   dlg.Destroy
   
   
if __name__=="__main__":
 """Metodo main"""
 app = wx.App()
 
 #creamos un objeto de la clase myframe
 frame = MyFrame()
 
 #Lo mostramos hasta que algun evento ocurra
 frame.Show(True)
 app.MainLoop()

Con esto hemos generado una pequeña aplicación gráfica de manera sencilla, de hecho más rápido y sencillo que otras alternativas en otros lenguajes de programación como Java o C (de hecho, es más sencillo que programar en Swing con Java o GTK+ con C :P). Trabajar con python puede ser más sencillo y enriquecedor, si lo que queremos es aprender a programar. WxPython es muy sencillo de utilizar y muy bonito ver que funciona en las distintas plataformas que existen, para ilustrarlo pondre unas capturas de como trabaja en Windows XP y Ubuntu.


Windows.

Ubuntu:

Aquí es mostrada la apariencia nativa del mismo programa en Ubuntu, aqui se ve claramente que no hubo necesidad de cambiar el código original.
Antes de terminar, les pondré unos cuantos enlaces para mayor información:

• Python (Wikipedia)
• WxPython (Wikipedia)
• Página Oficial de wxPython (en Inglés)
• Organización de widgets en python (blog)

Con esto he terminado esta pequeña reseña sobre como trabajar gráficos en python.

Python

Hoy les hablaré de Python como lenguaje de programación y sus características, así como un pequeño programa realizado en él. Python es un lenguaje de programación de alto nivel y está orientado a tener una filosofía que hace hincapié en tener una sintaxis muy limpia y legible.
Es un lenguaje que puede ser considerado multiparadigma, ya que soporta programación orientada a objetos, programación imperativa y en menor medida programación funcional.Python fue diseñado para ser leído con facilidad. Entre otras cosas se utilizan palabras en inglés donde otros lenguajes utilizarían símbolos (por ejemplo, los operadores lógicos !, || y && que son de uso común en Java, en Python se escriben not, or y and, respectivamente).
Para ilustrar un poco la forma de uso de Python, escribiré un pequeño programa:

#! /usr/bin/python 

#La línea anterior sirve para indicarle
#donde se encuentra el intérprete en nuestro sistema
#mientras que estas son solo comentarios de nuestro programa

nombre = raw_input("Dame tu nombre\n")

print nombre, "¡Has escrito tu primer programa en Python!"

Guardamos nuestro programa en un documento con terminación .py, por ejemplo "miPrimerPrograma.py" y ejecutamos en la terminal de la siguiente manera:

python miPrimerPrograma.py

y mostrará en pantalla lo siguiente:

Dame tu nombre
Miguel
Miguel ¡Has escrito tu primer programa en Python!

Así de sencillo hemos hecho un primer programa en Python.
Ahora les explicare que hace cada una de las líneas; en la primera linea se indica la ubicación del intérprete, esto iniciando con "#!", que indica la ubicación. La líneas subsecuentes que inician con el símbolo "#" a solas, sirven para escribir comentarios sobre nuestro programa. Siguiendo con este orden, después tenemos a la línea que inicia con la variable "nombre", en  esta guardaremos lo que leamos de la entrada estándar, esta invocación para la lectura de teclado la hacemos con la función "raw_input()", para que así lo que escribamos se lo asignemos a la variable "nombre". Terminando con esto, imprimimos en la salida estándar lo que leímos junto con un mensaje de aliento por el trabajo que hemos hecho hasta ahora.
Con el programa anterior se muestra lo sencillo que es empezar a programar en python.

El proceso del software (finalizando)

Continuando con la breve explicación de lo que es el proceso del software, en este post terminaré con los otros pasos que conllevan el proceso.
Anteriormente había comentado sobre la especificación del problema y el análisis y el diseño del algoritmo, ahora, para terminar les hablaré sobre  los siguientes pasos:

• Implementación o construcción del modelo:
• En éste paso o etapa, debemos de pasar nuestro algoritmo a un lenguaje de programación que hayamos elegido. A esta etapa se le conoce codificación. Esta etapa no debería de resultar difícil si es que hemos realizado un diseño que siga la filosofía del lenguaje.
• Validación:
• En esta etapa lo que se hace es probar lo que nuestro programa debe de hacer en principio para lo que fue diseñado. Para esto se realizan pruebas informales, que consisten en presentarle al programa diversos conjuntos de datos y verificar que el programa hace lo que tiene que hacer. En este tipo de pruebas se deben también de incluir conjuntos de datos erróneos, para así verificar que el programa sabe que hacer que hacer en situaciones anómalas. En este caso, dependiendo del tipo de lenguaje que se este utilizando, se debe de lanzar algún tipo de excepción para gestionar el tipo de error causado en tiempo de ejecución.
• Mantenimiento:
• Actualmente, el mantenimiento de los programas y diversos sistemas es la actividad que mayor coste representa. El mantenimiento de nuestros programas se puede realizar de dos maneras:
• Mantenimiento correctivo:
• Este tipo de mantenimiento se da cuando hay situaciones o eventos que el programa o sistema no está resolviendo de manera adecuada.
• Mantenimiento extensivo:
• Este tipo de mantenimiento se refiere a extender las capacidades originales de nuestro programa o sistema, esto quiere decir, que nuestro programa o sistema debe regresarnos un conjunto adicional de resultados.
• Para poder realizar un buen mantenimiento, es necesario incluir una buena documentación de nuestro programa, en caso contrario, sería imposible extender nuestro programa o sistema.
• Extensión y refinamiento:
• Esta etapa la realizan personas distintas a las que diseñaron originalmente el programa o sistema. En este caso, cuando se realiza la extensión de los programas o sistemas, lo que se busca es tratar de “tapar un hoyo, sin realizar otro en el programa o sistema”,  esto es fácil de realizar si se tiene modularidad en el programa o sistema, ya que es fácil atacarlo por módulos. Además debe tener la propiedad de encapsulamiento, esto es, que cada módulo tenga perfectamente delimitado su campo de acción,  esto permite tener una mejor comunicación entre módulos de manera controlada.

Estas etapas no necesariamente son realizadas de manera secuencial, ya que un buen trabajo de hace de manera cíclica entre los diversos pasos, esto para tener un software bien asentado, además de que pueden surgir problemas que conlleven a regresar a pasos anteriores que impliquen regresar a pasos anteriores para resolver dicho problema. Insisto que un buen diseño y análisis permiten tener éxito en etapas posteriores, sin necesidad de rehacer todo nuestro trabajo.

El proceso del software (Análisis y diseño del algoritmo).

Análisis y diseño del algoritmo
Ahora que tenemos el enunciado del problema a resolver, así como las entradas con las que contamos y las salidas que deseamos, es necesario que tengamos un algoritmo que nos permita resolver nuestro problema y obtener los resultados que esperamos.
Para esto es necesario el modelar o elaborar un modelo que nos permita resolver nuestro problema. En más de una ocasión es probable que para llegar a nuestro objetivo se involucren una serie de pasos intermedios(estados de los datos), o más que ello, sea posible que necesitemos tener un cierto comportamiento para no tener un resultado concreto sino un resultado relativo que también nos sirve para nuestro objetivo. En el primer caso, me refiero a soluciones que necesitan ser inmediatos, como la impresión de un saludo en pantalla o resolver una operación aritmética, y, en el segundo caso, a cosas como los videojuegos o simulaciones (un reloj o un calendario por ejemplo).
A pesar de que depende del entorno de nuestro problema tendremos distintos tipos de soluciones que nos resolverán nuestro problema, cada solución tendrá distintas características propias de su entorno, pero, a pesar de ello todas las soluciones comparten un conjunto de características:

• La solución debe de ser correcta, eficiente y efectiva.

Lo de correcta, creo que no hay nada que explicar sobre la correctez de una solución, ya que es lo que se desea cuando se diseña dicha solución. Con respecto a la eficiencia, se puede tener una excepción, ya que puede que solo si estamos haciendo un programa que nos ayude para resolver un problema para calcular algo o para sacarnos de un problema momentáneo, es decir, un programa que se va utilizar por un breve tiempo.
La eficiencia es una parte fundamental de una solución, ya que no podemos desperdiciar recursos(memoria principal, tiempo de procesamiento, etc.) de manera descuidada, ya que en más de una ocasión una pequeña falta de eficiencia en nuestras soluciones puede hacer que falle toda nuestra aplicación y la "tire".
Por efectiva nos referimos al hecho de que produce el efecto esperado en conjunción con la correctez y la eficiencia del mismo. Actualmente los programas son tan grandes que resulta muy difícil que una sola persona los realice por su propia cuenta, así que se tiende a trabajar en equipos(esto de manera muy GENERAL), entonces se requiere que los programas sean:

• Modulares: esto quiere decir que se pueda dividir en varios pedazos (tener fronteras entre diversas partes que hagan su parte por separado), así para que las tareas se puedan repartir de manera eficiente.
• Bajo nivel de acoplamiento: Esto es, que tengan que recibir o utilizar lo menor posible del exterior y entreguen lo mínimo posible (esto es que haya muy poco tráfico  entre los módulos), de tal forma que puedan ser reutilizados por otros.
• Alta cohesión: aquí nos referimos al hecho de que todo lo que se encuentre relacionado (variables, métodos) se encuentren juntos, para que el programa sea fácil de entender y modificar.

Esto es lo básico del análisis y diseño del algoritmo, en el siguiente post seguiré con las demás etapas del proceso del software.

El proceso del software (especificación del problema).

Especificación del problema:
En la especificación del problema, se nos presenta el enunciado del problema a resolver, entonces debemos de entender el problema que tenemos que resolver, así como pedir toda la información necesaria que necesitemos para resolverlo, de tal manera que cuando nos encontremos en pasos posteriores del proceso de desarrollo, sea fácil y sin dificultad de entender lo que estamos desarrollando.
Dado que hemos entendido nuestro problema, es momento de determinar de donde partimos, es decir, con que entradas contamos para tratar de resolver nuestro problema, así como a donde queremos llegar (salidas deseadas, o resultados de nuestro problema).
En ésta etapa se tienen que tener bien claro los siguientes incisos:

• Enunciado preciso del problema.
• Entradas.
• Salidas.

Y con esto tenemos nuestra especificación del problema, lo cual nos llevará a la siguiente etapa que es el análisis y diseño del algoritmo que nos permiirá resolver el problema planteado.
En el siguiente post les hablaré sobre el "Análisis y diseño del algoritmo".