Evolución Genética En Hardware

[Mars Attacks]

 Sacado de 3dpoder:

Una matriz de puertas programable en campo (Field Programmable Gate Array, o FPGA), es un tipo especial de placa de circuito con una matriz de celdas lógicas, cada una de las cuales puede actuar como cualquier tipo de puerta lógica, interconectado con conexiones flexibles que pueden conectar celdas. Estas dos funciones se controlan por software, así que simplemente cargando un programa especial en la placa, puede alterarse al vuelo para realizar las funciones de cualquier dispositivo de hardware de la amplia variedad existente.

El Dr. Adrian Thompson ha explotado este dispositivo, en conjunción con los principios de la evolución, para producir un prototipo de circuito reconocedor de voz que puede distinguir y responder a órdenes habladas utilizando sólo 37 puertas lógicas -una tarea que se habría considerado imposible para cualquier ingeniero humano. Generó cadenas aleatorias de bits de ceros y unos y las utilizó como configuraciones de la FPGA, seleccionando los individuos más aptos de cada generación, reproduciéndolos y mutándolos aleatoriamente, intercambiando secciones de su código y pasándolo hacia la siguiente ronda de selección. Su objetivo era evolucionar un dispositivo que pudiera en principio discriminar entre tonos de frecuencias distintas (1 y 10 kilohercios), y luego distinguir entre las palabras habladas ``go'' (adelante) y ``stop'' (para).

Su objetivo se alcanzó en 3.000 generaciones, pero el éxito fue mayor de lo que había anticipado. El sistema que evolucionó utilizaba muchas menos celdas que cualquier cosa que pudiera haber diseñado un ingeniero humano, y ni siquiera necesita del componente más crítico de los sistemas diseñados por humanos -un reloj. ¿Cómo funcionaba? Thompson no tiene ni idea, aunque ha rastreado la señal de entrada a través de un complejo sistema de bucles realimentados del circuito evolucionado. De hecho, de las 37 puertas lógicas que utiliza el producto final, cinco de ellas ni siquiera están conectadas al resto del circuito de ninguna manera -pero si se les retira la alimentación eléctrica, el circuito deja de funcionar. Parece que la evolución ha explotado algún sutil efecto electromagnético de estas celdas para alcanzar su solución, pero el funcionamiento exacto de la compleja e intrincada estructura evolucionada sigue siendo un misterio (Davidson 1997[19])

Si queréis leer más sobre evolución genética en hardware: http://the-geek.org/docs/algen/

[seryu]

 Resumen: pajas mentales de un tio que ha leido demasiado las teorias del relojero invidente.

[TheAzazel]

 Muy interesante el articulo :)

por cierto, eso del hardware es cierto? porque parece de coña jeje

[ethernet]

 Conociendo FPGA's y los sistemas de reconocimiento de voz solo me queda decir que para discriminar entre un tono de 1khz y 10 khz no necesitas más que 10 o 12 multiplicaciones y alguna suma, esto es, dos filtros y una comparación, y eso haciendolo bien, si lo haces sabiendo que pueden llegar solo dos tonos seguro que es mucho más simple.

Lo del efeto electromagnético es algo que me ha dejado boquiabierto, sobretodo teniendo en cuenta que las FPGA trabajan con señales digitales y más aún sabiendo que están integradas y que el campo electromagnético que puede generar una de esas celdas que está creada con unos cuantos transistores es imposible que afecte a otras partes del circuíto, incluso a otras celdas de la misma FPGA.

De todas maneras hay que reconocer que la historia mola XD

[Vicente]

 Tendríais que ver que otras cosas hacen los genéticos aplicados a hardware: una vez los pusieron a diseñar una antena, y salió una antena que era la caña, pero que a nadie en su sano juicio se le habría ocurrido así ;) Si encuntro alguna imagen la pongo. Un saludo!

Vicente

[Warchief]

Tendríais que ver que otras cosas hacen los genéticos aplicados a hardware: una vez los pusieron a diseñar una antena, y salió una antena que era la caña, pero que a nadie en su sano juicio se le habría ocurrido así ;) Si encuntro alguna imagen la pongo. Un saludo!

Vicente

Está en el enlace de Mars:

[zupervaca]

 Mas fuerza bruta <_<

[Vicente]

Mas fuerza bruta <_<

Te refieres a que al genético al final es una búsqueda por fuerza bruta? Un saludo!

Vicente

[zupervaca]

 Por lo que he visto por el momento basicamente es eso, ya que se van probando combinaciones (mutaciones) hasta que se obtiene un mejor resultado, no obstante esta claro que despues existen formas de descartar resultados de forma rapida sin tener que calcularlos.
