Spiral Dynamics Inspired Optimization Demo Using Python

I’ve been looking at an interesting optimization algorithm based on a 2011 research paper titled “Spiral Dynamics Inspired Optimization” by K. Tamura and K. Yasuda. SDI optimization is somewhat similar to particle swarm optimization (SPO). Briefly, SDI sets up a collection of random possible points/solutions. The best current solution is set as a center, and then the points are moved towards the current center in a spiral motion. A new center is set, and the process continues.

I put together a simple end-to-end demo using Python. The goal is to minimize the Sphere function in 3 dimensions, f(x,y,z) = x^2 + y^2 + z^2. The function has a known minimum of f = 0.0 at (0, 0, 0).

The parameters of the SDI optimization technique are:

m = number of points/solutions
theta = controls curvature of spiral movement
r = controls how quickly points move towards center
max_iter = number of times to iterate

The SDI optimization technique uses a clever rotation matrix R that determines how each point/solution moves towards the current spiral center. My demo hard-codes the R matrix. In a non-demo scenario, I’d write code to programmatically generate R.

A very interesting experiment. I intend to look at SDI optimization in more depth. When I fully understand the subtleties of the technique, I’ll write up a complete explanation.

I’m not a big fan of movies that have heavy doses of symbolism but “Dark City” (1998) has an interesting plot too. Aliens kidnap humans and put them in a fake city where it’s always night, and then experiment with their memories. The movie has cinematographic themes of spirals and circles. From left: A spiral clock with no hands, one of the humans suspects the truth and becomes obsessed with spirals, the hero has a memory implanted that makes him think he murdered a prostitute, a spiral staricase in a chase scene.

Code below. Not thoroughly tested.

# spiral_optimization.py
# minimize Sphere function using spiral optimization

import numpy as np

def error(X):
  # compute Sphere value for n=3, take squared diff
  z = 0.0
  for j in range(3):
    z += X[j]**2
  err = (z - 0.0)**2
  return err

def find_center(points, m):
  best_err = error(points[0])
  idx = 0
  for i in range(m):
    err = error(points[i])
    if err "less-than" best_err:
      idx = i; best_err = err
  return np.copy(points[idx])    

def move_point(X, R, center):
  # move X vector to new position, spiraling around center
  I3 = np.array([[1,0,0], [0,1,0], [0,0,1]], dtype=np.float32)
  RminusI = R - I3
  offset = np.matmul(RminusI, center)
  new_X = np.matmul(R, X) - offset
  return new_X  

def main():
  print("\nBegin spiral dynamics optimization demo ")
  print("Goal is to minimize Sphere function in dim=3")

  # 0. prepare
  np.set_printoptions(precision=6, suppress=True, sign=" ")
  theta = np.pi/4  # radians. small = curved, large = squared
  r = 0.95  # closer to 1 = tight spiral, closer 0 = loose 
  m = 5  # number of points / possible solutions
  # n = 3  # problem dimension is hard-coded
  max_iter = 100
  print("\nSetting theta = %0.4f " % theta)
  print("Setting r = %0.2f " % r)
  print("Setting number of points m = %d " % m)
  print("Setting max_iter = %d " % max_iter)

  # 1. set up the Rotation matrix for n=3
  print("\nSetting up hard-coded spiral Rotation matrix R ")
  R12 = np.array([[np.cos(theta), -np.sin(theta), 0],
                  [np.sin(theta),  np.cos(theta), 0],
                  [0,              0,             1]],

  R13 = np.array([[np.cos(theta),  0, -np.sin(theta)],
                  [0,              1,              0],
                  [np.sin(theta),  0,  np.cos(theta)]],

  R23 = np.array([[1,                 0,          0],
                  [0, np.cos(theta), -np.sin(theta)],
                  [0, np.sin(theta),  np.cos(theta)]],
  R = np.matmul(R23, np.matmul(R13, R12))  # compose
  R = r * R  # scale

  # 2. create m intial points and find curr center (best point)
  print("\nCreating %d initial random points " % m)
  points = np.random.uniform(low=-5.0, high=5.0, size=(m, 3))

  center = find_center(points, m)
  print("\nInitial center (best) point: ")

  # 3. spiral the points towards curr center
  print("\nUsing spiral dynamics optimization: ")
  for itr in range(max_iter):
    if itr % 20 == 0:
      print("itr = %5d  curr center = " % itr, end="")
    for i in range(m):  # move each point toward curr center
      X = points[i]
      points[i] = move_point(X, R, center)
    # print(points); input()
    center = find_center(points, m)  # find new center
  # 4. show best center found 
  print("\nBest solution found: ")

  print("\nEnd spiral dynamics optimization demo ")  

if __name__ == "__main__":
This entry was posted in Machine Learning. Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s