禁忌搜索算法

发表于 | 更新于 | 分类于

   本文将介绍禁忌搜索算法的一些基本概念、算法流程以及算法的ython实现。（注：本文由有何不可原创，如若转载，请注明文章出处！）

1. 基本思想

   禁忌搜索算法的思想最早由美国工程院院士Glover教授于1986年提出，并在1989年和1990年对该方法做出了进一步的定义和发展。
   为了克服局部邻域搜索算法容易陷入局部最优的不足，在禁忌搜搜算法中引入了“禁忌表”，该表用于记录已经搜索过的最优点。在下一次的搜索中，则不再或有选择的搜索该点。
   禁忌搜索算法是对局部邻域搜索算法的一种扩展，是一种全局邻域搜索算法。在局部邻域搜索算法的基础上，禁忌搜索算法引入“禁忌表”来禁止重复 搜索，并通过藐视准则来释放一些被禁止的对象，从而保证了多样化的搜索，最终实现全局优化。
   禁忌搜索算法，由于引入“禁忌表“，则具有了同人类一样的”记忆“的功能，用”记忆“来指导算法的搜索过程。对已经搜索过的地方，不再立即去搜索，转而去搜索其它地方，若在其它最终没有找到，则再去搜索过的地方进行搜索。

2. 算法中涉及的一些概念

  1. 初始解
  2. 候选解
  3. 领域结构
  4. 禁忌表（禁忌准则）
  5. 禁忌对象
  6. 禁忌长度
  7. 藐视准则
  8. 搜索策略
  9. 终止准则

3. 算法流程

  1. 初始化参数，并随机产生初始解和给定一种邻域结构；
       默认初始解为当前解和最优解，并更新禁忌表。
  2. 根据给定的邻域结构，由当前解随机产生指定数量的候选解；
  3. 判断候选解是否在禁忌表中；
      1). 候选解全都在禁忌表中，选择候选解中最优的解作为当前解和最优解。然后，将当前解与最优解进行比较，以决定是否更新最优解。最后，跳转到步骤 4）。
      2). 候选解部分在禁忌表中，判断候选解中是否存在最优解；
       a). 存在最优解，判断最优解是否在禁忌表中（禁忌表的操作不同同而已）；直接令最优的候选解作为当前解，并更新最优解。然后，跳转到步骤 4）。
       b). 不存在最优解，选取不在禁忌表中的最优的候选解，将其与当前解进行比较，以决定是否更新当前解。若更新当前解，则将当前解与最优解进行比较，以决定是否更新最优解。然后，跳转到步骤4）。
      3). 候选解全不在禁忌表中
        将候选解与当前解进行比较，以决定是否更新当前解。若更新当前解，则将当前解与最优解进行比较，以决定是否更新最优解。然后，跳转到步骤4）。
  4. 更新禁忌表;
  5. 判断是否达到迭代次数，若没有达到，则跳转到步骤 2）。否则，直接输出结果。

4. 代码示例 – Python

本文以两个自变量为例，通过计算一个指定函数的最小值，实现TS算法。

