¿Cuáles son buenos ejemplos de algoritmos genéticos/soluciones de programación genética?[cerrado]

https://stackoverflow.com/questions/1538235

20-09-2019
|

Pregunta

Algoritmos genéticos (GA) y programación genética (GP) son áreas de investigación interesantes.

Me gustaría saber acerca de los problemas específicos que ha resuelto usando GA/GP y qué bibliotecas/marcos utilizó si no creó el suyo propio.

Preguntas:

¿Qué problemas has utilizado GA/GP para resolver?
¿Qué bibliotecas/marcos usaste?

Estoy buscando experiencias de primera mano, así que no responda a menos que las tenga.

Solución

No tarea.

Mi primer trabajo como programador profesional (1995) era escribir un sistema de comercio automatizado con base genética-algoritmo para S & P500 futuros. La aplicación fue escrita en Visual Basic 3 [!] Y no tengo ni idea de cómo lo hice nada en ese entonces, ya VB3 ni siquiera tenía clases.

La aplicación comenzó con una población de cadenas generadas al azar de longitud fija (el "gen" parte), cada uno de los cuales correspondían a una forma específica en los datos de precios minuto a minuto de los futuros S & P500, así como un orden específico (compra o venta) y stop-loss y dejar de lucro cantidades. Cada cadena (o "gen") tuvo su funcionamiento de beneficio evaluado por una carrera a través de 3 años de datos históricos; siempre que la especificada "forma" coincide con los datos históricos, asumí la compra o venta correspondiente y se evalúa el resultado del comercio. Añadí la salvedad de que cada gen se inició con una cantidad fija de dinero y por lo tanto potencialmente podría ir a la quiebra y ser retirado de la reserva genética completo.

Después de cada evaluación de una población, los supervivientes se cruzaron al azar (por los bits simplemente de mezcla de dos padres), con la probabilidad de un gen que se selecciona como un padre que es proporcional a la ganancia que produjo. También he añadido la posibilidad de mutaciones puntuales para condimentar un poco las cosas. Después de unos pocos cientos de generaciones de esto, que terminó con una población de genes que podrían convertir $ 5000 en un promedio de alrededor de $ 10000 sin posibilidad de muerte / brokeness (en los datos históricos, por supuesto).

Por desgracia, nunca tuve la oportunidad de utilizar este sistema en vivo, ya que mi jefe ha perdido cerca de $ 100.000 en menos de 3 meses a operar de la manera tradicional, y perdió su voluntad de continuar con el proyecto. En retrospectiva, creo que el sistema habría hecho grandes ganancias - no porque yo estaba haciendo necesariamente nada bien, pero debido a que la población de genes que produje pasó a ser sesgada hacia las órdenes de compra (en contraposición a las órdenes de venta) en alrededor de un 5: 1 ratio. Y como sabemos con nuestra visión 20/20, el mercado subió un poco después de 1995.

Otros consejos

Hice pequeñas criaturas que vivieron en este pequeño mundo. Tenían un cerebro red neuronal que recibió algunas entradas del mundo y la salida fue un vector de movimiento entre otras acciones. Sus cerebros fueron los "genes".

El programa se inició con una población aleatoria de criaturas con cerebros al azar. Las entradas y las neuronas de salida eran estáticas, sino que lo que era en el medio no lo era.

El entorno contenía alimentos y peligros. Alimentos aumentó la energía y cuando se tiene suficiente energía, puede aparearse. Los peligros reducirían energía y si la energía fue de 0, que murió.

Con el tiempo las criaturas evolucionaron para mover todo el mundo y encontrar comida y evitar los peligros.

Entonces decidí hacer un pequeño experimento. Le di el cerebro de la criatura una neurona de salida llamado "boca" y una neurona de entrada llamado "oído". Empezamos una y se sorprendió al descubrir que evolucionaron para maximizar el espacio y cada criatura respectiva se quedaría en su respectiva parte (alimento se colocó al azar). Ellos aprendieron a cooperar entre sí y no conseguir en cada sentido otros. Había siempre las excepciones.

A continuación, he intentado algo interesante. I criaturas muertas se convertirían en los alimentos. Trata de adivinar lo que pasó! Hay dos tipos de seres evolucionados, los que atacaron al igual que en enjambres, y los que eran de alta evitación.

Entonces, ¿cuál es la lección aquí? Comunicación significa cooperación. Tan pronto como se introduce un elemento en lastimar a otro significa que adquiera algo, entonces la cooperación se destruye.

