algorithm - programacion - ¿Cuáles son buenos ejemplos de algoritmos genéticos/soluciones de programación genética?
ejemplos de algoritmos geneticos inteligencia artificial (30)
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, le muestra el proveedor.
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émoslo 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 chico del 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 decodificado sería un valor RGB). El consumidor elige 1 de los 4 colores (que es el más cercano a lo que él / ella tiene en mente). El programa asignaría entonces la aptitud máxima a ese individuo y pasaría a la siguiente generación utilizando mutación / cruce . Los pasos anteriores se repetirían hasta que el consumidor haya encontrado el color exacto y luego el tipo de color solía decirle la combinación RGB.
Al asignar un ajuste óptimo al color que el consumidor tiene en mente, el programa del chico del color aumenta las posibilidades de converger en el color, el consumidor tiene en mente exactamente. Lo encontré bastante divertido!
Ahora que tengo un -1, si está planeando más -1''s, por favor. ¡Elucidar la razón para hacerlo!
Los algoritmos genéticos (AG) y la programación genética (GP) son áreas interesantes de investigación.
Me gustaría saber acerca de los problemas específicos que resolvió utilizando GA / GP y qué bibliotecas / marcos usó si no hizo su propia cuenta.
Preguntas:
- ¿Qué problemas has usado GA / GP para resolver?
- ¿Qué bibliotecas / marcos usaste?
Estoy buscando experiencias de primera mano, así que no respondas a menos que tengas eso.
Además de algunos de los problemas comunes, como el Vendedor Viajante y una variación del programa Mona Lisa de Roger Alsing , también he escrito un solucionador de Sudoku evolutivo (que requería un poco más de pensamiento original de mi parte, en lugar de solo volver a implementarlo idea de alguien mas). Hay 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 "plataformas frías" 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 los algoritmos evolutivos.
Como parte de mi licenciatura en CompSci, se nos asignó el problema de encontrar indicadores jvm óptimos para la máquina virtual de investigación Jikes. Esto se evaluó utilizando la suite de referencia Dicappo que devuelve un tiempo a la consola. Escribí un alogirthm gentic 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 las fluctuaciones de hardware que afectan los resultados. El único problema fue que no aprendí correctamente sobre la teoría del compilador (que era la intención de la tarea).
Podría haber sembrado la población inicial con las banderas predeterminadas 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).
Edit: También escribí mi propio marco de algoritmo genético en Python para la tarea, y solo usé los comandos popen para ejecutar los distintos puntos de referencia, aunque si no fuera una tarea evaluada, habría mirado pyEvolve.
Como parte de mi tesis, escribí un marco genérico de Java para el algoritmo de optimización multiobjetivo mPOEMS (Optimización de prototipos multiobjetivo con pasos de mejora evolucionados), que es una AG que utiliza conceptos evolutivos. Es genérico de 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 quiera usar el algoritmo no tiene que comenzar desde cero y facilita mucho el trabajo.
Puedes encontrar el código here .
Las soluciones que puede encontrar con este algoritmo se han comparado en un trabajo científico con los algoritmos más avanzados SPEA-2 y NSGA, y se ha demostrado que el algoritmo tiene un rendimiento comparable o incluso mejor, según las métricas que utilice. Tómelo para medir el rendimiento y, especialmente, en función del problema de optimización que esté buscando.
Puedes encontrarlo here .
También 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 cartera. Se trata de seleccionar los proyectos que agreguen el mayor valor a la compañía, respaldar la mayor parte de la estrategia de la compañía o respaldar cualquier otro objetivo arbitrario. Por ejemplo, la selección de un cierto número de proyectos de una categoría específica, o la maximización de las 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 administración de cartera en uno de Fortune 500, donde usaron un software comercial que también aplicó una AG a la optimización del problema / cartera de selección de proyectos.
Otros recursos:
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 de optimización de objetivos múltiples arbitrario.
Construí una GA simple para extraer patrones útiles del espectro de frecuencias de la música mientras se reproducía. La salida se usó para impulsar efectos gráficos en un complemento de Winamp.
- Entrada: algunos marcos FFT (imagina una matriz 2D de flotadores)
- Salida: valor flotante único (suma ponderada de las entradas), umbral a 0.0 o 1.0
- Genes: pesos de entrada
- Función fitness: combinación de ciclo de trabajo, ancho de pulso y BPM dentro del rango sensible.
Tuve unos pocos GA sintonizados a diferentes partes del espectro, así como diferentes límites de BPM, por lo que no tienden a converger hacia el mismo patrón. Las salidas de los 4 principales 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 en general tardó 4-5 segundos en resolverlo.
Desarrollé un GA casero para un sistema de perfil de superficie láser 3D que mi empresa desarrolló para la industria del transporte en 1992. El sistema se basó en la triangulación tridimensional y usó un escáner de línea láser personalizado, una cámara de 512x512 (con captura de hw personalizada). 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 256,256 que usted 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 se preparó 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! ¡Dentro de unas 10 generaciones, mi cubo ''virtual'' (generado a partir del escaneo en bruto y recreado a partir de los parámetros de calibración) en realidad parecía un cubo! Después de alrededor de 50 generaciones tuve la calibración que necesitaba.
En el trabajo tuve el siguiente problema: dadas las tareas M y N DSP, ¿cuál era la mejor manera de asignar tareas a los DSP? "Mejor" se definió como "minimizar la carga del DSP más cargado". Había diferentes tipos de tareas, y varios tipos de tareas tenían diferentes ramificaciones de rendimiento dependiendo de dónde se asignaban, 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 "generar" La mejor cadena de asignación que pude.
Funcionó bastante bien (mucho mejor que mi método anterior, que fue evaluar todas las combinaciones posibles ... en tamaños de problemas no triviales, ¡habrían tardado años en completarse!), El único problema era que no había forma de saberlo Si la solución óptima había sido alcanzada o no. Solo podría decidir si el "mejor esfuerzo" actual era lo suficientemente bueno, o dejarlo correr por más tiempo para ver si podía hacerlo mejor.
En enero de 2004, Philips New Display Technologies se puso en contacto conmigo y estaba creando la electrónica para el primer e-ink comercial de la historia, el Sony Librie, que solo había sido lanzado en Japón, años antes de que Amazon Kindle y los demás salieran al mercado en Estados Unidos. una europa
Los ingenieros de Philips tuvieron un gran problema. Unos meses antes de que el producto saliera al mercado, todavía estaban apareciendo en la pantalla al cambiar de página. El problema fueron los 200 controladores que estaban creando el campo electrostático. Cada uno de estos controladores tenía un cierto voltaje que debía ajustarse entre cero y 1000 mV o algo así. Pero si cambiaste uno de ellos, cambiaría todo.
Por lo tanto, la optimización individual de la tensión de cada controlador estaba fuera de discusión. El número de posibles combinaciones de valores fue en miles de millones, y una cámara especial tardó aproximadamente 1 minuto en evaluar una combinación única. Los ingenieros habían probado muchas técnicas de optimización estándar, pero nada se acercaría.
El ingeniero jefe me contactó porque anteriormente había lanzado una biblioteca de programación genética a la comunidad de código abierto. Preguntó si los GP / GA ayudarían y si yo podría participar. Lo hice, y durante aproximadamente un mes trabajamos juntos, escribí y ajusté la biblioteca de GA, en datos sintéticos, y lo integré en su sistema. Entonces, un fin de semana lo dejaron correr en vivo con lo real.
El lunes siguiente recibí estos brillantes correos electrónicos de él y de su diseñador de hardware, sobre cómo nadie podía creer los sorprendentes resultados que encontró la AG. Esto fue. Más tarde ese año el producto llegó al mercado.
No me pagaron ni un centavo por eso, pero obtuve los derechos de "alardear". Dijeron desde el principio que ya habían superado el presupuesto, por lo que sabía cuál era el trato antes de comenzar a trabajar en ello. Y es una gran historia para aplicaciones de GA. :)
En primer lugar, "Programación genética" por Jonathan Koza ( en Amazon ) es prácticamente EL libro sobre algoritmos genéticos y evolutivos / técnicas de programación, con muchos ejemplos. Recomiendo encarecidamente echarle un vistazo.
En cuanto a mi propio uso de un algoritmo genético, usé un algoritmo genético (de cosecha propia) para desarrollar un algoritmo de enjambre para un escenario de colección / destrucción de objetos (el propósito práctico podría haber sido limpiar un campo minado). Aquí hay un enlace al papel . La parte más interesante de lo que hice fue la función de acondicionamiento físico en varias etapas, que era una necesidad, ya que las funciones de acondicionamiento físico simples no proporcionaron suficiente información para que el algoritmo genético diferencie suficientemente entre los miembros de la población.
Hace un par de semanas, sugerí una solución en SO usando algoritmos genéticos para resolver un problema de diseño gráfico. Es un ejemplo de un problema de optimización restringida.
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 propagación hacia atrás .
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).
Hace varios años usé ga''s para optimizar las gramáticas asr (reconocimiento de voz automático) para obtener mejores índices de reconocimiento. Comencé con listas de opciones bastante simples (donde el ga estaba probando combinaciones de términos posibles para cada espacio) y me abrí camino hacia gramáticas más abiertas y complejas. La aptitud física se determinó midiendo la separación entre términos / secuencias bajo un tipo de función de distancia fonética. También experimenté con hacer variaciones débilmente equivalentes en una gramática para encontrar una que compilara para una representación más compacta (al final fui con 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 realizadas por los revisores en un conjunto de datos).
Hice un marco GA completo llamado "GALAB", para resolver muchos problemas:
- localización de ANT GSM (BTS) para disminuir ubicaciones superpuestas y en blanco.
- Restricción de recursos en la programación de proyectos.
- Creación de imágenes evolutivas. ( Evopic )
- Problema de vendedor ambulante.
- N-Queen y problemas de N-Color.
- Tour de caballero y problemas con la mochila.
- Cuadrados mágicos y rompecabezas de Sudoku.
- Compresión de cadenas, basada en el problema Superstring.
- Problema de embalaje 2D.
- Pequeña vida artificial de la APP.
- Rompecabezas de Rubik.
Hice unas pequeñas criaturas que vivían en este pequeño mundo. Tenían un cerebro de red neuronal que recibió algunos aportes del mundo y la salida fue un vector de movimiento entre otras acciones. Sus cerebros fueron los "genes".
El programa comenzó con una población aleatoria de criaturas con cerebros aleatorios. Las entradas y las neuronas de salida eran estáticas, pero lo que estaba en medio no lo era.
El ambiente contenía comida y peligros. La comida aumenta la energía y cuando tienes suficiente energía, puedes aparearte. Los peligros reducirían la energía y si la energía fuera 0, morirían.
Eventualmente, las criaturas evolucionaron para moverse alrededor del mundo y encontrar comida y evitar los peligros.
Entonces decidí hacer un pequeño experimento. Le di a la criatura cerebro una neurona de salida llamada "boca" y una neurona de entrada llamada "oreja". Comenzó de nuevo y se sorprendió al descubrir que evolucionaron para maximizar el espacio y que cada criatura respectiva se quedaría en su parte respectiva (la comida se colocó al azar). Aprendieron a cooperar entre sí y no a meterse en los demás. Siempre hubo las excepciones.
Entonces probé algo interesante. Las criaturas muertas se convertirían en alimento. Intenta adivinar lo que pasó! Evolucionaron dos tipos de criaturas, las que atacaron como en los enjambres, y las que tenían un alto grado de evitación.
Entonces, ¿cuál es la lección aquí? Comunicación significa cooperación. Tan pronto como introduce un elemento donde dañar a otro significa que gana algo, se destruye la cooperación.
Me pregunto cómo se refleja esto en el sistema de mercados libres y capitalismo. Quiero decir, si las empresas pueden dañar su competencia y salirse con la suya , entonces está claro que harán todo lo que esté a su alcance para dañar 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 jugaron con ella. 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 sencilla de navegar por un espacio de soluciones, buscando un mínimo local y potencialmente global. Combina GA con redes neuronales y tienes una forma bastante buena de encontrar funciones que encuentren soluciones aproximadas para problemas genéricos. Debido a que estamos utilizando redes neuronales, estamos optimizando la función para algunas entradas, no para una función, mientras que otras utilizan 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:
- Instala darcs, libboost, liballegro, gcc, cmake, make
-
darcs clone --lazy http://www.mempko.com/darcs/neural/ -
cd neural -
cmake . -
make -
cd demos/eaters -
./eaters
No sé si la tarea cuenta ...
Durante mis estudios, lanzamos nuestro propio programa para resolver el problema del vendedor ambulante.
La idea era hacer una comparación en varios criterios (dificultad para mapear el problema, rendimiento, etc.) y también usamos otras técnicas como el recocido simulado .
Funcionó bastante bien, pero nos tomó 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''.
Propinas de fútbol. Construí un sistema GA para predecir el resultado semana a semana de los juegos en la AFL (Aussie Rules Football).
Hace unos años me aburrí del grupo de trabajo de fútbol estándar, todo el mundo se conectaba y tomaba las decisiones de algún experto de la prensa. Entonces, me di cuenta de que no podía ser demasiado difícil vencer a un grupo de estudiantes de periodismo, ¿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 la 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 considera la fuerza ofensiva, la fuerza defensiva, la ventaja en el campo local, la mejora semana a semana (o la falta de la misma) y la velocidad de los cambios en cada uno de estos. Esto creó un conjunto de ecuaciones polinomiales para cada equipo durante la temporada. El ganador y el puntaje de cada partido para una fecha determinada podrían calcularse. El objetivo era encontrar el conjunto de coeficientes que mejor se correspondía con el resultado de todos los juegos anteriores y usar ese conjunto para predecir el juego de las próximas semanas.
En la práctica, el sistema encontraría soluciones que predijeron con precisión más del 90% de los resultados de los juegos pasados. Luego seleccionarí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 un premio mayor en efectivo ni un sistema que pueda usar para vencer a Las Vegas. Aunque fue divertido
Construí todo desde cero, sin marco utilizado.
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 principal 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 ) evoluciona los árboles de sintaxis abstracta analizados 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 byte Java compilado a partir 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 aspecto agradable de la computación evolutiva es la simplicidad de la técnica que permite escribir sus propias implementaciones personalizadas sin demasiada dificultad. Para obtener un buen texto de introducción disponible gratuitamente sobre la programación genética, consulte la Guía de campo para la programación genética .
Un compañero de trabajo y yo estamos trabajando en una solución para cargar la carga en camiones utilizando los diversos criterios que exige nuestra empresa. He estado trabajando en una solución de algoritmo genético mientras él está usando una rama y enlace con poda agresiva. Todavía estamos en el proceso de implementar esta solución, pero hasta el momento hemos obtenido buenos resultados.
Una vez usé una GA para optimizar una función de 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; incrementos regulares de bits medios, etc.) La función de hash original era "maciza": tendía a tener clusters. en cada tercer cubo de hachís. El algoritmo mejorado tuvo una distribución casi perfecta.
Usé una AG para optimizar las asignaciones de asientos en la recepción de mi boda. 80 comensales en 10 mesas. La función de evaluación se basaba en mantener a las personas con sus fechas, juntar a las personas que tenían algo en común y en personas separadas con puntos de vista opuestos en tablas separadas.
Lo corrí varias veces. Cada vez, conseguí nueve buenas mesas, y una con todas las bolas impares. Al final, mi esposa hizo las asignaciones de asientos.
Mi optimista vendedor de viajes utilizó un nuevo mapeo del cromosoma al itinerario, lo que hizo que fuera trivial criar y mutar los cromosomas sin riesgo de generar recorridos no válidos.
Actualización : Porque un par de personas han preguntado cómo ...
Comience con una variedad de invitados (o ciudades) en un ordenamiento arbitrario pero consistente, por ejemplo, alfabetizado. Llama 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 las 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 a intercambiar. Para descodificar un cromosoma, comenzamos con la solución de referencia y aplicamos todos los swaps indicados por el cromosoma. El intercambio de dos entradas en la matriz siempre da como resultado una solución válida: cada invitado (o ciudad) aparece exactamente una vez.
Por lo tanto, los cromosomas pueden generarse aleatoriamente, mutarse y cruzarse con otros y siempre producirán una solución válida.
Utilicé algoritmos genéticos (así como algunas técnicas relacionadas) para determinar las mejores configuraciones para un sistema de administración de riesgos que intentaba evitar que los agricultores de oro usen tarjetas de crédito robadas para pagar los MMO. El sistema admitirí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 correctamente las transacciones fraudulentas sin tener demasiados falsos positivos.
Tuvimos 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 era superior a un umbral, la transacción era un fraude. La AG crearía un gran número de conjuntos aleatorios de valores, los evaluaría frente a un corpus de datos conocidos, seleccionaría los que obtuvieran los mejores puntajes (tanto en la detección de fraudes como en la limitación del número de falsos positivos), y luego cruzarían los mejores pocos. Cada generación para producir una nueva generación de candidatos. Después de un cierto número de generaciones, el conjunto de valores con mejor puntuación se consideró el ganador.
La creación del corpus de datos conocidos para probar fue el talón de Aquiles del sistema. Si esperó las devoluciones de cargo, se retrasó varios meses al tratar de responder a los estafadores, por lo que alguien tendría que revisar manualmente un gran número de transacciones para acumular ese corpus de datos sin tener que esperar demasiado.
Esto terminó identificando la gran mayoría del fraude que se produjo, pero no pudo obtenerlo por debajo del 1% en los artículos más propensos al fraude (dado que el 90% de las transacciones entrantes podrían ser fraude, eso estaba haciendo bastante bien).
Hice todo esto usando perl. Una ejecución del software en una caja de Linux bastante antigua demoraría entre 1 y 2 horas en ejecutarse (20 minutos para cargar datos a través de un enlace WAN, el resto del tiempo dedicado a procesar). El tamaño de cualquier generación dada estaba limitado por la RAM disponible. Lo ejecuté 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 venían con el intento manual de modificar los valores relativos de docenas de indicadores de fraude, y siempre ofreció mejores soluciones de las que podía crear a mano. AFAIK, todavía está en uso (unos 3 años después de que lo escribí).
No la tarea
Mi primer trabajo como programador profesional (1995) fue escribir un sistema de comercio automatizado basado en algoritmos genéticos para futuros de S & P500. La aplicación fue escrita en Visual Basic 3 [!] Y no tengo idea de cómo hice nada en ese 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 de S & P500, así como a un orden específico (compra o venta) y montos de pérdidas y pérdidas. A cada cadena (o "gen") se le evaluó el rendimiento de sus ganancias mediante una corrida a lo largo de 3 años de datos históricos; siempre que la "forma" especificada coincidía con los datos históricos, asumí la orden de compra o venta correspondiente y evalué 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 romperse y eliminarse por completo del conjunto genético.
Después de cada evaluación de una población, los sobrevivientes se cruzaron de forma aleatoria (solo mediante la mezcla de bits de dos padres), con la probabilidad de que un gen fuera seleccionado como padre de forma proporcional al beneficio que produjo. También agregué la posibilidad de mutaciones puntuales para condimentar un poco las cosas. Después de unas cientos de generaciones de esto, terminé con una población de genes que podrían convertir $ 5000 en un promedio de alrededor de $ 10000 sin posibilidad de muerte / ruptura (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 al operar de manera tradicional, y perdió su voluntad de continuar con el proyecto. En retrospectiva, creo que el sistema habría obtenido enormes beneficios, no porque necesariamente estaba haciendo algo bien, sino porque la población de genes que produje estaba sesgada hacia órdenes de compra (en lugar de órdenes de venta) en aproximadamente 5: 1 ratio. Y como sabemos con nuestra visión retrospectiva 20/20, el mercado subió un poco después de 1995.
Hubo una competencia en codechef.com (gran sitio por cierto, competiciones de programación mensuales) en la que se suponía que uno debía resolver un sudoku que no se puede resolver (uno debería estar lo más cerca posible con la menor cantidad de columnas / filas incorrectas / etc).
Lo que haría es generar primero un sudoku perfecto y luego anular los campos que se han dado. A partir de esta buena base, utilicé la programación genética para mejorar mi solución.
No podía pensar en un enfoque determinista en este caso, porque el sudoku era de 300x300 y la búsqueda habría tardado demasiado.
Desarrollé una simulación de navegación robotizada basada en un movimiento de subprocesos múltiples a través de un conjunto de terreno de cuadrícula aleatorizada 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 idóneos para un cromosoma robótico. Esto se hizo mediante la creación de gráficos y mapeo 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 / varios puntos de conexión, retrasos, cancelaciones, trabajos de construcción, hora punta, Huelgas públicas, consideración entre las rutas más rápidas y más baratas. Luego, proporcionar una recomendación equilibrada para la ruta a tomar en un día determinado.
En general, mi estrategia es usar la representación de genes basada en POJO y luego aplico implementaciones de interfaz específicas para la selección, la mutación, las estrategias de cruce y el punto de criterio. Básicamente, mi función de acondicionamiento físico se vuelve bastante compleja según la estrategia y los criterios que debo aplicar como medida heurística.
También he estudiado la aplicación de algoritmos genéticos en pruebas automatizadas dentro del código utilizando ciclos de mutación sistemáticos en los que el algoritmo entiende la lógica e intenta establecer un informe de errores con recomendaciones para correcciones de 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 un nuevo código programático. También he intentado 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ística / global, son lentas de aprender al principio, pero comienzan a recuperarse a medida que las soluciones se acercan cada vez más al estado del objetivo y siempre que su función de aptitud física y heurísticas estén bien alineadas para producir. Esa convergencia dentro de tu espacio de búsqueda.
Después de leer The Blind Watchmaker , me interesó el programa de pascal que Dawkins dijo que había desarrollado para crear modelos de organismos que podrían evolucionar con el tiempo. Me interesé lo suficiente como para escribir mi propio uso de Swarm . No hice todos los gráficos de fantasía que él hizo, sino los rasgos controlados de mis "cromosomas" que afectaban la capacidad de los organismos para sobrevivir. Vivían en un mundo simple y podían enfrentarse entre sí y con su entorno.
Los organismos vivieron o murieron en parte debido al azar, pero también se basaron en la eficacia con la que se adaptaron a sus entornos locales, en lo bien que consumieron los nutrientes y en el éxito con el que se reproducieron. Fue divertido, pero también una prueba más para mi esposa de que soy un geek.
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. Usamos distintivos de GA para generar la música. Creo que este programa puede ser útil para explorar nuevas composiciones.
Experimenté con GA en mi juventud. Escribí un simulador en Python que funcionaba de la siguiente manera.
Los genes codificaron los pesos de una red neuronal.
Las entradas de la red neuronal fueron "antenas" que detectaron 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 chico avanzaba. Si las ruedas estaban en direcciones opuestas, el tipo giró. La fuerza de la salida determina la velocidad de giro de la rueda.
Se generó un simple laberinto. Era realmente simple, incluso estúpido. Hubo un 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 al azar, por lo que siempre había un camino.
Comencé con chicos al azar (pensé en ellos como bichos) al principio. Tan pronto como un hombre alcanzó la meta, o se alcanzó un límite de tiempo, se calculó la condición física. Fue inversamente proporcional a la distancia a la meta en ese momento.
Luego los emparejé y los "crié" para crear la siguiente generación. La probabilidad de ser elegido para ser criado fue proporcional a su aptitud. A veces, esto significaba que uno se criaba consigo mismo repetidamente si tenía un estado físico muy alto.
Pensé que desarrollarían un comportamiento de "abrazo de la pared izquierda", pero siempre parecían seguir algo menos óptimo. En cada experimento, los errores convergieron a un patrón en espiral. Saldrían en espiral hacia afuera hasta que tocaran una pared a la derecha. Seguirían eso, luego, cuando llegaran a la brecha, se moverían hacia abajo (alejándose de la brecha) y alrededor. Hacían un giro de 270 grados a la izquierda, y luego, por lo general, entran en el hueco. Esto los llevaría a través de la mayoría de los muros, y con frecuencia 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 algunas generaciones, todos serían del mismo color, lo que me dice que debería tener una mejor estrategia de reproducción.
Intenté hacer que desarrollaran una mejor estrategia. Complicé la red neuronal, añadiendo un recuerdo y todo. No sirvió de nada. Siempre vi la misma estrategia.
Probé 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 la condición física con el tiempo. Hubo patrones definidos, como el máximo estado físico que se reduce antes de que suba. Nunca he visto un libro de evolución que habla de esa posibilidad.
Fue hace un tiempo, pero hice rodar una AG 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 exposiciones múltiples con el Hubble y mantener solo lo que es igual en todas las imágenes. Dado que el tiempo de HST es tan valioso, soy un aficionado a la astronomía, y había asistido recientemente al Congreso sobre computación evolutiva, pensé en usar una AG para limpiar exposiciones individuales.
Los individuos tenían la forma de árboles que tomaban un área de píxeles de 3x3 como entrada, realizaron algunos cálculos y tomaron una decisión sobre si y cómo modificar el píxel central y cómo hacerlo. La aptitud física se evaluó comparando la salida con una imagen limpiada de la forma tradicional (es decir, apilando exposiciones).
En realidad funcionó, pero no lo suficiente como para justificar el abandono del enfoque original. Si mi tesis no me hubiera limitado el tiempo, podría haber ampliado el contenedor de partes genéticas disponible para el algoritmo. Estoy bastante seguro de que podría haber mejorado significativamente.
Bibliotecas utilizadas: si recuerdo correctamente, IRAF y cfitsio para el procesamiento de datos de imágenes astronómicas y E / S.
Una vez traté de hacer un reproductor de computadora para el juego de Go, basado exclusivamente en la 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 eran muy buenos, incluso en un tablero 3x4 bastante pequeño.
Utilicé Perl, y codifiqué todo yo mismo. Hoy haría las cosas de manera diferente.
Utilicé un algoritmo genético simple para optimizar la relación señal a ruido de una onda que se representó como una cadena binaria. Al voltear los bits de varias maneras a lo largo de varios millones de generaciones, pude producir una transformada 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 utilizó en este caso. En su esencia, los algoritmos genéticos son simples, y esto fue casi tan simple como un caso de uso que he visto, por lo que no usé un marco para la creación y selección de generaciones, solo una semilla aleatoria y la relación Señal / Ruido función a la mano.
en la licenciatura, usamos NERO (una combinación de red neuronal y algoritmo genético) para enseñar a los robots del juego a tomar decisiones inteligentes. Fue bastante genial