tabusearch.rar_禁忌 遗传_禁忌算法_禁忌遗传_禁忌遗传算法_遗传禁忌搜索

% This program should only be used after the geneticalgorithm program has % been used to design a network connecting a set of points in a % geographical area. % This program uses the Tabu Search algorithm to find the best locations % for servers in a network. Each solution locates the servers at the % specified set of nodes. The cost of each solution consists of the % installation cost of the necessary processing power and a cost for the % bandwidth used to move the packets back and forth within the network. It % is assumed that the packets are sent to the nearest server node for % processing tabuloop = 1500; % This is the number of times we cycle through the tabu process listlength = 1000; % This is the number of former best solutions we keep in the list processweight = 3; % This is the weight we use to multiply the processing load startvalue = 1; % This is the value assigned to each node for the starting solution. It must be 0 or 1 % Initialise the tabu list for i = 1: listlength for j = 1: N tabulist (i, j) = 0; end end % The first step is to convert the output of the network designed in the % geneticalgorithm program for use here. for m = 1: N for n = 1: N network (m, n) = 0; end end for j = 1: k if solution (1,j) ==1 m = links (j,2); n = links (j,3); network (m, n) = 1; network (n, m) = 1; end end % The next task is to find the minimum hop count in the routes available % between every node, and every other node. We use the Dijkstra algorithm % applied for every node as a source (except the last node). for source = 1: N % Initialise hop counts (route costs) to 100 for dest = 1: N hops (dest) = 100; included (dest) = 0; end hops (source) = 0; included (source) = 1; % Find the links connected to source node, and set their hop % count (route cost) to 1 for n = 1: N if network (source, n) == 1 hops (n) = 1; end end % Start a for loop which will add all the other nodes to the % included set for j = 1: N - 1 % First we find the node, not yey included, which has the % lowest hop count minhop = 10000; for i = 1: N if included (i) == 0 & hops (i) < minhop minhop = hops (i); newnode = i; end end % We now add the new node to the set of included nodes. % Then we update the hop count by modifying the hop count % of the nodes we can reach from the new node included (newnode) = 1; for n = 1:N if network (newnode, n) ==1 & hops (newnode) + 1 < hops (n) hops (n) = hops (newnode) + 1; end end % We keep the hop count for this source to all other nodes % in the array networkcost end for n = 1: N networkcost (source, n) = hops(n); end end % Networkcost now gives us the minimum number of hops required to get from every % node to every other node. We will use this to construct the cost function % for every candidate solution % The next step is to generate a starting solution. Each solution is simply % a set of N bits. The easiest starting solution is to have all bits equal % to 1 or all bits equal to 0. The current best solution is called % "servernodes" for n = 1: N servernodes (n) = startvalue; end % We place this original solution in the tabulist and set the index to 2. % We will use the index to keep the place where the next solution is to go. for i = 1: N tabulist (1, i) = servernodes (i); end index = 2; lowestcost = 1000000; % We will use this variable to keep track of the cost of the best solution so far maxskipno = 0; % We will use this number to find the largest number of neighbours which were on the tabu list at any iteration % We now start the tabu search. We will limit the number of loops to run up % to tabuloop for loopno = 1: tabuloop % We visit the N neighbours of the current solution for n = 1: N neighbour (n) = servernodes (n); end for n = 1: N if n > 1 if neighbour (n - 1) == 1 neighbour (n - 1) = 0; else neighbour (n - 1) = 1; end end if neighbour (n) == 1 neighbour (n) = 0; else neighbour (n) = 1; end % If the neighbour is on the tabu list, there is no point in % evaluating its cost function. Therefore we search the list % We create an array whose members will be left equal to 0 if the % corresponding neighbour is not on the tabu list skip (n) = 0; for i = 1: listlength for j = 1: N vector (j) = tabulist (i, j); end if isequal(vector, neighbour) skip (n) = 1; end end if skip (n) == 0 % We now need to find which of the nodes with servers is the % nearest node to each node in the network. We do this by using the % array networkcost tabucost (n) = 0; for i = 1: N % i is the index of the ordinary nodes in the network minicost (i) = 1000; for j = 1: N % j is the index of the nodes which are servers if neighbour (j) == 1 if networkcost (i, j) < minicost (i) & i ~= j minicost (i) = networkcost (i, j); end if i == j minicost (i) = 0; end end end tabucost (n) = tabucost (n) + minicost (i); end % We now need to find out how much processing power is needed at % each of the processing nodes. To do this, we need to find out how % many nodes will be connected to each of the server nodes. To do % this we will need to count the number of nodes to which each % server connected with the lowest number of hops. If there is a % tie, then the load of that node will be equally distributed % between all the tieing server nodes % Initialise load to zero for j = 1: N load (j) = 0; end for i = 1: N count = 0; for j = 1: N if minicost (i) == networkcost (i, j) & neighbour (j) == 1 count = count + 1; end end % count is the number of server nodes which will share the load % for node i. for j = 1: N if neighbour (j) == 1 & minicost (i) == networkcost (i, j) load (j) = load (j) + 1/count; end end end for j = 1: N tabucost (n) = tabucost (n) + processweight * sqrt(load (j)); end end end % tabucost now contains the values of the cost functions of the N % neighbours of the current solution. We select the best of these to be % the new current solution lowcost = 1000000; for n = 1: N if tabucost (n) < lowcost & skip (n) == 0 lowcost = tabucost (n); bestn = n; end end if servernodes (bestn) == 1 servernodes (bestn) = 0; else servernodes (bestn) = 1; end % We record the best solution so far, and its cost if lowcost < lowestcost lowestcost = lowcost; for i = 1: N bestsolution (i) = servernodes (i); end end % We now add this solution to