Muestreo Espacial Óptimo vía Teoría de la Información
Implementa el algoritmo AdSEMES para muestreo espacial óptimo en campos aleatorios binarios — específicamente reservorios geológicos canalizados. Código acompañante de artículos publicados en Mathematical Geosciences y Natural Resources Research.
Contexto de Negocio
En exploración mineral y geoestadística, cada sondaje o ubicación de sensor cuesta tiempo y dinero significativos. La pregunta de dónde ubicar la siguiente medición para maximizar información geológica es un problema de optimización combinatoria con C(H×W, K) configuraciones posibles — computacionalmente intratable para tamaños de campo del mundo real.
Valor Estratégico
Esta implementación del algoritmo AdSEMES provee muestreo espacial óptimo con una garantía de aproximación demostrable de (1-1/e) ≈ 63.2% vía submodularidad. Seis estrategias de muestreo se comparan sistemáticamente (aleatorio, estratificado, multiescala, oráculo, entropía adaptiva, grilla regular) con funciones de penalización espacial que previenen agrupamiento de mediciones. Tres métodos de reconstrucción (vecino más cercano, kriging indicador, distancia inversa ponderada por entropía) recuperan el campo completo desde observaciones dispersas. Código acompañante de artículos publicados en Mathematical Geosciences y Natural Resources Research. Desarrollado bajo Proyecto Fondecyt 1140840.
El Desafío
Dadas K mediciones en un campo binario H×W, minimizar incertidumbre posterior. La búsqueda combinatoria sobre C(H×W, K) candidatos es NP-hard, requiriendo aproximación eficiente con cotas de calidad demostrables.
Nuestro Enfoque
Selección secuencial greedy explotando submodularidad logra garantía de aproximación de 63.2%. Compara seis estrategias de muestreo (aleatorio, estratificado, multiescala, oráculo, entropía adaptiva, grilla regular) con funciones de penalización espacial. Tres métodos de reconstrucción: vecino más cercano, kriging indicador, distancia inversa ponderada por entropía.
Indicadores Clave de Rendimiento
| KPI | Línea Base | Resultado | Impacto |
|---|---|---|---|
| Estrategias de Muestreo | Grilla regular o aleatorio | 6 estrategias con optimización de entropía | Ubicación basada en teoría de información |
| Reconstrucción | Método único | 3 métodos comparados sistemáticamente | Mejor método por escenario |
Arquitectura
ids owp
The Combinatorial Explosion
Given K measurements on an H×W binary random field, the number of possible placement configurations is C(H×W, K). For a 50×50 field with 20 measurements: over 10²⁶ possibilities. Exhaustive search is NP-hard. And traditional approaches — regular grids, random placement — ignore spatial information content entirely.
Six Strategies Compared
The system implements six fundamentally different approaches: random placement (baseline), stratified sampling (random within grid cells), multiscale refinement (coarse to fine), an oracle using true field knowledge (theoretical upper bound), the AdSEMES entropy maximization method, and regular grid spacing (standard practice).
Each strategy can incorporate spatial penalty functions that discourage clustering — important because entropy-optimal placement can concentrate measurements in high-uncertainty regions at the expense of spatial coverage.
Three reconstruction methods complete the pipeline: nearest neighbor (fast, no assumptions), indicator kriging (optimal under stationarity), and entropy-weighted inverse distance (hybrid approach weighting by both proximity and information content).
The Submodularity Guarantee
Entropy maximization satisfies submodularity: the marginal information gain from adding a measurement decreases as the existing set grows. This mathematical property guarantees the greedy sequential algorithm achieves at least (1 - 1/e) ≈ 63.2% of the globally optimal information gain. This is a provable bound, not an empirical observation — the greedy solution is certifiably close to optimal despite the combinatorial explosion of the search space.
Developed at the IDS Group, Universidad de Chile (2014–2016), under Fondecyt Grant 1140840.
Stack Tecnológico
Capturas de la Aplicación
Diagramas Técnicos
owp adsemes
owp information theory
owp resolvability
owp sampling comparison