När för en svår real-world optimering problem ingen bra problem-specifik algoritm är tillgänglig ofta randomiserade sökheuristik används. De hoppas kunna leverera bra lösningar i acceptabel tid. Teoretisk analys koncentrerar sig vanligen på den genomsnittliga tid som behövs för att hitta en optimal eller ungefär optimal lösning. Detta motsvarar varken tillämpningen i praktiken eller den empiriska analysen eftersom man vanligtvis inte känner till optimala lösningar och även om man inte kan känna igen dem. Oftast stoppas algoritmerna efter en tid. Detta motiverar en teoretisk analys för att koncentrera sig på kvaliteten på den bästa lösning som erhålls efter ett på förhand angivet antal funktionsutvärderingar som kallas budget. Med hjälp av detta perspektiv analyseras två enkla randomiserade sökheuristiker, slumpmässig lokal sökning och (1+1) evolutional algoritmen på några välkända exempelproblem. Högre och lägre gränser för den förväntade kvaliteten på en lösning för en fast budget av funktionsutvärderingar bevisas. Analysen visar nya och utmanande problem i studien av randomiserade sökheuristik. Den visar potentialen i detta skifte i perspektiv från förväntad körtid till förväntad lösningskvalitet.
Jansen och Zarges Ref diskuterade två algoritmer: slumpmässig lokal sökning och (1+1) EA och fick sådana gränser på några välkända exempelproblem.
Performance analysis of randomised search heuristics operating with a fixed budget
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}