bad example of heuristics
– choose random assignment first and remove selection
– choose lowest cost assignment first and remove from selection
common idea with heuristics
concept of interchange-jiggle current solution so we can improve it
genetic heuristics approaches in literature
– greedy
– interchange
– tabu search
– simulated annealing
– population heuristics (e.g. genetic algorithms)
simulate annealing
if delta E<0
– New configuration has lower energy
– The new configuration then becomes a new initial configuration for performing small perturbations
simulate annealing
if delta 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
higher temperatures
The higher the temperatures, the higher the probability that the system will “jump” to a higher energy state
simulated annealing
low temperatures
As the temperature decreases, the probability that such a “jump” will occur diminishes
simulated annealing
thermal equilibrium
is considered to be attained when, after a number of random perturbations, a significant decrease in energy is not possible
tabu search
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
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
aspiration criterion
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
penalization
can be done in different ways, depending on the analyst and the context of the problem concerned
intensification
process 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
recent past
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.”
examples of structured problems
-network flow (assignment, transportation, transshipment, maximum flow)
-shortest path
-spanning tree
Min-cut max-flow theorem
the maximum flow possible is equal to the capacity of the minimum cut disconnecting the source and the sink
spanning tree
a spanning tree of the network G(N,A) is any tree of the network G which contains the entire set of nodes N
link painting
exploring the link inclusion is often called link painting
goal
an objective in conjunction with an aspiration level
goal deviation
difference between between what is aspired to and what is aspired to and what is accomplished with objective
advantages of goal programming
-allows multiple objectives
-allows slack in the constraint (not hard)
disadvantages of goal programming
-complexity of the "overall objective"
-must elicit goal values (and weights) from Decision Maker
-must find a way to homogenize these values
solving goal programming
-weights method
-preemptive method
-taha's method
weights method
single objective function is the weighted sum of the functions representing the goals
preemptive method
-prioritize goals in order of importance
-model optimized with one goal at a time (higher priority goal never degraded by lower priority goal)