Miguel Leon försvarar sin doktorsavhandling i datavetenskap

Disputationer och licentiatseminarier

Datum: 2019-12-18
Tid: 13.15
Plats: sal Delta, MDH Västerås.

Miguel Leon, vid akademin för innovation, design och teknik (IDT), försvarar sin doktorsavhandling i datavetenskap, den 18 december, klockan 13.15 i sal Delta, MDH Västerås.

Titel: “Improving Differential Evolution with Adaptive and Local Search Methods”.

Serienummer: 302.

Opponent är adjungerad professor Kristian Sandström, RISE, Västerås.

Betygsnämnden utgörs av professor Juha Plosila, University of Turku, docent Rahim Rahmani, Stockholm University and adjungerad professor Georg Fodor, Q-Tagg, Västerås.

Reserv är professor Erik Dahlquist, MDH.

Sammanfattning:

Differential Evolution (DE) är en populationsbaserad algoritm som tillhör familjen för evolutionära algoritmer. På senare år har DE blivit en populär algoritm för optimering på grund av sin framgång vid lösning av olika typer av optimeringsproblem och tack vare sin enkla användning och implementation.

Trots detta medföljer stora svårigheter vid val av lämplig strategi för mutationer och val av kontrollparametrar när DE tillämpas på verkliga problem. Då både val av strategi för mutation och kontrollparametrar är beroende på problemen i hög grad måste de anpassas för olika sökområden och problem. Vid dålig anpassning av dessa parametrar kan utfallet innebära långsam konvergens i sökningen eller stagnation på grund av lokalt optimum.

Många försök till hantering av dessa problem har gjorts i tidigare forskning. De största insatserna har gjorts inom följande tre riktningar. Den första riktningen handlar om att anpassa urvalet bland olika strategier för mutation. Dock har val av strategier i dessa metoder inte tagit hänsyn till olikheter i kvalitet mellan individer, vilket betyder att alla individer bli tilldelade samma sannolikhet att välja en viss strategi för mutation bland kandidaterna. Dessa metoder kan ses som mindre önskvärda då lösningar med stora olikheter även kan anses kräva olikheter i operatorer för mutation för att nå förbättring. I den andra riktningen finns forskning som fokuserar på anpassningen av kontrollparametrarna för DE (mutation factor (F) och crossover rate (CR)). Dessa anpassningar beror i huvudsak på tidigare framgångsrika F och CR värden för att uppdatera sannolikheterna för att generera nya F och CR värden. På grund av detta kan den stokastiska natur som operatorer inom DE medför ignoreras så att även svaga F och CR värden framgångsrikt kan bidra till produktion av bättre lösningar. Användning av sådana oprecisa evalueringar vid bedömning av lämplighet kan dock förhindra att DE parametrarna i kommande generationer anpassas mot den mest effektiva lösningen. Den tredje forskningsinriktningen handlar om integration av olika lokala sökmetoder i DE för att förbättra exploatering av lovande regioner i sökområdet så att en snabbare konvergens mot optimum kan uppnås. Det är viktigt att anpassa karaktäristiken hos lokal sökning inom DE på ett lämpligt sätt så att balansen mellan exploatering och utforskning av nya områden passar väl för lösning av komplexa optimeringsproblem.

Denna avhandling fokuserar på att förbättra prestandan hos DE genom nya anpassningar och nya lokala sökmetoder. Resultaten kan i huvudsak sammanfattas i följande tre aspekter:

1) Förslag på en ny metod för rankbaserad anpassning av mutation, som tar hänsyn till kvaliteten på lösningar i populationen vid anpassning av sannolikheter för mutationsstrategier. Detta möjliggör hantering av lösningar av olika rang (med avseende på kvalitet) på olika sätt genom användande av olika urval och sannolikheter för mutationsoperatorer.

2) Utveckling av förbättrade metoder för anpassning av DE parametrar, med tonvikt på mer tillförlitlig och rättvis evaluering av kandidater (tilldelning av F och CR) i sökprocessen. Det föreslås att greedy search kan användas som en snabb och kostnadseffektiv teknik för att hitta bättre tilldelning av parametrarna F och CR i närheten av en kandidat. Vidare föreslås en metod för gemensam anpassning av parametrar som möjliggör kontinuerlig uppdatering av sannolikheter för urval för F och CR par, baserat på återkoppling inom sökprocessen.

3) Förslag på ny metod för bättre integration av lokal sökning inom DE algoritmen. Eager Random Search metoden undersöks som lokal sökmetod inuti DE, en metod som ger en annorlunda karaktäristik vid exploatering och utforskning genom användande av olika täthetsfunktioner. Framför allt föreslås ett nytt memetiskt ramverk där Alopex Local Search (ALS) utförs i samverkan med en DE algoritm. Ramverket ger en sömlös integration mellan exploatering och utforskning. Närmare bestämt kan beteendet för exploatering hos ALS kontrolleras av tillståndet hos den globala utforskningen i DE.

De föreslagna metoderna och algoritmerna har testats på ett flertal referensproblem och visat konkurrenskraftiga resultat jämfört med state-of-the-art algoritmerna. Vidare har Greedy Adaptive DE (GADE) algoritmen (som utvecklats baserat på greedy search för DE parametrar) testats i verkliga industriproblem, till exempel för att finna de bästa komponentparametrarna för att optimera prestanda hos harmoniska filter för överföring av elkraft. GADE har påvisats producera bättre harmoniska filtersystem med lägre harmoniska störningar jämfört med vanlig DE.