"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)"