背景
所有的随机优化算法(GA、ABC、PSO、STA、模拟退火)都是一个套路
- 通过当前的一个解或者一些产生一堆新的候选解,这一步叫产生候选解
- 然后通过某个评价函数(评价标准)更新解,就是找一堆里面好的一个或者一些,这叫更新当前解
- 不断循环,直到满足终止条件
可以先看看 连续状态转移算法(STA)的实现(python版)
DSTA主要涉及替换、交换、平移、对称这四个算子,大概如下:

替换算子

交换算子

平移算子

对称变换

文件结构

代码
otherlib.py
import numpy as np
def f1(x):
Q = np.array([
[4, -2, -3, 0, 1, 4, 5, -2],
[-2, -4, 0, 0, 2, 2, 0, 0],
[-3, 0, 8, -2, 0, 3, 4, 0],
[0, 0, -2, -4, 4, 4, 0, 1],
[1, 2, 0, 4, 100, 2, 0, -2],
[4, 2, 3, 4, 2, 100, 1, 0],
[5, 0, 4, 0, 0, 1, 200, 4],
[-3, 0, 0, 1, -2, 0, 4, 10],
])
C_T = np.array([-4, 1, -8, 3, -100, -10, -20, 0])
result = 0.5 * (x @ Q @ x.T) + (C_T @ x.T)
return result
def f2(x):
Q = np.array([[-1, -2, 2, 8, -5, 1, -4, 0, 0, 8],
[-2, 2, 0, -5, 4, -4, -4, -5, 0, -5],
[2, 0, 2, -3, 7, 0, -3, 7, 5, 0],
[8, -5, -3, -1, -3, -1, 7, 1, 7, 2],
[-5, 4, 7, -3, 1, 0, -4, 2, 4, -2],
[1, -4, 0, -1, 0, 1, 9, 5, 2, 0],
[-4, -4, -3, 7, -4, 9, 3, 1, 2, 0],
[0, -5, 7, 1, 2, 5, 1, 0, -3, -2],
[0, 0, 5, 7, 4, 2, 2, -3, 2, 3],
[8, -5, 0, 2, -2, 0, 0, -2, 3, 3]])
result = x @ Q @ x.T
return result
def f3(x):
Q = np.array([[-3, 7, 0, -5, 1, 1, 0, 2, -1, -1, -9, 3, 5, 0, 0, 1, 7, -7, -4, -6],
[7, 0, -5, 1, 1, 0, 2, -1, -1, -9, 3, 5, 0, 0, 1, 7, -7, -4, -6, -3],
[0, -5, 1, 1, 0, 2, -1, -1, -9, 3, 5, 0, 0, 1, 7, -7, -4, -6, -3, 7],
[-5, 1, 1, 0, 2, -1, -1, -9, 3, 5, 0, 0, 1, 7, -7, -4, -6, -3, 7, 0],
[1, 1, 0, 2, -1, -1, -9, 3, 5, 0, 0, 1, 7, -7, -4, -6, -3, 7, 0, -5],
[1, 0, 2, -1, -1, -9, 3, 5, 0, 0, 1, 7, -7, -4, -6, -3, 7, 0, -5, 1],
[0, 2, -1, -1, -9, 3, 5, 0, 0, 1, 7, -7, -4, -6, -3, 7, 0, -5, 1, 1],
[2, -1, -1, -9, 3, 5, 0, 0, 1, 7, -7, -4, -6, -3, 7, 0, -5, 1, 1, 0],
[-1, -1, -9, 3, 5, 0, 0, 1, 7, -7, -4, -6, -3, 7, 0, -5, 1, 1, 0, 2],
[-1, -9, 3, 5, 0, 0, 1, 7, -7, -4, -6, -3, 7, 0, -5, 1, 1, 0, 2, 1],
[-9, 3, 5, 0, 0, 1, 7, -7, -4, -6, -3, 7, 0, -5, 1, 1, 0, 2, 1, 2],
[3, 5, 0, 0, 1, 7, -7, -4, -6, -3, 7, 0, -5, 1, 1, 0, 2, 1, 2, 3],
[5, 0, 0, 1, 7, -7, -4, -6, -3, 7, 0, -5, 1, 1, 0, 2, 1, 2, 3, 9],
[0, 0, 1, 7, -7, -4, -6, -3, 7, 0, -5, 1, 1, 0, 2, 1, 2, 3, 9, 4],
[0, 1, 7, -7, -4, -6, -3, 7, 0, -5, 1, 1, 0, 2, 1, 2, 3, 9, 4, -1],
[1, 7, -7, -4, -6, -3, 7, 0, -5, 1, 1, 0, 2, 1, 2, 3, 9, 4, -1, -3],
[7, -7, -4, -6, -3, 7, 0, -5, 1, 1, 0, 2, 1, 2, 3, 9, 4, -1, -3, 9],
[-7, -4, -6, -3, 7, 0, -5, 1, 1, 0, 2, 1, 2, 3, 9, 4, -1, -3, 9, 7],
[-4, -6, -3, 7, 0, -5, 1, 1, 0, 2, 1, 2, 3, 9, 4, -1, -3, 9, 7, -9],
[-6, -3, 7, 0, -5, 1, 1, 0, 2, 1, 2, 3, 9, 4, -1, -3, 9, 7, -9, 8]])
C_T = np.array([-5, 2, -1, -3, 5, 4, -1, 0, 9, 4, 7, -4, 3, 5, 8, -1, 1, 5, -6, 9])
result = (x @ Q @ x.T) + (C_T @ x.T)
return result
if __name__ == "__main__":
x = np.random.randint(0, 99, 20)
a = f3(x)
print(a)
DSAT.py
import numpy as np
class DSTA():
def __init__(self,fun,Range,SE,MaxIter):
self.fun = fun
self.Range = Range
self.SE = SE
self.MaxIter = MaxIter
self.Dim = self.Range.shape[1]
def initialization(self):
self.Best = np.random.randint(self.Range[0,0],self.Range[1,0],self.Dim)
self.fBest = self.fun(self.Best)
self.history = []
self.history.append(self.fBest)
def op_swap(self):
State = np.zeros((self.SE,self.Dim),dtype = int)
for i in range(self.SE):
temp = self.Best.copy()
R = np.random.permutation(self.Dim)
a = R[0]
b = R[1]
temp[b],temp[a] = temp[a],temp[b]
State[i,:] = temp
return State
def op_substitute(self):
State = np.zeros((self.SE, self.Dim), dtype=int)
for i in range(self.SE):
temp = self.Best.copy()
index = np.random.randint(0, self.Dim)
temp[index] = np.random.randint(self.Range[0,index], self.Range[1,index]+1)
State[i, :] = temp
return State
def op_symmetry(self):
State = np.zeros((self.SE,self.Dim),dtype = int)
for i in range(self.SE):
temp = self.Best.copy()
R = np.random.permutation(self.Dim)
a = R[0]
b = R[1]
if a < b:
temp[list(range(a,b+1))] = temp[list(range(b,a-1,-1))]
else:
temp[list(range(b,a+1))] = temp[list(range(a,b-1,-1))]
State[i,:] = temp
return State
def op_shift(self):
State = np.zeros((self.SE,self.Dim),dtype = int)
for i in range(self.SE):
temp = self.Best.copy()
R = np.random.permutation(self.Dim)
a = R[0]
b = R[1]
if a < b:
temp[a:b],temp[b] = temp[a+1:b+1],temp[a]
else:
temp[b:a],temp[a] = temp[b+1:a+1],temp[b]
State[i,:] = temp
return State
def selection(self,State):
fState = np.zeros((self.SE,1))
for i in range(self.SE):
fState[i] = self.fun(State[i,:])
index_newBest = np.argmin(fState)
newBest = State[index_newBest,:]
fnewBest = fState[index_newBest,:]
if fnewBest < self.fBest:
self.Best = newBest
self.fBest = fnewBest
def run(self):
self.initialization()
for i in range(self.MaxIter):
State = self.op_swap()
self.selection(State)
State = self.op_substitute()
self.selection(State)
State = self.op_shift()
self.selection(State)
State = self.op_symmetry()
self.selection(State)
self.history.append(self.fBest[0])
"""让算法提前停止,如果连续100次都变化不明显"""
if i>100 and (abs(self.history[i] - self.history[i-100]) < 1e-10):
break
Test.py
from DSTA import DSTA
from otherlib import f1,f2,f3
import numpy as np
import matplotlib.pyplot as plt
SE = 30
MaxIter = 500
fun = f3
Dim = 20
Range = np.repeat([0,99],Dim).reshape(-1,Dim)
dsta = DSTA(fun,Range,SE,MaxIter)
dsta.run()
print(dsta.fBest)
plt.plot(dsta.history)
plt.show()
结果
效果挺好的三个测试函数只有最后一个不是每次都能找到最优,最有一个的局部最优太多了没办法,三个测试函数的信息可以在这篇论文里面找到。名字是 Discrete state transition algorithm for unconstrained integer optimization problems
,三个函数的最优值我截个图,有些同学可能不知道咋找论文

第三个函数的结果 -1439658
,运行了两三次的样子,就找到了最优点,其他两个函数请自行实验

后记,补一个四种算子的好看点的图
前面的图都是写书的时候没想到用彩色,我用二值的离散状态转移算法的彩色图显示下,二值的和离散的唯一区别就是二值的每个位置只能取(0 or 1),离散的可以取任意整数。
