H4: Heuristieken Flashcards
Leg het N-queens probleem uit. En hoe kunnen we dit probleem voorstellen.
N aantal queens moeten op een NxN speelbord worden geplaatst met de voorwaarde dat ze elkaar niet kunnen pakken.
Beslissing: waar elke queen plaatsen?
Doelfunctie: geen
Beperking: De queens moeten zo worden geplaatst dat ze elkaar niet kunnen pakken.
We kunnen de positie van de queens voorstellen adhv een vector of list. Bij de vector zal elke plaats een kolom voorstellen en het cijfer de rij.
Hoe kunnen we het traveling salesman problem voorstellen?
Er zijn verschillende manieren:
- Een graaf
- Een vector
- Koppels
- asymmetrische matrix
- Symmetrische matrix
Welke 3 grote groepen van metaheuristieken hebben we gezien in de les? en licht deze kort toe.
- Local search:
We beginnen met een complete oplossing en gaan hier zeer kleine wijzigingen op toepassen.
=> Iterated local search, Tabu search, Variable neigbourhood search, multiple local search - Constructieve metaheuristieken:
We beginnen met een onvolledige oplossing en gaan deze opbouwen tot een complete oplossing
=> Grasp, Ant colony - Populatie gebaseerde metaheuristieken:
We beginnen met meerdere oplossingen en gaan deze oplossingen combineren om nieuwe oplossingen te bekomen.
=> Evolutionaire/ genetische algoritmen
Local search
1. Iterated local search, welke begrippen worden hier gebruikt?
Local search:
- Iterated local search (ILS)
- Move = een gerichte en kleine wijziging
- Move type = de soort wijziging bv. veranderen van een byte
- Move strategy = keuze welke move je gaat maken
Strategieën:
- First improvement = de eerste betere oplossing wordt gekozen
- Best improvement = we gaan de hele neighbourhood bekijken en daar de beste uitnemen
- Random = slechter of beter, maakt niet uit, je kiest deze
- Radom improvement: random move maar je gaat enkel voort als het een betere oplossing is.
Local search
2. Tabu search, welke begrippen worden hier gebruikt?
Local search
2. Tabu search (TS)
Hierbij gebruikt men steeds een lijst van de moves die al werden gedaan.
Tabu tenure = geeft aan hoeveel stappen je terugkijkt
=> een dynamische lengte is hier ook mogelijk
Strategic oscillatie = je gaat bij het zoeken naar de oplossing over de capaciteit om een betere feasible oplossing te vinden.
Local search
3. Variable neighbourhood search, welke begrippen worden hier gebruikt?
Local search
- Variable Neighbourhood search
bv. Knapzakprobleem; steeds 1 bit aanpassen en verder gaan met beste oplossing
Local search
4. Multiple local search, welke begrippen worden hier gebruikt?
Hierbij vertrekken we van meerdere oplossingen tegelijk
Voor welk probleem wordt de Iterated local search veel gebruikt?
Traveling salesman problem
Welke stappen vinden we terug bij het iterated local search algoritme toegepast op een Traveling salesman problem?
Step 0: Generate initial solution: adhv een constructieve heuristiek of random.
Step 1: Local search (move = swap): steden worden verwisseld als deze voor een lagere afstand zorgen wordt de swap uitgevoerd, zoniet dan wordt er een nieuwe stap gezocht. Dit doen we tot dat er geen swap meer kan worden uitgevoerd. Dit kan betekenen dat we in de optimale oplossing hebben gevonden of dat we in een lokaal optimum zitten.
Step 2: Perturbation: Omdat we mogelijks in een lokaal optimum zitten gaan we een perturmatie algoritm toepassen waarbij de oplossing tijdelijk slechter is. Hierna gaan we terug stap 1 toepassen tot we een nieuw optimum vinden.
Dit wordt gedaan tot een stop criteria is voldaan
- tijdslimiet
- maximaal aantal perturbaties
- maximaal aantal perturbaties zonder verandering van optimum
Hoe kan het vastzitten in een lokaal optimum bij een tabu search worden opgelost?
Bij een tabu search zal er een tabu tenure zijn die aangeeft hoeveel stappen de tabu list bijhoudt. Bij een lokaal optimum zal de tabu tenure toenemen zodat we een grotere move maken en we dus tot nieuwe oplossingen kunnen bekomen.
Constructieve metaheuristieken
1. Grasp, leg uit
Constructieve metaheuristieken
1. Greedy random adaptive search procedure (GRASP)
We vertrekken hierbij vanuit een onvolledige oplossing.
We gebruiken een restricted candidate list (RCL), deze geeft aan wat de dischtsbijzijnde steden zijn.
bv alpha = 2 => 2 dichtsbijzijnde steden.
(Bij Alpha = 1 => Greedy)
(Bij Alpha = n => Random)
Hierna kiezen we uit de RCL een random kandidaat.
=> In het voorbeeld wordt GRASP toegepast op Single source transportation problem (SSTP)
Wat zijn de stappen in het GRASP?
Step 1: (Re)rank or (re)sort all combinations of users and sources according to increasing cost.
Step 2: Create or update the restricted candidate list (RCL) by taking the first 5 elements of the ranked list. [5 is a parameter that you choose yourself]
Step 3: Take a random element from the RCL according to a certain probability: Element 1 2 3 4 5
Probability 10% 20% 40% 20% 10% [choose yourself]
Step 4: Add this element to the solution and remove it from the ranked list and the RCL.
Step 5: Check capacity constraints:
– If capacity constraints are not violated: remove all elements that have that user number from the ranked list and the RCL.
– If capacity constraints are violated: remove this element from the solution.
=> All users are now assigned to sources. This solution can be used as an initial starting solution for another metaheuristic (e.g. local search).
Constructieve metaheuristieken
2. Ant colony, leg uit
Constructieve metaheuristieken
1. Ant colony
=> Gebaseerd op mieren die eten zoeken
Eenmaal dat mieren tot het eten geraken zullen ze feromonen achterlaten die de andere mieren ook tot het eten leidden. Hierdoor wordt het pad steeds rechter.
- Toegepast op Traveling salesman problem
Populatie gebaseerde metaheuristieken:
1. Evolutionaire/ genetische algoritmen, leg uit.
Populatie gebaseerde metaheuristieken:
1. Evolutionaire/ genetische algoritmen
Populatie = de verschillende oplossingen die we gebruiken Selectie = het proces dat beter aangepaste DNA zijn overlevingskansen verhoogd Crossover = het combineren van 2 'individuën'
=> Zeer goede manier op knapzakprobleem op te lossen!
Maar werkt niet goed voor TSP…
Wat zijn de stappen in het Evolutionaire/ genetische algoritmen?
Step 0: generate initial population
=> maak populatie van verschillende oplossingen
Kan random worden gekozen.
Repeat:
Step 1: selection: Hier gaan we twee individuën selecteren die gaan reproduceren.
- OPTIE 1: Toernooi selectie = binary tournament
=> Selecteer 2 oplossingen van de populatie en kies de beste oplossing, dit doen we tweemaal om de beste ouders te bekomen - OPTIE 2: Roulette wheel selectie
=> De beste doelfunctie waarde krijgt een hogere kans gekozen te worden
Step 2: recombination (using cross-over)
- one point crossover
- OF two point crossover
=> random geselecteerde positie een crossover zal worden toegepast. Hierdoor kunnen de delen worden gerecombineert.
Kijk nu wat de beste feasible oplossing is!
(Step 3: mutatie): random kleine wijziging maken, gebeurt niet elke keer!
Step 4: update population: Een reinsertion toepassen waarbij je de laagste of infeasible doelfunctie waarden vervangt met de juist gevonden oplossing. Als we dit blijven doen krijgen we steeds een betere populatie.