Me pregunto cómo esto se refleja en el sistema del libre mercado y el capitalismo. Es decir, si las empresas pueden dañar su competencia y salirse con la suya , su claro que van a hacer todo lo posible por hacer daño a la competencia.

Editar:

Lo escribí en C ++ sin utilizar marcos. Escribió mi propia red neuronal y el código de GA. Eric, gracias por diciendo que es plausible. La gente por lo general no creen en los poderes de GA (aunque las limitaciones son obvias) hasta que tocaron con él. GA es simple pero no simplista.

Para los que dudan, redes neuronales han demostrado ser capaces de simular cualquier función de si tienen más de una capa. GA es una forma bastante simple de navegar por un espacio de soluciones encontrar mínimo local y potencialmente global. Combinar GA con redes neuronales y usted tiene una muy buena manera de encontrar funciones que encuentran soluciones aproximadas para problemas genéricos. Debido a que estamos usando redes neuronales, entonces estamos optimizando la función de algunos insumos, no algunas entradas a una función que otros están usando GA

Aquí está el código de demostración para el ejemplo de la supervivencia: http: //www.mempko .com / darcs / neuronal / demos / comedores / Instrucciones de construcción:

Instalar darcs, libboost, liballegro, gcc, cmake, hacer
darcs clone --lazy http://www.mempko.com/darcs/neural/
cd neural
cmake .
make
cd demos/eaters
./eaters

comedores de pantalla

En enero de 2004, fui contactado por Philips Nuevas Tecnologías de pantallas que estaban creando la electrónica para la primera tinta electrónica jamás comercial, el Sony Librie, que sólo había sido lanzado en Japón, años antes de Amazon Kindle y los otros golpean la mercado en los Estados Unidos una Europa.

Los ingenieros de Philips tenían un problema importante. Unos meses antes de que el producto se supone que llegará al mercado, que todavía estaban recibiendo el efecto fantasma en la pantalla cuando se cambia páginas. El problema era que los 200 conductores que estaban creando el campo electrostático. Cada uno de estos conductores tenían una cierta tensión que tuvo que ser ubicado justo entre cero y 1000 mV o algo así. Pero si ha cambiado uno de ellos, que lo cambiaría todo.

Así que la optimización de la tensión de cada conductor individual estaba fuera de la cuestión. El número de combinaciones posibles de valores estaba en mil millones, y tardó aproximadamente 1 minuto para una cámara especial para evaluar una única combinación. Los ingenieros habían intentado muchas técnicas de optimización estándar, pero nada se aproximarían.

El ingeniero de cabeza puso en contacto conmigo porque yo había publicado previamente una biblioteca de programación genética a la comunidad de código abierto. Me preguntó si GP / GA del ayudaría y si pudiera participar. Lo hice, y alrededor de un mes que trabajamos juntos, yo escribiendo y puesta a punto de la biblioteca GA, en los datos sintéticos, y lo integra en su sistema. A continuación, un fin de semana que se deja correr en vivo con la cosa real.

El lunes siguiente me dieron estos mensajes de correo electrónico brillantes de él y su diseñador de hardware, acerca de cómo nadie podía creer los resultados sorprendentes de la GA se ha encontrado. Esto fue. Más tarde ese mismo año, el producto llegó al mercado.

No se les paga un centavo por ella, pero me dio 'presumiendo' derechos. Dijeron desde el principio que ya estaban por encima del presupuesto, así que sabía lo que el acuerdo era antes de empezar a trabajar en él. Y es una gran historia para aplicaciones de gas. :)

He utilizado un algoritmo genético para optimizar asignaciones de asientos en mi boda. 80 personas de más de 10 tablas. función de evaluación se basó en mantener a la gente con sus fechas, poner a la gente con algo en común entre sí, y mantener a la gente con puntos de vista opuestos extremos en mesas separadas.

Lo pasé varias veces. Cada vez, me dieron buenos nueve mesas, y una con todas las bolas impares. Al final, mi esposa hizo las asignaciones de asientos.

Mi viajante optimizador utiliza una novela mapeo del cromosoma al itinerario, lo que hizo trivial para reproducirse y mutar los cromosomas sin ningún riesgo de generar recorridos no válidos.

Actualizar : Debido a un par de personas han preguntado cómo ...

Iniciar con una variedad de huéspedes (o ciudades) en algún orden arbitraria pero consistente, por ejemplo, en orden alfabético. Llame a este la solución de referencia. Piense en el índice de un cliente como su / su número de asiento.

