Lishengxie

启发式优化算法学习-模拟退火

算法学习 Lishengxie

模拟退火算法(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

Related Posts