Algorithms for Pure Categorical Optimization

Abstract

Optimeringsproblem med kategoriska variabler är vanligt förekommande exempelvis inom bilindustrin och andra industrier där mekaniska komponenter ska väljas ut och kombineras på gynnsamma sätt. Avsaknaden av naturlig ordning på beslutsvariablerna gör att kategoriska optimeringsproblem oftast är svårare att lösa än diskreta eller kontinuerliga problem. Det är därför viktigt att ta fram metoder som löser kategoriska optimeringsproblem. Den här rapporten presenterar tre olika algoritmer som kan användas för att lösa kategoriska optimeringsproblem: en lokalsökningsalgoritm, en globalsökningsalgoritm, och en genetisk algoritm. Dessutom presenteras två olika omgivningsdefintioner att använda ihop med lokalsökningsalgoritmen, en diskret, och en kategorisk. Algoritmerna implementerades i Matlab och testades på två olika kategoriska optimeringsproblem: ett artificiellt problem, och ett balkproblem. De framtagna algoritmerna applicerades på ett stort antal instanser av testproblemen och deras prestanda utvärderades med hjälp av prestandaprofiler och dataprofiler. Lokalsökningsalgoritmen utrustad med den kategoriska omgivningen presterade bäst av de testade algoritmerna.