Nyhetsarkiv 2010

Giriga algoritmer bäst vid många mål

2010-12-08

Vilka algoritmer ska ett luftvärnssystem arbeta med? Partikelsvärmsalgoritmer om det är tio mål som ska bekämpas. Om det är fler mål än tio fungerar giriga algoritmer bäst. Resultaten presenterar Fredrik Johansson i sin doktorsavhandling vid Örebro universitet.

Så kallade TEWA-system (Threat Evaluation & Weapon Allocation) används för att skydda strategiska mål mot fientliga angrepp. Det kan till exempel röra sig om ett flygfält som ska skyddas mot inkommande missiler. Systemen upptäcker hot, utvärderar hoten och riktar in försvararens vapensystem för att hoten ska kunna slås ut. Det slutgiltiga beslutet om vapeninsats fattas därefter av en operatör.

– I den befintliga forskningslitteraturen finns förslag på vilka algoritmer som kan vara lämpliga att använda. Jag har utvecklat metoder för att undersöka vilka algoritmer som fungerar bäst i praktiken, förklarar Fredrik Johansson.

Giriga algoritmer

Fredrik Johanssons studie visar att det är antalet vapen I TEWA-systemet och mängden mål systemet har att hantera som avgör valet av algoritm.

– Så kallade partikelsvärmsalgoritmer är effektiva om det rör sig upp till cirka tio mål och tio vapen. Om TEWA-systemet ska hålla reda på fler mål och vapen än så bör vi använda det som kallas för giriga algoritmer istället, säger Fredrik Johansson.

En girig algoritm är – mycket förenklat – snabb men inte perfekt. Algoritmen jobbar efter grova riktlinjer och testar inte alla alternativ som krävs för att hitta en optimal lösning. Att den slipper pröva vissa lösningar gör algoritmen snabb. En egenskap som är avgörande i ett TEWA-system.

– Det får inte gå många sekunder mellan det att systemet upptäcker ett hot och tills dess att operatören har fattat ett beslut om vapeninsats, säger Fredrik Johanson.

Hela systemet

I tidigare forskning har TEWA-systemen nästan alltid behandlats som två delar: hotutvärdering för sig och vapenallokeringen för sig. Fredrik Johanssons studie är en av de första som ser systemet som en enhet. Men att säga att man är först med att undersöka något kan vara vanskligt när det gäller just TEWA-system.

– Den som forskar inom det här området vet inte alltid vilken kunskap som finns under ytan. Troligen finns det en del forskning om TEWA-system som är hemlig och inte är tillgänglig för oss vanliga forskare, avslutar Fredrik Johansson.

Text: Ulf Nylén
Foto: Anders Dahlbom

Uppdaterad: 2012-05-03

Sidansvarig: webbsupport