diff options
Diffstat (limited to 'casa/annealing')
| -rw-r--r-- | casa/annealing/Anneal.C | 152 | ||||
| -rw-r--r-- | casa/annealing/Anneal.H | 33 | ||||
| -rw-r--r-- | casa/annealing/AnnealingFilter.H | 93 | ||||
| -rw-r--r-- | casa/annealing/AnnealingPartitioner.C | 58 | ||||
| -rw-r--r-- | casa/annealing/AnnealingPartitioner.H | 43 | ||||
| -rw-r--r-- | casa/annealing/AnnealingSuccess.C | 47 | ||||
| -rw-r--r-- | casa/annealing/AnnealingSuccess.H | 57 | ||||
| -rw-r--r-- | casa/annealing/Bounds.C | 66 | ||||
| -rw-r--r-- | casa/annealing/Bounds.H | 28 |
9 files changed, 577 insertions, 0 deletions
diff --git a/casa/annealing/Anneal.C b/casa/annealing/Anneal.C new file mode 100644 index 0000000..b77e344 --- /dev/null +++ b/casa/annealing/Anneal.C @@ -0,0 +1,152 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include "io/Usage.H" + +#include "annealing/Anneal.H" +#include "annealing/Bounds.H" +#include "annealing/AnnealingSuccess.H" +#include "annealing/AnnealingPartitioner.H" + +#include "search/Search.H" +#include "search/StateGuide.H" + +#include "covering/space/SingleChangeSpace.H" +#include "covering/space/GraftSpace.H" +#include "covering/heuristic/CoveringArrayHeuristic.H" +#include "covering/goal/CoverageGoal.H" +#include "covering/filter/CoveringArrayAnnealingFilter.H" +#include "covering/report/IterationReport.H" + +#include "algorithms/BinarySearch.H" + +CoveringArray anneal + (const SpecificationFile&specification, + const ConstraintFile&constraints, + unsigned iterations, + double startingTemperature, + double decrement) { + std::cout << "Setting up annealing framework" << std::endl; + // Build and connect all of the pieces of the search. + // For simulated annealing: + SearchConfiguration configuration(false,true,1U,0U); +#ifdef WITHOUT_INNER + SingleChangeSpace space +#else + GraftSpace space +#endif + (specification.getStrength(), specification.getOptions()); + // Add the constraints. + { + SATSolver&solver = space.getSolver(); + const Array<InputClause>&clauses = constraints.getClauses(); + for (unsigned i = clauses.getSize(); i--;) { + solver.addClause(const_cast<InputClause&>(clauses[i])); + } + } + CoveringArrayHeuristic heuristic; + StateGuide<CoveringArray, CoverageCost>guide; + CoverageGoal goal(space.computeTargetCoverage()); + CoveringArrayAnnealingFilter filter(startingTemperature,decrement); + IterationReport iterationReport; + Search<CoveringArray, CoverageCost>search + (configuration, &space, &heuristic, &guide, &goal, &filter, true); + AnnealingPartitioner partitioner; + // Add the listeners. + { + // For cooling: + ((EventSource<SearchIteration>&)search).addListener(filter); + typedef EventSource<SearchFinish<CoveringArray, CoverageCost> > + FinishEventSourceT; + // Structure start states: + ((FinishEventSourceT&)search).addListener(space); + // Use search feedback to guide the outer search: + ((FinishEventSourceT&)search).addListener(partitioner); + // Give reports on iterations taken: + ((FinishEventSourceT&)search).addListener(iterationReport); + } + CoveringArray initialSolution + (0, + specification.getStrength(), + specification.getOptions(), + space.getSolver()); + + // Here we go... + std::cout << "Annealing" +#ifdef WITHOUT_INNER + << " (without t-set replacement)" +#endif +#ifdef WITHOUT_OUTER + << " (without extra outer search)" +#endif + << std::endl; + unsigned lower = + computeLowerBound(specification.getStrength(), specification.getOptions()); + unsigned upper = + computeUpperBound(specification.getStrength(), specification.getOptions()); + AnnealingSuccess annealingSuccess(search, iterations, initialSolution); + + std::cout << "Suspect that the optimum number of rows is in [" << lower << + ".." << upper << ']' << std::endl; + std::cout << "Starting binary search" << std::endl; + BinarySearch binarySearch(annealingSuccess, partitioner); + unsigned result = binarySearch(lower, upper + 1 - lower); + while (result > upper) { + upper <<= 1; + std::cout << "Trying more conservative upper bound " << upper << std::endl; + result = binarySearch(lower, upper + 1 - lower); + } +#ifndef WITHOUT_OUTER + do { + if (result == lower) { + if (lower > 5) { + lower -= 5; + } else { + --lower; + if (!lower) { + break; + } + } + std::cout << "Trying less conservative lower bound " << lower << + std::endl; + } + unsigned lastResult = result; + unsigned upped = 0; + do { + if (lastResult == result) { + iterations *= 2; + annealingSuccess.setIterations(iterations); + std::cout << "Upping iterations to " << iterations << std::endl; + ++upped; + } else { + upped = 0; + } + lastResult = result; + std::cout << "Restarting binary search with best result at " << + lastResult << " rows" << std::endl; + filter.setTemperature(startingTemperature); + result = binarySearch(lower, lastResult - lower); + } while ((result < lastResult || upped < retries) && result > lower); + } while (result == lower); +#endif + std::cout << "Giving up with best result at " << result << " rows" << + std::endl; + std::cout << "Total cost of computation: " << iterationReport.getTotal() << + " iteration(s)" << std::endl; + return annealingSuccess.getSolution(); +} diff --git a/casa/annealing/Anneal.H b/casa/annealing/Anneal.H new file mode 100644 index 0000000..8eaa6b1 --- /dev/null +++ b/casa/annealing/Anneal.H @@ -0,0 +1,33 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + +#ifndef ANNEAL_H +#define ANNEAL_H + +#include "io/SpecificationFile.H" +#include "io/ConstraintFile.H" + +#include "covering/state/CoveringArray.H" + +CoveringArray anneal + (const SpecificationFile&specification, + const ConstraintFile&constraints, + unsigned iterations, + double startingTemperature, + double decrement); + +#endif diff --git a/casa/annealing/AnnealingFilter.H b/casa/annealing/AnnealingFilter.H new file mode 100644 index 0000000..f787ae4 --- /dev/null +++ b/casa/annealing/AnnealingFilter.H @@ -0,0 +1,93 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef ANNEALING_FILTER_H +#define ANNEALING_FILTER_H + +#include <cassert> +#include <iostream> + +#include "search/GreedyFilter.H" +#include "events/Listener.H" + +// Decides, according to the rules of simulated annealing, when to take good +// moves and when to take bad ones. + +// Should be added as a listener to search iterations in order that cooling be +// synchronized with the search. + +template<class STATE, class COST>class AnnealingFilter : + public GreedyFilter<STATE,COST>, + public Listener<SearchIteration> { + + typedef Heuristic<STATE,COST> HeuristicT; + typedef Goal<STATE> GoalT; + + double temperature; + const double decay; + +public: + AnnealingFilter(double temperature, double decay) : + temperature(temperature), + decay(decay) { + assert(0 <= decay); + assert(decay <= 1); + } + virtual ~AnnealingFilter() {} + + void setTemperature(double temperature) { + this->temperature = temperature; + } + + virtual double convertToDelta(COST childEstimate, COST parentEstimate) const + = 0; + + void signal(const SearchIteration&message) { + temperature *= decay; + } + + void operator() + (std::set<STATE>&children, + const STATE&parent, + const HeuristicT&heuristic, + const GoalT&goal) const { + GreedyFilter<STATE,COST>::operator()(children, heuristic, goal); + assert(children.size() <= 1); + if (children.size()) { + typename std::set<STATE>::iterator child = children.begin(); + COST childEstimate = heuristic.estimate(*child, goal); + COST parentEstimate = heuristic.estimate(parent, goal); + if (!(parentEstimate < childEstimate)) { + // Always take good moves. + return; + } + double delta = convertToDelta(childEstimate, parentEstimate); + double probability = exp(delta / temperature); + int boundary = (int)(probability * RAND_MAX); + if (rand() < boundary) { + // Sometimes take bad moves. + return; + } + children.clear(); + } + // When no moves are possible or a bad move is rejected, keep the parent. + children.insert(parent); + } +}; + +#endif diff --git a/casa/annealing/AnnealingPartitioner.C b/casa/annealing/AnnealingPartitioner.C new file mode 100644 index 0000000..396d193 --- /dev/null +++ b/casa/annealing/AnnealingPartitioner.C @@ -0,0 +1,58 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include "annealing/AnnealingPartitioner.H" +#include "io/Usage.H" + +using namespace std; + +unsigned AnnealingPartitioner::operator ()(unsigned offset, unsigned size) { + if (guess && guess - offset < size) { + return guess; + } + return offset + (unsigned)(searchPartition * size); +} + +void AnnealingPartitioner::signal + (const SearchFinish<CoveringArray, CoverageCost>&finish) { + set<const Node<CoveringArray, CoverageCost>*>best = finish.source.getBest(); + if (!best.size()) { + guess = 0; + return; + } + const CoveringArray&state = (*best.begin())->getState(); + assert(state.isTrackingNoncoverage()); + if (finish.results.size()) { + if (finish.iterations < 128) { + lastGuess = guess; + guess = 0; + } else { + unsigned ratio = finish.maxIterations / finish.iterations; + unsigned delta = guess - lastGuess; + lastGuess = guess; + if (delta > 0){ + for (guess = state.getRows(); ratio; --guess, ratio >>= 1); + } else { + for (guess = state.getRows() + delta; ratio; --guess, ratio >>= 2); + } + } + } else { + lastGuess = guess; + guess = state.getRows() + state.getNoncoverage().size() / 2; + } +} diff --git a/casa/annealing/AnnealingPartitioner.H b/casa/annealing/AnnealingPartitioner.H new file mode 100644 index 0000000..34fd564 --- /dev/null +++ b/casa/annealing/AnnealingPartitioner.H @@ -0,0 +1,43 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef ANNEALING_PARTITIONER_H +#define ANNEALING_PARTITIONER_H + +#include "algorithms/BinarySearch.H" +#include "events/Listener.H" +#include "search/SearchFinish.H" + +#include "covering/state/CoveringArray.H" +#include "covering/cost/CoverageCost.H" + +class AnnealingPartitioner : + public Partitioner, + public Listener<SearchFinish<CoveringArray,CoverageCost> > { +protected: + unsigned guess; + unsigned lastGuess; +public: + AnnealingPartitioner() : + guess(0), + lastGuess(0) {} + unsigned operator ()(unsigned offset, unsigned size); + void signal(const SearchFinish<CoveringArray, CoverageCost>&finish); +}; + +#endif diff --git a/casa/annealing/AnnealingSuccess.C b/casa/annealing/AnnealingSuccess.C new file mode 100644 index 0000000..f7199f2 --- /dev/null +++ b/casa/annealing/AnnealingSuccess.C @@ -0,0 +1,47 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include <iostream> + +#include "covering/space/CoveringArraySpace.H" +#include "annealing/AnnealingSuccess.H" + +using namespace std; + +bool AnnealingSuccess::operator ()(unsigned rows) const { + bool result; + cout << "Trying " << rows << " rows" << endl; + const CoveringArraySpace*space = + dynamic_cast<const CoveringArraySpace*>(search.getSpace()); + assert(space); + cout << "Building start state" << endl; + CoveringArray startState = space->createStartState(rows); + search.addStartState(startState); + cout << "Searching" << endl; + set<NodeT*>solutions = search.search(iterations, false); + if (solutions.empty()) { + cout << "Failed to meet coverage with " << rows << " rows" << endl; + result = false; + } else { + cout << "Met coverage with " << rows << " rows" << endl; + result = true; + solution = (*solutions.begin())->getState(); + } + search.clear(); + return result; +} diff --git a/casa/annealing/AnnealingSuccess.H b/casa/annealing/AnnealingSuccess.H new file mode 100644 index 0000000..d108f2d --- /dev/null +++ b/casa/annealing/AnnealingSuccess.H @@ -0,0 +1,57 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef ANNEALING_SUCCESS_H +#define ANNEALING_SUCCESS_H + +#include "algorithms/BinarySearch.H" +#include "search/Search.H" + +#include "covering/state/CoveringArray.H" +#include "covering/cost/CoverageCost.H" + +class AnnealingSuccess : public ExpensiveUnaryPredicate { +protected: + typedef Node<CoveringArray, CoverageCost> + NodeT; + + Search<CoveringArray, CoverageCost>& search; + unsigned iterations; + mutable CoveringArray solution; + +public: + AnnealingSuccess + (Search<CoveringArray, CoverageCost>&search, + unsigned iterations, + const CoveringArray&initialSolution) : + search(search), + iterations(iterations), + solution(initialSolution) {} + + bool operator ()(unsigned rows) const; + + void setIterations(unsigned iterations) { + this->iterations = iterations; + } + + const CoveringArray&getSolution() const { + return solution; + } +}; + +#endif diff --git a/casa/annealing/Bounds.C b/casa/annealing/Bounds.C new file mode 100644 index 0000000..8e087e9 --- /dev/null +++ b/casa/annealing/Bounds.C @@ -0,0 +1,66 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#include <cmath> +#include <algorithm> +#include <functional> + +#include "annealing/Bounds.H" + +using namespace std; + +#ifndef UPPER_BOUND_SCALING_FACTOR +#define UPPER_BOUND_SCALING_FACTOR 5 +#endif + +unsigned computeLowerBound(unsigned strength, const Options&options) { + if (lowerBound) { + return lowerBound; + } + static greater<unsigned>backwards; + unsigned result = 1; + Array<unsigned>symbolCounts(options.getSize()); + for (unsigned i = symbolCounts.getSize(); i--;) { + symbolCounts[i] = options.getSymbolCount(i); + } + partial_sort + (symbolCounts + 0, + symbolCounts + strength, + symbolCounts + symbolCounts.getSize(), + backwards); + for (unsigned i = strength; i--;) { + result *= symbolCounts[i]; + } + return result; +} + +unsigned computeUpperBound(unsigned strength, const Options&options) { + if (upperBound) { + return upperBound; + } + unsigned max = 0; + Array<unsigned>symbolCounts(options.getSize()); + for (unsigned i = symbolCounts.getSize(); i--;) { + unsigned candidate = options.getSymbolCount(i); + if (candidate > max) { + max = candidate; + } + } + return (unsigned)(UPPER_BOUND_SCALING_FACTOR * + pow((double)max, (double)strength)); +} diff --git a/casa/annealing/Bounds.H b/casa/annealing/Bounds.H new file mode 100644 index 0000000..2062dfa --- /dev/null +++ b/casa/annealing/Bounds.H @@ -0,0 +1,28 @@ +// Copyright 2008, 2009 Brady J. Garvin + +// This file is part of Covering Arrays by Simulated Annealing (CASA). + +// CASA is free software: you can redistribute it and/or modify it +// under the terms of the GNU General Public License as published by +// the Free Software Foundation, either version 3 of the License, or +// (at your option) any later version. + +// CASA is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with CASA. If not, see <http://www.gnu.org/licenses/>. + + +#ifndef BOUNDS_H +#define BOUNDS_H + +#include "io/Usage.H" +#include "covering/bookkeeping/Options.H" + +unsigned computeLowerBound(unsigned strength, const Options&options); +unsigned computeUpperBound(unsigned strength, const Options&options); + +#endif |