En lugar de tratar de codificar este ordenamiento directamente en el cromosoma, codificamos instrucciones para la transformación de la solución de referencia en una nueva solución. Específicamente, tratamos a los cromosomas como listas de índices en la matriz a intercambiar. Para obtener decodificar un cromosoma, comenzamos con la solución de referencia y aplicar todas las permutas indicados por el cromosoma. El intercambio de dos entradas de la matriz siempre resulta en una solución válida:. Cada huésped (o ciudad) todavía aparece exactamente una vez

Así cromosomas pueden ser generados al azar, mutados, y cruzaron con los demás y siempre producirá una solución válida.

He utilizado algoritmos genéticos (así como algunas técnicas relacionadas) para determinar la mejor configuración para un sistema de gestión de riesgos que trató de mantener a los agricultores de oro del uso de tarjetas de crédito robadas para pagar por los MMO. El sistema tomaría en varios miles de operaciones con valores "conocidos" (fraude o no) y averiguar cuál es la mejor combinación de ajustes fue identificar adecuadamente las transacciones fraudulentas sin tener demasiados falsos positivos.

Tuvimos datos sobre varias características de una transacción, cada uno de los cuales se le dio un valor y ascendieron hasta docena (boolean). Si el total es mayor que un umbral, la operación fue de fraude. El GA crearía un gran número de juegos de azar de valores, evaluarlos contra un corpus de datos conocidos, seleccionar las que anotó el mejor (tanto en la detección del fraude y que limitan el número de falsos positivos), a continuación, raza cruzada la mejor cuantos de cada generación para producir una nueva generación de candidatos. Después de un cierto número de generaciones el mejor conjunto de puntuación de los valores fue considerado el ganador.

La creación del corpus de datos conocidos para probar en contra fue el talón del sistema de Aquiles. Si se espera para las devoluciones de cargos, que eras varios meses atrás cuando se trata de responder a los defraudadores, por lo que alguien tendría que revisar manualmente un gran número de transacciones para construir ese corpus de datos sin tener que esperar demasiado tiempo.

Esto terminó la identificación de la gran mayoría de los fraudes que entró, pero no pudo conseguirlo por debajo del 1% sobre los artículos más propensas a fraude (dado que el 90% de las transacciones de entrada podría ser el fraude, que estaba haciendo bastante también).

Yo hice todo esto usando Perl. Una carrera del software en una máquina Linux bastante antiguo tomaría 1-2 horas para correr (20 minutos para cargar datos a través de un enlace WAN, el resto del tiempo dedicado crujido). El tamaño de cualquier generación dada estaba limitado por la memoria RAM disponible. Me gustaría correr una y otra vez con ligeros cambios en los parámetros, buscando especialmente un buen conjunto de resultados.

En suma, evitar algunas de las metidas de pata que vinieron con tratar de ajustar manualmente los valores relativos de docenas de indicadores de fraude, y constantemente se acercó con mejores soluciones de lo que podía crear con la mano. Que yo sepa, todavía en uso (aproximadamente 3 años después de que lo escribí).

Fútbol vuelco. He construido un sistema para predecir el GA semana a semana resultado de los partidos de la AFL (Aussie Rules Football).

Hace algunos años me aburrí de la piscina de fútbol estándar de trabajo, todo el mundo era simplemente ir en línea y teniendo los picos de algún experto en la prensa. Por lo tanto, pensé que no podría ser demasiado difícil de superar un montón de carreras de difusión de periodismo, ¿verdad? Mi primera idea fue tomar los resultados de Massey Calificaciones y luego revelar al final de la temporada después de ganar mi estrategia la fama y la gloria. Sin embargo, por razones que nunca he descubierto Massey no hace un seguimiento de la AFL. El cínico en mí cree que es debido a que el resultado de cada juego de la AFL, básicamente, se ha convertido en el azar, pero mis quejas de los últimos cambios en las reglas pertenecen en un foro diferente.

El sistema básicamente considera ofensivo fuerza, la fuerza defensiva, la ventaja de campo, semana a semana mejora (o falta de ella) y la velocidad de los cambios en cada uno de estos. Esto creó un conjunto de ecuaciones polinómicas para cada equipo durante la temporada. El ganador y la puntuación para cada partido para una fecha determinada puede ser calculada. El objetivo era encontrar el conjunto de coeficientes que hacía juego con más de cerca los resultados de todos los juegos anteriores y utilizar ese conjunto de predecir la próxima semana juego.

