001package net.sf.cpsolver.ifs.algorithms; 002 003import org.apache.log4j.Logger; 004 005import net.sf.cpsolver.ifs.heuristics.NeighbourSelection; 006import net.sf.cpsolver.ifs.heuristics.StandardNeighbourSelection; 007import net.sf.cpsolver.ifs.model.Neighbour; 008import net.sf.cpsolver.ifs.model.Value; 009import net.sf.cpsolver.ifs.model.Variable; 010import net.sf.cpsolver.ifs.solution.Solution; 011import net.sf.cpsolver.ifs.solver.Solver; 012import net.sf.cpsolver.ifs.termination.TerminationCondition; 013import net.sf.cpsolver.ifs.util.Callback; 014import net.sf.cpsolver.ifs.util.DataProperties; 015import net.sf.cpsolver.ifs.util.Progress; 016 017/** 018 * Simple search neighbour selection. <br> 019 * <br> 020 * It consists of the following three phases: 021 * <ul> 022 * <li>Construction phase ({@link StandardNeighbourSelection} until all variables are assigned) 023 * <li>Hill-climbing phase ({@link HillClimber} until the given number if idle iterations) 024 * <li>Simulated annealing phase ({@link SimulatedAnnealing} until timeout is reached) 025 * <ul> 026 * <li>Or great deluge phase (when Search.GreatDeluge is true, {@link GreatDeluge} until timeout is reached) 027 * </ul> 028 * <li>At the end (when {@link TerminationCondition#canContinue(Solution)} is false), 029 * the search is finished with one sweep of final phase ({@link HillClimber} until the given number if idle iterations). 030 * </ul> 031 * <br> 032 * <br> 033 * 034 * @version IFS 1.2 (Iterative Forward Search)<br> 035 * Copyright (C) 2014 Tomáš Müller<br> 036 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 037 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 038 * <br> 039 * This library is free software; you can redistribute it and/or modify 040 * it under the terms of the GNU Lesser General Public License as 041 * published by the Free Software Foundation; either version 3 of the 042 * License, or (at your option) any later version. <br> 043 * <br> 044 * This library is distributed in the hope that it will be useful, but 045 * WITHOUT ANY WARRANTY; without even the implied warranty of 046 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 047 * Lesser General Public License for more details. <br> 048 * <br> 049 * You should have received a copy of the GNU Lesser General Public 050 * License along with this library; if not see 051 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 052 */ 053public class SimpleSearch<V extends Variable<V, T>, T extends Value<V, T>> implements NeighbourSelection<V, T>, TerminationCondition<V, T> { 054 private Logger iLog = Logger.getLogger(SimpleSearch.class); 055 private NeighbourSelection<V, T> iCon = null; 056 private boolean iConstructionUntilComplete = false; 057 private StandardNeighbourSelection<V, T> iStd = null; 058 private SimulatedAnnealing<V, T> iSA = null; 059 private HillClimber<V, T> iHC = null; 060 private HillClimber<V, T> iFin = null; 061 private GreatDeluge<V, T> iGD = null; 062 private int iPhase = -1; 063 private boolean iUseGD = true; 064 private Progress iProgress = null; 065 private Callback iFinalPhaseFinished = null; 066 private boolean iCanContinue = true; 067 private TerminationCondition<V, T> iTerm = null; 068 069 /** 070 * Constructor 071 * 072 * @param properties 073 * problem properties 074 */ 075 public SimpleSearch(DataProperties properties) throws Exception { 076 String construction = properties.getProperty("Construction.Class"); 077 if (construction != null) { 078 try { 079 @SuppressWarnings("unchecked") 080 Class<NeighbourSelection<V, T>> constructionClass = (Class<NeighbourSelection<V, T>>)Class.forName(properties.getProperty("Construction.Class")); 081 iCon = constructionClass.getConstructor(DataProperties.class).newInstance(properties); 082 iConstructionUntilComplete = properties.getPropertyBoolean("Construction.UntilComplete", iConstructionUntilComplete); 083 } catch (Exception e) { 084 iLog.error("Unable to use " + construction + ": " + e.getMessage()); 085 } 086 } 087 iStd = new StandardNeighbourSelection<V, T>(properties); 088 iSA = new SimulatedAnnealing<V, T>(properties); 089 if (properties.getPropertyBoolean("Search.CountSteps", false)) 090 iHC = new StepCountingHillClimber<V, T>(properties, "Step Counting Hill Climbing"); 091 else 092 iHC = new HillClimber<V, T>(properties); 093 iFin = new HillClimber<V, T>(properties); iFin.setPhase("Finalization"); 094 iGD = new GreatDeluge<V, T>(properties); 095 iUseGD = properties.getPropertyBoolean("Search.GreatDeluge", iUseGD); 096 } 097 098 /** 099 * Initialization 100 */ 101 @Override 102 public void init(Solver<V, T> solver) { 103 iStd.init(solver); 104 if (iCon != null) 105 iCon.init(solver); 106 iSA.init(solver); 107 iHC.init(solver); 108 iFin.init(solver); 109 iGD.init(solver); 110 if (iTerm == null) { 111 iTerm = solver.getTerminationCondition(); 112 solver.setTerminalCondition(this); 113 } 114 iCanContinue = true; 115 iProgress = Progress.getInstance(solver.currentSolution().getModel()); 116 } 117 118 /** 119 * Neighbour selection. It consists of the following three phases: 120 * <ul> 121 * <li>Construction phase ({@link StandardNeighbourSelection} until all variables are assigned) 122 * <li>Hill-climbing phase ({@link HillClimber} until the given number if idle iterations) 123 * <li>Simulated annealing phase ({@link SimulatedAnnealing} until timeout is reached) 124 * </ul> 125 */ 126 @SuppressWarnings("fallthrough") 127 @Override 128 public synchronized Neighbour<V, T> selectNeighbour(Solution<V, T> solution) { 129 Neighbour<V, T> n = null; 130 if (!isFinalPhase() && !iTerm.canContinue(solution)) 131 setFinalPhase(null); 132 switch (iPhase) { 133 case -1: 134 iPhase++; 135 iLog.info("***** construction phase *****"); 136 if (solution.getModel().nrUnassignedVariables() > 0) 137 iProgress.setPhase("Searching for initial solution...", solution.getModel().variables().size()); 138 case 0: 139 if (iCon != null && solution.getModel().nrUnassignedVariables() > 0) { 140 iProgress.setProgress(solution.getModel().variables().size() - solution.getModel().getBestUnassignedVariables()); 141 n = iCon.selectNeighbour(solution); 142 if (n != null || iConstructionUntilComplete) 143 return n; 144 } 145 iPhase++; 146 iLog.info("***** ifs phase *****"); 147 case 1: 148 if (iStd != null && solution.getModel().nrUnassignedVariables() > 0) { 149 iProgress.setProgress(solution.getModel().variables().size() - solution.getModel().getBestUnassignedVariables()); 150 return iStd.selectNeighbour(solution); 151 } 152 iPhase++; 153 iLog.info("***** hill climbing phase *****"); 154 case 2: 155 if (solution.getModel().nrUnassignedVariables() > 0) 156 return (iCon == null ? iStd : iCon).selectNeighbour(solution); 157 n = iHC.selectNeighbour(solution); 158 if (n != null) 159 return n; 160 iPhase++; 161 iLog.info("***** " + (iUseGD ? "great deluge" : "simulated annealing") + " phase *****"); 162 case 3: 163 if (solution.getModel().nrUnassignedVariables() > 0) 164 return (iCon == null ? iStd : iCon).selectNeighbour(solution); 165 if (iUseGD) 166 return iGD.selectNeighbour(solution); 167 else 168 return iSA.selectNeighbour(solution); 169 case 9999: 170 n = iFin.selectNeighbour(solution); 171 if (n != null) 172 return n; 173 iPhase = -1; 174 if (iFinalPhaseFinished != null) 175 iFinalPhaseFinished.execute(); 176 iCanContinue = false; 177 default: 178 return null; 179 } 180 } 181 182 /** 183 * Set final phase 184 * 185 * @param finalPhaseFinished 186 * to be called when the final phase is finished 187 **/ 188 public synchronized void setFinalPhase(Callback finalPhaseFinished) { 189 iLog.info("***** final phase *****"); 190 iFinalPhaseFinished = finalPhaseFinished; 191 iPhase = 9999; 192 } 193 194 /** Is final phase */ 195 public boolean isFinalPhase() { 196 return iPhase == 9999; 197 } 198 199 /** Termination condition (i.e., has final phase finished) */ 200 @Override 201 public boolean canContinue(Solution<V, T> currentSolution) { 202 return iCanContinue; 203 } 204 205}