Randomiserade sökheuristik tillämpas ofta på NP-hårda kombinatoriella optimeringsproblem. Runtime-analysen av randomiserade sökheuristiker har bidragit enormt till vår teoretiska förståelse. Nyligen har randomiserade sökheuristik undersökts när det gäller deras uppnåeliga framsteg inom en fast tidsbudget. Vi följer detta tillvägagångssätt och presentera en fast budget analys för en NP-hård kombinatoriell optimering problem. Vi anser att den välkända Traveling Salesperson Problem (TSP) och analysera den fitness ökning som randomiserade söka heuristics kan uppnå inom en given fast tidsbudget. I synnerhet analyserar vi Manhattan och Euclidean TSP instanser och Randomized Local Search (RLS), (1+1) EA och (1+λ) EA algoritmer för TSP i en utjämnad komplexitet inställning, och härleda de nedre gränserna för den förväntade fitnessvinst för ett visst antal generationer.
Nallaperuma, Neumann och Sudholt REF tillämpade den fasta budgetanalysen på det välkända problemet med resande säljare.
Expected Fitness Gains of Randomized Search Heuristics for the Traveling Salesperson Problem
{'venue': 'Evolutionary Computation', 'journal': 'Evolutionary Computation', 'mag_field_of_study': ['Mathematics', 'Medicine', 'Computer Science']}