En la práctica, el sistema sería encontrar soluciones que predijeron con precisión más del 90% de los resultados de los juegos anteriores. Sería entonces recoger con éxito alrededor del 60-80% de los juegos para la próxima semana (es decir la semana no en el conjunto de entrenamiento).

El resultado: justo por encima de mitad de la tabla. No importante premio en metálico ni un sistema que podría utilizar para vencer a Las Vegas. Fue divertido.

he construido todo desde cero, no existe un marco utilizado.

Además de algunos de los problemas comunes, como el vendedor ambulante y una variación en la Roger Alsing programa Mona Lisa , también he escrito un solucionador de Sudoku evolutiva (que requiere un poco más de pensamiento original de mi parte, en lugar de simplemente re-implementación de algún otro idea). Hay algoritmos más fiables para resolver Sudokus, pero el enfoque evolutivo funciona bastante bien.

En los últimos días he estado jugando con un programa evolutivo para encontrar "fríos" cubiertas de poker después de ver este artículo en Reddit. No es bastante satisfactoria en el momento pero creo que puedo mejorarlo.

mi propia marco que utilizo para los algoritmos evolutivos.

he desarrollado una GA cerveza casera para un sistema de perfil superficial con láser 3D mi empresa desarrollado para la industria del transporte en 1992. El sistema se basó en 3 dimensiones triangulación y se utiliza un escáner de línea láser personalizada, una cámara de 512x512 (con HW captura de costumbre). La distancia entre la cámara y el láser no iba a ser preciso y el punto focal de las cámaras eran que no se encuentra en la posición de 256.256 que esperaba que fuera!

Fue una pesadilla para tratar de resolver los parámetros de calibración utilizando la geometría estándar y simulado resolución de ecuaciones estilo de recocido.

El algoritmo genético fue azotado en una noche y me creó un cubo de calibración para probarlo en. Yo sabía que las dimensiones del cubo a una alta precisión y por lo tanto la idea era que mi GA podría evolucionar un conjunto de parámetros de triangulación a medida para cada unidad de exploración que superara las variaciones de producción.

El truco funcionaba un lujo. Estaba atónito por decir lo menos! Dentro de alrededor de 10 generaciones de mi cubo 'virtual' (generado a partir de la exploración de crudo y recreada a partir de los parámetros de calibración) en realidad se parecía a un cubo! Después de alrededor de 50 generaciones que tenía la calibración que necesitaba.

A menudo es difícil conseguir una combinación de colores exacta cuando planeas pintar tu casa.A menudo tienes algún color en mente, pero no es uno de los colores que te muestra el proveedor.

Ayer mi Prof.quien es un investigador de GA que 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 chico de color) solía ir de puerta en puerta para ayudar a las personas a encontrar el código de color exacto (en RGB) ese sería el armario de lo que el cliente tenía en mente.Así es como lo haría:

El chico de color solía llevar consigo un programa de software que utilizaba 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 parecido al que tiene en mente).El programa entonces asignaría el máximo aptitud física a ese individual y pasar al siguiente generación usando mutación/cruce.Los pasos anteriores se repetirían hasta que el consumidor encontrara el color exacto y luego chico de color ¡Solía decirle la combinación RGB!

Al asignar la máxima adecuación al color más cercano a lo que el consumidor tiene en mente, el chico de colorEl programa aumenta las posibilidades de converger exactamente hacia el color que el consumidor tiene en mente.¡Lo encontré muy divertido!

Ahora que tengo un -1, si estás planeando obtener más -1, por favor.¡Aclare el motivo de hacerlo!

Como parte de mi Universitario CompSci, nos asignaron el problema de encontrar indicadores JVM óptimas para el estudio de la máquina virtual Jikes. Esto se evaluó utilizando la suite de rendimiento Dicappo que devuelve una vez a la consola. Escribí un alogirthm gentic distribuida que cambió estas banderas para mejorar el tiempo de ejecución del conjunto de pruebas, aunque tomó días para correr para compensar la fluctuación de hardware que afecta a los resultados. El único problema era que no aprendió adecuadamente acerca de la teoría del compilador (que era la intención de la asignación).

Podría haber sembrado la población inicial con las banderas por defecto exisiting, pero lo interesante fue que el algoritmo encontró una configuración muy similar a la del nivel de optimización O3 (pero en realidad era más rápido en muchas pruebas).

Editar:. También escribí mi propio marco de algoritmo genético en Python para la asignación, y acabo de utilizar los comandos de popen para ejecutar los diversos puntos de referencia, aunque si no fuera una misión evaluado me hubiera mirado PyEvolve

