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/
Resumen: pajas mentales de un tio que ha leido demasiado las teorias del relojero invidente.
Muy interesante el articulo :)
por cierto, eso del hardware es cierto? porque parece de coña jeje
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
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
Cita de: "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
Está en el enlace de Mars:
(http://the-geek.org/docs/algen/genantenna.jpg)
Mas fuerza bruta <_<
Cita de: "zupervaca"Mas fuerza bruta <_<
Te refieres a que al genético al final es una búsqueda por fuerza bruta? Un saludo!
Vicente
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
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
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.
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
Oki, entonces lo que tenia mal en la cabeza era la definicion de fuerza bruta, por lo que entiendo de tu ultimo post. ¿?
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
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.
Cita de: "GeuS"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.
Hola,
yo por ejemplo en mi tesis investigo las aplicaciones en tiempo real, un buen punto de comienzo es buscar cosas de rtNEAT (redes neuronales evolutivas). Usan un genético en "tiempo real" (se elimina el concepto de generación y tal, la evolución es un poco más curiosa). Aunque está claro que cuando tienen muuucho tiempo para buscar la solución dan mucho mejores resultados.
Un saludo!
Vicente
Mars Attacks Citar
... ¿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...
Un genetico no hace milagros, es una buena tecnica, pero esto que se dice aqui, no tiene mucho sentido, salvo que el FPGA este mal construido.
GeuS Citar
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.
Los geneticos se han llegado a usar hasta para la navegacion de un robot a traves de circuitos, o sea que si que tienen aplicación a problemas que requieren una respuesta en tiempo real.
La verdad es que la naturaleza siempre termina por sorprendernos aportando formas de hacer las cosas. Los algoritmos genéticos son solo un ejemplo de esto, existen mas, como los OCH (Optimizacion por Colonias de Hormigas) que son una tecnica aproximada para obtener soluciones buenas en espacios de busquedas complejos y que estan basados en como las hormigas encuentran el camino sino optimo, si al menos bueno desde el hormiguero a la comida y viceversa.
Por cierto: creo que existe una sección de IA para todos estos temas... :)
Un saludo.
CitarLa verdad es que la naturaleza siempre termina por sorprendernos aportando formas de hacer las cosas
Mas que la naturaleza, creo que es la forma en que la percibimos ya que nuestro cerebro es el que interpreta lo que llega por los sentidos ;), podemos estar viendo lo mismo en la naturaleza y en un algoritmo que la imite, pero que realmente esto no sea asi.
Por lo que he podido informarme (coincidí ayer en un banquete de boda con la "mesa friki": profesores de informática, gente que estudió teleco e ingeniería industrial, etc., y saqué el tema), esos resultados ya tienen tiempo y no son ni de lejos los más sorprendentes. Al parecer, mientras que en teoría (como dice ethernet), hay fuerzas electromagnéticas que no deberían llegar a influir, en la práctica resulta que sí lo hacen. No es un fallo del circuito ni nada de eso; de hecho, por lo que me contaron, una de las cosas que este hombre consiguió con este método (sobre el estudio de antenas) fue una radio... que no necesitaba antena. Tenía una de esas placas con sus componentes aislados y cosas raras, la electricidad entraba por un lado, y en un momento indeterminado, la señal de radio simplemente aparecía.
En su opinión (los de la mesa), parece una cuestión de aplicación de mecánica cuántica a un nivel más grande del que a priori se podría esperar que funcionara.
Que conste que antes de preguntar, estaba casi convencido de que era un hoax o una exageración de una noticia (uoh)
Una FPGA dadas unas entradas siempre obtiene las mismas salidas y además es un dispositivo digital. Si varía en función de las celdas que funcionan u otra cosa no es una FPGA, es una FPGA estropeada u otro tipo de HW. No es un tema de que pueda haber interacciones eletromagnéticas, no cabe esa premisa porque si las hay no afectarían al funcionamiento y si lo hacen volvemos al caso de una FPGA estropeada.
Estaría bien saber si el experimento es repetible con una FPGA en condiciones. En cualquier caso, que ocurra algo así porque la placa esté averiada... me recuerda a alguna de las historias asimovianas de robots con funcionalidades "extra" debidas a fallos :)
En fin, lamentablemente no tengo el tiempo que me gustaría para investigar a fondo el tema, voy de puto culo. Si alguien se aburre, no estaría de más que echara un vistazo a ver qué sale.