18. AI using Python- Tabu Search Example (MST) by Sunil Sir

Heuristic Search Algorithms
1. Tabu Search
2. Minimum Spanning Tree with Constraints
3. Analysis of Tabu Search

-------
Def MOVEGEN(N)
Succ ={}
Succ= Succ U {Children of N}
Return Succ

Def APPEND(L1, L2)
New_list = L1 + L2
Return New_List

Def FITNESS(Node)
Score = f(Node), a function to calculate the score of a ‘Node’ if the aspiration criteria is satisfied
Return Score

Def ASP(TabuList)
For each Node in TabuList do
if Node in TabuList gives better solution than the current best solution or if TT of Node has reached to ‘0’ then return all such Nodes.

Def Tabu_Search(Start)
bestSolution={Start}
N=Start //Current Best Solution
CLOSED={N} //Tabu List
TabuListSize=Max
TT=t
While (not Terminating – Condition) do
CHILD={ MOVEGEN(N)}
CHILD={CHILD – CLOSED}
CHILD= APPEND(CHILD + ASP(CLOSED))
N = Pick front node from CHILD;
CHILD={CHILD – N }
for each Neighbor in CHILD do
if (FITNESS (Neighbor) GREATER-THAN= FITNESS(N) )then
N= Neighbor
end if
end for
if (FITNESS(N) GREATER-THAN= FITNESS(bestSolution) )then
bestSolution=N
end if
CLOSED = APPPEND(N,CLOSED)
if (Size(CLOSED) GREATER-THAN TabuListSize) then
remove nodes from CLOSED
end if
End while
Return bestSolution
------
ANALYSIS:

1. Completeness: The Tabu Search guarantee the solution if it exists, so it is complete.
2. Optimality: The solution given by Tabu Search is also low cost or optimal solution.
3. Time Complexity: The algorithm has high complexity as it allows the reuse of nodes in CLOSED list.
4. Space Complexity: The space complexity is significantly more as CLOSED list has to preserve the Tabu nodes in it.