Heuristics Flashcards
3 rules to determine UNIMODULARITY
For a Simplex tableau without z, obj func, or solution:
- Each element is 0, 1, or -1
- There are exactly 2 non-zero elements in each column
- The rows can be partitioned horizontally such that each column in each partition is 1 or 0.
Pros and cons of a greedy algorithm
Pro - quick and simple
Con - does not look ahead, therefore can give poor solutions
Describe a greedy algorithm for the TSP and Exam Scheduling
TSP - visit the nearest, feasible, unvisited city.
Exam scheduling - order the exams by size. Allocate each in turn to a feasible timeslot that minimises the number of students with consecutive exams.
Give greedy algorithm examples for TSP and Exam Scheduling
TSP - visit the next nearest, feasible, unvisited city
Exam Scheduling - order exams according to size. Allocate each in turn to a feasible timeslot which minimises the number of students with consecutive exams.
Describe random descent for TSP
Create a feasible solution at random
Cost = distance
Repeat the following:
1. Choose 2 non-adjacent edges at random and delete them
2. Create a new tour
3. Calculate new cost: if better than previous solution, accept, else, reject.
Stop after n moves without improvement, n = parameter.
Describe random descent for Exam Scheduling
Create a feasible solution at random
Cost = number of students with consecutive exams
Repeat the following:
1. Move an exam at random to a new feasible timeslot
2. Calculate new cost: if better than previous solution, accept, else, reject.
Stop after n moves without improvement, n = parameter.
Describe steepest descent for TSP
Create a feasible solution from a greedy algorithm
Cost = distance
Repeat the following:
1. In turn, choose 2 non-adjacent edges, delete them and create a new tour
3. Calculate the cost of each move: choose the move that results in the largest reduction in cost.
Stop when there are no improving moves.
Describe steepest descent for Exam Scheduling
Create a feasible solution from a greedy algorithm
Cost = number of students with consecutive exams
Repeat the following:
1. In turn, move each exam to a new, feasible timeslot
3. Calculate the cost of each move: choose the move that results in the largest reduction in cost.
Stop when there are no improving moves.
Describe simulated annealing for TSP
Set parameter t (temperature) to a start value
Create a starting solution (S) at random with cost F(S)
Store F(S) as ‘best_cost’
Cost = distance
Neighbourhood = solutions formed by deleting 2 non-adjacent edges and forming a new tour
Repeat the following:
1. Pick a neighbouring solution S* at random
2. If F(S) < F(S) then accept the move, else:
i). Let d = increase in cost
ii). Accept if exp^(-d/t) > r(0,1) (r is a random number between 0 and 1), else reject
3. If F(S) < best_cost, then best_cost = F(S)
4. After n iterations, reduce t via tp where p is the cooling ratio parameter and is between 1 and 0, and n is a parameter.
Stop when t becomes small.
Parameters needed = start t, end t, n, p.
Describe simulated annealing for Exam Scheduling
Set parameter t (temperature) to a start value
Create a starting solution (S) at random with cost F(S)
Store F(S) as ‘best_cost’
Cost = wt * number of students with clashes + number of students with consecutive exams. wt is a parameter and is large.
Neighbourhood = solutions formed by moving a random exam to a new timeslot
Repeat the following:
1. Pick a neighbouring solution S* at random
2. If F(S) < F(S) then accept the move, else:
i). Let d = increase in cost
ii). Accept if exp^(-d/t) > r(0,1) (r is a random number between 0 and 1), else reject
3. If F(S) < best_cost, then best_cost = F(S)
4. After n iterations, reduce t via tp where p is the cooling ratio parameter and is between 1 and 0, and n is a parameter.
Stop when t becomes small.
Parameters needed = start t, end t, n, p,
Describe Tabu Search for TSP
Create a feasible solution from a greedy algorithm
Cost = distance
Neighbourhood = solutions formed by deleting 2 non-adjacent edges and forming a new tour
Repeat the following:
1. Move to the lowest cost neighbour that is not tabu
2. Do accept tabu moves if it creates a NEW best solution
3. Edges removed from the tour are tabu for t iterations, t is a parameter
Stop after n moves with no improvement, n = parameter.
Describe Tabu Search for Exam Scheduling
Create a feasible solution from a greedy algorithm
Cost = wt * number of students with clashes + number of students with consecutive exams
Neighbourhood = solutions formed by moving a random exam to a new timeslot
Repeat the following:
1. Move to the lowest cost neighbour that is not tabu
2. Do accept tabu moves if it creates a NEW best solution
3. The moved exam can’t return to its previous timeslot (is tabu) for t iterations, t is a parameter
Stop after n moves with no improvement, n = parameter.
Describe a genetic algorithm for TSP
Create an initial population of random solutions
Fitness = distance
Repeat the following:
1. Choose 2 parents probabilistically according to 1/fitness
2. Apply crossover: selecting 2 crossover points at random and filling in the missing values in the order that they occur in in the other parent
3. Apply mutation when a random number is more than a mutation parameter: swap two adjacent cities.
4. Update population: best child replaces worst member of population
Stop after n generations, n = parameter
Describe a genetic algorithm for exam scheduling
Create an initial population of random solutions
Fitness = wt * number of students with clashes + number of students with consecutive exams, wt is a parameter and is large
Repeat the following:
1. Choose 2 parents probabilistically according to 1/fitness
2. Apply crossover: selecting a crossover point at random and swap the exams after the crossover point, skipping duplicates to keep every exam scheduled.
3. Apply mutation when a random number is more than a mutation parameter: move a random exam to a new timeslot
4. Update population: best child replaces worst member of population
Stop after n generations, n = parameter
Describe a memetic algorithm for TSP
Create an initial population of random solutions
Fitness = distance
Apply random descent
Repeat the following:
1. Choose 2 parents probabilistically according to 1/fitness
2. Apply crossover: selecting 2 crossover points at random and filling in the missing values in the order that they occur in in the other parent
3. Apply mutation when a random number is more than a mutation parameter: swap two adjacent cities.
4. Apply random descent
5. Update population: best child replaces worst member of population
Stop after n generations, n = parameter
