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) 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()