Metaoptimización

En optimisació numèrica, la metaoptimización consistix en l'us d'un método d'optimisació per a posar a punt un atre método d'optimisació. S'ha reportat el seu us, des de data tan primerenca com 1970, per Mercer i Sampson per a la busca de configuracions òptimes de paràmetros en algoritmes genètics. La metaoptimización es coneix també en la lliteratura com: fique-evolució, super-optimisació, calibración automàtica de paràmetros, etc. En general, el problema de trobar un vector de valors (configuració vàlida) per als paràmetros d'un algoritme A, de manera que en aplicar A sobre una instància del problema P s'obtinga el millor rendiment, es coneix com: selecció de configuracions, configuració de paràmetros o optimisació de configuracions. El rendiment d'un algoritme pot ser medit segons els recursos computacionals consumits (temps d'eixecució, cantitat de memòria RAM) o la calitat de la solució obtinguda, per la qual cosa dita mida deu ser definida per l'investigador en automatisar el procés d'ajust de paràmetros.

Motivació

Archiu:DEMeta-Fitness Landscape (12 benchmark problems).JPG

Topología de rendiment per a Evolució diferencial.

Els métodos d'optimisació, com els algoritmes genètics i l'evolució diferencial, tenen diversos paràmetros que governen el seu comportament i eficiència en optimisar un problema donat. Estos paràmetros deuen ser triats per l'investigador darrere d'alcançar resultats satisfactoris. La selecció de paràmetros a mà, és una tasca laboriosa susceptible a errors humans referent a: quins aspectes provoquen un bon rendiment.

Els paràmetros d'un algoritme d'optimisació poden ser variats i el rendiment del procés d'optimisació interpretat topológicament. Açò és computacionalment factible per a algoritmes de pocs paràmetros i problemes d'optimisació que requerixen poc temps d'eixecució, pero quan el número de paràmetros aumenta; el temps utilisat per a calcular tal topología (paisage) de rendiment, incrementa exponencialment. Açò es coneix com la maldicció de la dimensió per a un espai de busca conformat pels paràmetros del optimizador(algoritme). Per això, es necessita un método eficient per a explorar dit espai de busca.

Automatisar la selecció de configuracions adquirix gran importància en el desenroll d'algoritmes complexos puix l'us de métodos de configuració automàtics disminuïx sensiblement el temps dedicat a l'ajust de paràmetros i millora, potencialment, els resultats obtinguts per mig d'un procés manual. De manera similar, influïx en la comparació i evaluació d'algoritmes heurístics. Les ferramentes automàtiques permeten mitigar el problema de realisar comparacions injustes entre dos métodos heurístics distints i determinar, en efecte, com és superior en lloc d'cual va anar millor "ajustat" pels seus desenrolladors.

Métodos

Archiu:DEMeta-Optimization Progress (12 benchmark problems).JPG

Fique-optimisació en Evolució diferencial.

Una via simple per a buscar paràmetros adequats d'un algoritme d'optimisació és amprar un atre algoritme d'optimisació, per damunt d'est, cridat meta-optimizador. Existixen diverses maneres de realisar açò en dependència del tipo dels paràmetros(reals o discrets) i de la mida de rendiment utilisada.

Disseny Experimental

Varis treballs han abordat la selecció de configuracions recolzant-se en l'us d'un disseny experimental dels paràmetros, ya siga un disseny factorial complet o fraccionario de concorde el número de paràmetros.

En Coy et a el es propon un procediment basat en una combinació de disseny experimental(factorial complet o fraccionario) i descens de gradient per a trobar configuracions efectives en paràmetros d'heurístiques. El procés es dividix en dos etapes: Es busca una bona configuració per a cada instància - del problema - del conjunt d'entrenament usant un disseny experimental i després es combinen dites configuracions prenent el valor promig de cada paràmetro entre totes les configuracions. Este procediment solament és aplicable a paràmetros numèrics.

Un enfocament similar és amprat per Adenso-Díaz i Estany en el sistema CALIBRA. Est evalua cada configuració en un disseny factorial complet de 2 nivells(2 valors per paràmetro). A continuació, iterativament, explora l'espai de les configuracions en busca de regions prometedores usant un disseny experimental fraccionario, basat en els apanys ortogonals de Taguchi, a on s'evaluen 9 configuracions al voltant de la millor configuració trobada fins al moment. Quan alcança un òptim local, refina l'espai de busca i reinicia el procés. Este método té dos desventages: és necessari discretizar els paràmetros continus i solament pot optimisar un màxim de 5 paràmetros.

F-Race

Una proposta de Birattari, Stützle, Paquet, i Varrentrapp, baix el nom de F-Race, descriu un procediment basat en algoritmes de carrera per a configurar paràmetros de metaheurísticas. F-Race, inspirat en algoritmes d'aprenentage de màquines, propon l'evaluació d'un conjunt de configuracions candidates a on es descarten les pijors tan pronte com es tinga suficient evidència estadística en contra seua. A partir d'un algoritme A, un conjunt finito de configuracions inicials i una distribució I d'instàncies del problema es realisa un procés iterativo. Dit procés iterativo pot vore's com una "carrera" a on les pijors configuracions abandonen la competència a mida que esta alvança, favorint a les configuracions més prometedores que tindran més evaluacions i per això un millor estimat del seu comportament real. En cada iteración se selecciona una instància d'I, que s'evalua(eixecuta A sobre dita instància) para totes les configuracions. A continuació s'efectua la prova de Friedman per a comprovar si existixen diferències significatives entre les configuracions. Esta prova d'hipòtesis, complix la funció d'un "àrbit" que, determina quins corredors(configuracions) no reunixen les condicions necessàries per a alcançar bons resultats, açò és, millorar el rendiment oferit per les configuracions restants. Si la hipòtesis nula és rebujada, es realisen comparacions dos a dos entre totes les configuracions i la de millor rendiment, eliminant aquelles que són significativament pijor. Este procés contínua fins que queda una sola configuració en memòria o s'alcança determinat temps llímit.

Degut a que a l'inici totes les configuracions són evaluades, l'us de, F-Race està llimitat a escenaris a on siga factible enumerar totes les possibles configuracions de paràmetros. L'utilisació d'un disseny factorial complet, sobre l'espai de les configuracions, per a triar les configuracions inicials presupon una desventaja en F-Race puix el conjunt de configuracions candidates creix exponencialment respecte a la cantitat de paràmetros. Birattari et.a el proponen com a alternativa utilisar un mostreig aleatori, baix una distribució uniforme, dels valors dels paràmetros per a obtindre les configuracions inicials i demostra la superioritat de dit método front al disseny factorial complet. El disseny de mostreig aleatori, en el cas dels paràmetros numèrics, evita establir a priori nivells per als paràmetros i possibilita explorar, en promig, uniformemente l'espai de les configuracions en un número arbitrari de candidats. En l'objectiu de centrar la generació de candidats al voltant dels més prometedors, es planteja una nova variant nomenada Iterated F-Race. Esta propon l'aplicació iterada de F-Race de manera que en cada iteración les configuracions candidates siguen muestreadas a partir d'un subconjunt de les configuracions "sobreviviente" en la iteración anterior.

F-Race i les seues variants han rebut atenció significativa. Ha segut aplicat en l'ajust de paràmetros de metaheurísticas en la solució de problemes d'horaris de classes, en l'indústria com a part d'un estudi de viabilitat d'una ferramenta de solució de problemes de enrutamiento de vehículs i problemes de planificació, aixina com en el desenroll d'algoritmes, en particular el disseny d'una metaheurística híbrida per al problema d'horaris de cursos universitaris.

ParamILS

Hutter, Hoos i Leyton-Brown varen desenrollar un framework per a resoldre el problema de selecció de configuracions. Baixe el nom de ParamILS, presenten métodos per a optimisar el rendiment d'un algoritme objecte, determinista o estocàstic, en una certa classe d'instàncies de problemes per mig de la variació d'un conjunt de paràmetros ordinals i/o categòrics. Dita proposta es basa en un algoritme de busca local iterada que utilisa una combinació de configuracions triades, a priori o aleatoriament, en la seua inicialización; un método iterativo "Primer el millor" com a busca local subjacent i cert número de moviments aleatoris per a pertorbar la solució, darrere d'evitar mínims locals. Sempre accepta configuracions que milloren o igualen el rendiment de la millor configuració trobada i reinicializa la busca a partir d'una configuració aleatòria baix certa provabilitat. El método de busca local es "mou" per l'espai de busca modificant 1 paràmetro en cada ocasió.

Un aspecte essencial en ParamILS és donat dos configuracions determinar quin és la de millor rendiment. L'alternativa més simple dona lloc a una variant coneguda com BasicILS, a on es compara la mida estadística, associada a cada configuració, N voltes en abdós configuracions. Este enfocament, de fixar un N a priori, resulta efectiu quan les instàncies utilisades són molt heterogénees o és possible identificar un "menut" subconjunt d'instàncies que siga representatiu puix permet obtindre bones configuracions en poc esforç computacional. Triar un N apropiat és, per lo general, un problema complicat ya que un conjunt molt chicotet d'instàncies ocasionaria una pobra generalisació en les instàncies no evaluades mentres que conjunts d'entrenament molt grans, incrementarien el temps d'eixecució del procés de busca. En FocusedILS, una variant de ParamILS, es varia N adaptativamente d'una configuració a una atra per a estimar la calitat de cada una. S'utilisa un concepte de dominancia entre configuracions i s'assegura la realisació de moltes evaluacions sobre les configuracions bones.

En la primera publicació sobre ParamILS es varen reportar experiments sobre: l'algoritme SAPS del Problema de satisfacibilidad booleana, l'algoritme de busca local GLS+ en el problema d'Explicació Més Provable en Rets Bayesianas i l'algoritme SAT4J. Es va comparar el rendiment de les configuracions per defecte de cada algoritme, les obtingudes per la ferramenta CALIBRA i les donades per ParamILS en les seues dos variants. Entre els quatre escenaris estudiats, FocusedILS va superar ostensiblement a CALIBRA en dos d'ells i ho va millorar en promig en un tercer. A la seua volta, ParamILS va alcançar millores significatives sobre les configuracions per defecte. ParamILS va ser aplicat per a millorar el rendiment de la ferramenta d'optimisació CPLEX sobre una variada selecció de problemes entre ells: instàncies del problema d'assignació de tasques modelat per mig d'optimisació quadràtica en sancers en restriccions, instàncies del problema de la mochila modelat en programació llineal en sancers mixta i problemes quadràtics associats a l'estimació de paràmetros d'energia en cadenes de ARN. Abdós variants, BasicILS i FocusedILS, varen trobar configuracions millors que les configuracions per defecte de CPLEX, en ocasions en varis órdens de magnitut. També va ser inclós en el framework SATenstein per a realisar automàticament l'ajust de paràmetros, en algoritmes de busca local estocàstics per a SAT. En particular, FocusedILS es va utilisar per a configurar SATenstein davant 6 distribucions distintes de problemes, obtenint millors resultats que 11 algoritmes de l'estat de l'art de SAT, en les 6 categories de problemes.

SACO

La selecció automàtica de configuracions, definida de manera similar en F-Race i ParamILS, és la base de la ferramenta SACO proposta per Vora en 2011. SACO presenta una solució al problema general d'ajust de paràmetros en algoritmes exactes i estocàstics, basant-se en una variant adaptativa de la metaheurística poblacional Harmony Search. Esta proposta, diferencia el tractament dels paràmetros continus i discrets, o siga, els paràmetros continus no són discretizados la qual cosa representa una ventaja respecte a F-Race i ParamILS. En SACO s'utilisa un conjunt d'instàncies, que s'assumix finito i representatiu de les possible instàncies del problema, com a conjunt d'entrenament per a inicializar la població de configuracions inicials en Harmony Search i evaluar posteriorment les noves configuracions trobades durant l'eixecució de l'algoritme. Se seguix el marc definit per Harmony Search, açò és, en cada iteración es "improvisa" una nova configuració, paràmetro a paràmetro, a partir de les configuracions almagasenades en memòria o del domini de valors del paràmetro segons certa provabilitat definida en Harmony Search. Si el valor del paràmetro és seleccionat de la memòria baix certa provabilitat és pertorbat. En cada iteración es busca si existix alguna configuració en la memòria que oferixca pijor rendiment que la nova configuració construïda, i en cas afirmatiu es reemplaça per esta. Per a això es definix un criteri de dominancia entre configuracions. L'algoritme termina en alcançar un número predeterminat de iteraciones i torna la millor configuració trobada. SACO va ser utilisat en l'ajust de paràmetros d'algoritmes de Visió de Computadores, en particular per als problemes de segmentación d'imàgens en regions de textures diferents i seguiment de la posició d'un braç en seqüències de video, obtenint resultats satisfactoris.

Uns atres

La Fique-optimisació de paràmetros en algoritmes genètics va ser realisada per Grefenstette i Keane, entre uns atres, i s'han reportat experiments, per Bäck, a on es varen optimisar els paràmetros i els operadors genètics. Krus i Andersson varen portar a terme fique-optimisació en l'algoritme COMPLEX-RF i varen introduir l'índex de rendiment d'optimisació basat en la Teoria de l'Informació. La metaoptimización en optimisació per eixam de partícules (PSO) ha segut realisada per Meissner et al. aixina com per Pedersen i Chipperfield, qui ademés ha treballat en la fique-optimisació d'evolució diferencial. També han segut utilisats models estadístics per a revelar més informació sobre la relació establida entre la selecció de paràmetros i el rendiment del procés d'optimisació, per eixemple en Francois i Lavergne i Nannen i Eiben. Per la seua banda, Smit i Eiben varen realisar una comparació de vàries tècniques de meta-optimisació.