## 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=" ")
np.random.seed(0)
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]],
dtype=np.float32)

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

R23 = np.array([[1,                 0,          0],
[0, np.cos(theta), -np.sin(theta)],
[0, np.sin(theta),  np.cos(theta)]],
dtype=np.float32)

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: ")
print(center)

# 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="")
print(center)
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(center)

print("\nEnd spiral dynamics optimization demo ")

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