Heuristics: Bad Approach: 3 men assigned to 3 jobs with random costs. (First)
–Choose a man and a job at random
–Assign the chosen man to the chosen job
–Delete the chosen man and the chosen job from the problem
–Repeat with this new (smaller) problem
Heuristics: Bad Approach: 3 men assigned to 3 jobs with random costs. (Second)
–Choose the smallest cost in the cost matrix and assign the corresponding man to the corresponding job
–Delete them from the problem and repeat with this new (smaller) problem
A common idea with heuristics is the concept of
interchange – the basic idea is to jiggle the current solution to see if we can improve it
With regard to heuristics we have a number of generic approaches in the literature
– Greedy
– Interchange
– Tabu search
– Simulated annealing
– Population heuristics (e.g. genetic algorithms)
Simulated Annealing If E < 0
– New configuration has lower energy
– The new configuration then becomes a new initial configuration for performing small perturbations
Simulated Annealing If E > 0
– New configuration has higher energy
– However, the new configuration is not automatically excluded from the possibility of becoming a new initial configuration
Simulated Annealing (Temperature)
• In physical systems, “jumps” from lower to higher energy levels are possible
• The higher the temperatures, the higher the probability that the system will “jump” to a higher energy state
• As the temperature decreases, the probability that such a “jump” will occur diminishes
Probability (P) that at temperature T the energy will increase by DE is:
The decision whether a new configuration of particles
for which E > 0 should be accepted as a new initial configuration is made upon generation of a random number r from the interval [0,1]
Simulated Annealing if r
the new configuration is accepted, otherwise, it is excluded from
consideration
Thermal equilibrium
is considered to be attained when, after a number of random perturbations, a significant decrease in energy is not possible
Simulated Annealing if r
Simulated Annealing visual
Suppose you want to sequence n jobs on one machine. Time for job j is tj and the due date is dj. If you finish job j before its due date, there is a charge hj per unit time. Completing the job late incurs a penalty of pj per unit time.
• Define a temperature cooling schedule: T0 = 0.5z0; Ti = 0.5 Ti-1
– Change temperature after t=3 accept iterations
• Define neighborhood as a switch of two positions in the sequence
• Start with solution s0 = {1,2,3,4}
– Neighborhood N(s0) = {2,1,3,4}, {1,3,2,4}, {1,2,4,3}
Genetic Algorithms Definition
• In the case of genetic algorithms, an encoded parameter set is used
• The set of decision variables for a given problem is encoded into a bit string (chromosome, individual)
– Feasible solutions can be considered chromosomes, comprised of a set of genes
Steps in any genetic algorithm:
– Step 1: Encode the problem and set the values of parameters (decision variables)
– Step 2: Form the initial population P(0) consisting of n strings.
– Step 3: Select n parents from the current population
– Step 4: Randomly select a pair of parents for mating
–Step 5: Substitute the old population of strings with the new population
–Step 6: If the number of generations (populations) is smaller than the maximal pre-specified number of generations, go back to Step 3. Otherwise, stop
Genetic Algorithms Step 2: Form the initial population P(0) consisting of n strings.
• The value of n depends on the problem
• Evaluate the fitness of each string, record
the best solution so far
Genetic Algorithms Step 4: Randomly select a pair of parents for mating
• Create 2 offspring by exchanging strings with crossover
• To each of the created offspring, apply mutation randomly
–If infeasible, go to step 4
• Apply crossover and mutation operators
until n offspring (new population) are
created
Genetic Algorithms Step 5: Substitute the old population of strings with the new population
• Evaluate the fitness of all members in the new population
Genetic Algorithms Step 6: If the number of generations (populations) is smaller than the maximal pre-specified number of generations, go back to Step 3. Otherwise, stop
• For the final solution, choose the best string discovered during the search
Tabu Search
• Uses the concept of the so-called flexible memory
• The basic idea is to pronounce the subset of moves in a neighborhood forbidden
• Which moves are to be forbidden (tabu) is decided according to the recency or frequency that certain moves have participated in generating the previous
solutions
• Generate the initial solution to the problem by employing a heuristic algorithm for solving the traveling salesman problem.
–For example, suppose that the initial solution is represented by the tour (D, 2, 3, 4, 5, 1, D)
Initial Solution for Traveling Salesman with Tabu
Tabu Search-swapping
• In the case of the TSP, a swap exchanges the positions of 2 nodes in the route
• Once a swap has been made, a move has actually been made leading from one solution to another one
– a move has been made that leads us toward the solution
• After making a swap, the next solution has a smaller, equal, or larger objective function value as compared to the previous solution
Tabu Search-swapping 3 and 5
• E.g., nodes 3 and 5 swap positions D, 2, 3, 4, 5, 1, DD, 2, 5, 4, 3, 1, D
– After swapping nodes 3 and 5, the objective function has a larger value:
3.6 + 3.6 + 7.3 + 4.1 + 8.2 + 7.2 = 34
Tabu Search
• Glover and Laguna (1993) proposed the following tabu data structure to represent the remaining tabu tenure for node pairs:
Tabu restrictions do not apply in all situations
–If, for example, a tabu move leads to a solution with the shortest route so far discovered, the tabu classification will be disregarded and the move will be allowed
Tabu Search Gains
-Iteration 0 (initial solution) has a cost of 30.8
-Swap all combinations, find new gain
-Sort the first five best candidates for swap moves in order of descending gain
-Find the largest gain
–Swap their positions
–Suppose that in the subsequent three iterations, we are not allowed to swap the positions of these two nodes (put the number 3 (because 3 iterations) in their square on the graph, reduce to 2 next iteration).
Refinements Tabu Search
• The tabu list may prohibit a move that leads to an improved solution. The aspiration criterion allows improving moves to be made
• When a series of successive iterations does not yield an improved solution, we can use intensification and diversification strategies
Following the tabu status of certain swaps refers to
• the “recent past.” In this sense, it can be said that the tabu search technique is characterized by a “recency-based memory.”
• Glover and Laguna (1993) proposed that the recency-based memory be followed by frequency-based memory.
The data contained in the frequency- based memory
• enable us to follow the “search history” from the beginning
• This can serve to diversify the search by traveling to new regions
Tabu Search
• Penalization
can be done in different ways, depending on the analyst and the context of the problem concerned
Tabu Search
• intensification
The process of intensification consists of following the frequencies of subsets of elite solutions (corresponding to high quality local optima) and traveling to the regions promising a further improvement in the solution
Mutation
