CIS Quiz 2

Primary tabs

Bookmark to learn: Login to use bookmarks.

Statistics

'Repetition is the mother of all learning.'

Bookmark to learn: Login to use bookmarks.

Add to collection ... add CIS Quiz 2 to your collections:

Help using Flashcards ...just like in real life ;)

  1. Look at the card, do you know this one? Click to flip the card and check yourself.
  2. Mark card Right or Wrong, this card will be removed from the deck and your score kept.
  3. At any point you can Shuffle, Reveal cards and more via Deck controls.
  4. Continue to reveal the wrong cards until you have correctly answered the entire deck. Good job!
  5. Via the Actions button you can Shuffle, Unshuffle, Flip all Cards, Reset score, etc.
  6. Come back soon, we'll keep your score.
    “Repetition is the mother of all learning.”
  7. Signed in users can Create, Edit, Import, Export decks and more!.

Bookmark to learn: Login to use bookmarks.

Share via these services ...

Email this deck:

Right: #
Wrong: #
# Right & # Wrong of #

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)