Source: http://docplayer.es/1261157-Una-vision-general-de-los-algoritmos-memeticos.html
Timestamp: 2016-12-10 11:40:08+00:00

Document:
⭐Una Visión General de los Algoritmos Meméticos
Una Visión General de los Algoritmos Meméticos
Download "Una Visión General de los Algoritmos Meméticos"
Pascual Parra Caballero
1 Una Visión General de los Algoritmos Meméticos Carlos Cotta Dept. Lenguajes y Ciencias de la Computación, ETSI Informática, University of Málaga, Campus de Teatinos, Málaga, Spain. Resumen Los algoritmos meméticos (MAs) constituyen un paradigma de optimización basado en la explotación sistemática de conocimiento acerca del problema que se desea resolver, y de la combinación de ideas tomadas de diferentes metaheurísticas, tanto basadas en población como basadas en búsqueda local. De la utilidad práctica de los MAs da cuenta la plétora de problemas de optimización complejos que han podido atacarse con éxito gracias a estas técnicas. En este trabajo se proporciona una visión general del paradigma de los MAs, describiendo la arquitectura básica de estas técnicas, y proporcionando algunas directrices para el diseño de un MA satisfactorio en un cierto dominio. También se incluye una panorámica de algunas de aplicaciones destacadas de los MAs, y algunas reflexiones en torno al presente y al futuro de estos métodos. 1. Introducción Uno de los periodos clave en la historia de la Optimización como disciplina lo constituyen sin duda alguna las primeras décadas de la segunda mitad del siglo XX. En un tiempo en el que la concepción natural de la resolución de problemas era la obtención de la solución óptima al mismo (o cuanto menos de una solución con una garantía de aproximación al óptimo), empezó a tomar cuerpo una desagradable realidad: existían muchos problemas de utilidad cierta para los que no sólo resultaba insostenible plantear una resolución exacta, sino que ni tan siquiera un enfoque aproximado con garantías realistas era aceptable en la práctica. Esto abrió el camino a diferentes líneas de investigación para dar respuesta a esta problemática, y que más adelante desembocarían en lo que hoy se conoce como metaheurísticas. Entre las mismas, deben destacarse los algoritmos evolutivos [1, 2, 3, 4] (EAs 1 ) por estar íntimamente relacionados con el tema que nos ocupa: los algoritmos meméticos. A pesar de que estas técnicas fueran consideradas en su momento por parte de la comunidad científica como un reconocimiento de la derrota, el tiempo ha demostrado su utilidad como punta de lanza tecnológica en la optimización de problemas reales. Por supuesto, este éxito no es exclusivo de los EAs, sino que se extiende a otras técnicas relacionas tales como el recocido simulado [5] (SA), la búsqueda tabú [6] (TS), etc. Parte de la justificación (y de hecho, del enfoque metodológico) de los algoritmos meméticos (MAs) se haya precisamente en el éxito de métodos de optimización tan diversos. En este sentido, debe considerarse que en ciertos campos se desarrolló una tendencia al purismo algorítmico, esto es, a no apreciar como característica esencial de estas técnicas su flexibilidad y capacidad de asimilación de elementos algorítmicos externos o ad hoc, que pudieran acercar la técnica de resolución al problema que resolver en cada momento. No fue hasta mediados de los noventa cuando la formulación del así denominado 1 En este y en sucesivos acrónimos se empleará la versión inglesa por motivos de consistencia con la literatura, y para evitar posibles fuentes de confusión o ambigüedad. 12 Teorema de No Free Lunch por Wolpert and Macready [7] dio pie a una suerte de catarsis, a partir de la cual quedó definitivamente claro que un algoritmo de búsqueda u optimización se comporta en estricta concordancia con la cantidad y calidad del conocimiento específico del problema que incorpora. Mirando retrospectivamente a estos años nos encontramos con que esta filosofía que comenzó a imponerse de manera generalizada a finales del siglo XX ya estaba siendo promulgada de hecho con anterioridad por diversos investigadores, e.g., Hart and Belew [8], Davis [9], y Moscato [10]. El paradigma de los MAs surgiría precisamente a partir del trabajo de Pablo Moscato [11, 12, 13]. Los MAs son una familia de mataheurísticas que intentan aunar ideas y conceptos de diferentes técnicas de resolución, como por ejemplo EAs y TS. El adjetivo memético viene del término inglés meme, acuñado por R. Dawkins [14] para designar al análogo del gen en el contexto de la evolución cultural. Resulta conveniente resaltar sin embargo que el empleo de esta terminología no representa un propósito de adherirse a una metáfora de funcionamiento concreta (la evolución cultural en este caso), sino más bien lo contrario: hacer explícito que se difumina la inspiración puramente biológica, y se opta por modelos más genéricos en los que se manipula, se aprende y se transmite información. En relación con esto último y a la forma en la que más comúnmente un MA puede implementarse, pueden encontrarse diversos trabajos que hacen uso de nombre alternativos para referirse a éstos (e.g., EAs híbridos o lamarckianos), o que aun usando el propio término MA, hacen una interpretación muy restringida del mismo. Sea como fuere, puede decirse que un MA es una estrategia de búsqueda en la que una población de agentes optimizadores compiten y cooperan de manera sinérgica [10]. Más aún, estos agentes hacen uso explícito de conocimiento sobre el problema que se pretende resolver, tal como sugiere tanto la teoría como la práctica [15]. La siguiente sección proporciona una descripción algorítmica más detallada de los MAs. 2. Un Algoritmo Memético Básico Los MAs son metaheurísticas basadas en población. Esto quiere decir que mantienen un conjunto de soluciones candidatas para el problema considerado. De acuerdo con la jerga empleada en EAs, cada una de estas soluciones tentativas es denominada un individuo. Tal como se anticipó anteriormente, la naturaleza de los MAs sugiere que el término agente es no obstante más apropiado. El motivo básico es el hecho de que individuo denota un ente pasivo que está sujeto a los procesos y reglas evolutivas, mientras que el término agente implica la existencia de un comportamiento activo, dirigido a propósito a la resolución de un cierto problema. Dicho comportamiento activo se ve reflejado en diferentes constituyentes típicos del algoritmo, como por ejemplo técnicas de búsqueda local. La Figura 1 muestra el esquema general de un MA. Como en los EAs, la población de agentes está sujeta a los procesos de competición y cooperación mutua. Lo primero se consigue a través de los bien conocidos procedimientos de selección (línea 6) y reemplazo (línea 12): a partir de la información que proporciona una función de guía ad hoc se determina la bondad de los agentes en pop; acto seguido, se selecciona una parte de los mismos para pasar a la fase reproductiva atendiendo a dicha bondad. Posteriormente, se vuelve a hacer uso de esta información para determinar qué agentes serán eliminados de la población para hacer sitio a los nuevos agentes. En ambos casos selección y reemplazo pueden usarse cualesquiera de las estrategias típicas de los EAs, e.g., torneo, ranking, elitismo, etc. En cuanto a la cooperación, ésta se consigue a través de la reproducción. En esta fase se crean nuevos agentes a partir de los existentes mediante el empleo de una serie de operadores de reproducción. Tal como se muestra en la Figura 1, líneas 7 11, pueden considerarse un número arbitrario #op de tales operadores, que se aplican secuencialmente a la población de manera segmentada, dando lugar a varias poblaciones intermedias auxpop[i], 0 i #op, 23 Algoritmo Memético Entrada: una instancia I de un problema P. Salida: una solución sol. // generar población inicial 1 : para j 1:popsize hacer 2 : sea ind GenerarSoluciónHeuristica (I) 3 : sea pop[j] MejoraLocal (ind, I) 4 : finpara 5 : repetir // bucle generacional // Selección 6 : sea criadores SeleccionarDePoblación (pop) // Reproducción segmentada 7 : sea auxpop[0] pop 8 : para j 1:#op hacer 9 : sea auxpop[j] AplicarOperador (op[j], auxpop[j 1], I) 10 : finpara 11 : sea newpop auxpop[#op] // Reemplazo 12 : sea pop ActualizarProblación (pop, newpop) // Comprobar convergencia 13 : si Convergencia (pop) entonces 14 : sea pop RefrescarPoblación (pop, I) 15 : finsi 16 : hasta CriterioTerminación (pop, I) 17 : devolver Mejor (pop, I) Figura 1: Plantilla general de un MA donde auxpop[0] está inicializada a pop, y auxpop[#op] es la descendencia final. En la práctica, la situación más típica es la de utilizar simplemente tres operadores: recombinación, mutación, y mejora local. Apréciese en la línea 9 del pseudocódigo que estos operadores reciben no sólo las soluciones sobre las que actúan, sino también la instancia I que se desea resolver. Con esto se ilustra el hecho de que los operadores de un MA son conscientes del problema, y basan su funcionamiento en el conocimiento que incorporan sobre el mismo (a diferencia de los modelos más clásicos de EA). Uno de los procesos reproductivos que mejor encapsula la cooperación entre agentes (dos, o más [16]) es la recombinación. Esto se consigue mediante la construcción de nuevas soluciones a partir de la información relevante contenida en los agentes cooperantes. Por relevante se entiende que los elementos de información considerados tienen importancia a la hora de determinar (en un sentido o en otro) la calidad de las soluciones. Ésta es sin duda una noción interesante que se aleja de las más clásicas manipulaciones sintácticas, típicas de EAs simples. Volveremos a esto más adelante, en la próxima sección. El otro operador clásico la mutación cumple el rol de mantener vivo el fuego, inyectando nueva información en la población de manera continua (pero a ritmo bajo, ya que de lo contrario el algoritmo se degradaría a una pura búsqueda aleatoria). Por supuesto, esta interpretación es la que proviene del área de los algoritmos genéticos [17], y no necesariamente coincide con la otros investigadores (aquellos del área de la programación evolutiva [1] sin ir más lejos). De hecho, en ocasiones se ha aducido que la recombinación no es es más que una macro-mutation, y 34 ciertamente ese puede ser el caso en numerosas aplicaciones de los EAs en los que este operador de recombinación simplemente realiza una mezcla aleatoria de información. Sin embargo, no cabe hacer una apreciación similar en el campo de los MAs, ya que en éstos la recombinación se realiza típicamente mediante el empleo de estrategias astutas, y por lo tanto contribuyen de manera esencial a la búsqueda. Finalmente, una de las características más distintivas de los MAs es el empleo de estrategias de búsqueda local (LS). Éstas (nótese que pueden emplearse diferentes estrategias de LS en diferentes puntos del algoritmo) constituyen una de las razones esenciales por las que es apropiado usar el término agente en este contexto: su funcionamiento es local, y en ocasiones incluso autónomo. De esta manera, un MA puede verse como una colección de agentes que realizan una exploración autónoma del espacio de búsqueda, cooperando en ocasiones a través de la recombinación, y compitiendo por recursos computacionales a través de los mecanismos de selección/reemplazo. El pseudocódigo de la Figura 1 muestra un componente que merece asimismo atención: el procedimiento RefrescarPoblación (líneas 13 15). Este procedimiento tiene suma importancia con vistas al aprovechamiento de los recursos computacionales: si en un determinado instante de la ejecución todos los agentes tienen un estado similar (esto es, se ha producido convergencia), el avance de la búsqueda se torna muy complejo. Este tipo de circunstancias puede detectarse a través del empleo de medidas tales como la entropía de Shannon [18], fijando un umbral mínimo por debajo del cual se considera que la población ha degenerado. Obviamente, dicho umbral depende de la representación de problema que se esté usando, y debe decidirse por lo tanto de manera particular en cada caso. 3. Diseño de MAs Efectivos Atacar un cierto problema de optimización con MAs requiere instanciar la plantilla genérica descrita anteriormente, empleando para ello conocimiento del problema. Dado que el diseño de un algoritmo de búsqueda efectivo es en general tan complejo como los propios problemas que se desean resolver, nos encontramos ante la tesitura de tener que emplear directrices heurísticas para abordar dicho problema de diseño. A continuación se consideraran algunas de estas directrices para algunos de los componentes esenciales de los MAs Representación El primer elemento que debe determinarse es la representación de las soluciones que se va a usar. Es importante en este punto aclarar que representación no debe entenderse como meramente codificación, algo para lo que lo relevante son consideraciones relativas a consumo de memoria, complejidad de manipulación, etc. Muy al contrario, la representación hace referencia a la formulación abstracta de las soluciones desde el punto de vista del algoritmo [19]. En este sentido, recuérdese la mención a información relevante que se hizo en la Seccción 2. Dada una cierta representación de las soluciones, éstas pueden entenderse como compuestas de determinadas unidades de información; si los operadores que emplea el MA son conscientes del problema atacado, las unidades de información que identifiquen deben servir para determinar si una solución es buena/prometedora o no. La dinámica del sistema debe entonces tender a retener las unidades de información que lleven asociadas un efecto positivo, y a eliminar aquellas que tengan connotación negativa. El siguiente ejemplo puede ayudar a ilustrar este aspecto de la representación. Considérese un problema definido sobre un espacio de soluciones compuesto de todas las permutaciones de n elementos; estas soluciones pueden entenderse como compuestas por diferentes tipos de información [20], e.g., 45 posicional, i.e., el elemento e aparece en la posición j. precedencia, i.e., el elemento e aparece antes/después que el elemento e. adyacencia, i.e., el elemento e aparece junto al elemento e. La relevancia de cada tipo de información dependerá obviamente del problema que se desea resolver. Por ejemplo, la información de adyacencia es importante para el problema del viajante de comercio (TSP), pero no así la información posicional. Por otra parte, se ha comprobado que esta última sí es relevante en problemas de planificación de cadenas de montaje (flowshop scheduling) (FS) [21], siendo la información de adyacencia menos importante en este caso. Esto quiere decir que un operador de recombinación como ER (edge-recombination) [22] funcionará mejor que un operador basado en información posicional como PMX (partially-mapped crossover) [23] o UCX (uniform cycle crossover) [21] en el TSP, pero los últimos funcionarán mejor sobre FS. No es sorprendete a la vista de lo anterior que la obtención de métodos o medidas para cuantificar la bondad de una cierta representación para un cierto problema haya sido y sea un tema de gran interés. Ha habido diferentes propuestas en este sentido: epistasis (i.e., la influencia no aditiva que sobre la función objetivo tiene la combinación de varias unidades de información) [24, 25], varianza en la adecuación de formas (i.e., varianza en los valores que devuelve la función objetivo para soluciones que comparten un cierto conjunto de unidades de información) [26], y correlación de adecuación (correlación entre los valores de la función objetivo para entre unas soluciones y sus descendientes directos) [27, 28]. Debe reseñarse que además de usar una métrica para predecir cuán bueno puede ser el rendimiento de un cierto operador pre-existente (i.e., análisis inverso), pueden definirse nuevos operadores ad hoc para manipular la mejor representación (análisis directo) [13]. Sea cual fuere la métrica usada para cuantificar la bondad de una representación concreta, hay otras consideraciones que también pueden jugar un papel determinante en el rendimiento final del algoritmo, tales como por ejemplo la existencia de restricciones en el espacio de búsqueda. Esta última problemática puede atacarse de tres maneras: (i) usando funciones de penalización que dirijan la búsqueda hacia regiones factibles, (ii) usando mecanismos de reparación que produzcan soluciones factibles a partir de soluciones infactibles, y (iii) usando operadores reproductivos que permanezcan siempre dentro de la zona factible. En los dos primeros casos es posible mantener la complejidad de la representación a un nivel más bajo (aunque lógicamente el algoritmo se beneficiará de cualquier conocimiento que adicional que pudiera usarse aquí). En el tercer caso, es responsabilidad de la representación o de los operadores el garantizar la factibilidad, y esto conllevará una complejidad adicional. Así, es posible definir representaciones indirectas que mediante el empleo de decodificadores garanticen la factibilidad de las soluciones representadas. La idea básica es utilizar un mecanismo sofisticado para pasar del genotipo al fenotipo, de manera que no sólo se consigan soluciones factibles, sino que además se introduzca conocimiento del problema que facilite que éstas sean de calidad (e.g., [29, 30, 31] entre otras) Operadores Reproductivos La generación de nuevas soluciones durante la fase reproductiva se realiza mediante la manipulación de las unidades de información relevantes que se han identificado. A tal fin, puede emplearse cualquiera de las plantillas genéricas definidas para ello, e.g., RRR (random respectful recombination), RAR (random assorting recombination), y RTR (random transmitting recombination) entre otras [32]. En cualquier caso, huelga decir que el rendimiento de algoritmo se verá beneficiado si en lugar de manipular las unidades de información a ciegas, se hace de manera inteligente empleando conocimiento del problema. Desde un punto de vista general, esta inclusión de conocimiento del problema en la manipulación de las unidades de información tiene dos 56 vertientes: la selección de las características parentales que serán transmitidas a la descendencia, y la selección de las características no-parentales que serán incluidas en la misma. En relación a la selección de la información contenida en los padres que debe transmitirse a los hijos, la evidencia experimental aconseja conservar aquellas características comunes a ambos padres (e.g., [22, 33]). Una vez hecho esto, el descendiente puede completarse de diferentes maneras. Así, Radcliffe y Surry [26] proponen el empleo de estrategias de búsqueda local o de esquemas de enumeración implícitos. Estos últimos pueden usarse también para encontrar la mejor combinación posible de la información parental [34, 35, 36, 37] (dependiendo de las características de la representación, sería posible que esta combinación no necesariamente respetara las propiedades comunes). Puede apreciarse fácilmente que este tipo de recombinación sería monótono en el sentido de que los hijos serían siempre al menos tan buenos como los padres. Hasta cierto punto podría hacerse un análisis similar del operador de mutación, si bien es verdad que éste juega un papel bien distinto: introducir nueva información en la población. En principio, esto puede conseguirse mediante la eliminación de ciertas unidades de información de una solución, y su substitución por información puramente aleatoria, o por información obtenida por alguno de los métodos de completado descritos anteriormente. Sin embargo, hay que resaltar que el papel de la mutación tiene ciertos matices diferenciadores en MAs frente a los clásicos EAs. De hecho, es posible incluso que un MA no tenga un operador de mutación diferenciado, sino que éste esté simplemente empotrado en la búsqueda local, e.g., véase [38, 39]. Uno de los motivos es el hecho de que los MAs están dotados de mecanismos de reinicio de la población (véase la Sección 3.4), y en ciertos contextos puede ser mejor dejar converger la población rápidamente y luego reiniciar, que diversificar constantemente la búsqueda. En cualquier caso, hay situaciones en las que mutación sí adquiere un papel determinante, y en las que incluso se emplean varios operadores de mutación. Esto se realiza bien por el empleo de diferentes vecindades (e.g., [40]), o definiendo mutaciones débiles y fuertes que introduzcan diferentes niveles de perturbación (e.g., [41]). Nótese que en cierto sentido el empleo de diferentes operadores reproductivos implica de manera implícita la consideración de diferentes representaciones y/o vecindades durante la ejecución, muy en la línea de los que se hace en la búsqueda en vecindades variables [42] (VNS). Es posible introducir también conocimiento del problema mediante el empleo de heurísticas constructivas en los operadores de inicialización usados para la generación de la población inicial (Figura 1, línea 2). Por ejemplo, se han empleado estrategias voraces para este propósito en [43, 44] Búsqueda Local La presencia de componentes de búsqueda local (LS) es tal como se comento anteriormente una de las características más distintivas de los MAs. El hecho de que la mayoría de los MAs incorporen LS es una de las causas por las que a veces se pueden encontrar simplificaciones del tipo MA = EA + LS, y que deben evitarse; véase [11, 12, 13] para más detalles. De hecho, es posible encontrar enfoques metaheurísticos con muy similar filosofía a la de los MAs, y que sin embargo no pueden llamarse evolutivos a no ser que se asuma una definición tan amplia del termino que prácticamente abarque a cualquier método basado en población. La técnica de búsqueda dispersa (SS) [45] es un buen ejemplo en este sentido. Por otra parte, no es extraño encontrar enfoques evolutivos en los que el conocimiento del problema se concentra más en el operador de recombinación que en el uso de una búsqueda local, e.g., [35, 46]. En cualquier caso, esta claro que EA + LS MA, y que el componente LS es típicamente uno de los que más contribuyen al éxito del algoritmo. Las técnicas de mejorar local pueden modelarse como trayectorias en el espacio de búsqueda tal que soluciones vecinas en dicha trayectoria difieren en una pequeña cantidad de unidades de información. Esta definición idealizada puede requerir no obstante diferentes matizaciones si 67 por ejemplo se emplea TS para este fin, e.g., [47, 36, 48] entre otras muchas. Así, es normal que muchas implementaciones de TS usen estrategias de intensificación que hagan que en ciertos momentos la búsqueda se continúe por ciertas soluciones anteriores de calidad (así, más que a un camino lineal, el recorrido a través del espacio de búsqueda se asemejaría a una trayectoria ramificada). Más aún tanto en TS como en otras metaheurísticas tales como SA, puede darse que la calidad de las soluciones no se incremente de manera monótona, sino que en ciertos momentos empeore con la finalidad de poder escapar de óptimos locales. Por supuesto, al final de la ejecución del procedimiento se conserva la mejor solución encontrada, y no la última generada. A la hora de implementar el componente LS es importante determinar el criterio de terminación. Si se está empleando una técnica simple de escalada (HC) puede tener sentido determinar si la solución actual es un óptimo local y detener el procedimiento únicamente en ese caso. Obviamente, esto no es posible si se usa TS o SA, ya que estas técnicas tienen capacidades globales de optimización, por lo que lo más común es definir un tope computacional máximo (e.g., en forma de número de soluciones exploradas). Lógicamente, en este caso la solución final no tiene por qué ser un óptimo local (como algunas descripciones erróneas de MAs aseguran). Además, debe encontrarse un equilibrio adecuado entre el esfuerzo computacional que se realiza durante LS y el que la búsqueda poblacional subyacente realiza. La importancia de este hecho ha dado lugar a la noción de lamarckismo parcial [49, 50], esto es, no usar siempre la búsqueda local, sino únicamente sobre algunas soluciones o bien seleccionadas aleatoriamente, o bien en función de su calidad, o bien según algún otro método (véase también [51]). Del mismo modo que se pueden definir métricas para cuantificar la bondad de una representación (u operador que trabaje sobre la misma), pueden definirse métricas que ayuden a predecir si una determinada definición de vecindad puede ser beneficiosa. Por ejemplo, la correlación entre distancia y adecuación [52, 53] (FDC) es una de las propuestas. Esencialmente, la distancia mencionada se entiende como el número de movimientos (saltos de vecindad) que hay que realizar para pasar de un óptimo local al óptimo global. Si el coeficiente de correlación entre esta distancia y la calidad de la función objetivo es alta, entonces la calidad de las soluciones tiende a mejorar al acercarse al óptimo global, y la dinámica evolutiva del MA lo llevará a su cercanía. Si la correlación fuera negativa, el problema sería engañoso para el MA, ya que los óptimos locales mejores se alejarían del óptimo global. Otro aspecto importante en relación al paisaje de búsqueda es su topología global, y más precisamente si la relación de vecindad es regular o no, y que relación guarda con la calidad de las soluciones. Bierwirth et al. [54] han estudiado esta circunstancia para un problema de planificación, y han encontrado que las mejores soluciones tienen una mayor conectividad, lo que las hace más fácilmente alcanzables, incluso por mor de pura deriva genética. No todos los problemas tienen esta propiedad, y de hecho, Cotta y Fernández han encontrado que la representación directa para la búsqueda de reglas de Golomb de tamaño mínimo tiene precisamente la propiedad opuesta [55] Gestión de la Diversidad Hay diferentes maneras de enfocar la diversidad en algoritmos basados en población. Por un lado pueden considerarse métodos de preservación de la diversidad, dentro de los cuales se engloban claramente los operadores de mutación. Éstos no son los únicos mecanismos posibles sin embargo. Por ejemplo, pueden introducirse soluciones completamente nuevas (los así llamados inmigrantes aleatorios ) [56] en la población, e.g., [57], o pueden emplearse poblaciones con estructura espacial [58]. En este último caso, se restringe el emparejamiento de agentes o el reemplazo de los mismos a elementos situados en posiciones vecinas dentro de la estructura topológica de la población. Esto causa un ralentizamiento de la propagación de información a 78 través de la población, con lo que se impide (o al menos dificulta) que algunos super-agentes tomen rápidamente control de la misma y destruyan toda diversidad. En la literatura se han propuesto diferentes topologías para organizar la población, i.e., anillos, rejillas, hipercubos, etc. En relación con los MAs, una de las opciones más exitosas has sido una estructura jerárquica en forma de árbol ternario [59, 41, 60, 61]. Esta topología se ha combinado con una estrategia para organizar la distribución de las soluciones en función de su calidad. Más concretamente, cada nodo del árbol está restringido a tener una solución mejor que cualquiera de los nodos descendientes. Esto implica que cuando un agente tiene una solución mejor que la de su antecesor directo en el árbol, las intercambian. De esta manera, hay un continuo flujo de soluciones de calidad hacia la parte superior del árbol, lo cual también garantiza que cuando se realiza una recombinación, las soluciones que toman parte en ella son de calidad similar. Como complemento a los mecanismos de preservación anteriores se pueden considerar también los mecanismos de restauración de la diversidad: cuando se detecta que la diversidad ha caído por debajo de un cierto umbral, o cuando la dinámica del algoritmo apunta a un estado de degeneración en la búsqueda [62] se activa uno de estos mecanismos para relanzarla. Una posibilidad en este sentido es emplear hipermutación [63, 41] (cf. mutación pesada, véase Sección 3.2). Alternativamente, la población puede refrescarse mediante la llegada masiva de inmigrantes aleatorios que sustituyan a toda la población, salvo a algunas soluciones de elite. 4. Aplicaciones de los MA Uno de los campos más fructíferos para los MAs es el ámbito de la optimización combinatoria, para el que estas técnicas cuentan con cientos de aplicaciones. Eso no es sorprendente si tenemos en consideración que existen miles de problemas de optimización pertenecientes a la clase NP, donde los MA se han mostrado de gran valor. De entre todas éstas, y a modo ilustrativo, pueden destacarse las siguientes: problemas de particionado en grafos [64, 65], partición de números [66, 59], conjunto independiente de cardinalidad máxima [67, 68], empaquetado [69], coloreado de grafos [70, 71], recubrimiento de conjuntos [72], planificación de tareas en una máquina con tiempos de set-up y fechas de entrega [73, 74], planificación de tareas en varias máquinas [75, 76], problemas de asignación generalizados [77], problemas de mochila multidimensional [78, 79], programación entera no-lineal [80], asignación cuadrática [81, 53], particionado de conjuntos [82], y muy especialmente el problema del viajante de comercio [83, 53, 84]. Es de destacar que en una gran parte de estas publicaciones los propios autores destacan que la metodología constituye el estado del arte para el problema en consideración, lo que es de interés debido a que estos son problemas clásicos en el área de la optimización combinatoria. El paradigma fue utilizado en otros problemas menos conocidos, pero sin duda de igual importancia, como son: emparejamiento parcial de formas geométricas [85], optimización en paisajes NK [86], diseño de trayectorias óptimas para naves espaciales [87], asignación de frecuencias [88], construcción de árboles de expansión mínimos con restricciones de grado [89], problemas de emplazamiento [90, 91], optimización de rutas [92], problemas de transporte [93, 94], isomorfismos en grafos [95], problemas de biconexión de vértices [96], agrupamiento [97], telecomunicaciones [98], búsqueda de regleros de Golomb mínimos [99, 100], búsqueda de patrones estables en autómatas celulares [36, 101], identificación de sistemas no-lineares [102], programación de tareas de mantenimiento [103, 104], open shop scheduling [105, 40], flowshop scheduling [106, 44], planificación de proyectos [107, 108], planificación de almacén [109], planificación de producción [110, 111], confección de horarios [112, 113], planificación de turnos [114, 115], planificación de juegos deportivos [116] y planificación de exámenes [117, 118]. Los MAs, también han sido citados en la literatura de aprendizaje en máquinas y robótica como algoritmos genéticos híbridos. Destacamos algunas aplicaciones como por ejemplo: entre- 89 namiento de redes neuronales [119, 120], reconocimiento de características [121], clasificación de características [122, 123], análisis de series temporales [124], aprendizaje de comportamientos reactivos en agentes móviles [125], planificación de trayectorias [126, 127], control óptimo [128], etc. En las áreas de la Electrónica y la Ingeniería podemos destacar: proyectos de VLSI [129], optimización de estructuras [130] y mecánica de fracturas [131], modelado de sistemas [132], control de reactores químicos [133], calibración de motores [134], problemas de diseño óptimo en Aeronáutica [135, 136], diseño de sistemas ópticos [137], control de tráfico [138], y planificación en problemas de potencia [139] entre otros. Otras aplicaciones de estas técnicas pueden encontrarse en: Medicina [140, 141], Economía [142, 143], Oceanografia [144], Matemáticas [145, 146, 147], Procesamiento de imágenes y de voz [148, 149, 150], y un sinnúmero de ellas en Bioinformática ([49, 60, 151, 152] entre otras muchas). 5. Conclusiones A diferencia de otras técnicas de optimización, los MAs fueron explícitamente concebidos como un paradigma ecléctico y pragmático, abierto a la integración de otras técnicas (metaheurísticas o no). En última instancia, esta habilidad para combinar de manera sinergética diferentes métodos es una de las razones de su éxito. Los MAs proporcionan un marco de trabajo apropiado para integrar en un único motor de búsqueda diferentes heurísticas provechosas. En este sentido, los MAs deben considerarse no como competidores, sino como integradores: allá donde una metaheurística pura empiece a alcanzar sus límites, los MAs constituyen el siguiente paso natural. Aunque existe un importante componente experimental en el diseño de los MAs, no por ello puede afirmarse que el paradigma se reduce a combinar varias técnicas y realizar pruebas experimentales para comprobar si es satisfactoria. Muy al contrario, todo el corpus teórico disponible tanto para técnicas basadas en población como para técnicas de búsqueda local es de aplicación en el diseño de un MA. Otras estrategias de gran interés en este área son el diseño por analogía, y el máximo aprovechamiento de los recursos computaciones. Téngase en cuenta en relación a esto último que una técnica de búsqueda local muy sofisticada puede proporcionar mejores resultados que un simple HC, pero necesitar mucho más tiempo de cómputo para ello. En problemas en los que el coste de evaluar una solución es grande, o en los que los tamaños de las vecindades son considerables, éste es un problema que debe tenerse muy en cuenta. Está claro asimismo que nuestro mundo se está haciendo cada vez más complejo a un ritmo acelerado, al menos desde un punto de vista tecnológico. Los años venideros depararán nuevos desafíos desde el punto de vista de la optimización a los que habrá que dar respuesta con metaheurísticas. No sólo habrá que hacer frente a problemas de optimización a gran escala, sino que estos mismos serán cada vez más complejos per se. Para ello, las técnicas de optimización tendrán que adaptarse a esta complejidad, dejando de lado los tradicionales enfoques unidimensionales y puramente secuenciales. Así, algunos de los aspectos de los MAs que tomarán cada vez más relevancia son la optimización multi-objetivo [51, 153, 154], la auto-adaptación [155, 156], y el funcionamiento autónomo [157, 158]. Como puede apreciarse, ya hay algunas propuestas en este sentido, siendo posible además aprovechar ideas de técnicas relacionadas tales como las hiperheurísticas [159, 160]. Otros métodos jugarán también un papel esencial, e.g., las técnicas de reducción a un kernel seguro comúnmente empleadas dentro del campo de la complejidad parametrizada [161]. Dado que el eclecticismo es esencial para adaptarse a este nuevo escenario, sólo cabe decir que el futuro es prometedor para los MAs. 910 Agradecimientos El autor agradece el apoyo parcial del MCyT a través del contrato TIN C Referencias [1] Fogel, L.J., Owens, A.J., Walsh, M.J.: Artificial Intelligence through Simulated Evolution. John Wiley & Sons, New York (1966) [2] Holland, J.: Adaptation in Natural and Artificial Systems. University of Michigan Press (1975) [3] Rechenberg, I.: Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog, Stuttgart (1973) [4] Schwefel, H.P.: Kybernetische Evolution als Strategie der experimentellen Forschung in der Strömungstechnik. Diplomarbeit, Technische Universität Berlin, Hermann Föttinger Institut für Strömungstechnik (1965) [5] Kirkpatrick, S., Gelatt Jr., C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220 (1983) [6] Glover, F., Laguna, M.: Tabu Search. Kluwer Academic Publishers, Boston, MA (1997) [7] Wolpert, D.H., Macready, W.G.: No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation 1(1) (1997) [8] Hart, W.E., Belew, R.K.: Optimizing an arbitrary function is hard for the genetic algorithm. In Belew, R.K., Booker, L.B., eds.: Proceedings of the 4 th International Conference on Genetic Algorithms, San Mateo CA, Morgan Kaufmann (1991) [9] Davis, L.D.: Handbook of Genetic Algorithms. Van Nostrand Reinhold Computer Library, New York (1991) [10] Moscato, P.: On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms. Technical Report Caltech Concurrent Computation Program, Report. 826, California Institute of Technology, Pasadena, California, USA (1989) [11] Moscato, P.: Memetic algorithms: A short introduction. In Corne, D., Dorigo, M., Glover, F., eds.: New Ideas in Optimization. McGraw-Hill, Maidenhead, Berkshire, England, UK (1999) [12] Moscato, P., Cotta, C.: A gentle introduction to memetic algorithms. In Glover, F., Kochenberger, G., eds.: Handbook of Metaheuristics. Kluwer Academic Publishers, Boston MA (2003) [13] Moscato, P., Cotta, C., Mendes, A.S.: Memetic algorithms. In Onwubolu, G.C., Babu, B.V., eds.: New Optimization Techniques in Engineering. Springer-Verlag, Berlin Heidelberg (2004) [14] Dawkins, R.: The Selfish Gene. Clarendon Press, Oxford (1976) [15] Culberson, J.: On the futility of blind search: An algorithmic view of No Free Lunch. Evolutionary Computation 6 (1998)11 [16] Eiben, A.E., Raue, P.E., Ruttkay, Z.: Genetic algorithms with multi-parent recombination. In Davidor, Y., Schwefel, H.P., Männer, R., eds.: Parallel Problem Solving From Nature III. Volume 866 of Lecture Notes in Computer Science. Springer-Verlag (1994) [17] Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, MA (1989) [18] Davidor, Y., Ben-Kiki, O.: The interplay among the genetic algorithm operators: Information theory tools used in a holistic way. In Männer, R., Manderick, B., eds.: Parallel Problem Solving From Nature II, Amsterdam, Elsevier Science Publishers B.V. (1992) [19] Radcliffe, N.J.: Non-linear genetic representations. In Männer, R., Manderick, B., eds.: Parallel Problem Solving From Nature II, Amsterdam, Elsevier Science Publishers B.V. (1992) [20] Fox, B.R., McMahon, M.B.: Genetic operators for sequencing problems. In Rawlins, G.J.E., ed.: Foundations of Genetic Algorithms I, San Mateo, CA, Morgan Kaufmann (1991) [21] Cotta, C., Troya, J.M.: Genetic forma recombination in permutation flowshop problems. Evolutionary Computation 6 (1998) [22] Mathias, K., Whitley, L.D.: Genetic operators, the fitness landscape and the traveling salesman problem. In Männer, R., Manderick, B., eds.: Parallel Problem Solving From Nature II, Amsterdam, Elsevier Science Publishers B.V. (1992) [23] Goldberg, D.E., Lingle Jr., R.: Alleles, loci and the traveling salesman problem. In Grefenstette, J.J., ed.: Proceedings of the 1 st International Conference on Genetic Algorithms, Hillsdale NJ, Lawrence Erlbaum Associates (1985) [24] Davidor, Y.: Epistasis Variance: Suitability of a Representation to Genetic Algorithms. Complex Systems 4 (1990) [25] Davidor, Y.: Epistasis variance: A viewpoint on GA-hardness. In Rawlins, G.J.E., ed.: Foundations of Genetic Algorithms I, San Mateo, CA, Morgan Kaufmann (1991) [26] Radcliffe, N.J., Surry, P.D.: Fitness Variance of Formae and Performance Prediction. In Whitley, L.D., Vose, M.D., eds.: Foundations of Genetic Algorithms III, San Francisco, CA, Morgan Kaufmann (1994) [27] Dzubera, J., Whitley, L.D.: Advanced Correlation Analysis of Operators for the Traveling Salesman Problem. In Schwefel, H.P., Männer, R., eds.: Parallel Problem Solving from Nature III. Volume 866 of Lecture Notes in Computer Science., Dortmund, Germany, Springer-Verlag, Berlin, Germany (1994) [28] Manderick, B., de Weger, M., Spiessens, P.: The Genetic Algorithm and the Structure of the Fitness Landscape. In Belew, R.K., Booker, L.B., eds.: Proceedings of the 4 th International Conference on Genetic Algorithms, San Mateo, CA, Morgan Kaufmann (1991) [29] Aickelin, U., Dowsland, K.: Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem. Journal of Scheduling 3 (2000)12 [30] Cotta, C., Troya, J.: A hybrid genetic algorithm for the 0-1 multiple knapsack problem. In Smith, G., Steele, N., Albrecht, R., eds.: Artificial Neural Nets and Genetic Algorithms 3, Wien New York, Springer-Verlag (1998) [31] Varela, R., Puente, J., Vela, C.R.: Some issues in chromosome codification for scheduling with genetic algorithms. In Castillo, L., Borrajo, D., Salido, M.A., Oddi, A., eds.: Planning, Scheduling and Constraint Satisfaction: From Theory to Practice. Volume 117 of Frontiers in Artificial Intelligence and Applications. IOS Press (2005) 1 10 [32] Radcliffe, N.J.: The algebra of genetic algorithms. Annals of Mathematics and Artificial Intelligence 10 (1994) [33] Oğuz, C., Ercan, M.F.: A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks. Journal of Scheduling 8 (2005) [34] Cotta, C., Aldana, J., Nebro, A., Troya, J.: Hybridizing genetic algorithms with branch and bound techniques for the resolution of the TSP. In Pearson, D., Steele, N., Albrecht, R., eds.: Artificial Neural Nets and Genetic Algorithms 2, Wien New York, Springer-Verlag (1995) [35] Cotta, C., Troya, J.M.: Embedding branch and bound within evolutionary algorithms. Applied Intelligence 18 (2003) [36] Gallardo, J.E., Cotta, C., Fernández, A.J.: A memetic algorithm with bucket elimination for the still life problem. In Gottlieb, J., Raidl, G., eds.: Evolutionary Computation in Combinatorial Optimization. Volume 3906 of Lecture Notes in Computer Science., Berlin Heidelberg, Springer-Verlag (2006) [37] Ibaraki, T.: Combination with dynamic programming. In Bäck, T., Fogel, D., Michalewicz, Z., eds.: Handbook of Evolutionary Computation. Oxford University Press, New York NY (1997) D3.4:1 2 [38] Maheswaran, R., Ponnambalam, S.G., Aranvidan, C.: A meta-heuristic approach to single machine scheduling problems. International Journal of Advanced Manufacturing Technology 25 (2005) [39] Wang, L., Zheng, D.Z.: A modified genetic algorithm for job-shop scheduling. International Journal of Advanced Manufacturing Technology 20 (2002) [40] Liaw, C.F.: A hybrid genetic algorithm for the open shop scheduling problem. European Journal of Operational Research 124 (2000) [41] França, P.M., Gupta, J., Mendes, A.S., Moscato, P., Veltnik, K.J.: Evolutionary algorithms for scheduling a flowshop manufacturing cell with sequence dependent family setups. Computers and Industrial Engineering 48 (2005) [42] Hansen, P., Mladenović, N.: Variable neighborhood search: Principles and applications. European Journal of Operational Research 130 (2001) [43] Cotta, C.: Scatter search with path relinking for phylogenetic inference. European Journal of Operational Research 169 (2006) [44] Yeh, W.C.: A memetic algorithm fo the n/2/flowshop/αf+ βc max scheduling problem. International Journal of Advanced Manufacturing Technology 20 (2002)13 [45] Laguna, M., Martí, R.: Scatter Search. Methodology and Implementations in C. Kluwer Academic Publishers, Boston MA (2003) [46] Nagata, Y., Kobayashi, S.: Edge assembly crossover: A high-power genetic algorithm for the traveling salesman problem. In Bäck, T., ed.: Proceedings of the Seventh International Conference on Genetic Algorithms, East Lansing, EE.UU., San Mateo, CA, Morgan Kaufmann (1997) [47] Burke, E.K., Cowling, P.I., De Causmaecker, P., van den Berghe, G.: A memetic approach to the nurse rostering problem. Applied Intelligence 15 (2001) [48] Yamada, T., Reeves, C.R.: Solving the C sum permutation flowshop scheduling problem by genetic local search. In: 1998 IEEE International Conference on Evolutionary Computation, Piscataway, NJ, IEEE Press (1998) [49] Cotta, C.: Memetic algorithms with partial lamarckism for the shortest common supersequence problem. In Mira, J., Álvarez, J., eds.: Artificial Intelligence and Knowledge Engineering Applications: a Bioinspired Approach. Volume 3562 of Lecture Notes in Computer Science., Berlin Heidelberg, Springer-Verlag (2005) [50] Houck, C., Joines, J.A., Kay, M.G., Wilson, J.R.: Empirical investigation of the benefits of partial lamarckianism. Evolutionary Computation 5 (1997) [51] Ishibuchi, H., Yoshida, T., Murata, T.: Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Transactions on Evolutionary Computation 7 (2003) [52] Jones, T.C., Forrest, S.: Fitness distance correlation as a measure of problem difficulty for genetic algorithms. In Eshelman, L.J., ed.: Proceedings of the 6 th International Conference on Genetic Algorithms, Morgan Kaufmann (1995) [53] Merz, P., Freisleben, B.: Fitness landscapes and memetic algorithm design. In Corne, D., Dorigo, M., Glover, F., eds.: New Ideas in Optimization. McGraw-Hill, Maidenhead, Berkshire, England, UK (1999) [54] Bierwirth, C., Mattfeld, D.C., Watson, J.P.: Landscape regularity and random walks for the job shop scheduling problem. In Gottlieb, J., Raidl, G.R., eds.: Evolutionary Computation in Combinatorial Optimization. Volume 3004 of Lecture Notes in Computer Science., Berlin, Springer-Verlag (2004) [55] Cotta, C., Fernández, A.: Analyzing fitness landscapes for the optimal golomb ruler problem. In Gottlieb, J., Raidl, G., eds.: Evolutionary Computation in Combinatorial Optimization. Volume 3248 of Lecture Notes in Computer Science., Berlin, Springer-Verlag (2005) [56] Grefenstette, J.J.: Genetic algorithms for changing environments. In Männer, R., Manderick, B., eds.: Parallel Problem Solving from Nature II, Amsterdam, North-Holland Elsevier (1992) [57] Hadj-Alouane, A.B., Bean, J.C., Murty, K.G.: A hybrid genetic/optimization algorithm for a task allocation problem. Journal of Scheduling 2 (1999) [58] Tomassini, M.: Spatially Structured Evolutionary Algorithms: Artificial Evolution in Space and Time. Springer-Verlag (2005) 1314 [59] Berretta, R., Cotta, C., Moscato, P.: Enhancing the performance of memetic algorithms by using a matching-based recombination algorithm: Results on the number partitioning problem. In Resende, M., Pinho de Sousa, J., eds.: Metaheuristics: Computer-Decision Making. Kluwer Academic Publishers, Boston MA (2003) [60] Mendes, A., Cotta, C., Garcia, V., França, P., Moscato, P.: Gene ordering in microarray data using parallel memetic algorithms. In Skie, T., Yang, C.S., eds.: Proceedings of the 2005 International Conference on Parallel Processing Workshops, Oslo, Norway, IEEE Press (2005) [61] Moscato, P., Mendes, A., Cotta, C.: Scheduling and production & control. In Onwubolu, G.C., Babu, B.V., eds.: New Optimization Techniques in Engineering. Springer-Verlag, Berlin Heidelberg (2004) [62] Cotta, C., Alba, E., Troya, J.M.: Stochastic reverse hillclimbing and iterated local search. In: Proceedings of the 1999 Congress on Evolutionary Computation, Washington D.C., IEEE Neural Network Council - Evolutionary Programming Society - Institution of Electrical Engineers (1999) [63] Cobb, H.G.: An investigation into the use of hypermutation as an adaptive operator in genetic algorithms having continuous, time-dependent nonstationary environments. Technical Report AIC , Naval Research Laboratory, Washington DC (1990) [64] Merz, P., Freisleben, B.: Fitness Landscapes, Memetic Algorithms and Greedy Operators for Graph Bi-Partitioning. Evolutionary Computation 8 (2000) [65] Yeh, W.C.: A memetic algorithm for the min k-cut problem. Control and Intelligent Systems 28 (2000) [66] Berretta, R., Moscato, P.: The number partitioning problem: An open challenge for evolutionary computation? In Corne, D., Dorigo, M., Glover, F., eds.: New Ideas in Optimization. McGraw-Hill, Maidenhead, Berkshire, England, UK (1999) [67] Aggarwal, C., Orlin, J., Tai, R.: Optimized crossover for the independent set problem. Operations Research 45 (1997) [68] Hifi, M.: A genetic algorithm-based heuristic for solving the weighted maximum independent set and some equivalent problems. Journal of the Operational Research Society 48 (1997) [69] Reeves, C.: Hybrid genetic algorithms for bin-packing and related problems. Annals of Operations Research 63 (1996) [70] Coll, P., Durán, G., Moscato, P.: On worst-case and comparative analysis as design principles for efficient recombination operators: A graph coloring case study. In Corne, D., Dorigo, M., Glover, F., eds.: New Ideas in Optimization. McGraw-Hill, Maidenhead, Berkshire, England, UK (1999) [71] Dorne, R., Hao, J.: A new genetic local search algorithm for graph coloring. In Eiben, A., Bäck, T., Schoenauer, M., Schwefel, H.P., eds.: Parallel Problem Solving From Nature V. Volume 1498 of Lecture Notes in Computer Science., Berlin, Springer-Verlag (1998) [72] Beasley, J., Chu, P.: A genetic algorithm for the set covering problem. European Journal of Operational Research 94 (1996)15 [73] França, P., Mendes, A., Moscato, P.: Memetic algorithms to minimize tardiness on a single machine with sequence-dependent setup times. In: Proceedings of the 5th International Conference of the Decision Sciences Institute, Athens, Greece, Atlanta, GA, USA, Decision Sciences Institute (1999) [74] Miller, D., Chen, H., Matson, J., Liu, Q.: A hybrid genetic algorithm for the single machine scheduling problem. Journal of Heuristics 5 (1999) [75] Mendes, A., Muller, F., França, P., Moscato, P.: Comparing meta-heuristic approaches for parallel machine scheduling problems with sequence-dependent setup times. In: Proceedings of the 15th International Conference on CAD/CAM Robotics & Factories of the Future, Aguas de Lindoia, Brasil. Volume 1., Campinas, SP, Brazil, Technological Center for Informatics Foundation (1999) 1 6 [76] Min, L., Cheng, W.: Identical parallel machine scheduling problem for minimizing the makespan using genetic algorithm combined with simulated annealing. Chinese Journal of Electronics 7 (1998) [77] Chu, P., Beasley, J.: A genetic algorithm for the generalised assignment problem. Computers & Operations Research 24 (1997) [78] Beasley, J., Chu, P.: A genetic algorithm for the multidimensional knapsack problem. Journal of Heuristics 4 (1998) [79] Gottlieb, J.: Permutation-based evolutionary algorithms for multidimensional knapsack problems. In Carroll, J., Damiani, E., Haddad, H., Oppenheim, D., eds.: ACM Symposium on Applied Computing 2000, ACM Press (2000) [80] Taguchi, T., Yokota, T., Gen, M.: Reliability optimal design problem with interval coefficients using hybrid genetic algorithms. Computers & Industrial Engineering 35 (1998) [81] Merz, P., Freisleben, B.: A Comparison of Memetic Algorithms, Tabu Search, and Ant Colonies for the Quadratic Assignment Problem. In Angeline, P., ed.: 1999 Congress on Evolutionary Computation (CEC 99), Piscataway, NJ, USA, IEEE Press (1999) [82] Levine, D.: A parallel genetic algorithm for the set partitioning problem. In Osman, I., Kelly, J., eds.: Meta-Heuristics: Theory & Applications. Kluwer Academic Publishers, Boston, MA, USA (1996) [83] Holstein, D., Moscato, P.: Memetic algorithms using guided local search: A case study. In Corne, D., Dorigo, M., Glover, F., eds.: New Ideas in Optimization. McGraw-Hill, Maidenhead, Berkshire, England, UK (1999) [84] Merz, P.: A comparison of memetic recombination operators for the traveling salesman problem. In Langdon, W., et al., eds.: GECCO, Morgan Kaufmann (2002) [85] Ozcan, E., Mohan, C.: Steady state memetic algorithm for partial shape matching. In Porto, V., Saravanan, N., Waagen, D., eds.: Evolutionary Programming VII. Volume 1447 of Lecture Notes in Computer Science., Springer, Berlin (1998) [86] Merz, P., Freisleben, B.: On the Effectiveness of Evolutionary Search in High Dimensional NK-Landscapes. In Fogel, D., ed.: Proceedings of the 1998 IEEE International Conference on Evolutionary Computation, Piscataway, NJ, USA, IEEE Press (1998)16 [87] Crain, T., Bishop, R., Fowler, W., Rock, K.: Optimal interplanetary trajectory design via hybrid genetic algorithm/recursive quadratic program search. In: Ninth AAS/AIAA Space Flight Mechanics Meeting, Breckenridge CO (1999) [88] Kassotakis, I., Markaki, M., Vasilakos, A.: A hybrid genetic approach for channel reuse in multiple access telecommunication networks. IEEE Journal on Selected Areas in Communications 18 (2000) [89] Raidl, G., Julstron, B.: A weighted coding in a genetic algorithm for the degree-constrained minimum spanning tree problem. In Carroll, J., Damiani, E., Haddad, H., Oppenheim, D., eds.: ACM Symposium on Applied Computing 2000, ACM Press (2000) [90] Hopper, E., Turton, B.: A genetic algorithm for a 2d industrial packing problem. Computers & Industrial Engineering 37 (1999) [91] Krzanowski, R., Raper, J.: Hybrid genetic algorithm for transmitter location in wireless networks. Computers, Environment and Urban Systems 23 (1999) [92] Rodrigues, A., Ferreira, J.S.: Solving the rural postman problem by memetic algorithms. In de Sousa, J.P., ed.: Proceedings of the 4th Metaheuristic International Conference (MIC 2001), Porto, Portugal, July 16-20, (2001) [93] Gen, M., Ida, K., Yinzhen, L.: Bicriteria transportation problem by hybrid genetic algorithm. Computers & Industrial Engineering 35 (1998) [94] Novaes, A., De-Cursi, J., Graciolli, O.: A continuous approach to the design of physical distribution systems. Computers & Operations Research 27 (2000) [95] Torres-Velazquez, R., Estivill-Castro, V.: A memetic algorithm instantiated with selection sort consistently finds global optima for the error-correcting graph isomorphism. In Yao, X., ed.: Proceedings of the IEEE 2002 Congress on Evolutionary Computation, CEC 02, May 12-17, 2002, Honolulu, Hawaii, USA. (2002) [96] Kersting, S., Raidl, G., Ljubić, I.: A memetic algorithm for vertex-biconnectivity augmentation. In Cagnoni, S., et al., eds.: Applications of Evolutionary Computing, Proceedings of EvoWorkshops2002: EvoCOP, EvoIASP, EvoSTim. Volume 2279 of LNCS., Kinsale, Ireland, Springer-Verlag (2002) [97] Merz, P., Zell, A.: Clustering gene expression profiles with memetic algorithms. In: 7th International Conference on Parallel Problem Solving from Nature - PPSN VII, September 7-11, 2002, Granada, Spain. (2002) [98] Buriol, L., Resende, M., Ribeiro, C., Thorup, M.: A memetic algorithm for OSPF routing. In: Sixth INFORMS Telecommunications Conference, March 10-13, 2002 Hilton Deerfield Beach, Boca Raton, Florida. (2002) [99] Cotta, C., Fernández, A.: A hybrid GRASP - evolutionary algorithm approach to golomb ruler search. In Yao, X., et al., eds.: Parallel Problem Solving From Nature VIII. Volume 3242 of Lecture Notes in Computer Science., Berlin, Springer-Verlag (2004) [100] Cotta, C., Dotú, I., Fernández, A.J., Hentenryck, P.V.: A memetic approach to golomb rulers. In Runarsson, T., et al., eds.: Parallel Problem Solving from Nature IX. Volume 4193 of Lecture Notes in Computer Science., Berlin Heidelberg, Springer-Verlag (2006)17 [101] Gallardo, J.E., Cotta, C., Fernández, A.J.: A multi-level memetic/exact hybrid algorithm for the still life problem. In Runarsson, T., et al., eds.: Parallel Problem Solving from Nature IX. Volume 4193 of Lecture Notes in Computer Science., Berlin Heidelberg, Springer-Verlag (2006) [102] dos Santos Coelho, L., Rudek, M., Junior, O.C.: Fuzzy-memetic approach for prediction of chaotic time series and nonlinear identification. In: 6th On-line World Conference on Soft Computing in Industrial Applications, Organized by World Federation of Soft Computing. (2001) Co-sponsored by IEEE Systems, Man, and Cybenertics Society. [103] Burke, E., Smith, A.: A memetic algorithm to schedule grid maintenance. In: Proceedings of the International Conference on Computational Intelligence for Modelling Control and Automation, Vienna: Evolutionary Computation and Fuzzy Logic for Intelligent Control, Knowledge Acquisition and Information Retrieval, IOS Press (1999) [104] Burke, E., Smith, A.: A multi-stage approach for the thermal generator maintenance scheduling problem. In: Proceedings of the 1999 Congress on Evolutionary Computation, Piscataway, NJ, USA, IEEE (1999) [105] Cheng, R., Gen, M., Tsujimura, Y.: A tutorial survey of job-shop scheduling problems using genetic algorithms. II. Hybrid genetic search strategies. Computers & Industrial Engineering 37 (1999) [106] Sevaux, M., Jouglet, A., Oğuz, C.: Combining constraint programming and memetic algorithm for the hybrid flowshop scheduling problem. In: ORBEL 19 th annual conference of the SOGESCI-BVWB, Louvain-la-Neuve, Belgium (2005) [107] Ramat, E., Venturini, G., Lente, C., Slimane, M.: Solving the multiple resource constrained project scheduling problem with a hybrid genetic algorithm. In Bäck, T., ed.: Proceedings of the Seventh International Conference on Genetic Algorithms, San Francisco CA, Morgan Kaufmann (1997) [108] Ozdamar, L.: A genetic algorithm approach to a general category project scheduling problem. IEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews) 29 (1999) [109] Watson, J., Rana, S., Whitley, L., Howe, A.: The impact of approximate evaluation on the performance of search algorithms for warehouse scheduling. Journal of Scheduling 2 (1999) [110] Dellaert, N., Jeunet, J.: Solving large unconstrained multilevel lot-sizing problems using a hybrid genetic algorithm. International Journal of Production Research 38 (2000) [111] Ming, X., Mak, K.: A hybrid hopfield network-genetic algorithm approach to optimal process plan selection. International Journal of Production Research 38 (2000) [112] Burke, E.K., Elliman, D.G., Weare, R.F.: A hybrid genetic algorithm for highly constrained timetabling problems. In: Proceedings of the Sixth International Conference on Genetic Algorithms, Morgan Kaufmann, San Francisco, CA (1995) [113] Paechter, B., Cumming, A., Norman, M., Luchian, H.: Extensions to a Memetic timetabling system. In Burke, E., Ross, P., eds.: The Practice and Theory of Automated Timetabling. Volume 1153 of Lecture Notes in Computer Science. Springer Verlag (1996)18 [114] de Causmaecker, P., van den Berghe, G., Burke, E.: Using tabu search as a local heuristic in a memetic algorithm for the nurse rostering problem. In: Proceedings of the Thirteenth Conference on Quantitative Methods for Decision Making, Brussels, Belgium (1999) abstract only, poster presentation [115] Burke, E.K., De Causmaecker, P., van den Berghe, G.: Novel metaheuristic approaches to nurse rostering problems in belgian hospitals. In Leung, J., ed.: Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman Hall/CRC Press (2004) [116] Costa, D.: An evolutionary tabu search algorithm and the NHL scheduling problem. INFOR 33 (1995) [117] Burke, E.K., Newall, J.: A multi-stage evolutionary algorithm for the timetable problem. IEEE Transactions on Evolutionary Computation 3 (1999) [118] Gonçalves, J.: A memetic algorithm for the examination timetabling problem. In: Optimization 2001, Aveiro, Portugal, July 23-25, (2001) [119] Ichimura, T., Kuriyama, Y.: Learning of neural networks with parallel hybrid GA using a Royal Road function. In: 1998 IEEE International Joint Conference on Neural Networks. Volume 2., New York, NY, IEEE (1998) [120] Topchy, A., Lebedko, O., Miagkikh, V.: Fast learning in multilayered networks by means of hybrid evolutionary and gradient algorithms. In: Proceedings of International Conference on Evolutionary Computation and its Applications. (1996) [121] Aguilar, J., Colmenares, A.: Resolution of pattern recognition problems using a hybrid genetic/random neural network learning algorithm. Pattern Analysis and Applications 1 (1998) [122] Krishna, K., Narasimha-Murty, M.: Genetic k-means algorithm. IEEE Transactions on Systems, Man and Cybernetics, Part B (Cybernetics) 29 (1999) [123] Mignotte, M., Collet, C., Pérez, P., Bouthemy, P.: Hybrid genetic optimization and statistical model based approach for the classification of shadow shapes in sonar imagery. IEEE Transactions on Pattern Analysis and Machine Intelligence 22 (2000) [124] Ostermark, R.: A neuro-genetic algorithm for heteroskedastic time-series processes: empirical tests on global asset returns. Soft Computing 3 (1999) [125] Cotta, C., Troya, J.: Using a hybrid evolutionary-a approach for learning reactive behaviors. In Cagnoni, S., et al., eds.: Real-World Applications of Evolutionary Computation. Volume 1803 of Lecture Notes in Computer Science., Edinburgh, Springer-Verlag (2000) [126] Pratihar, D., Deb, K., Ghosh, A.: Fuzzy-genetic algorithms and mobile robot navigation among static obstacles. In: Proceedings of the 1999 Congress on Evolutionary Computation, Washington D.C., IEEE (1999) [127] Ridao, M., Riquelme, J., Camacho, E., Toro, M.: An evolutionary and local search algorithm for planning two manipulators motion. In Del Pobil, A., Mira, J., Ali, M., eds.: Tasks and Methods in Applied Artificial Intelligence. Volume 1416 of Lecture Notes in Computer Science. Springer-Verlag, Berlin Heidelberg (1998)19 [128] Chaiyaratana, N., Zalzala, A.: Hybridisation of neural networks and genetic algorithms for time-optimal control. In: Proceedings of the 1999 Congress on Evolutionary Computation, Washington D.C., IEEE (1999) [129] Areibi, S., Moussa, M., Abdullah, H.: A comparison of genetic/memetic algorithms and heuristic searching. In: Proceedings of the 2001 International Conference on Artificial Intelligence ICAI 2001, Las Vegas, Nevada, June 25. (2001) [130] Yeh, I.: Hybrid genetic algorithms for optimization of truss structures. Computer Aided Civil and Infrastructure Engineering 14 (1999) [131] Pacey, M., Patterson, E., James, M.: A photoelastic technique for characterising fatigue crack closure and the effective stress intensity factor. Zeszyty Naukowe Politechniki Opolskiej, Seria: Mechanika z.67 (2001) VII Summer School of Fracture Mechanic, Current Research in Fatigue and Fracture, Pokrzywna (Poland), Jun [132] Wang, L., Yen, J.: Extracting fuzzy rules for system modeling using a hybrid of genetic algorithms and kalman filter. Fuzzy Sets and Systems 101 (1999) [133] Zelinka, I., Vasek, V., Kolomaznik, K., Dostal, P., Lampinen, J.: Memetic algorithm and global optimization of chemical reactor. In: PC Control 2001, 13th International Conference on Process Control, High Tatras, Slovakia. (2001) [134] Knödler, K., Poland, J., Zell, A., Mitterer, A.: Memetic algorithms for combinatorial optimization problems in the calibration of modern combustion engines. In Langdon, W.B., et al., eds.: GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, New York, Morgan Kaufmann Publishers (2002) 687 [135] Bos, A.: Aircraft conceptual design by genetic/gradient-guided optimization. Engineering Applications of Artificial Intelligence 11 (1998) [136] Quagliarella, D., Vicini, A.: Hybrid genetic algorithms as tools for complex optimisation problems. In Blonda, P., Castellano, M., Petrosino, A., eds.: New Trends in Fuzzy Logic II. Proceedings of the Second Italian Workshop on Fuzzy Logic, Singapore, World Scientific (1998) [137] Hodgson, R.: Memetic algorithm approach to thin-film optical coating design. In Hart, W., Krasnogor, N., Smith, J., eds.: Second Workshop on Memetic Algorithms (2nd WOMA), San Francisco, California, USA (2001) [138] Srinivasan, D., Cheu, R., Poh, Y., Ng, A.: Development of an intelligent technique for traffic network incident detection. Engineering Applications of Artificial Intelligence 13 (2000) [139] Urdaneta, A., Gómez, J., Sorrentino, E., Flores, L., Díaz, R.: A hybrid genetic algorithm for optimal reactive power planning based upon successive linear programming. IEEE Transactions on Power Systems 14 (1999) [140] Haas, O., Burnham, K., Mills, J.: Optimization of beam orientation in radiotherapy using planar geometry. Physics in Medicine and Biology 43 (1998) [141] Wehrens, R., Lucasius, C., Buydens, L., Kateman, G.: HIPS, A hybrid self-adapting expert system for nuclear magnetic resonance spectrum interpretation using genetic algorithms. Analytica Chimica ACTA 277 (1993)20 [142] Li, F., Morgan, R., Williams, D.: Economic environmental dispatch made easy with hybrid genetic algorithms. In: Proceedings of the International Conference on Electrical Engineering. Volume 2., Beijing, China, Int. Acad. Publishers (1996) [143] Ostermark, R.: Solving irregular econometric and mathematical optimization problems with a genetic hybrid algorithm. Computational Economics 13 (1999) [144] Musil, M., Wilmut, M., Chapman, N.: A hybrid simplex genetic algorithm for estimating geoacoustic parameters using matched-field inversion. IEEE Journal of Oceanic Engineering 24 (1999) [145] Reich, C.: Simulation of imprecise ordinary differential equations using evolutionary algorithms. In Carroll, J., Damiani, E., Haddad, H., Oppenheim, D., eds.: ACM Symposium on Applied Computing 2000, ACM Press (2000) [146] Wei, P., Cheng, L.: A hybrid genetic algorithm for function optimization. Journal of Software 10 (1999) [147] Wei, X., Kangling, F.: A hybrid genetic algorithm for global solution of nondifferentiable nonlinear function. Control Theory & Applications 17 (2000) [148] Cadieux, S., Tanizaki, N., Okamura, T.: Time efficient and robust 3-D brain image centering and realignment using hybrid genetic algorithm. In: Proceedings of the 36th SICE Annual Conference, IEEE (1997) [149] Krishna, K., Ramakrishnan, K., Thathachar, M.: Vector quantization using genetic k- means algorithm for image compression. In: 1997 International Conference on Information, Communications and Signal Processing. Volume 3., New York, NY, IEEE (1997) [150] Yoneyama, M., Komori, H., Nakamura, S.: Estimation of impulse response of vocal tract using hybrid genetic algorithm-a case of only glottal source. Journal of the Acoustical Society of Japan 55 (1999) [151] Merz, P., Zell, A.: Clustering gene expression profiles with memetic algorithms. In Yao, X., et al., eds.: Parallel Problem Solving From Nature VIII. Volume 3242 of Lecture Notes in Computer Science., Berlin, Springer-Verlag (2004) [152] Moscato, P., Berretta, R., Mendes, A.: A new memetic algorithm for ordering datasets: Applications in microarray analysis. In Doerner, K., et al., eds.: Proceedings of the 6th Metaheuristics International Conference, Vienna, Austria (2005) [153] Knowles, J., Corne, D.: M-PAES: A memetic algorithm for multiobjective optimization. In: Proceedings of the 2000 Congress on Evolutionary Computation CEC00, La Jolla Marriott Hotel La Jolla, California, USA, IEEE Press (2000) [154] Ponnambalam, S.G., Mohan Reddy, M.: A GA-SA multiobjective hybrid search algorithm for integrating lot sizing and sequencing in flow-line scheduling. International Journal of Advanced Manufacturing Technology 21 (2003) [155] Krasnogor, N., Smith, J.E.: Emergence of profitable search strategies based on a simple inheritance mechanism. In Spector, L., et al., eds.: Proceedings of the 2001 Genetic and Evolutionary Computation Conference, Morgan Kaufmann (2001) [156] Li, J., Kwan, R.S.K.: A self adjusting algorithm for driver scheduling. Journal of Heuristics 11 (2005) Mostrar más
Técnicas Metaheurísticas para Problemas de Telecomunicación Autor: Antonio Muñoz-Cruzado Marenco Codirector: Enrique Alba Torres Codirector: José Francisco Chicano García Introducción Las Telecomunicaciones Más detalles Comparativa de Algoritmo Genético, Memético y SI para el diseño de horarios de una Institución Educativa
Comparativa de Algoritmo Genético, Memético y SI para el diseño de horarios de una Institución Educativa Lucero de Montserrat Ortiz Aguilar a, Juan Martín Carpio Valadez a, Héctor José Puga Soberanes a, Más detalles Scheduling Problem. Cuándo y dónde debo hacer cada trabajo?
Scheduling Problem Cuándo y dónde debo hacer cada trabajo? Ejemplos de problemas de asignación de recursos Fabricación de varios tipos de productos Asignación de turnos de trabajo Inversión financiera Más detalles Propuesta de un algoritmo evolutivo aplicado a problemas de optimización
Propuesta de un algoritmo evolutivo aplicado a problemas de optimización Javier Izetta Riera 1 y Nilda M. Pérez Otero 1 1 Grupo de Investigación y Desarrollo en Informática Aplicada, Facultad de Ingeniería, Más detalles &$3Ì78/2 $/*25,7026 (92/87,926 $9$1=$'26 3$5$ 763 6.1. INTRODUCCIÓN
&$3Ì78/2 6.1. INTRODUCCIÓN Los primeros avances para solucionar el TSP, por medio de Algoritmos Evolutivos han sido introducidos por Goldberg y Lingle en [68] y Grefenstette en [72]. En éste área muchos Más detalles RESOLUCIÓN DE PROBLEMAS DE PACKING EN UNA EMPRESA DE
RESOLUCIÓN DE PROBLEMAS DE PACKING EN UNA EMPRESA DE CALCAMONIAS MEDIANTE ALGORITMOS GENÉTICOS. Alberto Gómez Gómez, José Parreño Fernández y Isabel Fernández Quesada. RESUMEN. El objetivo del presente Más detalles Algoritmos Genéticos Y
Algoritmos Genéticos Y Optimización n Heurística Dr. Adrian Will Grupo de Aplicaciones de Inteligencia Artificial Universidad Nacional de Tucumán awill@herrera.unt.edu.ar Optimización n Tradicional Problemas Más detalles Medición en Fábrica - 2003
Algoritmos Genéticos y Optimización Heurística Dr. Adrian Will F.A.C.E.T. U.N.T. Cátedra de Tópicos Selectos de Inteligencia Artificial Optimización Tradicional Problemas Reales Problemas Reales Función Más detalles Algoritmos Genéticos.
Algoritmos Genéticos. Miguel Cárdenas Montes, Antonio Gómez Iglesias Centro de Investigaciones Energéticas Medioambientales y Tecnológicas, Madrid, Spain miguel.cardenas@ciemat.es 15-19 de Octubre de 2011 Más detalles METAHEURÍSTICA ACO APLICADA A PROBLEMAS DE PLANIFICACIÓN
METAHEURÍSTICA ACO APLICADA A PROBLEMAS DE PLANIFICACIÓN EN ENTORNOS DINÁMICOS de San Pedro M., Pandolfi D., Lasso M., Villagra A. Laboratorio de Tecnologías Emergentes (LabTEm) Proyecto UNPA-29/B084/1 Más detalles Comportamiento de los parámetros principales de un Algoritmo Genético para el Flow Shop Scheduling
Comportamiento de los parámetros principales de un Algoritmo Genético para el Flow Shop Scheduling Yunior César Fonseca Reyna Universidad de Granma E-mail: fonseca@udg.co.cu Temática: Inteligencia Artificial Más detalles 18:15 19:15 13.5. Reunión de la red HEUR. Sala Andalucía 3. 19:30 21:00 Acto de Inauguración y Conferencia Invitada CEDI2005. Miércoles, 14 Septiembre
IVCongresoEspañolde Metaheurísticas,Algoritmos EvolutivosyBioinspirados MAEB 05 18:15 19:15 13.5.ReunióndelaredHEUR SalaAndalucía3 19:30 21:00 ActodeInauguraciónyConferencia InvitadaCEDI2005 Miércoles,14Septiembre Más detalles Algoritmos genéticos como métodos de aproximación analítica y búsqueda de óptimos locales
Algoritmos genéticos como métodos de aproximación analítica y búsqueda de óptimos locales Jorge Salas Chacón A03804 Rubén Jiménez Goñi A93212 Juan Camilo Carrillo Casas A91369 Marco Vinicio Artavia Quesada Más detalles Estrategia evolutiva para el problema de la supersecuencia común más corta
Estrategia evolutiva para el problema de la supersecuencia común más corta Marcela Rivera Martínez Facultad de Ciencias de la Computación, Benemérita Universidad Autónoma de Puebla mrivmar@hotmail.com Más detalles Investigación de Operaciones (IO) Operations Research
Investigación de Operaciones (IO) Operations Research Dr. Ricardo Soto [ricardo.soto@ucv.cl] [http://www.inf.ucv.cl/ rsoto] Escuela de Ingeniería Informática Pontificia Universidad Católica de Valparaíso Más detalles Algoritmo de Colonias de Abejas Artificiales para la composición de equipos médicos *
Algoritmo de Colonias de Abejas Artificiales para la composición de equipos médicos * José A. Delgado-Osuna 1, Manuel Lozano 2, and Carlos García-Martínez 3 1 H.U. Reina Sofía jantonio.delgado.sspa@juntadeandalucia.es, Más detalles Analizando la Evolución Diferencial sobre una topología toroidal
Analizando la Evolución Diferencial sobre una topología toroidal D.Sc. Yván Jesús Túpac Valdivia Conversatorio de Investigación 26 de setiembre de 2013 Yván Túpac (CC/UCSP) Pág 1/29 Objetivo Mostrar una Más detalles Investigación de operaciones en acción: Heurísticas para la solución del TSP
Investigación de operaciones en acción: Heurísticas para la solución del TSP Roger Z. Ríos Mercado* José Luis González Velarde** Abstract One of the most common and difficult problem in the theory of optimization Más detalles Diseño de redes viales urbanas usando algoritmos genéticos. M. Angélica Pinninghoff J.* Eduardo Matthews D. * Héctor Díaz C.
Diseño de redes viales urbanas usando algoritmos genéticos M. Angélica Pinninghoff J.* Eduardo Matthews D. * Héctor Díaz C. e-mail: mapinnin@inf.udec.cl * Departamento de Ingeniería Informática y Ciencias Más detalles Nuevas Tendencias y Retos en Métodos Heurísticos para Problemas de Scheduling
Nuevas Tendencias y Retos en Métodos Heurísticos para Problemas de Scheduling Ramiro Varela Grupo de Tecnologías de la Computación. Departamento de Informática. Centro de Inteligencia Artificial Universidad Más detalles Estrategias evolutivas para la minimización del makespan en una máquina con tiempos de preparación dependientes de la secuencia
Ingeniería Investigación y Tecnología, volumen XV (número 1), enero-marzo 2014: 1-10 ISSN 1405-7743 FI-UNAM (artículo arbitrado) Estrategias evolutivas para la minimización del makespan en una máquina Más detalles Hibridación Iterativa de DE con Búsqueda Local con reinicio para problemas de alta dimensionalidad
Hibridación Iterativa de DE con Búsqueda Local con reinicio para problemas de alta dimensionalidad Daniel Molina 1 and Francisco Herrera 2 1 Universidad de Cádiz, daniel.molina@uca.es 2 Universidad de Más detalles Aproximación evolutiva a la inducción constructiva basada en expresiones algebraicas
Aproximación evolutiva a la inducción constructiva basada en expresiones algebraicas Manuel Baena García, Rafael Morales Bueno y Carlos Cotta Porras Workshop MOISES Septiembre 2004 1/15 Contenido Inducción Más detalles Análisis del NSGA-II para el TSALBP-1/3 cuando existe variación de demanda en una producción mixta
Análisis del NSGA-II para el TSALBP-1/3 cuando existe variación de demanda en una producción mixta Manuel Chica, Óscar Cordón, Sergio Damas y Joaquín Bautista Resumen En este trabajo introducimos la aplicación Más detalles Un algoritmo genético híbrido para resolver el EternityII. Rico, Martin; Ros, Rodrigo Directora: Prof. Dra. Irene Loiseau
Un algoritmo genético híbrido para resolver el EternityII Rico, Martin; Ros, Rodrigo Directora: Prof. Dra. Irene Loiseau Temas Temas Introducción Eternity II Historia Descripción Demo Metaheurísticas Algoritmos Más detalles Un algoritmo genético para el problema de Job Shop Flexible
Ingeniare. Revista chilena de ingeniería, vol. 19 Nº 1, 2011, pp. 53-61 Un algoritmo genético para el problema de Job Shop Flexible A genetic algorithm for the Flexible Job Shop problem Rosa Medina Durán Más detalles Problemas de Rutas. Vicente Campos Aucejo Dpt. Estadística i Investigació Operativa Universitat de València vicente.campos@uv.es
Problemas de Rutas Vicente Campos Aucejo Dpt. Estadística i Investigació Operativa Universitat de València vicente.campos@uv.es Resumen El objetivo de este trabajo es el de divulgar la existencia de un Más detalles ALGORITMO GENÉTICO APLICADO AL PROBLEMA DE ASIGNACIÓN DE CANAL EN COMUNICACIONES MÓVILES CELULARES
Memorias de la XVII Semana Regional de Investigación y Docencia en Matemáticas, Departamento de Matemáticas, Universidad de Sonora, México. Mosaicos Matemáticos No. 2, agosto 27, pp. 29-36. Nivel Superior Más detalles TÉCNICAS EVOLUTIVAS PARA EL PROBLEMA DEL VIAJANTE
Mecánica Computacional Vol. XXII M. B. Rosales, V. H. Cortínez y D. V. Bambill (Editores) Bahía Blanca, Argentina, Noviembre 2003. TÉCNICAS EVOLUTIVAS PARA EL PROBLEMA DEL VIAJANTE Jessica A. Carballido, Más detalles ESTRATEGIAS EVOLUTIVAS COMO UNA OPCIÓN PARA LA OPTIMIZACIÓN DE FUNCIONES NO LINEALES CON RESTRICCIONES
Revista Ingenierías Universidad de Medellín ESTRATEGIAS EVOLUTIVAS COMO UNA OPCIÓN PARA LA OPTIMIZACIÓN DE FUNCIONES NO LINEALES CON RESTRICCIONES Diana M. Ortiz Juan David Velásquez H Patricia Jaramillo Más detalles Jhoan Sebastián Cadavid Jaramillo Ingeniero Industrial, Universidad Nacional de Colombia, jscadav0@unal.edu.co RESUMEN
PROBLEMA DE PROGRAMACIÓN DE PRODUCCIÓN ABIERTA CON CARACTERÍSTICAS DE MÁQUINAS MÓVILES DEDICADAS Y CON TIEMPOS DE PREPARACIÓN DEPENDIENTES DE LA SECUENCIA ENTRE ETAPAS Alexander Alberto Correa Espinal Más detalles Combinación de Algoritmos Evolutivos y Técnicas Heurísticas para Problemas de Scheduling
Combinación de Algoritmos Evolutivos y Técnicas Heurísticas para Problemas de Scheduling Ramiro Varela, Javier Blanco, Camino Rodríguez, Jorge Puente y César Alonso Centro de Inteligencia Artificial. Universidad Más detalles Un modelo híbrido de inteligencia computacional para resolver el problema de Job Shop Scheduling
Un modelo híbrido de inteligencia computacional para resolver el problema de Job Shop Scheduling Jacob Meneses Angel, Marcela Rivera Martínez, Luis René Marcial Castillo, Sandoval Solís Lourdes Benemérita Más detalles Búsqueda tabú y evolución genética para el árbol de expansión capacitado de costo mínimo
Búsqueda tabú y evolución genética para el árbol de expansión capacitado de costo mínimo Efraín Ruiz Dept. d Estadística i Investigació Operativa Universitat Politècnica de Catalunya Jordi Girona, 1-3. Más detalles Una heurística basada en memoria para el problema del diseño de recorridos en transporte público urbano
Una heurística basada en memoria para el problema del diseño de recorridos en transporte público urbano Antonio Mauttone María E. Urquhart Departamento de Investigación Operativa, Instituto de Computación, Más detalles Búsqueda Local. cbea (LSI-FIB-UPC) Inteligencia Artificial Curso 2011/2012 1 / 33
Introducción Búsqueda Local A veces el camino para llegar a la solución no nos importa, buscamos en el espacio de soluciones Queremos la mejor de entre las soluciones posibles alcanzable en un tiempo razonable Más detalles Una Estrategia para la Selección de Individuos Recibidos en la Migración en un Algoritmo Genético Distribuido
Una Estrategia para la Selección de Individuos Recibidos en la Migración en un Algoritmo Genético Distribuido Germán Dupuy 1 - Carolina Salto 1-2 1 Facultad de Ingeniería - Universidad Nacional de La Pampa Más detalles Temario III Algoritmos Combinatorios y Metaheurísticas
Temario III Algoritmos Combinatorios y Metaheurísticas Verificación y Validación de Software UNCo 1 Contenidos Combinación de Datos de Test Algoritmos Combinatorios Metaheurísticas Búsqueda Tabú Algoritmos Más detalles SECUENCIACIÓN DE SISTEMAS DE TIPO JOB SHOP MEDIANTE APRENDIZAJE AUTOMÁTICO
Obtención de Sistemas Basados en Difusas Precisos y Compactos mediante Algoritmos Geneticos Multiobjetivo R. Alcalá, J. Alcalá-Fdez, M. J. Gacto y F. Herrera Departamento de Ciencias de la Computación Más detalles Una permutación eficiente para minimizar la suma de los tiempos de acabado de "n" trabajos en "m" máquinas Freddy Abarca R. fabarca@ic-itcr.ac.
Una permutación eficiente para minimizar la suma de los tiempos de acabado de "n" trabajos en "m" máquinas Freddy Abarca R. fabarca@ic-itcr.ac.cr El problema de la asignación de cargas de trabajo, a pesar Más detalles Introducción a los Algoritmos Genéticos
Marcos Gestal Pose Depto. Tecnologías de la Información y las Comunicaciones Universidade da Coruña http://sabia.tic.udc.es/ mgestal mgestal@udc.es Índice 1. Introducción 2 2. Orígenes 2 3. Bases Biológicas Más detalles Metaheurísticas: una visión global *
Metaheurísticas: una visión global * Belén Melián, José A. Moreno Pérez, J. Marcos Moreno Vega DEIOC. Universidad de La Laguna 38271 La Laguna {mbmelian,jamoreno,jmmoreno}@ull.es Resumen Las metaheurísticas Más detalles Un algoritmo evolutivo simple para el problema de asignación de tareas a procesadores
Un algoritmo evolutivo simple para el problema de asignación de tareas a procesadores Pablo Ezzatti CeCal, Facultad de Ingeniería Universidad de la República, Uruguay pezzatti@fing.edu.uy Sergio Nesmachnow Más detalles Algoritmos Genéticos
Introducción a la Computación Evolutiva Tercera Clase: Algoritmos Genéticos Algoritmos Genéticos Desarrollados en USA durante los años 70 Autores principales: J. Holland, K. DeJong, D. Goldberg Aplicados Más detalles Tesis Doctoral: Método Neuro-Genético para resolver problemas de la programación de la producción.
EDUCACION New Mexico State University, Las Cruces NM. Doctor en Ingeniería con especialidad en Ingeniería Industrial. 1999-2002 Asesor: Dr. Linda Ann Riley Tesis Doctoral: Método Neuro-Genético para resolver Más detalles Selección Sexual Discriminatoria en un Algoritmo Evolutivo con una Matriz de Preferencias para la mejora de calidad de los Horarios de Trabajo
Selección Sexual Discriminatoria en un Algoritmo Evolutivo con una Matriz de Preferencias para la mejora de calidad de los Horarios de Trabajo Víctor Arroyo Ciencia de la Computación Universidad Católica Más detalles Programación de la producción en talleres de flujo con máquinas sin interrupción. Algoritmos y aplicaciones *
3 rd International Conference on Industrial Engineering and Industrial Management XIII Congreso de Ingeniería de Organización Barcelona-Terrassa, September 2nd-4th 2009 Programación de la producción en Más detalles HEURISTIC FOR SCHEDULING OF PROJECTS WITH RESTRICTION OF RESOURCES UN HEURÍSTICO PARA PLANEACIÓN DE PROYECTOS CON RESTRICCIÓN DE RECURSOS
DISEÑO DE METAHEURÍSTICOS HÍBRIDOS PARA PROBLEMAS DE RUTAS CON FLOTA HETEROGÉNEA (2 Parte) : GRASP Y CONCENTRACIÓN HEURÍSTICA Cristina R. Delgado Serna Departamento de ECONOMÍA (Área de Economía Aplicada) Más detalles UNA TÉCNICA PARA ESTABILIZAR LA CANTIDAD DE INDIVIDUOS EN ALGORITMOS GENÉTICOS DE POBLACIÓN VARIABLE
UNA TÉCNICA PARA ESTABILIZAR LA CANTIDAD DE INDIVIDUOS EN ALGORITMOS GENÉTICOS DE POBLACIÓN VARIABLE Patricio A. Maller The University of Alabama College of Engineering Department of Computer Science Box Más detalles Comparación de técnicas metaheurísticas para la generación automática de casos de prueba que obtengan una cobertura software
Comparación de técnicas metaheurísticas para la generación automática de casos de prueba que obtengan una cobertura software Eugenia Díaz, Raquel Blanco, Javier Tuya Departamento de Informática, Universidad Más detalles Análisis Comparativo de Heurísticas para el Problema de Calendarización de Trabajos con Transferencia Cero
Análisis Comparativo de Heurísticas para el Problema de Calendarización de Trabajos con Transferencia Cero Beatriz Pérez Rojas Departamento de Sistemas Computación Instituto Tecnológico de Puebla am120@cs.buap.m Más detalles APRENDIZAJE HÍBRIDO DE LA BASE DE CONOCIMIENTO DE UN SISTEMA BASADO EN REGLAS DIFUSAS MEDIANTE ALGORITMOS GENÉTICOS Y COLONIAS DE HORMIGAS
APRENDIZAJE HÍBRIDO DE LA BASE DE CONOCIMIENTO DE UN SISTEMA BASADO EN REGLAS DIFUSAS MEDIANTE ALGORITMOS GENÉTICOS Y COLONIAS DE HORMIGAS J. Casillas, O. Cordón, F. Herrera P. Villar Dept. Ciencias de Más detalles Un Algoritmo Genético Híbrido Paralelo para Instancias Complejas del Problema VRP
Un Algoritmo Genético Híbrido Paralelo para Instancias Complejas del Problema VRP Bernabé Dorronsoro, Antonio J. Nebro, Daniel Arias, y Enrique Alba Resumen En este trabajo proponemos un algoritmo genético Más detalles MODELOS DE PLANIFICACIÓN
MODELOS DE PLANIFICACIÓN Santiago de Compostela, Octubre 2006 1 s jk C max P Jm prmt L max NP Rm tree C j Algoritmos wj U j Uj Calendarios Fm prec w j U j Práctica CONTENIDO. Contents 1 Descripción del Más detalles Algoritmo de hormigas mejorado para la descripción de modelos difusos interpretables mediante reglas con excepciones
Algoritmo de hormigas mejorado para la descripción de modelos difusos interpretables mediante reglas con excepciones P. Carmona 1 J.L. Castro 1 1 Depto. de Ingeniería de Sistemas Informáticos y Telemáticos, Más detalles Propuesta de un algoritmo genético para la programación diaria de los pedidos de una empresa del sector de la construcción
5 th International Conference on Industrial Engineering and Industrial Management XV Congreso de Ingeniería de Organización Cartagena, 7 a 9 de Septiembre de 2011 Propuesta de un algoritmo genético para Más detalles Algoritmos Evolutivos
Algoritmos Evolutivos 2003-11-20 Cristóbal Romero, Pedro González y Sebastián Ventura 1.1 Introducción En general, cualquier tarea abstracta a realizar puede considerarse como la resolución de un problema Más detalles Secuenciación de tareas mediante metaheurísticos
VIII Congreso de Ingeniería de Organización Leganés, 9 y 10 de septiembre de 2004 Secuenciación de tareas mediante metaheurísticos Santiago López de Haro 1, Pedro Sánchez Martín 2, Javier Conde Collado Más detalles Desarrollo de un sistema capaz de optimizar rutas de entrega utilizando algoritmos genéticos
MT 6 Desarrollo de un sistema capaz de optimizar rutas de entrega utilizando algoritmos genéticos Rosario Baltazar 1 Judith Esquivel Vázquez 2 Andrea Rada 3 Claudia Díaz 4 Resumen Durante los últimos 15 Más detalles David Jordi Vallet Weadon. David Jordi Vallet Weadon 1 Introducción Durante las últimas décadas, la personalización ha sido aplicada en diferentes campos de la informática, tanto en la rama científica como Más detalles Programación de tareas, un reto diario en la empresa
Programación de tareas, un reto diario en la empresa Pedro Sánchez Martín Ingeniero del ICAI (1993) y Doctor en Ingeniería Industrial por la UPCO (1998). Profesor del Departamento de Organización Industrial Más detalles ASALBP: Alternative Subgraphs Assembly Line Balancing Problem *
IX Congreso de Ingeniería de Organización Gijón, 8 y 9 de septiembre de 2005 ASALBP: Alternative Subgraphs Assembly Line Balancing Problem * Liliana Capacho Betancourt 1, Rafael Pastor Moreno 2 1 Dpto Más detalles Evaluación de Algoritmos de Ruteo de Paquetes en Redes de Computadoras. Fax: 54-2652-430224 Fax: 34-91-3367426
Evaluación de Algoritmos de Ruteo de Paquetes en Redes de Computadoras Berón, Mario Marcelo Gagliardi, Edilma Olinda Departamento de Informática Facultad de Ciencias Físico, Matemáticas y Naturales Universidad Más detalles Especificación de sistemas concurrentes usando conceptos de teoría económica: Sintaxis, semántica, aplicaciones y extensiones del lenguaje formal PAMR
CURRICULUM VITAE DE MIEMBROS DE COMISIONES PARA CONCURSOS DE ACCESO A LOS CUERPOS DOCENTES UNIVERSITARIOS 1. DATOS PERSONALES Apellidos y Nombre: Rodríguez Laguna, Ismael Cuerpo docente al que pertenece: Más detalles Experimentos con Algoritmos Genéticos para resolver un problema real de Programación Maestros-Horarios-Cursos
Experimentos con Algoritmos Genéticos para resolver un problema real de Programación Maestros-Horarios-Cursos Pedro FLORES, Ernesto BRAU, Jazmín A. MONTEVERDE, Norman F. SALAZAR, José FIGUEROA, Eliseo Más detalles Descripción inicial del sistema. Descripción final del sistema. Estado 1 Estado 2 Estado n
Búsqueda en Inteligencia Artificial Fernando Berzal, berzal@acm.org Búsqueda en I.A. Introducción Espacios de búsqueda Agentes de búsqueda Uso de información en el proceso de búsqueda Búsqueda sin información Más detalles GENERACIÓN AUTOMÁTICA DE REDES NEURONALES CON AJUSTE DE PARÁMETROS BASADO EN ALGORITMOS GENÉTICOS
GENERACIÓN AUTOMÁTICA DE REDES NEURONALES CON AJUSTE DE PARÁMETROS BASADO EN ALGORITMOS GENÉTICOS Fiszelew, A. 1 & García-Martínez, R. 2 1. Investigador Asistente del Laboratorio de Sistemas Inteligentes. Más detalles ALGORITMOS EVOLUTIVOS DISTRIBUIDOS: PROPUESTAS QUE COMBINAN PREVENCIÓN DE INCESTO Y MULTIPLICIDAD
ALGORITMOS EVOLUTIVOS DISTRIBUIDOS: PROPUESTAS QUE COMBINAN PREVENCIÓN DE INCESTO Y MULTIPLICIDAD Alfonso H., Minetti G., Salto C. Facultad de Ingeniería - Universidad Nacional de La Pampa Calle 110 esq. Más detalles Modelado de relaciones existentes en un equipo de proyecto de software Modeling relationships in a software project team
Modelado de relaciones existentes en un equipo de proyecto de software Modeling relationships in a software project team Rafael Rodríguez-Puente 1, Eliana B. Ril-Valentin 2 1 Departamento de Técnicas de Más detalles Capítulo VI MÉTODOS DE SOLUCIÓN PARA JOB SHOP SCHEDULING
Capítulo VI MÉTODOS DE SOLUCIÓN PARA JOB SHOP SCHEDULING 6.1. HEURÍSTICAS CONVENCIONALES El problema de job shop scheduling (JSSP) es un problema muy importante [69]; está entre los problemas de optimización Más detalles ALGORITMOS GENÉTICOS
Arranz de la Peña, Jorge Universidad Carlos III 100025106@alumnos.uc3m.es ALGORITMOS GENÉTICOS Parra Truyol, Antonio Universidad Carlos III 100023822@alumnos.uc3m.es En este documento se pretende analizar Más detalles Representación con Restricciones de Medidas Cualitativas: Aplicación a un Problema de Scheduling
Representación con Restricciones de Medidas Cualitativas: Aplicación a un Problema de Scheduling Salvador E. Ayala-Raggi German Cuaya-Simbro Modesto G. Medina-Melendrez Angélica Muñoz-Meléndez Instituto Más detalles 6. CONTRIBUCIÓN A LA FORMACIÓN PROFESIONAL Y FORMACIÓN GENERAL Esta disciplina contribuye al logro de los siguientes resultados de la carrera:
Universidad Católica San Pablo Facultad de Ingeniería y Computación Programa Profesional de Ciencia de la Computación SILABO CS360. Computación Bioinspirada (Electivo) 2012-2 1. DATOS GENERALES 1.1 CARRERA Más detalles OPTIMIZACIÓN DEL PROBLEMA DEL AGENTE VIAJERO USANDO EL SISTEMA DE COLONIA DE HORMIGAS Y BUSQUEDA GREEDY
OPTIMIZACIÓN DEL PROBLEMA DEL AGENTE VIAJERO USANDO EL SISTEMA DE COLONIA DE HORMIGAS Y BUSQUEDA GREEDY Esquivel Estrada Jaime*, Ordoñez Arizmendi Armando*, Ortiz Servín Juan José**. *Universidad Autónoma Más detalles Flow-Shop Dinámico. Por: Juan Carlos Rivera Samuel De Greiff
Flow-Shop Dinámico Por: Juan Carlos Rivera Samuel De Greiff 1 Configuración tipo Flow- Shop Disposición lineal de los equipos. Productos con altos niveles de estandarización. Varios productos en volúmenes Más detalles Introducción a los Algoritmos Genéticos. Tomás Arredondo Vidal 17/4/09
Introducción a los Algoritmos Genéticos Tomás Arredondo Vidal 17/4/09 Esta charla trata de lo siguiente: Introducción a algunos aspectos de los algoritmos genéticos. Introducción a algunas aplicaciones Más detalles Análisis de un problema Job Shop por medio de un Sistema Experto y un Agente Inteligente
3rd International Conference on Industrial Engineering and Industrial Management XIII Congreso de Ingeniería de Organización Barcelona-Terrassa, September 2nd-4th 2009 Análisis de un problema Job Shop Más detalles MODELO JERÁRQUICO PARA EL JOB SHOP FLEXIBLE
!#"$%$$ %!& '($! *)!!#% $)$ +-,/.103254 687/9:6(;=1.1?A@50 Más detalles PROGRAMACIÓN POR METAS CON NIVELES DE ASPIRACIÓN IMPRECISOS
Revista de Dirección y Administración de Empresas. Número 19, diciembre 2012 págs. 117-128 Enpresen Zuzendaritza eta Administrazio Aldizkaria. 19. zenbakia, 2012 abendua 117-128 orr. PROGRAMACIÓN POR METAS Más detalles Representación, Codificación en un AG Población Inicial. Aptitud. Estrategia de Selección. Cruce, Mutación, Reemplazo. Condición de Parada.
Computación n Evolutiva: Algoritmos Genéticos 1.- Metaheurísticos. Computación Evolutiva: Algoritmos Genéticos 2.- Conceptos principales de un Algoritmo Genético 3.- Estructura de un Algoritmo Genético Más detalles Evaluación de la disponibilidad de los servicios desplegados sobre Volunteer Computing
Evaluación de la disponibilidad de los servicios desplegados sobre Volunteer Computing Antonio Escot Praena Enginyeria Informàtica i Tècnica de Gestió Dirección del TFC Ángel A. Juan, PhD. Eva Vallada Más detalles ENTORNO PARA LA PLANIFICACION DE LA PRODUCCION DE SISTEMAS DE FABRICACION FLEXIBLES
ENTORNO PARA LA PLANIFICACION DE LA PRODUCCION DE SISTEMAS DE FABRICACION FLEXIBLES Mercedes E. Narciso Farias, Miquel Angel Piera i Eroles Unidad de Ingeniería de Sistemas y Automática. Universidad Autónoma Más detalles Desarrollo de algoritmos genéticos, de recocido simulado e híbridos para la planificación de un taller flexible
X Congreso de Ingeniería de Organización Valencia, 7 y 8 de septiembre de 2006 Desarrollo de algoritmos genéticos, de recocido simulado e híbridos para la planificación de un taller flexible Sara Lumbreras Más detalles Optimización inspirada en la naturaleza
Optimización inspirada en la naturaleza Efrén Mezura-Montes Laboratorio Nacional de Informática Avanzada (LANIA AC) Xalapa, Veracruz, MEXICO emezura@lania.mx http://www.lania.mx/~emezura 10ª feria de Posgrados Más detalles Generación automática de casos de prueba mediante búsqueda dispersa
Generación automática de casos de prueba mediante búsqueda dispersa Raquel Blanco, Eugenia Díaz, Javier Tuya Departamento de Informática, Universidad de Oviedo {rblanco madiaz tuya}@uniovi.es Abstract Más detalles Sistema de apoyo a procesos productivos en Pymes: Un caso de aplicación 1
Sistema de apoyo a procesos productivos en Pymes: Un caso de aplicación 1 Ricardo Contreras A., M. Angélica Pinninghoff J., Evelyn Osses L. Departamento de Ingeniería Informática y Ciencias de la Computación Más detalles Una heurística para la asignación de máquinas a trabajos fijos
1 Algoritmos Genéticos aplicados a la resolución de problemas de optimización Luis Marco Giménez lmarcogimenez@gmail.com http://www.luismarco.nom.es RESUMEN Los Algoritmos Genéticos, como paradigma principal Más detalles Extracción Automática de Conocimiento en Bases de Datos e Ingeniería del Software
Extracción Automática de Conocimiento en Bases de Datos e Ingeniería del Software Mª. José Ramírez Quintana José Hernández Orallo Programa: Programación Declarativa e Ingeniería de la Programación Objetivos Más detalles Julian López Franco Universidad de La Salle Carrera 2 No. 10 70 Bogotá, Colombia jullopez@unisalle.edu.co
ESTRATEGIAS PARA EL DISEÑO E HIBRIDACIÓN DE UNA METAHEURÍSTICA BASADA EN BÚSQUEDA DISPERSA QUE RESUELVA EL PROBLEMA MDVRP MULTIOBJETIVO: COSTO Y BALANCEO DE CARGA Julian López Franco Universidad de La Más detalles Rubén Ruiz, Concepción Maroto, Javier Alcaraz.
27 Congreso Nacional de Estadística e Investigación Operativa Lleida, 8 11 de abril de 2003 UN ALGORITMO GENÉTICO HÍBRIDO PARA EL TALLER DE FLUJO DE PERMUTACIÓN Rubén Ruiz, Concepción Maroto, Javier Alcaraz. Más detalles Aplicación de la inteligencia artificial a la resolución del problema de asignación de estudiantes del departamento de PDI
Aplicación de la inteligencia artificial a la resolución del problema de asignación de estudiantes del departamento de PDI Ricardo Köller Jemio Departamento de Ciencias Exactas e Ingeniería, Universidad Más detalles 6th International Conference on Industrial Engineering and Industrial Management. XVI Congreso de Ingeniería de Organización. Vigo, July 18-20, 2012
6th International Conference on Industrial Engineering and Industrial Management. XVI Congreso de Ingeniería de Organización. Vigo, July 18-20, 2012 Un algoritmo genético híbrido para el equilibrado de Más detalles 2016 © DocPlayer.es Política de privacidad | Condiciones del servicio | Feedback

References: resolución 
 resolución 
 resolución 
 resolución 
 RESOLUCIÓN 

RESOLUCIÓN 
 resolución 
 resolución 
 resolución 
 resolución