La optimización extrema (EO) es una heurística de optimización inspirada en el modelo de Bak-Sneppen de criticidad autoorganizada del campo de la física estadística. Esta heurística fue diseñada inicialmente para abordar problemas de optimización combinatoria como el problema del viajante y los vidrios de espín , aunque se ha demostrado que la técnica funciona en dominios de optimización.
Relación con la criticidad autoorganizada
La criticidad autoorganizada (SOC) es un concepto de física estadística que describe una clase de sistemas dinámicos que tienen un punto crítico como atractor. En concreto, se trata de sistemas que no están en equilibrio y que evolucionan mediante avalanchas de cambios y disipaciones que alcanzan las escalas más altas del sistema. Se dice que la SOC rige la dinámica de algunos sistemas naturales que presentan estos fenómenos de tipo estallido, como la formación del paisaje, los terremotos, la evolución y la dinámica granular de los montículos de arroz y arena. En este caso, resulta de especial interés el modelo de Bak-Sneppen de SOC, que es capaz de describir la evolución mediante el equilibrio puntuado (eventos de extinción), modelando así la evolución como un proceso crítico autoorganizado.
Relación con la complejidad computacional
Otra pieza del rompecabezas es el trabajo sobre la complejidad computacional, en particular, que se ha demostrado que existen puntos críticos en problemas NP-completos , donde las soluciones casi óptimas están ampliamente dispersas y separadas por barreras en el espacio de búsqueda, lo que hace que los algoritmos de búsqueda locales se queden atascados o se vean gravemente obstaculizados. Fue el modelo de criticidad autoorganizada evolutiva de Bak y Sneppen y la observación de puntos críticos en problemas de optimización combinatoria lo que condujo al desarrollo de la Optimización Extrema por Stefan Boettcher y Allon Percus.
La técnica
EO fue diseñado como un algoritmo de búsqueda local para problemas de optimización combinatoria . A diferencia de los algoritmos genéticos , que trabajan con una población de soluciones candidatas, EO desarrolla una única solución y realiza modificaciones locales a los peores componentes. Esto requiere que se seleccione una representación adecuada que permita asignar a los componentes individuales de la solución una medida de calidad ("aptitud"). Esto difiere de los enfoques holísticos como la optimización de colonias de hormigas y el cálculo evolutivo que asignan la misma aptitud a todos los componentes de una solución en función de su evaluación colectiva frente a una función objetivo. El algoritmo se inicializa con una solución inicial, que puede construirse aleatoriamente o derivarse de otro proceso de búsqueda.
La técnica es una búsqueda de grano fino y superficialmente se parece a una técnica de escalada de colinas (búsqueda local). Un examen más detallado revela algunos principios interesantes, que pueden tener aplicabilidad e incluso cierta similitud con enfoques más amplios basados en la población ( computación evolutiva y sistema inmunológico artificial ). El principio rector detrás de este algoritmo es el de la mejora mediante la eliminación selectiva de componentes de baja calidad y su reemplazo con un componente seleccionado al azar. Esto obviamente está en desacuerdo con los algoritmos genéticos , el algoritmo de computación evolutiva por excelencia que selecciona buenas soluciones en un intento de crear mejores soluciones.
La dinámica resultante de este principio simple es, en primer lugar, un comportamiento de búsqueda robusto de escalada de pendientes y, en segundo lugar, un mecanismo de diversidad que se asemeja al de la búsqueda de reinicios múltiples. La representación gráfica de la calidad de la solución holística a lo largo del tiempo (iteraciones del algoritmo) muestra períodos de mejora seguidos de caídas de calidad (avalanchas) de forma muy similar a la descrita por el equilibrio puntuado . Son estas caídas o saltos dramáticos en el espacio de búsqueda los que permiten al algoritmo escapar de los óptimos locales y diferenciar este enfoque de otros procedimientos de búsqueda local. Aunque este comportamiento de equilibrio puntuado puede "diseñarse" o "codificarse", debe destacarse que se trata de un efecto emergente del principio de selección de componentes negativos fundamental para el algoritmo.
La EO se ha aplicado principalmente a problemas combinatorios como la partición de gráficos y el problema del viajante , así como a problemas de física estadística como los vidrios de espín .
Variaciones sobre el tema y aplicaciones.
La optimización extrema generalizada (GEO) se desarrolló para operar en cadenas de bits donde la calidad de los componentes está determinada por la tasa absoluta de cambio del bit o la contribución de los bits a la calidad de la solución holística. Este trabajo incluye la aplicación a problemas de optimización de funciones estándar, así como a dominios de problemas de ingeniería. Otra extensión similar a la EO es la Optimización Extrema Continua (CEO).
La EO se ha aplicado a la rasterización de imágenes y también se ha utilizado como una búsqueda local después de utilizar la optimización de colonias de hormigas . La EO se ha utilizado para identificar estructuras en redes complejas. La EO se ha utilizado en un problema de seguimiento de múltiples objetivos. Por último, se ha trabajado en la investigación de la distribución de probabilidad utilizada para controlar la selección.
Véase también
Referencias
- Bak, Per; Tang, Chao; Wiesenfeld, Kurt (27 de julio de 1987). "Criticidad autoorganizada: una explicación del ruido 1/f". Physical Review Letters . 59 (4). American Physical Society (APS): 381–384. Bibcode :1987PhRvL..59..381B. doi :10.1103/physrevlett.59.381. ISSN 0031-9007. PMID 10035754. S2CID 7674321.
- Bak, Per; Sneppen, Kim (1993-12-13). "Equilibrio puntuado y criticidad en un modelo simple de evolución". Physical Review Letters . 71 (24). American Physical Society (APS): 4083–4086. Bibcode :1993PhRvL..71.4083B. doi :10.1103/physrevlett.71.4083. ISSN 0031-9007. PMID 10055149.
- P Cheeseman, B Kanefsky, WM Taylor, "Dónde están los problemas realmente difíciles" [ enlace muerto permanente ] , Actas de la 12.ª IJCAI, (1991)
- G Istrate, "Complejidad computacional y transiciones de fase", Actas de la 15.ª Conferencia anual del IEEE sobre complejidad computacional, 104-115 (2000)
- Stefan Boettcher, Allon G. Percus, "Optimización extrema: métodos derivados de la coevolución", Actas de la Conferencia sobre computación genética y evolutiva (1999)
- Boettcher, Stefan (1999-01-01). "Optimización extrema de la partición de grafos en el umbral de percolación". Journal of Physics A: Mathematical and General . 32 (28). IOP Publishing: 5201–5211. arXiv : cond-mat/9901353 . Bibcode :1999JPhA...32.5201B. doi :10.1088/0305-4470/32/28/302. ISSN 0305-4470. S2CID 7925735.
- Boettcher, Stefan; Percus, Allon (2000), "La forma en que la naturaleza optimiza", Inteligencia artificial , 119 (1–2): 275–286, arXiv : cond-mat/9901351 , doi :10.1016/S0004-3702(00)00007-2, S2CID 7128022
- Boettcher, S. (2000). "Optimización extrema: heurísticas a través de avalanchas coevolutivas". Computing in Science & Engineering . 2 (6). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 75–82. arXiv : cond-mat/0006374 . Bibcode :2000CSE.....2f..75B. doi :10.1109/5992.881710. ISSN 1521-9615. S2CID 7259036.
- Boettcher, Stefan; Percus, Allon G. (4 de junio de 2001). "Optimización con dinámica extrema". Physical Review Letters . 86 (23). American Physical Society (APS): 5211–5214. arXiv : cond-mat/0010337 . Código Bibliográfico :2001PhRvL..86.5211B. doi :10.1103/physrevlett.86.5211. ISSN 0031-9007. PMID 11384460. S2CID 3261749.
- Dall, Jesper; Sibani, Paolo (2001). "Simulaciones de Monte Carlo más rápidas a bajas temperaturas. El método del tiempo de espera". Computer Physics Communications . 141 (2): 260–267. arXiv : cond-mat/0107475 . Código Bibliográfico :2001CoPhC.141..260D. doi :10.1016/s0010-4655(01)00412-x. ISSN 0010-4655. S2CID 14585624.
- Boettcher, Stefan; Grigni, Michelangelo (28 de enero de 2002). "Modelo de interferencia para la heurística de optimización extremal". Journal of Physics A: Mathematical and General . 35 (5). IOP Publishing: 1109–1123. arXiv : cond-mat/0110165 . Bibcode :2002JPhA...35.1109B. doi :10.1088/0305-4470/35/5/301. ISSN 0305-4470. S2CID 640976.
- Souham Meshoul y Mohamed Batouche, "Correspondencia de puntos robusta para el registro de imágenes mediante optimización con dinámica extrema" [ enlace muerto permanente ] , Lecture Notes in Computer Science 2449 , 330–337 (2002)
- Onody, Roberto N.; De Castro, Paulo A. (2003). "Self-Organized Criticality, Optimization and Biodiversity". Revista Internacional de Física Moderna C . 14 (7). World Scientific Pub Co Pte Lt: 911–916. arXiv : cond-mat/0302260 . Código Bibliográfico :2003IJMPC..14..911O. doi :10.1142/s0129183103005054. ISSN 0129-1831. S2CID 14553130.
- Boettcher, Stefan; Percus, Allon G. (24 de junio de 2004). "Optimización extrema en la transición de fase del problema de tres colores". Physical Review E . 69 (6). American Physical Society (APS): 066703. arXiv : cond-mat/0402282 . Bibcode :2004PhRvE..69f6703B. doi :10.1103/physreve.69.066703. ISSN 1539-3755. PMID 15244779. S2CID 3070942.
- Middleton, A. Alan (14 de mayo de 2004). "Optimización extrema mejorada para el vidrio de espín de Ising". Physical Review E . 69 (5). American Physical Society (APS): 055701(R). arXiv : cond-mat/0402295 . Bibcode :2004PhRvE..69e5701M. doi :10.1103/physreve.69.055701. ISSN 1539-3755. PMID 15244875. S2CID 28439352.
- Heilmann, F; Hoffmann, K. H; Salamon, P (2004). "La mejor distribución de probabilidad posible sobre rangos de optimización extremal". Europhysics Letters (EPL) . 66 (3). IOP Publishing: 305–310. Bibcode :2004EL.....66..305H. doi :10.1209/epl/i2004-10011-3. ISSN 0295-5075. S2CID 250810936.
- [1] Pontus Svenson, "Optimización extrema para el preprocesamiento de informes de sensores", Proc SPIE 5429 , 162–171 (2004)
- Zhou, Tao; Bai, Wen-Jie; Cheng, Long-Jiu; Wang, Bing-Hong (6 de julio de 2005). "Optimización extrema continua para cúmulos de Lennard-Jones". Physical Review E . 72 (1). American Physical Society (APS): 016702. arXiv : cond-mat/0411428 . Bibcode :2005PhRvE..72a6702Z. doi :10.1103/physreve.72.016702. ISSN 1539-3755. PMID 16090129. S2CID 26578844.
- Duch, Jordi; Arenas, Alex (24 de agosto de 2005). "Detección de comunidades en redes complejas mediante optimización extremal". Physical Review E . 72 (2). American Physical Society (APS): 027104. arXiv : cond-mat/0501368 . Bibcode :2005PhRvE..72b7104D. doi :10.1103/physreve.72.027104. ISSN 1539-3755. PMID 16196754. S2CID 13898113.
- Ahmed, E.; Elettreby, MF (2006). "Sobre la optimización combinatoria motivada por la biología". Matemáticas Aplicadas y Computación . 172 (1). Elsevier BV: 40–48. doi :10.1016/j.amc.2005.01.122. ISSN 0096-3003.
Enlaces externos
- Stefan Boettcher – Departamento de Física, Universidad Emory
- Allon Percus – Universidad de Graduados de Claremont
- Algoritmos de optimización global: teoría y aplicación – Archivado el 11 de septiembre de 2008 en Wayback Machine – Thomas Weise
