Skip to content
Tutorials Center
My learning

Topics

Lesson 212 of 225 ยท Advanced Topics

Pseudo-Random Generators and Simulated Annealing

Build linear congruential and xorshift random number generators, test their quality, then use random moves and a cooling schedule in simulated annealing.

Computers are deterministic, so where do random numbers come from? Usually from a pseudo-random number generator (PRNG): a small formula that turns one number (the state) into the next, producing a sequence that merely looks random. Understanding one is useful for testing, games and hashing, and it explains why random.seed(42) repeats a run exactly.

Then you will put randomness to work. Simulated annealing is a search strategy for hard optimization problems, such as a short tour through many cities, that deliberately accepts some worse moves early on so it does not get stuck in a poor local optimum. It pairs naturally with the ideas in Randomized Algorithms and NP-Completeness.

A linear congruential generator (LCG)

The oldest recipe is one line:

TEXT
state = (a * state + c) mod m

With good constants the sequence visits all m states before repeating. The same seed always gives the same sequence, which is exactly why it is called pseudo-random.

Python A linear congruential generator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The low bits of an LCG with a power-of-two modulus are weak: the lowest bit simply alternates 0, 1, 0, 1. That is why random() above uses the high bits (the division by 2**32), not state % 2.

Xorshift: shifts and XORs

A modern, simple alternative uses only bit operations (see Bit Manipulation). The classic 32-bit xorshift mixes the state with three shifted copies of itself. The state must never be 0, or it stays 0 forever.

Python Xorshift32 and a quick quality check

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both generators are fast but not secure: given a few outputs you can recover the state and predict everything. For passwords and tokens use Python's secrets module. Python's own random uses a much larger generator, the Mersenne Twister.

Simulated annealing

Imagine searching for the lowest point of a bumpy landscape. Greedy descent (always step downhill) gets trapped in the first valley. Simulated annealing imitates cooling metal: it keeps a temperature T.

  1. Propose a small random change to the current solution.
  2. If the new cost is lower, accept it.
  3. If it is higher by delta, accept it anyway with probability exp(-delta / T).
  4. Lower T a little (the cooling schedule) and repeat.

When T is high, almost any move is accepted and the search explores freely. As T falls, worse moves are rejected more often, and the search settles into a deep valley.

A first example: a bumpy function

Python Annealing on a function with many valleys

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Greedy descent ends in whichever valley it started near; annealing usually reaches the global one. It never guarantees the optimum, but it finds very good answers when exact search is too slow.

A harder example: a short tour

Given points on a plane, visit all of them once and return to the start with the shortest total length (the travelling salesman problem). A natural move is 2-opt: choose two positions and reverse the stretch of the tour between them. It can remove a crossing. Compare it with a random tour.

Python Travelling salesman by annealing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A random tour through 40 points is about 2,100 units long; annealing cuts it to about 510, roughly a quarter. The three seeds end within a percent of each other, a sign that they all found a very good, though not provably optimal, tour.

Choose the cooling rate by experiment: cooling too fast freezes the search in a poor valley, too slowly wastes time. Common practice is to restart a few times with different seeds and keep the best result.

Common mistakes

  • Seeding with 0 in xorshift. The state stays 0 forever; guard against it.
  • Using the lowest bits of an LCG. They have very short periods; take high bits.
  • Using these generators for secrets. They are predictable. Use secrets.
  • Cooling too quickly in annealing. The run becomes plain greedy descent.
  • Forgetting to remember the best state. Annealing may wander away from the best solution it has seen; store it separately.
  • Expecting a guaranteed optimum. Annealing gives good answers, not proofs. For exact answers see dynamic programming and Branch and Bound.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a pseudo-random number generator do with the same seed?

    A PRNG is a deterministic formula; the state alone decides the next value. That is why seeds make runs repeatable.
  2. 2. Why is state % 2 a poor random bit from an LCG with modulus 2^32?

    With a power-of-two modulus the lowest bit has period 2, so use the high bits instead.
  3. 3. In simulated annealing, when is a worse solution accepted?

    Accepting some worse moves early lets the search escape local minima; as T decreases it becomes pickier.
  4. 4. Which of these is a good use for xorshift?

    Xorshift is fast and fine for simulation, but it is predictable, so it must never protect secrets.

Summary

  • A PRNG is a deterministic state update; an LCG uses (a * s + c) % m, xorshift uses shifts and XORs, and both repeat from the same seed.
  • Use high bits of an LCG, never seed xorshift with 0, and use secrets for anything security related.
  • Simulated annealing accepts worse moves with probability exp(-delta / T) while T cools, escaping local minima.
  • Moves such as the 2-opt reversal and a patient cooling schedule give good tours for hard problems like the travelling salesman problem.

Next: Skip Lists