1
2
3
4
# Import the libs
import numpy as np
import matplotlib.pyplot as plt
import random as rd
1
2
MIN_VAL = [-5.0, -5.0]            # The minmum limit of variable
MAX_VAL = [5.0, 5.0]              # The maxxmum limit of variable
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
# TS
class TS():
    """
        TS class
    """

    def __init__(self,vcount=2,ccount=20,tabuL=25,iters=200,tabu_objs=10):
        """
            Initiate the parameters of TS
            -----------------------------
            Parameter:
                vcount    : The number of variables
                ccount    : The number of candidate solutions
                tabuL     : Tabu length(tenure)
                iters     : Number of iterations
                tabu_objs : Number of tabu objects
        """

        self.vcount = vcount                                    # The number of variables.
        self.ccount = ccount                                    # The number of candidate solutions.
        self.iters = iters                                      # Number of iterations, as the end rule.
        self.tabu_objs = tabu_objs 
        self.tabu_list = [None]*self.tabu_objs                  # Tabu list, used to store the tabu object.
        self.tabu_len = tabuL                                   # Tabu length.
        self.tabu_len_list = np.array([0]*self.tabu_objs)       # Tabu length list, Corresponds to the Tabu list.
        self.cur_solu = np.array([0.0]*self.vcount)             # The current solution.
        self.best_solu = np.array([0.0]*self.vcount)            # The best solution.
        self.trace = []                                         # Record the route of best solution.
        
    def valuate(self, x):
        """
            valuation function
            ------------------
            The valuation function as the rule of contempt is usually the objective function.
            ------------------
            Parameter:
                x : The solution of the valuation function.
        """

        # Objective function
        value = 5*np.cos(x[0]*x[1])+x[0]*x[1]+x[1]**3
        # Return value
        return value

    def update_Tabu(self, mode, index=None, solu=None):
        """
            upadte_Tabu function
            --------------------
            This function is used to update the tabu list and the tenure of tabu object.
            --------------------
            Parameter:
                mode  :
                index :
                solu  :
        """
        
        indices = []                               # Store the index the value, which is equal to zero.
        # Update the tenure of tabu object.
        for i in range(len(self.tabu_len_list)):   
            if self.tabu_len_list[i] != 0:
                self.tabu_len_list[i] -= 1         
        # The ralease mode
        if mode == 'release':
            self.sequence_Tabu(index)                 
        # The add mode
        elif mode == 'add':
            tabuObj = self.valuate(solu) 
            if self.tabu_list[0] == None:
                self.sequence_Tabu(0)
            self.tabu_list[len(self.tabu_list)-1] = tabuObj
            self.tabu_len_list[len(self.tabu_list)-1] = self.tabu_len
        # Update the tabu list depending on the content of the tabu_list_list.
        for i in range(len(self.tabu_len_list)):
            if self.tabu_len_list[i] == 0:
                indices.append(i)
        if len(indices) == 1:
            self.sequence_Tabu(indices[0])
        elif len(indices) > 1:
            # Part 1
            maxindex = max(indices)                # Maximum index
            self.sequence_Tabu(maxindex)
            # Part 2
            for i in indices:
                if i != max(indices):
                    self.tabu_list[i] = None       # Set the tabu object as None.
                    self.tabu_len_list[i] = 0      # Set the tenure of tabu object as zero.
            objs = []
            objs1 = []
            for obj in self.tabu_list[:maxindex]:
                if obj != None:
                    objs.append(obj)
            for obj in self.tabu_len_list[:maxindex]:
                if obj != 0:
                    objs1.append(obj)
            if objs != []:
                for i in range(len(objs)):
                    self.tabu_list[maxindex-i-1] = objs[i]
                    self.tabu_len_list[maxindex-i-1] = objs1[i]
                for i in range(maxindex-len(objs)):
                    self.tabu_list[i] = None
                    self.tabu_len_list[i] = 0
            else:
                for i in range(maxindex):
                    self.tabu_list[i] = None
                    self.tabu_len_list[i] = 0
            
    def sequence_Tabu(self, index):
        """
            sequence_Tabu function
            ----------------------
            Parameter:
                index : The index of the tabu object to be deleted.
        """
        
        if index != len(self.tabu_list)-1:
            for i in range(len(self.tabu_list)-1-index):
                self.tabu_list[index+i] =  self.tabu_list[index+i+1]
                self.tabu_len_list[index+i] = self.tabu_len_list[index+i+1]
            self.tabu_list[len(self.tabu_list)-1] = None
            self.tabu_len_list[len(self.tabu_list)-1] = 0

    def run(self):
        """
            run function
            ------------
            Execute the TS algorithm.
        """

        # Produce the initial solution and set the best soluiton.
        for i in range(self.vcount):
            self.cur_solu[i] = rd.uniform(-2,2)
            self.best_solu[i] = self.cur_solu[i]
        # Update the tabu list and the tenure of tabu object.
        self.update_Tabu('add', solu=self.cur_solu)
        # Iteration
        counter = 0                                             # The counter of iteration      
        while counter < self.iters:
            counter += 1                                        # The counter add 1 when finishs a loop.
            candi_solu = np.zeros((self.ccount, self.vcount))   # Store the candidate solutions.
            # Select some candidate solutions from the near area of the current solution.
            for i in range(self.ccount):
                for j in range(self.vcount):
                    candi_solu[i,j] = self.cur_solu[j] + rd.uniform(-1, 1)
            # Identify whether the candidate solutions are kept in the limited area.
            for i in range(self.vcount):
                for j in range(self.ccount):
                    if candi_solu[j,i] > MAX_VAL[i]:
                        candi_solu[j,i] = MAX_VAL[i]
                    elif candi_solu[j,i] < MIN_VAL[i]:
                        candi_solu[j,i] = MIN_VAL[i]
            isAll = False                                       # A sign of all solutions kept in tabu list.
            isPart = False                                      # A sign of a part of solutions kept in tabu list.
            count = [0]*self.ccount
            for i in range(self.ccount):
                for k in range(len(self.tabu_list)):
                    if self.valuate(candi_solu[i]) == self.tabu_list[k]:
                        count[i] = 1
            temp = 0
            for i in count:
                if i == 1:
                    temp += 1
            if temp == self.ccount:
                isAll = True
            elif temp < self.ccount and temp > 0:
                isPart = True
                
            if isAll == True:
                ############################################
                #    Part1 : All solutions in Tabu list.   #
                ############################################
                temp_tabu_list = []
                for tabuObj in self.tabu_list:
                    if tabuObj != None:
                        temp_tabu_list.append(tabuObj)
                index = np.argmin(np.array(temp_tabu_list))         # Obtain the index of minimum value from the tabu list
                temp_solu = np.array([0.0]*self.vcount)
                for solu in candi_solu:
                    if self.valuate(solu) == self.tabu_list[index]:
                        temp_solu = solu
                # Update the current solution.
                self.cur_solu = temp_solu
                # Update the best solution according to the valuate function and requirements.
                if self.valuate(self.cur_solu) < self.valuate(self.best_solu):
                    self.best_solu = self.cur_solu           
                # Update the tabu list and the tenure of tabu object.
                self.update_Tabu('release',index=index)
                
            elif isPart == True:
                ##################################################
                #    Part2 : A part of solutions in Tabu list.   #
                ##################################################
                isExistbest = False
                temp_bsolu = []
                bsolu = np.array([0.0]*self.vcount)
                for solu in candi_solu:
                    if self.valuate(solu) < self.valuate(self.best_solu):
                        isExistbest = True
                        temp_bsolu.append(solu)
                if isExistbest == True:
                    ###################################################################
                    #    Part2.1 : Exist the best solution in  candidate solutions.   #
                    #              Some of these exist in tabu list.                  #
                    ###################################################################
                    isInTabu = False
                    index = 0
                    #
                    if len(temp_bsolu) == 1:
                        bsolu = temp_bsolu[0]
                    elif len(temp_bsolu) != 1 and len(temp_bsolu) != 0:
                        bsolu = temp_bsolu[0]
                        for solu in temp_bsolu[1:]:
                            if self.valuate(solu) < self.valuate(bsolu):
                                bsolu = solu
                    #
                    for i in range(len(self.tabu_list)):
                        if self.valuate(bsolu) == self.tabu_list[i]:
                            isInTabu = True
                            index = i
                    # Update the current solution.
                    self.cur_solu = bsolu
                    # Update the best solution.
                    if self.valuate(bsolu) < self.valuate(self.best_solu):
                        self.best_solu = bsolu
                    # 
                    if isInTabu == True:
                        # Update the tabu list and the tenure of tabu object.
                        self.update_Tabu('release', index=index)
                    else:
                        index = len(self.tabu_list)-1
                        # Update the tabu list and the tenure of tabu object.
                        self.update_Tabu(index, 'add', solu=self.cur_solu)
                else:
                    #################################################################
                    #    Part2.2 : None the best solution in candidate solutions.   #
                    #              None solutions exist in tabu list.               #
                    #################################################################
                    notInTabu = []
                    for solu in candi_solu:
                        count = 0
                        for i in range(len(self.tabu_list)):
                            if self.valuate(solu) != self.tabu_list[i]:
                                count += 1
                        if count == len(self.tabu_list):
                            notInTabu.append(solu)
                    temp_solu = notInTabu[0]
                    if len(notInTabu) != 1:
                        for solu in notInTabu[1:]:
                            if self.valuate(solu) < self.valuate(temp_solu):
                                temp_solu = solu
                    # Update the current solution according to the valuate function and requirements.
                    if self.valuate(temp_solu) < self.valuate(self.cur_solu):
                        self.cur_solu = temp_solu
                        # Update the tabu list and the tenure of tabu object.
                        self.update_Tabu('add', index=len(self.tabu_list)-1, solu=self.cur_solu) 
                        # Update the best solution according to the valuate function and requirements.
                        if self.valuate(self.cur_solu) < self.valuate(self.best_solu):
                            self.best_solu = self.cur_solu
                
            else:
                #############################################
                #    Part3 : None solutions in tabu list.   #
                #############################################
                bcandi_solu = candi_solu[0]
                for solu in candi_solu[1:]:
                    if self.valuate(solu) < self.valuate(bcandi_solu):
                        bcandi_solu = solu
                # Update the current solution according to the valuate function and requirements.
                if self.valuate(bcandi_solu) < self.valuate(self.cur_solu):                    
                    self.cur_solu = bcandi_solu                    
                    # Update the tabu list and the tenure of tabu object.
                    self.update_Tabu('add', index=len(self.tabu_list)-1, solu=self.cur_solu)
                    # Update the best solution according to the valuate function and requirements.
                    if self.valuate(self.cur_solu) < self.valuate(self.best_solu):
                        self.best_solu = self.cur_solu                                                
                
            # Add the best solution to the trace list
            self.trace.append(self.valuate(self.best_solu))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# main
def main():
    """
        main function
    """

    ts = TS(iters=200)
    ts.run()
    print('最优解:', ts.best_solu)
    print('最小值', ts.valuate(ts.best_solu))

    plt.plot(ts.trace, 'r')
    title = 'TS: ' + str(ts.valuate(ts.best_solu))
    plt.title(title)
    plt.xlabel("Number of iterations")
    plt.ylabel("Function values")
    plt.show()

5. 代码链接

   具体代码参见Github

有何不可 wechat
Subscribe to my blog by scanning my wechat account~
书山有路勤为径，学海无涯苦作舟~