PD: Pongo en negrita eso por que realmente no he visto mas algortimos que de este tipo que menciono.

Editado: Lo gracioso es que en la vida real aprendemos tambien por fuerza bruta, si el cuadrado no encaja en el circulo apretamos hasta que lo rompemos :D  

[Vicente]

 Hola,

no son fuerza bruta. Los algoritmos genéticos funcionan siguiendo una cosa que se llama "Teoría de Esquemas".

Un genético utiliza dos operadores posibles para conseguir una solución: un operador de cruce de que saca de dos genomas padres uno nuevo hijo, y el operador de mutación que modifica los valores de algunos genes de un genoma. La probabilidad de un cruce suele ser bastante alta, mientras que la mutación suele se suele poner muy baja (un individuo de toda la población o algo así). El genético principalmente busca por cruce, la mutación le ayuda a evitar atrancarse en mínimos locales o le permitir acceder a posiciones del espacio de búsqueda a las que su composición inicial de individuos no tendría acceso.

Muchas veces si que se combinan con métodos de búsqueda local (ascenso o descenso por gradiente por ejemplo) para cuando ya has acotado la búsqueda a una zona, usar la búsqueda local que seguramente será más rápida.

Otra cosa que tiene que ver con como búsca un genético es la presión del algoritmo: un algoritmo genético pone la presión selectiva en el cruce de progenitores (quienes son los genomas que tienen derecho a reproducirse), mientras que una estrategia evolutiva pone la presión selectiva en la supervivencia (quienes son los individuos que sobreviven de una generación a otra).

Esta claro que si solo buscaran por mutación, serían como dices una cuestion de fuerza bruta, pero hacen más cosas ;) Un saludo!

Vicente

[zupervaca]

 Antes de nada hablo sin saber mucho sobre el tema, con lo que puedo estar metiendo la pata.

Cuando lei un poco el tema de geneticos habia entendido que la teoria de esquemas era una metodologia en la cual te daban varios patrones o soluciones para realizar las menores combinaciones (generaciones) para obtener el resultado mas optimo (superviviente), al final a mi todo esto me parecen busquedas que se van generando a base de probar combinaciones, no obstante lo dicho, despues existen metodos para evitar probar combinaciones inutiles mediante la metodologia de la teoria de esquemas, pero basicamente creo que ir probando combinaciones (aunque sean las minimas) es fuerza bruta.

Al final la conclusion que saque es que los geneticos consisten en realizar busquedas con uno u otro algoritmo.

[Vicente]

 Hola,

a ver, fuerza bruta es cuando buscas sin nada que dirija la búsqueda, simplemente pruebas al azar donde cada posible solución tiene las mismas posibilidades de ser probada. Un A* no es fuerza bruta de un camino, tiene una heurística que dirige la búsqueda. En un genético a cada genoma se le asigna un fitness que representa su calidad como solución. Normalmente solo sobreviven las soluciones que tu consideras mejores y esas son las que tienen derecho a generar soluciones nuevas. No buscas al azar por el espacio de búsqueda, tienes un criterio. Por eso no es fuerza bruta.

Los genéticos son otra forma de buscar cosas, valen para ciertos problemas, y para otros no. Suelen usarse mucho por ejemplo para buscar los mejores parámetros de otro algoritmo (incluido de otro genético).

No se si esto te convence más. Un saludo!

Vicente

[zupervaca]

 Oki, entonces lo que tenia mal en la cabeza era la definicion de fuerza bruta, por lo que entiendo de tu ultimo post. ¿?

[Vicente]

 Creo que sip, o al menos eso es lo que yo entiendo por fuerza bruta (por ejemplo, en criptografía probar todas las claves una detrás de otra para romper un cifrado, cada clave tiene la misma probabilidad). Un saludo!

Vicente

[GeuS]

 eso de fuerza bruta es relativo, así que queda muy en el aire. Ordenes de complejidad mejor
A* es exponencial respecto el tamaño de su espacio de estados, aunque tiene muy buen comportamiento respecto a un backtraking, si aumentamos mucho el espacio de estados, por bueno que sea ya sabemos que pasa. Un algoritmo genético es de orden polinomico. Aunque nunca tendrás la certeza de tener la mejor solución.

Esa página la ví hace bastante tiempo y he hecho algo con AG, realmente me resulta sorpendente que funcionen.

En mi opinión aunque no me fiaría de ella para aportar soluciones en tiempo de ejecución, en tiempo de diseño puede ser una gran herramienta.

Saludos.