Problem Spaces, Initial Positions, and Local Optima

Initial positions can have significant effect on the outcome of a local search procedure, since you risk arriving at a local optimum. As an example, consider this quine:

;; initial position
(let ((s "format t ~S"))
  (format t "~S" s))

;; local optimum
(let ((s "(format t ~A")
      (l "~@?~S))~%  ~@?~A))~%")
      (u " r s l u r s (string 'l) u")
      (r "(let ((s ~S)~%      (l ~S)~%      (u ~S)~%      (r "))
  (format t L r s l u r s (string 'l) u))

This is a partly pathological example, since part of the point in writing the quine was to probe at the fixed-pointness of quines by choosing an arbitrary starting point. However, consider a different starting point:

;; initial position
((lambda (x) (princ x))
 'initial-position)

There is little chance of gradually mutating this solution to the above quine. Indeed, there is another quine much nearer to it in the problem space:

;; local optimum
((LAMBDA (X) (PRINC `(,X ',X))) '(LAMBDA (X) (PRINC `(,X ',X))))

Admittedly, this latter quine (the standard Common Lisp solution?) is more elegant than the first one.

This raises an important point: reaching a good solution easily depends on your initial position in the problem space. This can be a challenge, since overcoming the local search effect means you have to try out a different initial position. In other words, you have to overcome the Einstellung effect. Practical ideas: Take a break. Ask someone where their initial position would be. Locate a number of initial positions before starting local search. Make a habit of staking at least two significantly different initial positions.

Circumlude: If unfamiliar, I heartily recommend Richard Haming’s lecture on n-dimensional space. There is math. There are high level reflections and takeaways.

The problem with problem solving is that in order to find the global optimum, you must search the entire solution space. This gets pretty heavy for high-dimensional problems. Consider a high-dimensional problem space, one with many variables. Suppose you want to optimize for a set of variables. So, you start out in your initial position and do a local search until you find that while you have optimized one variable, any move to optimize other desired variables leads to de-optimizing your variable. You have arrived at the Pareto front.

There might be no solution that optimizes the value of all involved variables simultaneously. Thus, a scoring function is necessary, which means you introduce a weighting on the variables so that some solution will satisfy you the most. Perhaps you don’t even care about the value for some variables, beyond some minimum requirement. That might effectively constrain the search space to find a satisfying solution.

However, consider the problem of selecting your initial positions: If you already know the problem space, then parts of it must have been solved or scored already. The initial positions were already placed in the past. Thus, initial positions must be staked blindly. Certainly, heuristics may play a good role – perhaps by pattern matching against other problems with similar characteristics. But the initial stakes are essentially placed blindly. Stabs in the dark. Intuition. (If something is a routine problem, then it might not be a problem anymore so much as an application of a previous solution.)