MCS algoritm
För matematisk optimering är Multilevel Coordinate Search ( MCS ) en effektiv algoritm för bunden begränsad global optimering som endast använder funktionsvärden .
representeras det n-dimensionella sökutrymmet av en uppsättning icke-korsande hyperkuber (rutor). Lådorna delas sedan iterativt längs ett axelplan enligt värdet av funktionen vid en representativ punkt av rutan (och dess grannar) och lådans storlek. Dessa två uppdelningskriterier kombineras för att bilda en global sökning genom att dela upp stora rutor och en lokal sökning genom att dela upp områden för vilka funktionsvärdet är bra.
Dessutom kan en lokal sökning som kombinerar en (flerdimensionell) kvadratisk interpolant av funktionen och linjesökningar användas för att öka prestanda hos algoritmen ( MCS med lokal sökning ); i detta fall används den vanliga MCS för att tillhandahålla startpunkterna (initial). Informationen som tillhandahålls av lokala sökningar (lokala minima för objektivfunktionen) återkopplas sedan till optimeraren och påverkar uppdelningskriterierna, vilket resulterar i minskad sampelklustring kring lokala minima, snabbare konvergens och högre precision.
Förenklat arbetsflöde
MCS-arbetsflödet visualiseras i figurerna 1 och 2. Varje steg i algoritmen kan delas upp i fyra steg:
- Identifiera en potentiell kandidat för klyvning (magenta, tjock).
- Identifiera den optimala klyvningsriktningen och det förväntade optimala läget för klyvpunkten (grön).
- Utvärdera målfunktionen vid delningspunkten eller återställ den från den redan beräknade uppsättningen; det senare gäller om den aktuella klyvningspunkten redan har uppnåtts vid klyvning av en angränsande låda.
- Generera nya rutor (magenta, tunna) baserat på värdena för objektivfunktionen vid delningspunkten.
Vid varje steg är den gröna punkten med den tillfälliga gula gloria den unika baspunkten för lådan; varje ruta har ett tillhörande värde för målet, nämligen dess värde vid boxens baspunkt.
För att avgöra om en ruta kommer att delas används två separata uppdelningskriterier. Den första, uppdelad efter rang , säkerställer att stora lådor som inte har delats för ofta kommer att delas upp så småningom. Om det gäller så bestäms klyvningspunkten lätt vid en fast bråkdel av längden på sidan som klyvs. Den andra, uppdelning efter förväntad förstärkning , använder en lokal endimensionell parabolisk kvadratisk modell (surrogat) längs en enda koordinat. I det här fallet definieras delningspunkten som minimum av surrogatet längs ett linjesegment och boxen delas endast om interpolantvärdet (som tjänar som en proxy för det sanna värdet av objektivet) är lägre än det nuvarande bästa samplade funktionsvärdet .
Konvergens
Algoritmen kommer garanterat att konvergera till det globala minimumet på lång sikt (dvs. när antalet funktionsutvärderingar och sökdjupet är godtyckligt stort) om den objektiva funktionen är kontinuerlig i närheten av den globala minimeraren. Detta följer av det faktum att vilken ruta som helst kommer att bli godtyckligt liten så småningom, varför avståndet mellan sampel tenderar till noll eftersom antalet funktionsutvärderingar tenderar till oändligt.
Rekursiv implementering
MCS är designat för att implementeras på ett effektivt rekursivt sätt med hjälp av träd . Med detta tillvägagångssätt är mängden minne som krävs oberoende av problemdimensionalitet eftersom samplingspunkterna inte lagras explicit. Istället sparas bara en enda koordinat för varje prov och de återstående koordinaterna kan återställas genom att spåra historien för en ruta tillbaka till roten (initial box). Denna metod föreslogs av författarna och användes i sin ursprungliga implementering.