Review 7

Simulated Annealling (SA)

Write down psuedocode for SA. Assume you are running three vectors: current, next, `best``. You may use the function:

def maybeJump2WorseSolution(old,new,t,cooling=1):
  return math.exp((old - new)/t) < r()**cooling:

Annealling is a process of slowly cooling a crystalline structure such that the particles reach minimum distance to all other atoms.

What is the connection of annealling to simulated annealling (SA)?
SA using "cooling". What is the difference between "hot" SA and "cool" SA?
Without "hot" SA, what might go wrong with SA- optimization?
Traditional SA is single objective optimizer:
- Give an example of a aggregation function that can turn an n-goal optimization problem into a 1-goal optiization problem.
- Such aggregation functions has a problem with "magic weights". What is that problem?

Write down psuedocode for MaxWalkSat. Hint: start with with simulated annealling, keep the same three vectors, remove cooling, at restarts.

Explain: GAs evolve a population over multi-generations
Given a population of vectors of candidate solutions, define:
- mutate
- crossover (assume single point crossover)
- select (assume binary domination and select via exhaustive domination search)
Suggest alternatives for single point crossover.

Write down the psuedo-code for DE.
- Include cr (probability of crossover);
- f (the crossover amount); and
- np (the number of candidates in the population)
Explain (ensuring that you take special care explaining the terms in italics):www
DE is an evolutionary program that uses a small external archive as the source for mutations

In PSO, canidates mutate at some velocity, At every step of PSO, a particle's velocity is changed using

where r is a random number 0 ≤ r ≤ 1.

In the above

How is the role of Φ₁ different to Φ₂?
What is X,Y?
What is the role of the v₀ term?
Comments on the following: "While SA, DE, GAs, optimize to a plateau, and stop, PSO is a better way to continual check and, maybe, update solutions".