Algoritmos Genéticos

Buena os pongo otro post interesante (que le puede resultar útil a alquien y no quiero que se pierda) que he puesto en el mismo foro que el post anterior:

A mi me interesa bastante la IA como ya muchos sabreis :D. Hace tiempo que estudie el tema y mola mucho :D

Os dejo un código que hice hace tiempo, parece sencillo, pero tiene bastante teoría detras. Yo siempre uso Python para cacharrear y C++ para implementarlo en serio.

http://pastebin.com/Y0KxMg7X

El problema me lo invente. El objetivo del código:

– Resolver la ecuación: f(x) = A*x^2-4*x-1 . Es decir el coeficiente A es la única variable. B = -4 y C = -1

Teniendo en cuenta:
– f(-10) = 339
– f(0) = -1
– f(10) = 259

Mi idea inicial, era hacer el cromosomo A, B y C pero como tardaba mil años, limite B y C. Y el espacio de soluciones quedo así:

Cromosoma(randomClamp(-10000, 10000), -4, -1)

La solución es 3. Pero se trata de resolverla por AG en lugar de métodos analíticos.

Cada ejecución puede tardar más o menos, mi salida es:
Problema: f(x) = A*x^2-4*x-1 y 3 puntos. Calcular A:
Solucion A = 3.000040 – Con un Error de 0.000063 en 15620 generaciones
Presione una tecla para continuar . . .

Tarda unas 15000 generaciones(que son pocos segundos de computación) debido a que el espacio de soluciones es muy grande y la perturbación es de solo un 5%, por tanto muta relativamente despacio en un espacio muy grande. Una mutación muy grande es casi peor, porque se convierte en busqueda aleatoria pero es más probable que encuentre un optimo global, en cambio si tiene mutaciones pequeñas puede quedarse estancado en un óptimo local como el oso panda XD

Un saludo. Ricardo

 

Wiithon 1.1 publicado!

Actualizado: sábado, 21 de noviembre de 2009

Bueno por fin publicamos la nueva versión tras casi 5 meses desde el anuncio de la 1.0.
Para mi wiithon me ha aportado mucho en conocimientos, me he acostumbrado tras muchos años de SQL puro, el uso de bases de datos ORM. He aprendido la potencia del combo python + pygtk. He aprendido a crear paquetes deb que siguen las políticas de Debian. Crear manpages, hacerme un repositorio de paquetes, resolver conflictos de bazaar, subir paquetes, comprender los problemas de punteros en 32bits y 64 bits y por último, he aprendido a amar a los Makefiles y esa gran satisfacción de hacer cosas complejas de forma controlada y sencilla.

Sin más rollo os pongo un tutorial mucho más simplificado, si lo comparamos con el de la versión anterior:

1. Novedades
2. Características ya existentes
3. Reporte de bugs
4. Instalación
5. Actualización
6. Uso de Wiithon en Consola (CLI)
7. Descargar código fuente
8. Colaborar en Wiithon
9. Estado de traducción de Wiithon.
10. Team wiithon
11. Pantallazos

Wiithon 1.0 liberado!!

POST ANTICUADO, última versión wiithon: 1.1 https://blogricardo.wordpress.com/2009/11/20/wiithon-1-1-publicado/

Actualizado: martes, 28 de julio de 2009

Creo que ya es el momento de publicar esta versión de wiithon con un GUI basado en GTK. Un desarrollo que empeze en abril, (trás publicar wiithon 0.98) sin tener apenas expriencia en GTK, gracias a Jose Luis Segura(LK2) y Google, he aprendido lo sufuciente en GTK para llegar al punto en el que estamos.

Sin dar más vueltas os expongo ls partes que va a tener esta presentación:

1. Características
2. Descargas
3. Instalación
4. Ejecución
5. Actualización
6. Traducir wiithon
7. Agradecimientos.
8. Team wiithon
9. Screenshots

Script para generar diccionarios de fuerza bruta

Ultima modificación : miércoles, 10 de diciembre de 2009

Necesitaba abrir un pdf protegido por contraseña. Era un pdf con las notas de mi novia, y el cual el profesor se iba equivocado metiendo la contraseña y la pobre se iba a quedar todas las navidades sin saber la nota, asi que intentamos hacer fuerza bruta sobre el fichero, con exito.

Desarrolle un script en python que generara palabras de una longitud máxima a partir de un cadena que define un alfabeto. En mi ejemplo configuro las variables con estos valores:

LONGITUD = 6
ALFABETO = "abcdefghijklmnopqrstuvwxyz0123456789_-."

Generar todas las combinaciones posibles conlleva no solo considerar las de longitud 6, si no tambien las de longitud 5,4,3,2 e incluso 1. El alfabeto tiene 39 caracteres por tanto todas las combinaciones posibles son:

cálculo de combinaciones

Contraseñas de longitud mayor que 8 son muy costosas computacionalmente, por ello el script que he realizado me interesa que de mucha información de cuanto queda y cuanto lleva. En concreto 3 cosas:

• El porcentaje que lleva del total.
• Tiempo estimado restante (en horas, lo he puesto).
• Velocidad: en palabras generadas por segundo

Con el dual core de mi portatil a 2.2 Ghz y con el ejemplo que pongo de palabras de hasta 6 caracteres y un alfabeto de 39 caracteres, los tiempos son muy buenos (aunque queda pendiente el uso de paralelización por MPI o algo así):

• Velocidad media aprox: 610.000 palabras generadas / seg
• Tiempo total : 1 hora 50 min

A continuación os pasteo el script (abrir un gedit generarDiccionario ):