模拟退火算法(SA)
参考教程 https://blog.csdn.net/brilliantZC/article/details/124436967
模拟退火算法（Simulated Annealing，SA）是一种模拟物理退火过程而设计的优化算法。模拟退火算法采用类似于物理退火的过程。先在一个高温状态下（算法初始化随机解），然后逐渐退火，在每个温度下慢慢冷却，最终达到物理基态（相当于算法找到最优解）。模拟退火算法采用Metropolis准则，并用一组称为冷却进度表的参数控制算法的进程，使得算法在多项式时间里可以给出一个近似最优解。
SA算法运行流程
step1: 设定当前解（即为当前的最优解)：令\(T =T_0\)，即开始退火的初始温度，随机生成一个初始解\(x_0\)，并计算相应的目标函数值\(E(x_0)\)。 step2: 产生新解与当前解差值：根据当前解\(x_i\)进行扰动，产生一个新解\(x_j\)，计算相应的目标函数值\(E(x_j)\)，得到\(\Delta E = E(x_j)-E(x_i)\)。 step3: 判断新解是否被接受 ：若\(\Delta E< 0\)，则新解\(x_j\)被接受；若\(\Delta E> 0 \)，则新解\(x_j\)按概率\(e^{\frac{-(E(x_j)-E(x_i))}{T_i}}\)被接受，\(T_i\)为当前温度。 step4: 当新解被确定接受时，新解\(x_j\)被作为当前解。 step5: 循环以上四个步骤：在温度\(T_i\)下，重复\(k\)次的扰动和接受过程，接着执行下一步骤。 step6: 最后找到全局最优解：判断\(T\)是否已经达到终止温度\(T_f\)，是，则终止算法；否，则转到循环步骤继续执行。
SA算法求解映射问题
映射问题本质上可以看作一个序列的排序问题，使用SA算法求解时，需要关注的是如何产生新解，这里我们采用如下的方法：再序列中随机选取两个不重合的位置，将这两个位置中间的序列反转达到局部扰动的目的。
SA算法求解映射问题代码
# -*- coding: utf-8 -*-
# Lishengxie
# 2023-02-23
# Implementation of a Simulated Annealing algorithm for crossbar mapping/placing
# 参考链接: https://blog.csdn.net/weixin_58427214/article/details/125901431
# 参考链接: https://blog.csdn.net/brilliantZC/article/details/124436967
import numpy as np
import copy
import sys
import random
class SAPlacer:
"""
SA algorithm
-------------
Class used to find the mapping from computing cores to routers on NoC which minizes the communication cost
"""
def __init__(self, dim_x, dim_y, spike_table, L=200, K=0.95, S=0.04, T=100, T_threshold=0.01):
"""
Initialization of PsoPlacer.
Args:
dim_x: int, the `x` dimension on NoC
dim_y: int, the `y` dimension on NoC
spike_table: 2D-array, the number of spikes between core `i` and core `j`
L: int, 每个温度下的迭代次数
K: float, 温度的衰减参数, T = K*T
S: float, 步长因子
T: float, 初始温度
T_threshold: float, 终止温度
"""
self.dim_x = dim_x
self.dim_y = dim_y
self.dim_size = dim_x * dim_y
self.L = L
self.K = K
self.S = S
self.T = T
self.T_threshold = T_threshold
if spike_table is not None:
self.init_solution(spike_table)
def init_solution(self, spike_table):
"""
Init spike table, hop distance table and solution.
"""
# init spike table
self.spike_table = np.zeros((self.dim_size, self.dim_size))
h, w = spike_table.shape
for i in range(h):
for j in range(w):
self.spike_table[i,j] = spike_table[i,j]
# init hop distance table
self.hop_xy()
# init solution
self.pre_x = np.arange(self.dim_size)
np.random.shuffle(self.pre_x)
self.pre_bestx = self.pre_x
self.pre_x = np.arange(self.dim_size)
np.random.shuffle(self.pre_x)
self.prex_cost = self.fitnessFuntcion(self.pre_x)
self.bestx = self.pre_x
self.bestx_cost = self.fitnessFuntcion(self.bestx)
def hop_xy(self):
"""
The hop distance between router `x` and `y` in the 2D-Mesh NoC using XY routing
"""
self.hop_dist = np.zeros((self.dim_size, self.dim_size))
for i in range(self.dim_size):
for j in range(self.dim_size):
self.hop_dist[i,j] = abs(i % self.dim_x - j % self.dim_x) \
+ abs(i // self.dim_x - j // self.dim_x)
def fitnessFuntcion(self, solution):
"""
Compute the communication cost for each mapping solution
Args:
solution: List, a possible mapping solution
"""
cost = 0
for i in range(self.dim_size):
for j in range(self.dim_size):
cost += self.spike_table[i,j] * self.hop_dist[solution[i], solution[j]]
return cost
def place(self):
"""
Execute the Simulated Annealing algorithm
"""
P = 0
next_x = np.arange(self.dim_size)
np.random.shuffle(next_x)
nextx_cost = self.fitnessFuntcion(next_x)
while (self.T > self.T_threshold):
self.T = self.K * self.T # 降温
# 当前温度T下迭代次数
for i in range(self.L):
# ====在此点附近随机选下一点=====
# 选择两个随机位置, 将两个位置之间的数组进行翻转
positions = np.random.choice(list(range(self.dim_size)), replace=False, size=2)
x = min(positions[0], positions[1])
y = max(positions[0], positions[1])
mid_reversed = next_x[x:y+1][::-1]
next_x[x:y+1] = mid_reversed
if random.random() <= 0.0001:
np.random.shuffle(next_x)
nextx_cost = self.fitnessFuntcion(next_x)
if nextx_cost < self.bestx_cost:
self.pre_bestx = self.bestx
self.bestx = next_x
self.bestx_cost = nextx_cost
if nextx_cost < self.prex_cost:
self.pre_x = next_x
self.prex_cost = nextx_cost
P = P + 1
else:
changer = -1 * (nextx_cost - self.prex_cost) / self.T
p1 = np.exp(changer)
if p1 > np.random.random():
self.pre_x = next_x
self.prex_cost = nextx_cost
P = P + 1
print("Current T: {:.7f}, best cost: {}".format(self.T, self.bestx_cost))
return self.bestx