En primer lugar, "programación genética" por Jonathan Koza ( en Amazon ) es más o menos el libro sobre técnicas de algoritmo / programación genética y evolutiva, con muchos ejemplos. Le recomiendo echarle un vistazo.

En cuanto a mi propio uso de un algoritmo genético, he usado un (cosecha propia) algoritmo genético para desarrollar un algoritmo de enjambre para un escenario de recogida de objetos / destrucción (propósito práctico podría haber estado limpiando un campo de minas). Aquí hay un enlace a el papel . La parte más interesante de lo que hice fue la función de aptitud múltiples etapas, que era una necesidad ya que las funciones de fitness simples no proporcionan suficiente información para el algoritmo genético suficiente grado de diferenciación entre los miembros de la población.

Hace un par de semanas, me sugirió 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 con restricciones.

También en el área de aprendizaje automático, he implementado un marco reglas de clasificación basado en GA en C / C ++ desde cero.
También he utilizado GA en un proyecto de ejemplo para la formación redes neuronales artificiales (ANN) en contraposición a la utilización de la famosa algoritmo de retropropagación .

Además, y como parte de mi investigación graduada, que he usado en la formación GA Modelos Ocultos de Markov como un enfoque adicional a la base-EM Baum-Welch algoritmo (en C / C ++ de nuevo).

Soy parte de un equipo que investiga el uso de la computación evolutiva (CE) 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 (ver la página principal de este proyecto ).

Tenemos dos aplicaciones de esta técnica de reparación CE.

La primera ( código y la información de reproducción disponible a través de la página del proyecto ) evoluciona los árboles de sintaxis abstracta analizadas desde los programas existentes de C y se implementa en Ocaml usando nuestro propio motor EC personalizado.
El segundo ( código y la información de reproducción disponible a través de la página del proyecto ), mi contribución personal al proyecto, se desarrolla el montaje x86 o código de bytes de Java compilado a partir de los programas escritos en una serie de lenguajes de programación. Esta aplicación se implementa en Clojure y también utiliza su propio motor hecha a la medida de la CE.

Un aspecto positivo de la computación evolutiva es la simplicidad de la técnica hace que sea posible escribir sus propias implementaciones personalizadas sin demasiada dificultad. Para una buena libremente disponible de texto de introducción a la Programación Genética ver la Guía de Campo de Programación Genética .

Un compañero de trabajo y yo estamos trabajando en una solución para el transporte de mercancías en camiones de carga que utilizan los diversos criterios nuestra empresa requiera. Yo he estado trabajando en una solución Algoritmo Genético, mientras que él está utilizando una rama y atado con la poda agresiva. Todavía estamos en el proceso de implementación de esta solución, pero hasta ahora, hemos estado consiguiendo buenos resultados.

Hace varios años yo solía ga de optimizar ASR (gramáticas de reconocimiento automático del habla) para obtener mejores tasas de reconocimiento. Empecé con las listas de opciones bastante simples (en el que el GA estaba probando combinaciones de términos posibles para cada ranura) y trabajó mi camino hasta las gramáticas más abiertas y complejas. Gimnasio se determinó midiendo la separación entre términos / secuencias bajo una especie de función de distancia fonético. También he experimentado con haciendo variaciones débilmente equivalentes de una gramática para encontrar uno que compila a una representación más compacta (al final me fui con un algoritmo directo, y se incrementó drásticamente el tamaño de la "lengua" que podríamos utilizar en aplicaciones) .

Más recientemente he usado ellos como hipótesis por defecto contra el cual poner a prueba la calidad de las soluciones generadas a partir de diversos algoritmos. Esto tiene categorización en gran medida involucrados y diferentes tipos de problemas de ajuste (es decir, crear una "regla" que explica un conjunto de decisiones tomadas por los colaboradores sobre un conjunto de datos (s)).

Hice un marco completo GA llamado "GALAB", para resolver muchos problemas:

Ubicación de ANTs GSM (BTS) para disminuir la superposición y ubicaciones en blanco.
programación de proyectos restricción de recursos.
evolutivo de creación de imagen. ( Evopic )
El viajar problema del vendedor.
N-Queen y N-color.
problemas de turismo de mochila y de Knight.
cuadrados y Magic Sudoku puzzles.
Compresión de cadena, basado en un problema de supercuerdas.
2D problema de embalaje.
Tiny APP vida artificial.
rompecabezas de Rubik.

