@ Jason: Gracias por sugerir eso de Google. Si bien parece ser algo útil, no veo cómo podría responder a esta pregunta, ya que se dirige específicamente a usuarios SO con experiencia GA / GP.
"Esperamos que las respuestas sean respaldadas por ... experiencia específica ..." ¡Compruebe! "[E] su pregunta probablemente requerirá debate, argumentos, encuestas o discusión extendida". Falso. Hay muchas respuestas, pero no es una encuesta y no hay muchos comentarios o debates en los comentarios. ¿Por qué se cerró esto?
Mi primer trabajo como programador profesional (1995) fue escribir un sistema de comercio automatizado basado en algoritmos genéticos para futuros S & P500. La aplicación fue escrita en Visual Basic 3 [!] Y no tengo idea de cómo hice algo en aquel entonces, ya que VB3 ni siquiera tenía clases.
La aplicación comenzó con una población de cadenas de longitud fija generadas aleatoriamente (la parte del "gen"), cada una de las cuales correspondía a una forma específica en los datos de precios minuto a minuto de los futuros S & P500, así como a un pedido específico (comprar o vender) y cantidades de stop-loss y stop-profit. Cada cadena (o "gen") tuvo su rendimiento de beneficios evaluado por una ejecución a través de 3 años de datos históricos; cada vez que la "forma" especificada coincidía con los datos históricos, asumía la orden de compra o venta correspondiente y evaluaba el resultado de la operación. Agregué la advertencia de que cada gen comenzó con una cantidad fija de dinero y, por lo tanto, podría quebrarse y eliminarse por completo del grupo de genes.
Después de cada evaluación de una población, los sobrevivientes fueron cruzados aleatoriamente (simplemente mezclando bits de dos padres), con la probabilidad de que un gen sea seleccionado como padre sea proporcional al beneficio que produjo. También agregué la posibilidad de mutaciones puntuales para condimentar un poco las cosas. Después de unos cientos de generaciones de esto, terminé con una población de genes que podrían convertir $ 5000 en un promedio de aproximadamente $ 10000 sin posibilidad de muerte / quiebra (en los datos históricos, por supuesto).
Desafortunadamente, nunca tuve la oportunidad de usar este sistema en vivo, ya que mi jefe perdió cerca de $ 100,000 en menos de 3 meses comerciando de la manera tradicional, y perdió su voluntad de continuar con el proyecto. En retrospectiva, creo que el sistema habría obtenido grandes ganancias, no porque necesariamente estuviera haciendo algo bien, sino porque la población de genes que produje estaba sesgada hacia las órdenes de compra (en lugar de las órdenes de venta) en aproximadamente un 5: 1 ratio. Y como sabemos con nuestra retrospectiva 20/20, el mercado subió un poco después de 1995.
"Creo que el sistema habría obtenido grandes ganancias" - sí, apuesto a que funcionó perfectamente en el entorno de backtesting ;-)
Joel
30
@ Joel: por supuesto que sí, pero no es por eso que creo que habría sido rentable. Habría ganado dinero debido al fuerte sesgo hacia la compra en lugar de vender. Un sistema que acaba de comprar futuros de S & P500 en momentos aleatorios entre 1995 y 1999 (sin ningún tipo de tonterías GA) habría generado toneladas de dinero, pero solo sabemos esto en retrospectiva.
MusiGenesis
10
Joel probablemente se refería a "sobreajuste".
Eric Normand
10
Debe reservar un poco de sus datos históricos para realizar pruebas. Lo mejor es hacer validación cruzada.
Eric Normand
¿Qué quieres decir con "forma" en each of which corresponded to a specific shape in the minute-by-minute price data?
CodyBugstein
89
Hice unas pequeñas criaturas que vivían en este pequeño mundo. Tenían un cerebro de red neuronal que recibió algunas entradas del mundo y la salida era un vector para el movimiento, entre otras acciones. Sus cerebros eran los "genes".
El programa comenzó con una población aleatoria de bichos con cerebros aleatorios. Las neuronas de entrada y salida eran estáticas, pero lo que estaba en medio no lo era.
El medio ambiente contenía alimentos y peligros. Los alimentos aumentan la energía y cuando tienes suficiente energía, puedes aparear. Los peligros reducirían la energía y si la energía fuera 0, morían.
Finalmente, las criaturas evolucionaron para moverse por el mundo y encontrar comida y evitar los peligros.
Entonces decidí hacer un pequeño experimento. Le di al cerebro de la criatura una neurona de salida llamada "boca" y una neurona de entrada llamada "oído". Comenzó de nuevo y se sorprendió al descubrir que evolucionaron para maximizar el espacio y cada criatura respectiva se quedaría en su parte respectiva (la comida se colocaba al azar). Aprendieron a cooperar entre sí y no interponerse en los demás. Siempre hubo excepciones.
Entonces probé algo interesante. Las criaturas muertas se convertirían en comida. ¡Intenta adivinar lo que pasó! Evolucionaron dos tipos de criaturas, las que atacaban como enjambres y las que evitaban mucho.
Entonces, ¿cuál es la lección aquí? La comunicación significa cooperación. Tan pronto como introduces un elemento en el que lastimar a otro significa que ganas algo, entonces la cooperación se destruye.
Me pregunto cómo se refleja esto en el sistema de libre mercado y capitalismo. Quiero decir, si las empresas pueden perjudicar a su competencia y salirse con la suya , entonces está claro que harán todo lo que esté en su poder para perjudicar a la competencia.
Editar:
Lo escribí en C ++ sin marcos. Escribí mi propia red neuronal y código GA. Eric, gracias por decir que es plausible. La gente generalmente no cree en los poderes de GA (aunque las limitaciones son obvias) hasta que juegan con él. GA es simple pero no simplista.
Para los que dudan, se ha demostrado que las redes neuronales pueden simular cualquier función si tienen más de una capa. GA es una forma bastante simple de navegar por un espacio de solución encontrando un mínimo local y potencialmente global. Combine GA con redes neuronales y tendrá una muy buena manera de encontrar funciones que encuentren soluciones aproximadas para problemas genéricos. Debido a que estamos usando redes neuronales, entonces estamos optimizando la función para algunas entradas, no algunas entradas para una función, ya que otras están usando GA
¿Y dónde está tu premio Turing para ir con esta historia? Debes haber tenido algunos avances locos en la ciencia para que tal experimento incluso se ejecute en cualquier cosa que no sea RoadRunner.
San Jacinto
1
De acuerdo con Eric. Puede escribir un NN simple en menos de una hora (y, de hecho, lo hice en un examen), y un GA básico no es necesariamente más de un día o dos de trabajo. Esto es más un algoritmo A-Life que un algoritmo genético, pero todavía estamos hablando de cosas muy simples y factibles aquí.
Kylotan
2
Esto no es falso en lo más mínimo ... Verano después de mi primer año, hice un proyecto para funsies muy similar a esto usando XNA en C #, menos las redes neuronales, los GA de uso y una población de criaturas con una miríada de rasgos diferentes. . Por ejemplo, un gen controlaba su visión: más alto significaba más visión, más bajo significaba un radio de visión más amplio. Los obstáculos y la comida se colocarían al azar, y las criaturas repondrían su energía al comer la comida. Los rasgos mutarían al agregarles números gaussianos generados aleatoriamente, lo que daría como resultado genes distribuidos normalmente como en la evolución real.
Philip Guin
2
Trabajo en un grupo de investigación donde este tipo de cosas (ALife) era lo que la gente hacía todos los días. Su historia es totalmente creíble, y para ser sincero, me sorprendió un poco ver que alguien pensaría que es falso. Por otra parte, por lo general, el objetivo de hacerlas es señalar que un comportamiento complejo puede surgir de sistemas muy simples; supongo que el punto no se ha hecho lo suficientemente bien.
Lucas
1
Encontré algunas pruebas en su sitio web: www.mempko.com/darcs/neural. Afirma que "proporcioné un buen ejemplo de pequeños hombres en un pequeño mundo, evolucionando para sobrevivir". Aquí está el código de ejemplo: mempko.com/darcs/neural/demos/eaters
guerda
51
En enero de 2004, me contactó Philips New Display Technologies, que estaba creando la electrónica para la primera tinta electrónica comercial, la Sony Librie, que solo había sido lanzada en Japón, años antes de que Amazon Kindle y los demás llegaran al mercado en los EE. UU. una Europa
Los ingenieros de Philips tuvieron un gran problema. Unos meses antes de que se suponía que el producto llegaría al mercado, todavía estaban apareciendo imágenes fantasma en la pantalla al cambiar de página. El problema eran los 200 controladores que creaban el campo electrostático. Cada uno de estos controladores tenía un cierto voltaje que tenía que establecerse entre cero y 1000 mV o algo así. Pero si cambiaras uno de ellos, cambiaría todo.
Por lo tanto, optimizar el voltaje de cada controlador individualmente estaba fuera de discusión. El número de posibles combinaciones de valores fue de miles de millones, y una cámara especial tardó aproximadamente 1 minuto en evaluar una sola combinación. Los ingenieros habían probado muchas técnicas de optimización estándar, pero nada se acercaba.
El ingeniero jefe se puso en contacto conmigo porque previamente había lanzado una biblioteca de programación genética a la comunidad de código abierto. Me preguntó si los GP / GA ayudarían y si podría involucrarme. Lo hice, y durante aproximadamente un mes trabajamos juntos, escribiendo y ajustando la biblioteca de GA, en datos sintéticos, y él integrándolo en su sistema. Luego, un fin de semana lo dejaron en vivo con lo real.
El lunes siguiente recibí estos brillantes correos electrónicos de él y su diseñador de hardware, sobre cómo nadie podía creer los sorprendentes resultados que encontró el GA. Esto fue. Más tarde ese año, el producto llegó al mercado.
No me pagaron ni un centavo por ello, pero obtuve derechos de 'alardear'. Dijeron desde el principio que ya estaban por encima del presupuesto, así que supe cuál era el trato antes de comenzar a trabajar en él. Y es una gran historia para aplicaciones de GA. :)
Lo del "sobre presupuesto" es falso. Por supuesto que tenían el dinero para pagarle, pero decidieron no hacerlo. Eso realmente apesta y muestra cómo las grandes empresas pueden aprovechar los buenos programadores.
Martin Capodici
50
Utilicé un GA para optimizar la asignación de asientos en la recepción de mi boda. 80 invitados en 10 mesas. La función de evaluación se basó en mantener a las personas con sus fechas, poner a las personas con algo en común y mantener a las personas con puntos de vista opuestos extremos en tablas separadas.
Lo corrí varias veces. Cada vez, obtuve nueve buenas mesas, y una con todas las bolas impares. Al final, mi esposa hizo las asignaciones de asientos.
El optimizador de mi vendedor ambulante usó un mapeo novedoso de cromosomas en el itinerario, lo que hizo trivial reproducir y mutar los cromosomas sin ningún riesgo de generar recorridos no válidos.
Actualizar : Porque un par de personas han preguntado cómo ...
Comience con una serie de invitados (o ciudades) en un orden arbitrario pero consistente, por ejemplo, alfabetizado. Llame a esto la solución de referencia. Piense en el índice de un invitado como su número de asiento.
En lugar de intentar codificar este orden directamente en el cromosoma, codificamos instrucciones para transformar la solución de referencia en una nueva solución. Específicamente, tratamos los cromosomas como listas de índices en la matriz para intercambiar. Para decodificar un cromosoma, comenzamos con la solución de referencia y aplicamos todos los intercambios indicados por el cromosoma. Intercambiar dos entradas en la matriz siempre da como resultado una solución válida: cada invitado (o ciudad) todavía aparece exactamente una vez.
Por lo tanto, los cromosomas se pueden generar aleatoriamente, mutar y cruzar con otros y siempre producirán una solución válida.
@Manuel: en lugar de codificar el recorrido directamente en el "cromosoma", codifiqué una transformación que convierte un recorrido de referencia en una solución. Las transformaciones son solo intercambios entre ciudades en el índice. Por lo tanto, pueden recombinarse de cualquier manera antigua y aún generar un recorrido que visita cada ciudad exactamente una vez.
Adrian McCarthy
¡Gracias! Estoy un poco confundido con el aspecto de intercambio. Cada cromosoma codifica una lista de índices para intercambiar, ¿no significa eso que un índice puede aparecer más de una vez en el cromosoma?
user3019612
1
El cromosoma tiene índices c1, c2, c3, ..., cn. "Solución" es la matriz a. Inicialice a con su lista de referencias. Luego, para cada par de índices en el cromosoma, intercambie dos elementos en la solución ( temp = a[c1]; a[c1] = a[c2]; a[c2] = temp). No importa si dos índices son idénticos, ya que un contendrá todos los invitados (o ciudades) exactamente una vez.
Adrian McCarthy
33
Utilicé algoritmos genéticos (así como algunas técnicas relacionadas) para determinar la mejor configuración para un sistema de gestión de riesgos que intentaba evitar que los productores de oro usaran tarjetas de crédito robadas para pagar los MMO. El sistema tomaría varios miles de transacciones con valores "conocidos" (fraude o no) y descubriría cuál era la mejor combinación de configuraciones para identificar adecuadamente las transacciones fraudulentas sin tener demasiados falsos positivos.
Teníamos datos sobre varias docenas de características (booleanas) de una transacción, cada una de las cuales recibió un valor y se totalizó. Si el total fue superior a un umbral, la transacción fue fraude. El GA crearía una gran cantidad de conjuntos de valores aleatorios, los evaluaría frente a un conjunto de datos conocidos, seleccionaría los que obtuvieran la mejor puntuación (tanto en la detección de fraude como en la limitación del número de falsos positivos), y luego cruzaría los mejores. cada generación para producir una nueva generación de candidatos. Después de un cierto número de generaciones, el mejor conjunto de valores de puntuación se consideró ganador.
Crear el corpus de datos conocidos para probar fue el talón de Aquiles del sistema. Si esperaba las devoluciones de cargo, se atrasaba varios meses cuando intentaba responder a los estafadores, por lo que alguien tendría que revisar manualmente un gran número de transacciones para generar ese corpus de datos sin tener que esperar demasiado.
Esto terminó identificando la gran mayoría del fraude que se produjo, pero no pudo llegar por debajo del 1% en los artículos más propensos al fraude (dado que el 90% de las transacciones entrantes podría ser fraude, eso estaba funcionando bastante bien).
Hice todo esto usando perl. Una ejecución del software en una caja de Linux bastante antigua tardaría de 1 a 2 horas en ejecutarse (20 minutos para cargar datos a través de un enlace WAN, el resto del tiempo dedicado a la compresión). El tamaño de cualquier generación dada estaba limitado por la RAM disponible. Lo ejecutaba una y otra vez con ligeros cambios en los parámetros, buscando un conjunto de resultados especialmente bueno.
En general, evitó algunos de los errores que surgieron al tratar de ajustar manualmente los valores relativos de docenas de indicadores de fraude, y siempre encontró mejores soluciones de las que podía crear a mano. AFAIK, todavía está en uso (aproximadamente 3 años después de que lo escribí).
Creo que podría haber usado una red neuronal para hacer el ajuste de parámetros (aunque tomaría más tiempo ser más efectivo que hacerlo a mano).
alexpinho98
21
Propinas de fútbol. Creé un sistema GA para predecir el resultado de los juegos semanales en la AFL (Aussie Rules Football).
Hace unos años me aburrí del billar de fútbol de trabajo estándar, todo el mundo estaba simplemente en línea y tomando las selecciones de algún experto en la prensa. Entonces, pensé que no podría ser demasiado difícil vencer a un grupo de grandes periodistas de transmisión, ¿verdad? Mi primer pensamiento fue tomar los resultados de Massey Ratings y luego revelar al final de la temporada mi estrategia después de ganar fama y gloria. Sin embargo, por razones que nunca he descubierto, Massey no rastrea AFL. El cínico en mí cree que se debe a que el resultado de cada juego de AFL se ha convertido básicamente en una posibilidad aleatoria, pero mis quejas de cambios recientes en las reglas pertenecen a un foro diferente.
El sistema básicamente consideraba la fuerza ofensiva, la fuerza defensiva, la ventaja de campo local, la mejora semanal (o la falta de ella) y la velocidad de los cambios en cada una de ellas. Esto creó un conjunto de ecuaciones polinómicas para cada equipo durante la temporada. Se podría calcular el ganador y la puntuación de cada partido para una fecha determinada. El objetivo era encontrar el conjunto de coeficientes que mejor se ajustaran al resultado de todos los juegos pasados y usar ese conjunto para predecir el juego de las próximas semanas.
En la práctica, el sistema encontraría soluciones que predecían con precisión más del 90% de los resultados de juegos anteriores. Luego elegiría con éxito alrededor del 60-80% de los juegos para la próxima semana (esa es la semana que no está en el conjunto de entrenamiento).
El resultado: justo por encima de la mitad del paquete. No hay grandes premios en efectivo ni un sistema que pueda usar para vencer a Las Vegas. Aunque fue divertido.
Construí todo desde cero, no utilicé ningún framework.
Además de algunos de los problemas comunes, como el vendedor ambulante y una variación del programa Mona Lisa de Roger Alsing , también he escrito un solucionador de Sudoku evolutivo (que requirió un poco más de pensamiento original de mi parte, en lugar de simplemente volver a implementar idea de otra persona). Existen algoritmos más confiables para resolver Sudokus, pero el enfoque evolutivo funciona bastante bien.
En los últimos días, he estado jugando con un programa evolutivo para encontrar "mazos fríos" para el póker después de ver este artículo en Reddit. No es del todo satisfactorio en este momento, pero creo que puedo mejorarlo.
Tengo mi propio marco que utilizo para algoritmos evolutivos.
Desarrollé un GA casero para un sistema de perfil de superficie láser 3D que mi compañía desarrolló para la industria de carga en 1992. El sistema se basaba en la triangulación tridimensional y utilizaba un escáner de línea láser personalizado, una cámara de 512x512 (con captura personalizada hw). ¡La distancia entre la cámara y el láser nunca iba a ser precisa y el punto focal de las cámaras no se encontraba en la posición de 256,256 que esperaba!
Fue una pesadilla tratar de resolver los parámetros de calibración utilizando geometría estándar y resolución de ecuaciones de estilo de recocido simulado.
El algoritmo genético fue creado en una tarde y creé un cubo de calibración para probarlo. Conocía las dimensiones del cubo con gran precisión y, por lo tanto, la idea era que mi GA pudiera desarrollar un conjunto de parámetros de triangulación personalizados para cada unidad de escaneo que superara las variaciones de producción.
El truco funcionó de maravilla. ¡Me quedé estupefacto por decir lo menos! ¡En alrededor de 10 generaciones, mi cubo 'virtual' (generado a partir del escaneo sin procesar y recreado a partir de los parámetros de calibración) realmente parecía un cubo! Después de alrededor de 50 generaciones tuve la calibración que necesitaba.
A menudo es difícil obtener una combinación de colores exacta cuando planea pintar su casa. A menudo, tiene algo de color en mente, pero no es uno de los colores, el vendedor le muestra.
Ayer, mi profesor, que es un investigador de GA, mencionó una historia real en Alemania (lo siento, no tengo más referencias, sí, puedo averiguarlo si alguien lo solicita). Este tipo (llamémosle el tipo de color ) solía ir de puerta en puerta para ayudar a las personas a encontrar el código de color exacto (en RGB ) que sería el armario para lo que el cliente tenía en mente. Así es como lo haría:
El tipo de color solía llevar consigo un programa de software que usaba GA. Solía comenzar con 4 colores diferentes, cada uno codificado como un cromosoma codificado (cuyo valor descodificado sería un valor RGB). El consumidor elige 1 de los 4 colores (que es el más cercano al que tiene en mente). El programa luego asignaría la aptitud física máxima a ese individuo y pasaría a la próxima generación usando mutación / cruce . ¡Los pasos anteriores se repetirían hasta que el consumidor encontrara el color exacto y luego el tipo de color solía decirle la combinación RGB!
Al asignar la aptitud física máxima al color se cierra a lo que el consumidor tiene en mente, el programa del tipo de color está aumentando las posibilidades de converger al color, el consumidor tiene en mente exactamente. ¡Lo encontré muy divertido!
Ahora que tengo un -1, si estás planeando más -1, por favor. dilucidar la razón para hacerlo!
No voy a rechazarte, pero supongo que es porque no lo hiciste tú mismo. El OP te pidió específicamente cosas que tú mismo habías hecho.
jprete
Esta es más o menos una versión simplificada de los biomorfos de Richard Dawkins.
Nick Johnson el
1
Lo curioso del color es que no puedes considerarlo solo. Los consultores de color no aparecen con un solo color: vienen en paletas y esquemas. No tiene sentido simplemente elegir un color por sí solo. No voté en contra, pero su respuesta es ampliar la definición de GA. ¿Cómo mutas / cruzas un color? Esto es más honestamente una demostración de reducir iterativamente un conjunto de datos limitado.
Kirk Broadhurst el
2
Esto tal vez explica los votos negativos: esto parece más una escalada, no GA.
Eric Normand
8
Hace un par de semanas, sugerí una solución en SO utilizando algoritmos genéticos para resolver un problema de diseño gráfico. Es un ejemplo de un problema de optimización restringido.
También en el área de aprendizaje automático, implementé un marco de reglas de clasificación basado en GA en c / c ++ desde cero.
También he usado GA en un proyecto de muestra para entrenar redes neuronales artificiales (ANN) en lugar de usar el famoso algoritmo de retropropagación .
Además, y como parte de mi investigación de posgrado, he usado GA en la capacitación de modelos ocultos de Markov como un enfoque adicional para el algoritmo Baum-Welch basado en EM (en c / c ++ nuevamente).
Hola amro ¿Hiciste una comparación completa entre los resultados obtenidos con backprop y GA? Si es así, ¿podría compartir los resultados de la comparación con nosotros? ¿Cómo implementó el paso cruzado para dos NN?
lmsasu
@lmsasu: nada lujoso: cada cadena o cromosoma en la población representa los valores de peso y sesgo de la red, y se usó un simple operador cruzado de 1 o 2 puntos. Por lo que recuerdo, la red tardó mucho tiempo en entrenarse con GA. Mi implementación fue más una prueba de concepto que cualquier otra cosa (vea aquí un ejemplo de juguete para controlar buscaminas virtuales) ... De todos modos, debería haber muchos documentos que discutan el uso de GA para no solo aprender los pesos, sino también evolucionar La estructura de la red.
Amro
8
Como parte de mi título universitario de CompSci, se nos asignó el problema de encontrar banderas jvm óptimas para la máquina virtual de investigación Jikes. Esto se evaluó utilizando el conjunto de pruebas Dicappo que devuelve un tiempo a la consola. Escribí un alogirthm genético distribuido que cambió estas banderas para mejorar el tiempo de ejecución de la suite de referencia, aunque tardó días en ejecutarse para compensar la fluctuación de hardware que afecta los resultados. El único problema fue que no aprendí adecuadamente sobre la teoría del compilador (que era la intención de la tarea).
Podría haber sembrado la población inicial con los indicadores predeterminados existentes, pero lo interesante fue que el algoritmo encontró una configuración muy similar al nivel de optimización de O3 (pero en realidad fue más rápido en muchas pruebas).
Editar: También escribí mi propio marco de algoritmo genético en Python para la tarea, y solo usé los comandos popen para ejecutar los diversos puntos de referencia, aunque si no fuera una tarea evaluada, habría analizado pyEvolve.
En primer lugar, "Programación genética" de Jonathan Koza ( en Amazon ) es prácticamente EL libro sobre algoritmos genéticos y evolutivos / técnicas de programación, con muchos ejemplos. Le recomiendo que lo revise.
En cuanto a mi propio uso de un algoritmo genético, utilicé un algoritmo genético (de cosecha propia) para desarrollar un algoritmo de enjambre para un escenario de recolección / destrucción de objetos (el propósito práctico podría haber sido limpiar un campo minado). Aquí hay un enlace al documento . La parte más interesante de lo que hice fue la función de estado físico de varias etapas, que era una necesidad ya que las funciones de estado físico simples no proporcionaban suficiente información para que el algoritmo genético diferenciara lo suficiente entre los miembros de la población.
La serie de Koza en GP es muy densa y tal vez no para alguien que es nuevo en GP. Sugeriría la Guía de campo de Riccardo Poli para la programación genética (disponible como copia html gratuita) o Una introducción a los algoritmos genéticos por Melanie Mitchell
Nadie el
7
Soy parte de un equipo que investiga el uso de la Computación Evolutiva (EC) para corregir automáticamente los errores en los programas existentes. Hemos reparado con éxito una serie de errores reales en proyectos de software del mundo real (consulte la página de inicio de este proyecto ).
Tenemos dos aplicaciones de esta técnica de reparación EC.
El primero (información de código y reproducción disponible a través de la página del proyecto ) desarrolla los árboles de sintaxis abstracta analizados a partir de los programas C existentes y se implementa en Ocaml utilizando nuestro propio motor EC personalizado.
El segundo (información de código y reproducción disponible a través de la página del proyecto ), mi contribución personal al proyecto, desarrolla el ensamblado x86 o el código de bytes Java compilado de programas escritos en varios lenguajes de programación. Esta aplicación se implementa en Clojure y también utiliza su propio motor EC personalizado.
Un buen aspecto de la computación evolutiva es la simplicidad de la técnica que hace posible escribir sus propias implementaciones personalizadas sin demasiada dificultad. Para un buen texto introductorio disponible gratuitamente sobre Programación Genética, vea la Guía de Campo para Programación Genética .
Un compañero de trabajo y yo estamos trabajando en una solución para cargar carga en camiones utilizando los diversos criterios que requiere nuestra empresa. He estado trabajando en una solución de Algoritmo Genético mientras él usa una Rama y Encuadernación con poda agresiva. Todavía estamos en el proceso de implementar esta solución, pero hasta ahora hemos obtenido buenos resultados.
Hace varios años, utilicé ga's para optimizar las gramáticas asr (reconocimiento automático de voz) para obtener mejores tasas de reconocimiento. Comencé con listas bastante simples de opciones (donde el ga estaba probando combinaciones de posibles términos para cada ranura) y avancé hasta encontrar gramáticas más abiertas y complejas. La aptitud se determinó midiendo la separación entre términos / secuencias bajo un tipo de función de distancia fonética. También experimenté haciendo variaciones débilmente equivalentes en una gramática para encontrar una que compilara una representación más compacta (al final elegí un algoritmo directo y aumentó drásticamente el tamaño del "lenguaje" que podríamos usar en las aplicaciones) .
Más recientemente, los he usado como una hipótesis predeterminada contra la cual probar la calidad de las soluciones generadas a partir de varios algoritmos. Esto ha implicado en gran medida la categorización y diferentes tipos de problemas de adaptación (es decir, crear una "regla" que explique un conjunto de elecciones hechas por los revisores sobre un conjunto de datos).
Una vez utilicé una GA para optimizar una función hash para las direcciones de memoria. Las direcciones tenían tamaños de página de 4K u 8K, por lo que mostraron cierta previsibilidad en el patrón de bits de la dirección (bits menos significativos todos cero; bits intermedios que se incrementan regularmente, etc.) La función hash original era "gruesa": tendía a agrupar los golpes en cada tercer cubo de hash. El algoritmo mejorado tenía una distribución casi perfecta.
Durante mis estudios, desarrollamos nuestro propio programa para resolver el problema del vendedor ambulante.
La idea era hacer una comparación de varios criterios (dificultad para mapear el problema, rendimiento, etc.) y también utilizamos otras técnicas como el recocido simulado .
Funcionó bastante bien, pero nos llevó un tiempo entender cómo hacer la fase de 'reproducción' correctamente: modelar el problema en cuestión en algo adecuado para la programación genética realmente me pareció la parte más difícil ...
Fue un curso interesante ya que también incursionamos en redes neuronales y similares.
Me gustaría saber si alguien usó este tipo de programación en el código de 'producción'.
Construí un GA simple para extraer patrones útiles fuera del espectro de frecuencia de la música mientras se estaba reproduciendo. La salida se usó para generar efectos gráficos en un complemento de winamp.
Entrada: algunos cuadros FFT (imagine una matriz 2D de flotadores)
Salida: valor flotante único (suma ponderada de entradas), umbral de 0.0 o 1.0
Genes: pesos de entrada
Función de aptitud: combinación de ciclo de trabajo, ancho de pulso y BPM dentro del rango sensible.
Tenía algunos GA sintonizados en diferentes partes del espectro, así como diferentes límites de BPM, por lo que no tienden a converger hacia el mismo patrón. Los resultados de los 4 primeros de cada población se enviaron al motor de renderizado.
Un efecto secundario interesante fue que el estado físico promedio de la población era un buen indicador de los cambios en la música, aunque generalmente tardó de 4 a 5 segundos en resolverlo.
Como parte de mi tesis, escribí un marco genérico de Java para el algoritmo de optimización multiobjetivo mPOEMS (optimización de prototipo multiobjetivo con pasos de mejora evolucionados), que es una AG que utiliza conceptos evolutivos. Es genérico de una manera que todas las partes independientes del problema se han separado de las partes dependientes del problema, y se proporciona una interfaz para usar el marco con solo agregar las partes dependientes del problema. Por lo tanto, quien quiere usar el algoritmo no tiene que comenzar desde cero, y facilita mucho el trabajo.
Las soluciones que puede encontrar con este algoritmo se han comparado en un trabajo científico con los algoritmos SPEA-2 y NSGA de última generación, y se ha demostrado que el algoritmo funciona de manera comparable o incluso mejor, dependiendo de las métricas que tome para medir el rendimiento, y especialmente dependiendo del problema de optimización que esté buscando.
Además, como parte de mi tesis y prueba de trabajo, apliqué este marco al problema de selección de proyectos que se encuentra en la gestión de la cartera. Se trata de seleccionar los proyectos que agreguen más valor a la empresa, respalden más la estrategia de la empresa o cualquier otro objetivo arbitrario. Por ejemplo, selección de un cierto número de proyectos de una categoría específica, o maximización de sinergias de proyectos, ...
Después de eso, trabajé en un departamento de gestión de cartera en uno de los Fortune 500, donde utilizaron un software comercial que también aplicó una AG al problema de selección de proyectos / optimización de cartera.
En realidad, con un poco de entusiasmo, todos podrían adaptar fácilmente el código del marco genérico a un problema arbitrario de optimización de objetivos múltiples.
En el trabajo tuve el siguiente problema: dadas M tareas y N DSP, ¿cuál era la mejor manera de asignar tareas a DSP? "Mejor" se definió como "minimizar la carga del DSP más cargado". Hubo diferentes tipos de tareas, y varios tipos de tareas tuvieron varias ramificaciones de rendimiento dependiendo de dónde fueron asignados, por lo que codifiqué el conjunto de asignaciones de trabajo a DSP como una "cadena de ADN" y luego usé un algoritmo genético para "reproducirse" la mejor cadena de asignación que pude.
Funcionó bastante bien (mucho mejor que mi método anterior, que era evaluar todas las combinaciones posibles ... ¡en tamaños de problemas no triviales, habría tardado años en completarse!), El único problema era que no había forma de saberlo si se alcanzó la solución óptima o no. Solo podía decidir si el "mejor esfuerzo" actual era lo suficientemente bueno, o dejar que durara más para ver si podía hacerlo mejor.
Hubo una competencia en codechef.com (gran sitio por cierto, competencias de programación mensuales) donde se suponía que uno debía resolver un sudoku irresoluble (uno debería acercarse lo más posible con la menor cantidad de columnas / filas / etc. incorrectas posible).
Lo que haría sería generar primero un sudoku perfecto y luego anular los campos que se han dado. Desde esta base bastante buena utilicé la programación genética para mejorar mi solución.
No podría pensar en un enfoque determinista en este caso, porque el sudoku era 300x300 y la búsqueda habría tomado demasiado tiempo.
Utilicé un algoritmo genético simple para optimizar la relación señal / ruido de una onda que se representaba como una cadena binaria. Al voltear los bits de ciertas maneras durante varios millones de generaciones, pude producir una transformación que resultó en una mayor relación señal / ruido de esa onda. El algoritmo también podría haber sido "Recocido simulado" pero no se usó en este caso. En esencia, los algoritmos genéticos son simples, y este fue el caso de uso más simple que he visto, por lo que no utilicé un marco para la creación y selección de generación, solo una semilla aleatoria y la relación señal / ruido función a la mano.
En un seminario en la escuela, desarrollamos una aplicación para generar música basada en el modo musical. El programa fue construido en Java y la salida fue un archivo midi con la canción. Utilizamos enfoques distintos de GA para generar la música. Creo que este programa puede ser útil para explorar nuevas composiciones.
en pregrado, usamos NERO (una combinación de red neuronal y algoritmo genético) para enseñar a los robots en el juego a tomar decisiones inteligentes. Fue muy bueno.
Desarrollé una simulación basada en columpios multiproceso de navegación de robots a través de un conjunto de cuadrículas aleatorias de fuentes de alimentos y minas y desarrollé una estrategia basada en algoritmos genéticos para explorar la optimización del comportamiento robótico y la supervivencia de los genes más aptos para un cromosoma robótico. Esto se realizó mediante gráficos y mapeos de cada ciclo de iteración.
Desde entonces, he desarrollado aún más el comportamiento del juego. Una aplicación de ejemplo que construí recientemente para mí fue un algoritmo genético para resolver el problema del vendedor ambulante en la búsqueda de rutas en el Reino Unido, teniendo en cuenta los estados de inicio y objetivo, así como uno / múltiples puntos de conexión, retrasos, cancelaciones, trabajos de construcción, hora punta, huelgas públicas, consideración entre las rutas más rápidas versus las más baratas. Luego, proporcione una recomendación equilibrada para que la ruta tome en un día determinado.
En general, mi estrategia es utilizar la representación de genes basada en POJO, luego aplico implementaciones de interfaz específicas para la selección, la mutación, las estrategias de cruce y el punto de criterio. Mi función de aptitud física básicamente se vuelve bastante compleja en función de la estrategia y los criterios que necesito aplicar como medida heurística.
También he examinado la aplicación de algoritmos genéticos en pruebas automatizadas dentro del código utilizando ciclos de mutación sistemáticos donde el algoritmo comprende la lógica e intenta determinar un informe de error con recomendaciones para corregir el código. Básicamente, una forma de optimizar mi código y proporcionar recomendaciones para mejorar, así como una forma de automatizar el descubrimiento de nuevo código programático. También he tratado de aplicar algoritmos genéticos a la producción musical, entre otras aplicaciones.
En general, encuentro estrategias evolutivas como la mayoría de las estrategias de optimización metaheurísticas / globales, son lentas para aprender al principio, pero comienzan a recuperarse a medida que las soluciones se acercan más y más al estado objetivo y siempre que su función de aptitud física y heurística estén bien alineadas para producir esa convergencia dentro de su espacio de búsqueda.
Una vez intenté hacer un reproductor de computadora para el juego de Go, basado exclusivamente en programación genética. Cada programa se trataría como una función de evaluación para una secuencia de movimientos. Sin embargo, los programas producidos no fueron muy buenos, incluso en un tablero 3x4 bastante pequeño.
Usé Perl y codifiqué todo por mí mismo. Hoy haría las cosas de manera diferente.
Después de leer The Blind Watchmaker , me interesó el programa pascal que Dawkins dijo que había desarrollado para crear modelos de organismos que podrían evolucionar con el tiempo. Estaba lo suficientemente interesado como para escribir el mío usando Swarm . No hice todos los gráficos de criaturas elegantes que hizo, pero mis 'cromosomas' controlaron rasgos que afectaron la capacidad de los organismos para sobrevivir. Vivían en un mundo simple y podían enfrentarse entre ellos y su entorno.
Los organismos vivieron o murieron en parte debido al azar, pero también en función de cuán efectivamente se adaptaron a sus entornos locales, qué tan bien consumieron nutrientes y qué tan exitosamente se reprodujeron. Fue divertido, pero también una prueba más para mi esposa de que soy un geek.
Hace un tiempo, pero hice rodar un GA para evolucionar lo que en realidad eran núcleos de procesamiento de imágenes para eliminar los rastros de rayos cósmicos de las imágenes del Telescopio Espacial Hubble (HST). El enfoque estándar es tomar múltiples exposiciones con el Hubble y mantener solo las cosas que son iguales en todas las imágenes. Como el tiempo HST es tan valioso, soy un aficionado a la astronomía, y recientemente asistí al Congreso de Computación Evolutiva, pensé en usar un GA para limpiar exposiciones individuales.
Los individuos estaban en forma de árboles que tomaban un área de 3x3 píxeles como entrada, realizaban algunos cálculos y producían una decisión sobre si modificar el píxel central y cómo hacerlo. La aptitud se juzgó comparando la salida con una imagen limpiada de la manera tradicional (es decir, apilando exposiciones).
Realmente funcionó, pero no lo suficientemente bien como para justificar renunciar al enfoque original. Si mi tesis no me hubiera limitado el tiempo, podría haber expandido el contenedor de partes genéticas disponible para el algoritmo. Estoy bastante seguro de que podría haberlo mejorado significativamente.
Bibliotecas utilizadas: si recuerdo correctamente, IRAF y cfitsio para el procesamiento de datos de imágenes astronómicas y E / S.
Experimenté con GA en mi juventud. Escribí un simulador en Python que funcionó de la siguiente manera.
Los genes codificaron los pesos de una red neuronal.
Las entradas de la red neuronal eran "antenas" que detectaban toques. Los valores más altos significaban muy cerca y 0 significaba no tocar.
Las salidas fueron a dos "ruedas". Si ambas ruedas avanzaban, el tipo avanzaba. Si las ruedas iban en direcciones opuestas, el tipo giraba. La fuerza de la salida determinó la velocidad de giro de la rueda.
Se generó un laberinto simple. Fue realmente simple, incluso estúpido. Hubo el comienzo en la parte inferior de la pantalla y un gol en la parte superior, con cuatro paredes en el medio. Cada pared tenía un espacio extraído al azar, por lo que siempre había un camino.
Comencé con muchachos al azar (los consideraba como errores) al principio. Tan pronto como un hombre alcanzó la meta, o se alcanzó un límite de tiempo, se calculó el estado físico. Era inversamente proporcional a la distancia a la meta en ese momento.
Luego los emparejé y los "crié" para crear la próxima generación. La probabilidad de ser elegido para ser criado fue proporcional a su aptitud. A veces esto significaba que uno era criado consigo mismo repetidamente si tenía una aptitud relativa muy alta.
Pensé que desarrollarían un comportamiento de "abrazo a la pared izquierda", pero siempre parecían seguir algo menos óptimo. En cada experimento, los errores convergieron en un patrón en espiral. Girarían en espiral hacia afuera hasta tocar una pared a la derecha. Seguirían eso, luego, cuando llegaran a la brecha, bajarían en espiral (alejándose de la brecha) y alrededor. Hacían un giro de 270 grados a la izquierda, luego generalmente entraban en el espacio. Esto los llevaría a través de la mayoría de las paredes, y a menudo a la meta.
Una característica que agregué fue poner un vector de color en los genes para rastrear la relación entre los individuos. Después de unas pocas generaciones, todos serían del mismo color, lo que me dice que debería tener una mejor estrategia de reproducción.
Traté de hacer que desarrollaran una mejor estrategia. Compliqué la red neuronal: agregué un recuerdo y todo. No sirvió de nada. Siempre vi la misma estrategia.
Intenté varias cosas, como tener grupos de genes separados que solo se recombinaron después de 100 generaciones. Pero nada los empujaría a una mejor estrategia. Tal vez fue imposible.
Otra cosa interesante es graficar el estado físico con el tiempo. Había patrones definidos, como el estado físico máximo que bajaba antes de que subiera. Nunca he visto un libro de evolución hablar sobre esa posibilidad.
Respuestas:
No tarea.
Mi primer trabajo como programador profesional (1995) fue escribir un sistema de comercio automatizado basado en algoritmos genéticos para futuros S & P500. La aplicación fue escrita en Visual Basic 3 [!] Y no tengo idea de cómo hice algo en aquel entonces, ya que VB3 ni siquiera tenía clases.
La aplicación comenzó con una población de cadenas de longitud fija generadas aleatoriamente (la parte del "gen"), cada una de las cuales correspondía a una forma específica en los datos de precios minuto a minuto de los futuros S & P500, así como a un pedido específico (comprar o vender) y cantidades de stop-loss y stop-profit. Cada cadena (o "gen") tuvo su rendimiento de beneficios evaluado por una ejecución a través de 3 años de datos históricos; cada vez que la "forma" especificada coincidía con los datos históricos, asumía la orden de compra o venta correspondiente y evaluaba el resultado de la operación. Agregué la advertencia de que cada gen comenzó con una cantidad fija de dinero y, por lo tanto, podría quebrarse y eliminarse por completo del grupo de genes.
Después de cada evaluación de una población, los sobrevivientes fueron cruzados aleatoriamente (simplemente mezclando bits de dos padres), con la probabilidad de que un gen sea seleccionado como padre sea proporcional al beneficio que produjo. También agregué la posibilidad de mutaciones puntuales para condimentar un poco las cosas. Después de unos cientos de generaciones de esto, terminé con una población de genes que podrían convertir $ 5000 en un promedio de aproximadamente $ 10000 sin posibilidad de muerte / quiebra (en los datos históricos, por supuesto).
Desafortunadamente, nunca tuve la oportunidad de usar este sistema en vivo, ya que mi jefe perdió cerca de $ 100,000 en menos de 3 meses comerciando de la manera tradicional, y perdió su voluntad de continuar con el proyecto. En retrospectiva, creo que el sistema habría obtenido grandes ganancias, no porque necesariamente estuviera haciendo algo bien, sino porque la población de genes que produje estaba sesgada hacia las órdenes de compra (en lugar de las órdenes de venta) en aproximadamente un 5: 1 ratio. Y como sabemos con nuestra retrospectiva 20/20, el mercado subió un poco después de 1995.
fuente
each of which corresponded to a specific shape in the minute-by-minute price data?Hice unas pequeñas criaturas que vivían en este pequeño mundo. Tenían un cerebro de red neuronal que recibió algunas entradas del mundo y la salida era un vector para el movimiento, entre otras acciones. Sus cerebros eran los "genes".
El programa comenzó con una población aleatoria de bichos con cerebros aleatorios. Las neuronas de entrada y salida eran estáticas, pero lo que estaba en medio no lo era.
El medio ambiente contenía alimentos y peligros. Los alimentos aumentan la energía y cuando tienes suficiente energía, puedes aparear. Los peligros reducirían la energía y si la energía fuera 0, morían.
Finalmente, las criaturas evolucionaron para moverse por el mundo y encontrar comida y evitar los peligros.
Entonces decidí hacer un pequeño experimento. Le di al cerebro de la criatura una neurona de salida llamada "boca" y una neurona de entrada llamada "oído". Comenzó de nuevo y se sorprendió al descubrir que evolucionaron para maximizar el espacio y cada criatura respectiva se quedaría en su parte respectiva (la comida se colocaba al azar). Aprendieron a cooperar entre sí y no interponerse en los demás. Siempre hubo excepciones.
Entonces probé algo interesante. Las criaturas muertas se convertirían en comida. ¡Intenta adivinar lo que pasó! Evolucionaron dos tipos de criaturas, las que atacaban como enjambres y las que evitaban mucho.
Entonces, ¿cuál es la lección aquí? La comunicación significa cooperación. Tan pronto como introduces un elemento en el que lastimar a otro significa que ganas algo, entonces la cooperación se destruye.
Me pregunto cómo se refleja esto en el sistema de libre mercado y capitalismo. Quiero decir, si las empresas pueden perjudicar a su competencia y salirse con la suya , entonces está claro que harán todo lo que esté en su poder para perjudicar a la competencia.
Editar:
Lo escribí en C ++ sin marcos. Escribí mi propia red neuronal y código GA. Eric, gracias por decir que es plausible. La gente generalmente no cree en los poderes de GA (aunque las limitaciones son obvias) hasta que juegan con él. GA es simple pero no simplista.
Para los que dudan, se ha demostrado que las redes neuronales pueden simular cualquier función si tienen más de una capa. GA es una forma bastante simple de navegar por un espacio de solución encontrando un mínimo local y potencialmente global. Combine GA con redes neuronales y tendrá una muy buena manera de encontrar funciones que encuentren soluciones aproximadas para problemas genéricos. Debido a que estamos usando redes neuronales, entonces estamos optimizando la función para algunas entradas, no algunas entradas para una función, ya que otras están usando GA
Aquí está el código de demostración para el ejemplo de supervivencia: http://www.mempko.com/darcs/neural/demos/eaters/ Instrucciones de compilación:
darcs clone --lazy http://www.mempko.com/darcs/neural/cd neuralcmake .makecd demos/eaters./eatersfuente
En enero de 2004, me contactó Philips New Display Technologies, que estaba creando la electrónica para la primera tinta electrónica comercial, la Sony Librie, que solo había sido lanzada en Japón, años antes de que Amazon Kindle y los demás llegaran al mercado en los EE. UU. una Europa
Los ingenieros de Philips tuvieron un gran problema. Unos meses antes de que se suponía que el producto llegaría al mercado, todavía estaban apareciendo imágenes fantasma en la pantalla al cambiar de página. El problema eran los 200 controladores que creaban el campo electrostático. Cada uno de estos controladores tenía un cierto voltaje que tenía que establecerse entre cero y 1000 mV o algo así. Pero si cambiaras uno de ellos, cambiaría todo.
Por lo tanto, optimizar el voltaje de cada controlador individualmente estaba fuera de discusión. El número de posibles combinaciones de valores fue de miles de millones, y una cámara especial tardó aproximadamente 1 minuto en evaluar una sola combinación. Los ingenieros habían probado muchas técnicas de optimización estándar, pero nada se acercaba.
El ingeniero jefe se puso en contacto conmigo porque previamente había lanzado una biblioteca de programación genética a la comunidad de código abierto. Me preguntó si los GP / GA ayudarían y si podría involucrarme. Lo hice, y durante aproximadamente un mes trabajamos juntos, escribiendo y ajustando la biblioteca de GA, en datos sintéticos, y él integrándolo en su sistema. Luego, un fin de semana lo dejaron en vivo con lo real.
El lunes siguiente recibí estos brillantes correos electrónicos de él y su diseñador de hardware, sobre cómo nadie podía creer los sorprendentes resultados que encontró el GA. Esto fue. Más tarde ese año, el producto llegó al mercado.
No me pagaron ni un centavo por ello, pero obtuve derechos de 'alardear'. Dijeron desde el principio que ya estaban por encima del presupuesto, así que supe cuál era el trato antes de comenzar a trabajar en él. Y es una gran historia para aplicaciones de GA. :)
fuente
Utilicé un GA para optimizar la asignación de asientos en la recepción de mi boda. 80 invitados en 10 mesas. La función de evaluación se basó en mantener a las personas con sus fechas, poner a las personas con algo en común y mantener a las personas con puntos de vista opuestos extremos en tablas separadas.
Lo corrí varias veces. Cada vez, obtuve nueve buenas mesas, y una con todas las bolas impares. Al final, mi esposa hizo las asignaciones de asientos.
El optimizador de mi vendedor ambulante usó un mapeo novedoso de cromosomas en el itinerario, lo que hizo trivial reproducir y mutar los cromosomas sin ningún riesgo de generar recorridos no válidos.
Actualizar : Porque un par de personas han preguntado cómo ...
Comience con una serie de invitados (o ciudades) en un orden arbitrario pero consistente, por ejemplo, alfabetizado. Llame a esto la solución de referencia. Piense en el índice de un invitado como su número de asiento.
En lugar de intentar codificar este orden directamente en el cromosoma, codificamos instrucciones para transformar la solución de referencia en una nueva solución. Específicamente, tratamos los cromosomas como listas de índices en la matriz para intercambiar. Para decodificar un cromosoma, comenzamos con la solución de referencia y aplicamos todos los intercambios indicados por el cromosoma. Intercambiar dos entradas en la matriz siempre da como resultado una solución válida: cada invitado (o ciudad) todavía aparece exactamente una vez.
Por lo tanto, los cromosomas se pueden generar aleatoriamente, mutar y cruzar con otros y siempre producirán una solución válida.
fuente
temp = a[c1]; a[c1] = a[c2]; a[c2] = temp). No importa si dos índices son idénticos, ya que un contendrá todos los invitados (o ciudades) exactamente una vez.Utilicé algoritmos genéticos (así como algunas técnicas relacionadas) para determinar la mejor configuración para un sistema de gestión de riesgos que intentaba evitar que los productores de oro usaran tarjetas de crédito robadas para pagar los MMO. El sistema tomaría varios miles de transacciones con valores "conocidos" (fraude o no) y descubriría cuál era la mejor combinación de configuraciones para identificar adecuadamente las transacciones fraudulentas sin tener demasiados falsos positivos.
Teníamos datos sobre varias docenas de características (booleanas) de una transacción, cada una de las cuales recibió un valor y se totalizó. Si el total fue superior a un umbral, la transacción fue fraude. El GA crearía una gran cantidad de conjuntos de valores aleatorios, los evaluaría frente a un conjunto de datos conocidos, seleccionaría los que obtuvieran la mejor puntuación (tanto en la detección de fraude como en la limitación del número de falsos positivos), y luego cruzaría los mejores. cada generación para producir una nueva generación de candidatos. Después de un cierto número de generaciones, el mejor conjunto de valores de puntuación se consideró ganador.
Crear el corpus de datos conocidos para probar fue el talón de Aquiles del sistema. Si esperaba las devoluciones de cargo, se atrasaba varios meses cuando intentaba responder a los estafadores, por lo que alguien tendría que revisar manualmente un gran número de transacciones para generar ese corpus de datos sin tener que esperar demasiado.
Esto terminó identificando la gran mayoría del fraude que se produjo, pero no pudo llegar por debajo del 1% en los artículos más propensos al fraude (dado que el 90% de las transacciones entrantes podría ser fraude, eso estaba funcionando bastante bien).
Hice todo esto usando perl. Una ejecución del software en una caja de Linux bastante antigua tardaría de 1 a 2 horas en ejecutarse (20 minutos para cargar datos a través de un enlace WAN, el resto del tiempo dedicado a la compresión). El tamaño de cualquier generación dada estaba limitado por la RAM disponible. Lo ejecutaba una y otra vez con ligeros cambios en los parámetros, buscando un conjunto de resultados especialmente bueno.
En general, evitó algunos de los errores que surgieron al tratar de ajustar manualmente los valores relativos de docenas de indicadores de fraude, y siempre encontró mejores soluciones de las que podía crear a mano. AFAIK, todavía está en uso (aproximadamente 3 años después de que lo escribí).
fuente
Propinas de fútbol. Creé un sistema GA para predecir el resultado de los juegos semanales en la AFL (Aussie Rules Football).
Hace unos años me aburrí del billar de fútbol de trabajo estándar, todo el mundo estaba simplemente en línea y tomando las selecciones de algún experto en la prensa. Entonces, pensé que no podría ser demasiado difícil vencer a un grupo de grandes periodistas de transmisión, ¿verdad? Mi primer pensamiento fue tomar los resultados de Massey Ratings y luego revelar al final de la temporada mi estrategia después de ganar fama y gloria. Sin embargo, por razones que nunca he descubierto, Massey no rastrea AFL. El cínico en mí cree que se debe a que el resultado de cada juego de AFL se ha convertido básicamente en una posibilidad aleatoria, pero mis quejas de cambios recientes en las reglas pertenecen a un foro diferente.
El sistema básicamente consideraba la fuerza ofensiva, la fuerza defensiva, la ventaja de campo local, la mejora semanal (o la falta de ella) y la velocidad de los cambios en cada una de ellas. Esto creó un conjunto de ecuaciones polinómicas para cada equipo durante la temporada. Se podría calcular el ganador y la puntuación de cada partido para una fecha determinada. El objetivo era encontrar el conjunto de coeficientes que mejor se ajustaran al resultado de todos los juegos pasados y usar ese conjunto para predecir el juego de las próximas semanas.
En la práctica, el sistema encontraría soluciones que predecían con precisión más del 90% de los resultados de juegos anteriores. Luego elegiría con éxito alrededor del 60-80% de los juegos para la próxima semana (esa es la semana que no está en el conjunto de entrenamiento).
El resultado: justo por encima de la mitad del paquete. No hay grandes premios en efectivo ni un sistema que pueda usar para vencer a Las Vegas. Aunque fue divertido.
Construí todo desde cero, no utilicé ningún framework.
fuente
Además de algunos de los problemas comunes, como el vendedor ambulante y una variación del programa Mona Lisa de Roger Alsing , también he escrito un solucionador de Sudoku evolutivo (que requirió un poco más de pensamiento original de mi parte, en lugar de simplemente volver a implementar idea de otra persona). Existen algoritmos más confiables para resolver Sudokus, pero el enfoque evolutivo funciona bastante bien.
En los últimos días, he estado jugando con un programa evolutivo para encontrar "mazos fríos" para el póker después de ver este artículo en Reddit. No es del todo satisfactorio en este momento, pero creo que puedo mejorarlo.
Tengo mi propio marco que utilizo para algoritmos evolutivos.
fuente
Desarrollé un GA casero para un sistema de perfil de superficie láser 3D que mi compañía desarrolló para la industria de carga en 1992. El sistema se basaba en la triangulación tridimensional y utilizaba un escáner de línea láser personalizado, una cámara de 512x512 (con captura personalizada hw). ¡La distancia entre la cámara y el láser nunca iba a ser precisa y el punto focal de las cámaras no se encontraba en la posición de 256,256 que esperaba!
Fue una pesadilla tratar de resolver los parámetros de calibración utilizando geometría estándar y resolución de ecuaciones de estilo de recocido simulado.
El algoritmo genético fue creado en una tarde y creé un cubo de calibración para probarlo. Conocía las dimensiones del cubo con gran precisión y, por lo tanto, la idea era que mi GA pudiera desarrollar un conjunto de parámetros de triangulación personalizados para cada unidad de escaneo que superara las variaciones de producción.
El truco funcionó de maravilla. ¡Me quedé estupefacto por decir lo menos! ¡En alrededor de 10 generaciones, mi cubo 'virtual' (generado a partir del escaneo sin procesar y recreado a partir de los parámetros de calibración) realmente parecía un cubo! Después de alrededor de 50 generaciones tuve la calibración que necesitaba.
fuente
A menudo es difícil obtener una combinación de colores exacta cuando planea pintar su casa. A menudo, tiene algo de color en mente, pero no es uno de los colores, el vendedor le muestra.
Ayer, mi profesor, que es un investigador de GA, mencionó una historia real en Alemania (lo siento, no tengo más referencias, sí, puedo averiguarlo si alguien lo solicita). Este tipo (llamémosle el tipo de color ) solía ir de puerta en puerta para ayudar a las personas a encontrar el código de color exacto (en RGB ) que sería el armario para lo que el cliente tenía en mente. Así es como lo haría:
El tipo de color solía llevar consigo un programa de software que usaba GA. Solía comenzar con 4 colores diferentes, cada uno codificado como un cromosoma codificado (cuyo valor descodificado sería un valor RGB). El consumidor elige 1 de los 4 colores (que es el más cercano al que tiene en mente). El programa luego asignaría la aptitud física máxima a ese individuo y pasaría a la próxima generación usando mutación / cruce . ¡Los pasos anteriores se repetirían hasta que el consumidor encontrara el color exacto y luego el tipo de color solía decirle la combinación RGB!
Al asignar la aptitud física máxima al color se cierra a lo que el consumidor tiene en mente, el programa del tipo de color está aumentando las posibilidades de converger al color, el consumidor tiene en mente exactamente. ¡Lo encontré muy divertido!
Ahora que tengo un -1, si estás planeando más -1, por favor. dilucidar la razón para hacerlo!
fuente
Hace un par de semanas, sugerí una solución en SO utilizando algoritmos genéticos para resolver un problema de diseño gráfico. Es un ejemplo de un problema de optimización restringido.
También en el área de aprendizaje automático, implementé un marco de reglas de clasificación basado en GA en c / c ++ desde cero.
También he usado GA en un proyecto de muestra para entrenar redes neuronales artificiales (ANN) en lugar de usar el famoso algoritmo de retropropagación .
Además, y como parte de mi investigación de posgrado, he usado GA en la capacitación de modelos ocultos de Markov como un enfoque adicional para el algoritmo Baum-Welch basado en EM (en c / c ++ nuevamente).
fuente
Como parte de mi título universitario de CompSci, se nos asignó el problema de encontrar banderas jvm óptimas para la máquina virtual de investigación Jikes. Esto se evaluó utilizando el conjunto de pruebas Dicappo que devuelve un tiempo a la consola. Escribí un alogirthm genético distribuido que cambió estas banderas para mejorar el tiempo de ejecución de la suite de referencia, aunque tardó días en ejecutarse para compensar la fluctuación de hardware que afecta los resultados. El único problema fue que no aprendí adecuadamente sobre la teoría del compilador (que era la intención de la tarea).
Podría haber sembrado la población inicial con los indicadores predeterminados existentes, pero lo interesante fue que el algoritmo encontró una configuración muy similar al nivel de optimización de O3 (pero en realidad fue más rápido en muchas pruebas).
Editar: También escribí mi propio marco de algoritmo genético en Python para la tarea, y solo usé los comandos popen para ejecutar los diversos puntos de referencia, aunque si no fuera una tarea evaluada, habría analizado pyEvolve.
fuente
En primer lugar, "Programación genética" de Jonathan Koza ( en Amazon ) es prácticamente EL libro sobre algoritmos genéticos y evolutivos / técnicas de programación, con muchos ejemplos. Le recomiendo que lo revise.
En cuanto a mi propio uso de un algoritmo genético, utilicé un algoritmo genético (de cosecha propia) para desarrollar un algoritmo de enjambre para un escenario de recolección / destrucción de objetos (el propósito práctico podría haber sido limpiar un campo minado). Aquí hay un enlace al documento . La parte más interesante de lo que hice fue la función de estado físico de varias etapas, que era una necesidad ya que las funciones de estado físico simples no proporcionaban suficiente información para que el algoritmo genético diferenciara lo suficiente entre los miembros de la población.
fuente
Soy parte de un equipo que investiga el uso de la Computación Evolutiva (EC) para corregir automáticamente los errores en los programas existentes. Hemos reparado con éxito una serie de errores reales en proyectos de software del mundo real (consulte la página de inicio de este proyecto ).
Tenemos dos aplicaciones de esta técnica de reparación EC.
El primero (información de código y reproducción disponible a través de la página del proyecto ) desarrolla los árboles de sintaxis abstracta analizados a partir de los programas C existentes y se implementa en Ocaml utilizando nuestro propio motor EC personalizado.
El segundo (información de código y reproducción disponible a través de la página del proyecto ), mi contribución personal al proyecto, desarrolla el ensamblado x86 o el código de bytes Java compilado de programas escritos en varios lenguajes de programación. Esta aplicación se implementa en Clojure y también utiliza su propio motor EC personalizado.
Un buen aspecto de la computación evolutiva es la simplicidad de la técnica que hace posible escribir sus propias implementaciones personalizadas sin demasiada dificultad. Para un buen texto introductorio disponible gratuitamente sobre Programación Genética, vea la Guía de Campo para Programación Genética .
fuente
Un compañero de trabajo y yo estamos trabajando en una solución para cargar carga en camiones utilizando los diversos criterios que requiere nuestra empresa. He estado trabajando en una solución de Algoritmo Genético mientras él usa una Rama y Encuadernación con poda agresiva. Todavía estamos en el proceso de implementar esta solución, pero hasta ahora hemos obtenido buenos resultados.
fuente
Hace varios años, utilicé ga's para optimizar las gramáticas asr (reconocimiento automático de voz) para obtener mejores tasas de reconocimiento. Comencé con listas bastante simples de opciones (donde el ga estaba probando combinaciones de posibles términos para cada ranura) y avancé hasta encontrar gramáticas más abiertas y complejas. La aptitud se determinó midiendo la separación entre términos / secuencias bajo un tipo de función de distancia fonética. También experimenté haciendo variaciones débilmente equivalentes en una gramática para encontrar una que compilara una representación más compacta (al final elegí un algoritmo directo y aumentó drásticamente el tamaño del "lenguaje" que podríamos usar en las aplicaciones) .
Más recientemente, los he usado como una hipótesis predeterminada contra la cual probar la calidad de las soluciones generadas a partir de varios algoritmos. Esto ha implicado en gran medida la categorización y diferentes tipos de problemas de adaptación (es decir, crear una "regla" que explique un conjunto de elecciones hechas por los revisores sobre un conjunto de datos).
fuente
Hice un marco completo de GA llamado "GALAB", para resolver muchos problemas:
fuente
Una vez utilicé una GA para optimizar una función hash para las direcciones de memoria. Las direcciones tenían tamaños de página de 4K u 8K, por lo que mostraron cierta previsibilidad en el patrón de bits de la dirección (bits menos significativos todos cero; bits intermedios que se incrementan regularmente, etc.) La función hash original era "gruesa": tendía a agrupar los golpes en cada tercer cubo de hash. El algoritmo mejorado tenía una distribución casi perfecta.
fuente
No sé si la tarea cuenta ...
Durante mis estudios, desarrollamos nuestro propio programa para resolver el problema del vendedor ambulante.
La idea era hacer una comparación de varios criterios (dificultad para mapear el problema, rendimiento, etc.) y también utilizamos otras técnicas como el recocido simulado .
Funcionó bastante bien, pero nos llevó un tiempo entender cómo hacer la fase de 'reproducción' correctamente: modelar el problema en cuestión en algo adecuado para la programación genética realmente me pareció la parte más difícil ...
Fue un curso interesante ya que también incursionamos en redes neuronales y similares.
Me gustaría saber si alguien usó este tipo de programación en el código de 'producción'.
fuente
Construí un GA simple para extraer patrones útiles fuera del espectro de frecuencia de la música mientras se estaba reproduciendo. La salida se usó para generar efectos gráficos en un complemento de winamp.
Tenía algunos GA sintonizados en diferentes partes del espectro, así como diferentes límites de BPM, por lo que no tienden a converger hacia el mismo patrón. Los resultados de los 4 primeros de cada población se enviaron al motor de renderizado.
Un efecto secundario interesante fue que el estado físico promedio de la población era un buen indicador de los cambios en la música, aunque generalmente tardó de 4 a 5 segundos en resolverlo.
fuente
Como parte de mi tesis, escribí un marco genérico de Java para el algoritmo de optimización multiobjetivo mPOEMS (optimización de prototipo multiobjetivo con pasos de mejora evolucionados), que es una AG que utiliza conceptos evolutivos. Es genérico de una manera que todas las partes independientes del problema se han separado de las partes dependientes del problema, y se proporciona una interfaz para usar el marco con solo agregar las partes dependientes del problema. Por lo tanto, quien quiere usar el algoritmo no tiene que comenzar desde cero, y facilita mucho el trabajo.
Puedes encontrar el código aquí .
Las soluciones que puede encontrar con este algoritmo se han comparado en un trabajo científico con los algoritmos SPEA-2 y NSGA de última generación, y se ha demostrado que el algoritmo funciona de manera comparable o incluso mejor, dependiendo de las métricas que tome para medir el rendimiento, y especialmente dependiendo del problema de optimización que esté buscando.
Lo puedes encontrar aquí .
Además, como parte de mi tesis y prueba de trabajo, apliqué este marco al problema de selección de proyectos que se encuentra en la gestión de la cartera. Se trata de seleccionar los proyectos que agreguen más valor a la empresa, respalden más la estrategia de la empresa o cualquier otro objetivo arbitrario. Por ejemplo, selección de un cierto número de proyectos de una categoría específica, o maximización de sinergias de proyectos, ...
Mi tesis que aplica este marco al problema de selección de proyectos: http://www.ub.tuwien.ac.at/dipl/2008/AC05038968.pdf
Después de eso, trabajé en un departamento de gestión de cartera en uno de los Fortune 500, donde utilizaron un software comercial que también aplicó una AG al problema de selección de proyectos / optimización de cartera.
Recursos adicionales:
La documentación del marco: http://thomaskremmel.com/mpoems/mpoems_in_java_documentation.pdf
Documento de presentación de mPOEMS: http://portal.acm.org/citation.cfm?id=1792634.1792653
En realidad, con un poco de entusiasmo, todos podrían adaptar fácilmente el código del marco genérico a un problema arbitrario de optimización de objetivos múltiples.
fuente
En el trabajo tuve el siguiente problema: dadas M tareas y N DSP, ¿cuál era la mejor manera de asignar tareas a DSP? "Mejor" se definió como "minimizar la carga del DSP más cargado". Hubo diferentes tipos de tareas, y varios tipos de tareas tuvieron varias ramificaciones de rendimiento dependiendo de dónde fueron asignados, por lo que codifiqué el conjunto de asignaciones de trabajo a DSP como una "cadena de ADN" y luego usé un algoritmo genético para "reproducirse" la mejor cadena de asignación que pude.
Funcionó bastante bien (mucho mejor que mi método anterior, que era evaluar todas las combinaciones posibles ... ¡en tamaños de problemas no triviales, habría tardado años en completarse!), El único problema era que no había forma de saberlo si se alcanzó la solución óptima o no. Solo podía decidir si el "mejor esfuerzo" actual era lo suficientemente bueno, o dejar que durara más para ver si podía hacerlo mejor.
fuente
Hubo una competencia en codechef.com (gran sitio por cierto, competencias de programación mensuales) donde se suponía que uno debía resolver un sudoku irresoluble (uno debería acercarse lo más posible con la menor cantidad de columnas / filas / etc. incorrectas posible).
Lo que haría sería generar primero un sudoku perfecto y luego anular los campos que se han dado. Desde esta base bastante buena utilicé la programación genética para mejorar mi solución.
No podría pensar en un enfoque determinista en este caso, porque el sudoku era 300x300 y la búsqueda habría tomado demasiado tiempo.
fuente
Utilicé un algoritmo genético simple para optimizar la relación señal / ruido de una onda que se representaba como una cadena binaria. Al voltear los bits de ciertas maneras durante varios millones de generaciones, pude producir una transformación que resultó en una mayor relación señal / ruido de esa onda. El algoritmo también podría haber sido "Recocido simulado" pero no se usó en este caso. En esencia, los algoritmos genéticos son simples, y este fue el caso de uso más simple que he visto, por lo que no utilicé un marco para la creación y selección de generación, solo una semilla aleatoria y la relación señal / ruido función a la mano.
fuente
En un seminario en la escuela, desarrollamos una aplicación para generar música basada en el modo musical. El programa fue construido en Java y la salida fue un archivo midi con la canción. Utilizamos enfoques distintos de GA para generar la música. Creo que este programa puede ser útil para explorar nuevas composiciones.
fuente
en pregrado, usamos NERO (una combinación de red neuronal y algoritmo genético) para enseñar a los robots en el juego a tomar decisiones inteligentes. Fue muy bueno.
fuente
Desarrollé una simulación basada en columpios multiproceso de navegación de robots a través de un conjunto de cuadrículas aleatorias de fuentes de alimentos y minas y desarrollé una estrategia basada en algoritmos genéticos para explorar la optimización del comportamiento robótico y la supervivencia de los genes más aptos para un cromosoma robótico. Esto se realizó mediante gráficos y mapeos de cada ciclo de iteración.
Desde entonces, he desarrollado aún más el comportamiento del juego. Una aplicación de ejemplo que construí recientemente para mí fue un algoritmo genético para resolver el problema del vendedor ambulante en la búsqueda de rutas en el Reino Unido, teniendo en cuenta los estados de inicio y objetivo, así como uno / múltiples puntos de conexión, retrasos, cancelaciones, trabajos de construcción, hora punta, huelgas públicas, consideración entre las rutas más rápidas versus las más baratas. Luego, proporcione una recomendación equilibrada para que la ruta tome en un día determinado.
En general, mi estrategia es utilizar la representación de genes basada en POJO, luego aplico implementaciones de interfaz específicas para la selección, la mutación, las estrategias de cruce y el punto de criterio. Mi función de aptitud física básicamente se vuelve bastante compleja en función de la estrategia y los criterios que necesito aplicar como medida heurística.
También he examinado la aplicación de algoritmos genéticos en pruebas automatizadas dentro del código utilizando ciclos de mutación sistemáticos donde el algoritmo comprende la lógica e intenta determinar un informe de error con recomendaciones para corregir el código. Básicamente, una forma de optimizar mi código y proporcionar recomendaciones para mejorar, así como una forma de automatizar el descubrimiento de nuevo código programático. También he tratado de aplicar algoritmos genéticos a la producción musical, entre otras aplicaciones.
En general, encuentro estrategias evolutivas como la mayoría de las estrategias de optimización metaheurísticas / globales, son lentas para aprender al principio, pero comienzan a recuperarse a medida que las soluciones se acercan más y más al estado objetivo y siempre que su función de aptitud física y heurística estén bien alineadas para producir esa convergencia dentro de su espacio de búsqueda.
fuente
Una vez intenté hacer un reproductor de computadora para el juego de Go, basado exclusivamente en programación genética. Cada programa se trataría como una función de evaluación para una secuencia de movimientos. Sin embargo, los programas producidos no fueron muy buenos, incluso en un tablero 3x4 bastante pequeño.
Usé Perl y codifiqué todo por mí mismo. Hoy haría las cosas de manera diferente.
fuente
Después de leer The Blind Watchmaker , me interesó el programa pascal que Dawkins dijo que había desarrollado para crear modelos de organismos que podrían evolucionar con el tiempo. Estaba lo suficientemente interesado como para escribir el mío usando Swarm . No hice todos los gráficos de criaturas elegantes que hizo, pero mis 'cromosomas' controlaron rasgos que afectaron la capacidad de los organismos para sobrevivir. Vivían en un mundo simple y podían enfrentarse entre ellos y su entorno.
Los organismos vivieron o murieron en parte debido al azar, pero también en función de cuán efectivamente se adaptaron a sus entornos locales, qué tan bien consumieron nutrientes y qué tan exitosamente se reprodujeron. Fue divertido, pero también una prueba más para mi esposa de que soy un geek.
fuente
Hace un tiempo, pero hice rodar un GA para evolucionar lo que en realidad eran núcleos de procesamiento de imágenes para eliminar los rastros de rayos cósmicos de las imágenes del Telescopio Espacial Hubble (HST). El enfoque estándar es tomar múltiples exposiciones con el Hubble y mantener solo las cosas que son iguales en todas las imágenes. Como el tiempo HST es tan valioso, soy un aficionado a la astronomía, y recientemente asistí al Congreso de Computación Evolutiva, pensé en usar un GA para limpiar exposiciones individuales.
Los individuos estaban en forma de árboles que tomaban un área de 3x3 píxeles como entrada, realizaban algunos cálculos y producían una decisión sobre si modificar el píxel central y cómo hacerlo. La aptitud se juzgó comparando la salida con una imagen limpiada de la manera tradicional (es decir, apilando exposiciones).
Realmente funcionó, pero no lo suficientemente bien como para justificar renunciar al enfoque original. Si mi tesis no me hubiera limitado el tiempo, podría haber expandido el contenedor de partes genéticas disponible para el algoritmo. Estoy bastante seguro de que podría haberlo mejorado significativamente.
Bibliotecas utilizadas: si recuerdo correctamente, IRAF y cfitsio para el procesamiento de datos de imágenes astronómicas y E / S.
fuente
Experimenté con GA en mi juventud. Escribí un simulador en Python que funcionó de la siguiente manera.
Los genes codificaron los pesos de una red neuronal.
Las entradas de la red neuronal eran "antenas" que detectaban toques. Los valores más altos significaban muy cerca y 0 significaba no tocar.
Las salidas fueron a dos "ruedas". Si ambas ruedas avanzaban, el tipo avanzaba. Si las ruedas iban en direcciones opuestas, el tipo giraba. La fuerza de la salida determinó la velocidad de giro de la rueda.
Se generó un laberinto simple. Fue realmente simple, incluso estúpido. Hubo el comienzo en la parte inferior de la pantalla y un gol en la parte superior, con cuatro paredes en el medio. Cada pared tenía un espacio extraído al azar, por lo que siempre había un camino.
Comencé con muchachos al azar (los consideraba como errores) al principio. Tan pronto como un hombre alcanzó la meta, o se alcanzó un límite de tiempo, se calculó el estado físico. Era inversamente proporcional a la distancia a la meta en ese momento.
Luego los emparejé y los "crié" para crear la próxima generación. La probabilidad de ser elegido para ser criado fue proporcional a su aptitud. A veces esto significaba que uno era criado consigo mismo repetidamente si tenía una aptitud relativa muy alta.
Pensé que desarrollarían un comportamiento de "abrazo a la pared izquierda", pero siempre parecían seguir algo menos óptimo. En cada experimento, los errores convergieron en un patrón en espiral. Girarían en espiral hacia afuera hasta tocar una pared a la derecha. Seguirían eso, luego, cuando llegaran a la brecha, bajarían en espiral (alejándose de la brecha) y alrededor. Hacían un giro de 270 grados a la izquierda, luego generalmente entraban en el espacio. Esto los llevaría a través de la mayoría de las paredes, y a menudo a la meta.
Una característica que agregué fue poner un vector de color en los genes para rastrear la relación entre los individuos. Después de unas pocas generaciones, todos serían del mismo color, lo que me dice que debería tener una mejor estrategia de reproducción.
Traté de hacer que desarrollaran una mejor estrategia. Compliqué la red neuronal: agregué un recuerdo y todo. No sirvió de nada. Siempre vi la misma estrategia.
Intenté varias cosas, como tener grupos de genes separados que solo se recombinaron después de 100 generaciones. Pero nada los empujaría a una mejor estrategia. Tal vez fue imposible.
Otra cosa interesante es graficar el estado físico con el tiempo. Había patrones definidos, como el estado físico máximo que bajaba antes de que subiera. Nunca he visto un libro de evolución hablar sobre esa posibilidad.
fuente