Abstract Lokal sökning är en grundläggande byggsten i memetiska algoritmer. Guidad lokal sökning (GLS) kan förbättra effektiviteten i lokal sökning. Genom att ändra guidefunktionen guidar GLS en lokal sökning för att fly från lokalt optimala lösningar och hitta bättre lösningar. Nyckelkomponenten i GLS är dess straffmekanism som bestämmer vilken funktion som väljs för att bestraffa när sökningen är fångad i en lokalt optimal lösning. Den ursprungliga GLS straffmekanism endast använder sig av kostnaden och det aktuella straffvärdet för varje funktion. Det är välkänt att många kombinatoriska optimeringsproblem har en stor dalstruktur, d.v.s. ju bättre en lösning är, desto större är chansen att den är närmare en globalt optimal lösning. I detta dokument föreslås att man använder sig av stora antaganden om dalstrukturen för att förbättra mekanismen för att bestraffa GLS. En förbättrad GLS-algoritm som kallas Elite Biased GLS (EB-GLS) föreslås. EB-GLS registrerar och upprätthåller en elitlösning som en uppskattning av de globalt optimala lösningarna, och minskar chansen att bestraffa funktionerna i denna lösning. Vi har systematiskt testat den föreslagna algoritmen på det symmetriska reseförsäljarproblemet. Experimentella resultat visar att EB-GLS är betydligt bättre än GLS.
Shi och Al. REF förbättrade GLS baserat på den stora dalen antagande TSP.
EB-GLS: An Improved Guided Local Search Based on the Big Valley Structure
{'venue': 'Memetic Computing, 2017: 1-18', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}