Una vez utilizado un algoritmo genético para optimizar una función hash para direcciones de memoria. Las direcciones eran 4K 8K o tamaños de página, por lo que mostraron cierto grado de previsibilidad en el patrón de bits de la dirección (bits menos significativos de todo cero; bits de medias incrementando con regularidad, etc.) La función hash original era "grueso" - que tiende a agruparse éxitos cada tercer cubo hash. El algoritmo mejorado tenía una distribución casi perfecta.

No sé si la tarea cuenta ...

Durante mis estudios rodamos nuestro propio programa para resolver el problema del viajante.

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 la Simulated Annealing .

Se trabajó bastante bien, pero nos tomó un tiempo para entender cómo hacer la fase de 'reproducción' correctamente: modelar el problema que nos ocupa en algo adecuado para la programación genética realmente me llamó la atención como la parte más difícil ...

Fue un curso interesante ya que también incursionó con redes neuronales y similares.

Me gustaría saber si alguien usa este tipo de programación en código de 'producción'.

he construido un simple GA para la extracción de patrones útiles fuera del espectro de frecuencias de la música, ya que se está reproduciendo. La salida se utilizó para conducir efectos gráficos en un plugin winamp.

Entrada: unos cuantos fotogramas FFT (imagina una matriz 2D de flotantes)
Salida: valor flotante individual (suma ponderada de las entradas), con 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 alcance razonable

I tenía unos pocos GAs sintonizado 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 la parte superior 4 de cada población fueron enviados al motor de renderizado.

Un efecto secundario interesante fue que la aptitud media en toda la población era un buen indicador de los cambios en la música, aunque por lo general se llevó 4-5 segundos para averiguarlo.

Como parte de mi tesis que escribió un marco genérico java para los mPOEMS algoritmo de optimización multi-objetivo (optimización multiobjetivo prototipo con medidas de mejora evolucionadas), que es una GA utilizando conceptos evolutivos. Es genérico de manera que todas las partes independiente-problema han sido separados de las partes dependiente de problemas, y una interfaz se povided utilizar el marco con solamente la adición de las partes dependientes de problemas. Así, una persona que quiera utilizar el algoritmo no tiene que empezar desde cero, y facilita trabajar mucho.

Puede encontrar el código aquí .

Las soluciones que se pueden encontrar con este algoritmo se han comparado en un trabajo científico con algoritmos del estado de la técnica de SPE-A-2 y NSGA, y se ha demostrado que el algoritmo performes comparable o incluso mejor, en función de los parámetros que toma para medir el rendimiento, y sobre todo en función de la optimización de problemas que busca sucesivamente.

Se puede encontrar aquí .

También como parte de mi tesis y prueba de trabajo He aplicado este marco para el problema de selección de proyectos se encuentran en la gestión de carteras. Se trata de la selección de los proyectos que agregan mayor valor a la empresa, apoyar la mayor parte de la estrategia de la empresa o cualquier otro objetivo apoyar arbitraria. P.ej. la selección de un determinado número de proyectos de una categoría específica, o la maximización de las sinergias del proyecto, ...

Mi tesis que se aplica este marco para el 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 la cartera en una de la fortuna 500, donde se utiliza un software comercial que también aplica un algoritmo genético para el problema de optimización / cartera de selección de proyectos.

Otros recursos:

La documentación del marco: http://thomaskremmel.com/mpoems/mpoems_in_java_documentation.pdf

papel mPOEMS presentación: http://portal.acm.org/citation.cfm?id=1792634.1792653

En realidad con un poco de todo el mundo el entusiasmo puede fácilmente adaptar el código del marco genérico para un problema de optimización multi-objetivo arbitraria.

En el trabajo que tenía el siguiente problema: las tareas dadas M y N DSP, lo que era la mejor manera de asignar tareas a los DSP? "Mejor" se definió como "minimizar la carga de la DSP más cargado". Había diferentes tipos de tareas, y diversos tipos de tareas tenido varias ramificaciones de rendimiento dependiendo de donde fueron asignados, así que codifica el conjunto de asignaciones entre puestos de DSP como una "cadena de ADN" y luego se usa un algoritmo genético para "raza" la mejor cadena de misiones que pude.

Se trabajó bastante bien (mucho mejor que mi método anterior, que fue el de evaluar todas las combinaciones posibles ... en tamaños de problemas no triviales, que habría tomado años para completar!), El único problema era que no había manera de saber si la solución óptima se ha alcanzado o no. Sólo se podía decidir si la corriente de "mejor esfuerzo" era lo suficientemente bueno, o se deja correr más tiempo para ver si se podía hacer algo mejor.

