#include <ImprovementHeuristic.hh>
Public Member Functions | |
ImprovementHeuristic (ABA_MASTER *master, Graph *theGraph, StableSetStatistics *theStatistics) | |
~ImprovementHeuristic () | |
int | improve (double &value) |
Definition at line 38 of file ImprovementHeuristic.hh.
|
Constructor.
Definition at line 37 of file ImprovementHeuristic.cpp. 00038 : 00039 master_(master), 00040 itsGraph(theGraph), 00041 itsStatistics(theStatistics) 00042 { 00043 }
|
|
Destructor. Definition at line 49 of file ImprovementHeuristic.cpp.
|
|
Try to improve a stable set.
Definition at line 61 of file ImprovementHeuristic.cpp. References StableSetMaster::getSolution(), and StableSetMaster::m_timeLimitForImprovementHeuristic. 00061 { 00062 00063 clock_t t1 = clock(); // Get current time. 00064 00065 int i, j, k; // Loop counter. 00066 int cnt; // Counter. 00067 int cnt2; 00068 int vertex; // A node. 00069 int indexOfVertex; // Index of node vertex. 00070 int indexOfNode; 00071 int node; 00072 int index; 00073 int nodeOfPathOne; 00074 int nodeOfPathTwo; 00075 int v11, v12, v13; // Three nodes of a path. 00076 int v21, v22, v23; // Three nodes of a path. 00077 int beginOne; 00078 int beginTwo; 00079 int stack; 00080 int member; 00081 int status = 0; // Return value; 00082 double timeLimit = stableSetMaster()->m_timeLimitForImprovementHeuristic; 00083 vector<int> *solution = stableSetMaster()->getSolution(); 00084 if (solution->size() <= 2) { 00085 return status; 00086 } 00087 00088 // 00089 // Improve until time limit is reached. 00090 // 00091 while (timeLimit > (double)(clock() - t1)/CLOCKS_PER_SEC) { 00092 00093 // Choose randomly two nodes to start from. 00094 indexOfVertex = stableSetMaster()->getRandomNumber(solution->size()); 00095 vertex = (*solution)[indexOfVertex]; 00096 index = stableSetMaster()->getRandomNumber(solution->size()); 00097 if (index == indexOfVertex) { 00098 index++; 00099 index = index % solution->size(); 00100 } 00101 node = index +1; 00102 node = node % solution->size(); 00103 if (node == indexOfVertex) { 00104 node++; 00105 node = node % solution->size(); 00106 } 00107 cnt = 0; 00108 v11 = -1; 00109 v12 = -1; 00110 while((cnt < 2) && (timeLimit > (double)(clock() - t1)/CLOCKS_PER_SEC)) { 00111 if (node == index) { 00112 break; 00113 } 00114 // Find path from 'vertex' to '(*solution)[node]' with length 3. 00115 if (calculateDistance(vertex, (*solution)[node], v11, v12, v21, 00116 v22)) { 00117 cnt++; 00118 if (cnt == 1) { 00119 v13 = (*solution)[node]; 00120 } 00121 else { 00122 v23 = (*solution)[node]; 00123 } 00124 } 00125 node++; 00126 node = node % solution->size(); 00127 if (node == indexOfVertex) { 00128 node++; 00129 node = node % solution->size(); 00130 } 00131 } 00132 00133 // 00134 // Two paths have been computed. Try to improve the stable set. 00135 // 00136 if (cnt == 2) { 00137 00138 cnt2 = 0; 00139 // Solution is allways sorted! 00140 beginOne = 0; 00141 beginTwo = 0; 00142 for (j=0; j<solution->size(); j++) { 00143 stack = (*solution)[j]; 00144 if (stack != vertex) { 00145 if(itsGraph->isMemberOfAdjacentList(v11, beginOne, stack)) { 00146 cnt2++; 00147 member = stack; 00148 } 00149 else { 00150 if(itsGraph->isMemberOfAdjacentList(v21, beginTwo, 00151 stack)) { 00152 cnt2++; 00153 member = stack; 00154 } 00155 } 00156 } 00157 if (cnt2 > 1) { 00158 break; 00159 } 00160 } 00161 00162 // 00163 // If cnt = 0 the new stable set will have a greater size. 00164 // 00165 if (cnt2 < 2) { 00166 // Update solution. 00167 solution->erase(solution->begin() + indexOfVertex); 00168 if (cnt2 == 1) { 00169 k = 0; 00170 while ((*solution)[k] != member) { 00171 k++; 00172 } 00173 solution->erase(solution->begin() + k); 00174 } 00175 00176 solution->push_back(v11); 00177 solution->push_back(v21); 00178 sort(solution->begin(), solution->end()); 00179 testStableSet(solution); 00180 if (cnt2 == 0) { 00181 itsStatistics->improvementHeuristics(); 00182 } 00183 } 00184 } 00185 00186 } 00187 00188 value = 1.0*solution->size(); 00189 00190 // Update bounds. 00191 if (master_->betterPrimal(value)) { 00192 // Heuristic found better solution. 00193 master_->out() << "\nImprovement of heuristic was successful:\n"; 00194 master_->out() << "\tNew value:\t" << value << endl; 00195 00196 // Update lower bound (best known feasible solution) 00197 // (this is done automatically by ABACUS, too). 00198 master_->primalBound(value); 00199 00200 // Update statistics. 00201 itsStatistics->solutionFound(2); 00202 00203 status = 1; 00204 } 00205 00206 // Return with status. 00207 return status; 00208 00209 }// int improve(..)
|