Spiral Dynamics Optimization in 3D

I’m slowly but surely dissecting the ideas in a 2011 research paper titled “Spiral Dynamics Inspired Optimization” by K. Tamura and K. Yasuda. The idea of SDI optimization is an algorithm to find the minimum value of some function using a geometric technique, rather than a technique based on Calculus gradients. SDI optimization is similar in some respects to particle swarm optimization (SPO) and Nelder-Mead optimization (also known as amoeba method).

My most recent experiment is best explained by this image of a demo program:

The problem is set up in 3 dimensions. The starting point is at (10, 10, 10) and the goal of the demo is to iterate so that each succeeding point gets closer to the center point of (0, 0, 0) by moving in a spiral.

The ideas aren’t terribly complicated, but they’re difficult to explain. In a 2D scenario if you have a point (x,y), you can move in a spiral by multiplying the point by a fraction (like 0.95) of the matrix R12 =

cos(theta)  -sin(theta)
sin(theta)   cos(theta)

Here theta is an angle in radians, typically like pi/4.

In 3D you can look at each pair of the dimensions and compute three R matrices:

R12 =
cos(theta)  -sin(theta)   0
sin(theta)   cos(theta)   0
0            0            1

R13 =
cos(theta)   0           -sin(theta)
0            1            0
sin(theta)   0            cos(theta)

R23 =
1            0            0
0            cos(theta)  -sin(theta)
0            sin(theta)   cos(theta)

Here R12 means in the 1st and 2nd plane, or x-y plane. R13 is the x-z plne and R23 is the y-z plane.

If you multiply a 3D point (x,y,z) by any one of the three matrices, you will spiral in the associated plane. But if you compose the three matrices like R = R23 * R13 * R12, you will get a matrix that will spiral in 3D. Quite tricky.

Spiraling in 3D sets up the core of an optimiztion technique where you can minimize some function of three variables. Briefly, you set up several random, possible solutions. Each initial possible solution looks something like (13.0, 14.5, 11.7). From the collection of possible solutions, you select the current best solution and use it as the spiral center. Then you spiral all possible solutions towards the current center. Then you compute a new center, and continue.

As you iterate you explore possible solutions in a principled way and will eventually find a good (but not necessarily best) solution.

The next task on my list of things to understand is to extend the spiral mechanism to 4 or more dimensions. I have a lot more work to do before I get a working end-to-end spiral optimization demo working, but I’m confident I’ll get there eventaully.

Some of the most memorable women in old science fiction movies have spiral inspired hair styles. Left: Princess Achen played by Zeta Graff in “The Fifth Element” (1997). Left Center: Dame Vaako played by Thandie Newton in “The Chronicles of Riddick” (2004). Right Center: Queen Amidala played by Natalie Portman in “Star Wars the Phantom Menace” (1999). Right: Lady Jessica played by Francesca Annis in “Dune” (1984).

Code below.

# spirals.py
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

print("\nBegin 3D spiral rotation demo ")

np.set_printoptions(precision=3, suppress=True)
theta = np.pi/4  # in radians. small = curved, large = squared
r = 0.95  # closer to 1 = tight spiral, closer 0 = loose 

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)]],
R12 = r * R12; R13 = r * R13; R23 = r * R23


R = np.matmul(R23, np.matmul(R13, R12))  # compose

X = np.array([10.0, 10.0, 10.0], dtype=np.float32)  # 1x3
X = X.T  # 3x1 column vector, starting point

xd = []; yd = []; zd = []  # for plotting

for k in range(7):
  xd.append(X[0]); yd.append(X[1]); zd.append(X[2])
  print("k = " + str(k) + "   X = ", end="")
  X = np.matmul(R, X)

fig = plt.figure()
ax = fig.add_subplot(projection='3d')
ax.set_xlim3d(-14, 14)
ax.set_ylim3d(-10, 10)
ax.set_zlim3d(-14, 14)

for i in range(len(xd)):
  ax.scatter(xd[i], yd[i], zd[i], c='red')
  ax.text(xd[i], yd[i], zd[i], '. k=%s' % (str(i)), size=10, \
    zorder=1, color='k')

ax.scatter(0,0,0, c='green')
ax.text(0,0,0, '. %s' % 'center', size=8, zorder=1, color='k') 




print("\nEnd demo ")
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