Había una competencia en codechef.com (sitio interesante por cierto, competiciones mensuales de programación) donde uno se suponía que resolver un sudoku unsolveable (uno debe acercarse lo más posible con el menor número equivocado collumns / filas / etc como sea posible).

lo que yo haría, era generar primero un sudoku perfecto y luego anular los campos, que han sido dadas. De esta bastante buena base sobre la que solía programación genética para mejorar mi solución.

No podía pensar en un enfoque determinista, en este caso, debido a que el sudoku era 300x300 y búsqueda habría llevado demasiado tiempo.

I usado un algoritmo genético simple para optimizar la relación señal a ruido de una onda que se representa como una cadena binaria. Por voltear los bits de las formas determinadas por varios millones de generaciones que era capaz de producir una transformación que dio lugar a una mayor señal a ruido de la ola. El algoritmo también podría haber sido "recocido simulado", pero no se utiliza en este caso. En su esencia, los algoritmos genéticos son simples, y esto fue tan simple de un caso de uso que he visto, así que no hizo uso de un marco para la creación de la generación y selección - solamente una semilla aleatoria y la relación señal-ruido función a la mano.

En un seminario en la escuela, se desarrolla una aplicación para generar música basada en el modo musical. El programa fue construido en Java y la salida era un archivo MIDI con la canción. Nos usando distincts aproachs de GA para generar la música. Creo que este programa puede ser útil para explorar nuevas composiciones.

en la licenciatura, utilizamos NERO (una combinación de redes neuronales y algoritmos genéticos) para enseñar a los robots en el juego para tomar decisiones inteligentes. Que era muy bueno.

he desarrollado una simulación basada oscilación multiproceso de navegación del robot a través de un conjunto de rejilla terreno aleatorio de las fuentes de alimentos y minas y desarrolló una estrategia basada en el algoritmo genético de la exploración de la optimización del comportamiento robótico y la supervivencia de los genes más aptos para un cromosoma robótico. Esto se hizo utilizando la cartografía y mapeo de cada ciclo de iteración.

Dado que, a continuación, he desarrollado aún más el comportamiento de juego. Un ejemplo de aplicación lo construido recientemente para mí fue un algoritmo genético para resolver el problema del hombre de ventas ambulantes en la búsqueda de rutas en el Reino Unido, teniendo en estados de inicio de cuenta y metas, así como uno / múltiples puntos de conexión, retrasos, cancelaciones, las obras de construcción, Hora punta, huelgas públicas, la consideración más rápido entre vs rutas más baratos. A continuación, proporcionar una recomendación equilibrada para la ruta a tomar en un día determinado.

En general, mi estrategia es utilizar POJO representaton con base de genes Luego aplico implementaciones de interfaces específicas para la selección, mutación, las estrategias de cruce, y el punto de criterios. Mi función de aptitud a continuación, básicamente, se convierte en un complejo bastante sobre la base de la estrategia y los criterios que necesito para aplicar como una medida heurística.

También he mirado en la aplicación de algoritmos genéticos en las pruebas automatizadas en el código usando ciclos de mutación sistemáticas en el que el algoritmo comprende la lógica y trata de establecer un informe de error con recomendaciones para los arreglos de código. Básicamente, una manera de optimizar el código y proporcionar recomendaciones para la mejora, así como una forma de automatizar el descubrimiento del nuevo código de programación. También he tratado de aplicar algoritmos genéticos para la producción de música, entre otras aplicaciones.

En general, me parece estrategias evolutivas como la mayoría de las estrategias metaheurístico / optimización global, son lentos para aprender al principio, pero empezar a recoger ya que las soluciones se vuelven más y más al estado de la meta y el tiempo que su función de aptitud y heurística están bien alineados para producir que la convergencia dentro de su espacio de búsqueda.

Una vez traté de hacer un jugador de equipo para el juego de Go, basada exclusivamente en la programación genética. Cada programa sería tratado como una función de evaluación para una secuencia de movimientos. Los programas producidos no eran muy buenos, aunque, incluso en un tablero de 3x4 en lugar diminuitive.

He utilizado Perl, y se codifica todo yo mismo. Me gustaría hacer las cosas de manera diferente hoy en día.

Después de leer El relojero ciego , estaba interesado en el programa Pascal Dawkins dijo que tenía desarrollado para crear modelos de organismos que podrían evolucionar con el tiempo. Yo estaba interesado lo suficiente como para escribir mi propio uso de Swarm . Yo no lo hacen todos los gráficos de lujo critter que hizo, pero mis cromosomas '' rasgos controlados que afectaron la capacidad de los organismos para sobrevivir. Ellos vivían en un mundo simple y podría pegarse unos contra otros y su entorno.

Los organismos vivieron o murieron debido en parte a la casualidad, sino también en función de cómo efectivamente se adaptaron a su entorno local, lo bien que se consumen los nutrientes y el éxito con que se reproducen. Fue divertido, pero también una prueba más a mi esposa que soy un friki.

Fue hace un tiempo, pero me puso un AG para evolucionar lo que eran en efecto los núcleos de procesamiento de imágenes para eliminar las trazas de rayos cósmicos del telescopio espacial Hubble (HST) imágenes. El enfoque estándar es tomar múltiples exposiciones con el Hubble y mantener sólo la materia que es el mismo en todas las imágenes. Dado que el tiempo es tan valioso HST, soy un aficionado a la astronomía, y había asistido recientemente al Congreso sobre computación evolutiva, pensé en utilizar un algoritmo genético para limpiar las exposiciones individuales.

Los individuos fueron en forma de árboles que tuvieron un área de píxeles 3x3 como entrada, realizar algunos cálculos, y produjeron una decisión sobre si y cómo modificar el píxel central. Gimnasio se juzgó mediante la comparación de la salida con una imagen limpiado de la manera tradicional (es decir, las exposiciones de apilamiento).

En realidad, tipo de trabajado, pero no lo suficientemente bien como para justificar el anterior enfoque original. Si no hubiera sido por tiempo limitado mi tesis, podría haber ampliado el recipiente de partes genéticas disponibles para el algoritmo. Estoy bastante seguro de que podría haber mejorado significativamente.

Bibliotecas utilizados:. Si no recuerdo mal, IRAF y cfitsio para el procesamiento de datos de imágenes astronómicas y E / S

he experimentado con GA en mi juventud. Escribí un simulador en Python que funcionaba de la siguiente manera.

Los genes codificados los pesos de una red neural.

entradas de la red neuronal eran "antenas" que detecta los toques. Los valores más altos significan muy cerca y 0 significa no tocar.

Las salidas eran a dos "ruedas". Si las dos ruedas fueron adelante, el chico fue adelante. Si las ruedas estaban en direcciones opuestas, el chico volvió. La fuerza de la salida determina la velocidad de la rueda girando.

Un laberinto sencillo fue generado. Era muy simple - incluso estúpida. No fue el comienzo de la parte inferior de la pantalla y un objetivo en la parte superior, con cuatro paredes de por medio. Cada pared había un espacio sacado al azar, así que siempre había una ruta.

Empecé chicos al azar (pensé en ellos como insectos) en la salida. Tan pronto como llegó a un chico que se alcanzó la meta, o un límite de tiempo, se calculó el gimnasio. Fue inversamente proporcional a la distancia al objetivo en ese momento.

Entonces les emparejó y "criados" para crear la próxima generación. La probabilidad de ser elegido para ser criados era proporcional a su condición física. A veces esto significa que uno ha sido criado con ella misma varias veces si es que tenía una muy alta aptitud relativa.

pensé que iban a desarrollar un comportamiento "pared izquierda abrazos", pero siempre parecía seguir algo menos óptima. En cada experimento, los errores convergieron a un patrón espiral. Ellos espiral hacia afuera hasta tocar la pared a la derecha. Habían siguen que, a continuación, cuando llegaron a la brecha, que habían espiral hacia abajo (lejos de la brecha) y sus alrededores. Harían un giro de 270 grados a la izquierda, a continuación, se entra en la brecha. Esto sería obtener a través de la mayoría de las paredes, y con frecuencia a la meta.

Una característica añadí era poner en un vector de color en los genes para rastrear la relación entre los individuos. Después de unas pocas generaciones, estarían todos del mismo color, que me dicen que debería tener una mejor estrategia de mejoramiento.

He intentado conseguir a desarrollar una mejor estrategia. Complique la red neuronal - la adición de una memoria y todo. No sirvió de nada. Siempre he visto la misma estrategia.

I intentado varias cosas como tener fondos de genes separados que sólo recombinados después de 100 generaciones. Pero nada podría empujarlos a una mejor estrategia. Tal vez fue imposible.

Otra cosa interesante es Graficando la condición física en el tiempo. Había patrones definidos, como la aptitud máxima bajando antes de que subiría. Nunca he visto una charla sobre el libro la evolución en esa posibilidad.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow