001package org.cpsolver.ifs.algorithms; 002 003import java.util.ArrayList; 004import java.util.List; 005 006import org.apache.log4j.Logger; 007import org.cpsolver.ifs.assignment.Assignment; 008import org.cpsolver.ifs.assignment.context.AssignmentContext; 009import org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext; 010import org.cpsolver.ifs.heuristics.NeighbourSelection; 011import org.cpsolver.ifs.heuristics.StandardNeighbourSelection; 012import org.cpsolver.ifs.model.Neighbour; 013import org.cpsolver.ifs.model.Value; 014import org.cpsolver.ifs.model.Variable; 015import org.cpsolver.ifs.solution.Solution; 016import org.cpsolver.ifs.solver.Solver; 017import org.cpsolver.ifs.util.DataProperties; 018import org.cpsolver.ifs.util.Progress; 019 020/** 021 * Meta-heuristic search neighbor selection. <br> 022 * <br> 023 * It consists of the following (up to four) phases: 024 * <ul> 025 * <li>Construction phase until the construction neighbor selection is not exhausted (i.e., null is returned as the next neighbor), 026 * <li>Incomplete phase (e.g., {@link StandardNeighbourSelection}) until all variables are assigned (this heuristics is also used whenever the solution becomes incomplete, until it is complete again), 027 * <li>Hill-climbing phase (e.g., {@link HillClimber}) until the given number if idle iterations (this phase is optional) 028 * <li>Improvement phase (e.g., {@link GreatDeluge} or {@link SimulatedAnnealing}) until timeout is reached 029 * </ul> 030 * The search is based on the {@link SimpleSearch}, however each phase can be customized by providing the appropriate neighbor selection. 031 * Also, a different selection can be used in each thread. 032 * <br> 033 * <br> 034 * 035 * @version IFS 1.3 (Iterative Forward Search)<br> 036 * Copyright (C) 2014 Tomáš Müller<br> 037 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 038 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 039 * <br> 040 * This library is free software; you can redistribute it and/or modify 041 * it under the terms of the GNU Lesser General Public License as 042 * published by the Free Software Foundation; either version 3 of the 043 * License, or (at your option) any later version. <br> 044 * <br> 045 * This library is distributed in the hope that it will be useful, but 046 * WITHOUT ANY WARRANTY; without even the implied warranty of 047 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 048 * Lesser General Public License for more details. <br> 049 * <br> 050 * You should have received a copy of the GNU Lesser General Public 051 * License along with this library; if not see 052 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 053 * @param <V> Variable 054 * @param <T> Value 055 */ 056public class MetaHeuristicSearch<V extends Variable<V, T>, T extends Value<V, T>> extends NeighbourSelectionWithContext<V,T,MetaHeuristicSearch<V,T>.MetaHeuristicSearchContext> { 057 private Logger iLog = Logger.getLogger(SimpleSearch.class); 058 private List<NeighbourSelection<V, T>> iConstructionPhase = new ArrayList<NeighbourSelection<V,T>>(); 059 private List<NeighbourSelection<V, T>> iIncompletePhase = new ArrayList<NeighbourSelection<V,T>>(); 060 private List<NeighbourSelection<V, T>> iHillClimberPhase = new ArrayList<NeighbourSelection<V,T>>(); 061 private List<NeighbourSelection<V, T>> iImprovementPhase = new ArrayList<NeighbourSelection<V,T>>(); 062 private Progress iProgress = null; 063 064 /** 065 * Constructor 066 * <ul> 067 * <li>MetaHeuristic.ConstructionClass ... construction heuristics (if needed) 068 * <li>MetaHeuristic.IncompleteClass ... incomplete heuristics (e.g., {@link StandardNeighbourSelection}) 069 * <li>MetaHeuristic.HillClimberClass ... hill-climber heuristics (e.g., {@link HillClimber} or {@link StepCountingHillClimber}) 070 * <li>MetaHeuristic.ImprovementClass ... improvement heuristics (e.g., {@link SimulatedAnnealing} or {@link GreatDeluge}) 071 * </ul> 072 * @param properties problem configuration 073 */ 074 public MetaHeuristicSearch(DataProperties properties) { 075 String constructions = properties.getProperty("MetaHeuristic.ConstructionClass"); 076 if (constructions != null) { 077 for (String construction: constructions.split(",")) { 078 try { 079 boolean pc = false; 080 if (construction.endsWith("@PC")) { 081 pc = true; 082 construction = construction.substring(0, construction.length() - 3); 083 } 084 if (construction.isEmpty() || "null".equalsIgnoreCase(construction)) { 085 iConstructionPhase.add(null); 086 continue; 087 } 088 @SuppressWarnings("unchecked") 089 Class<NeighbourSelection<V, T>> constructionClass = (Class<NeighbourSelection<V, T>>)Class.forName(construction); 090 NeighbourSelection<V, T> constructionSelection = constructionClass.getConstructor(DataProperties.class).newInstance(properties); 091 if (pc) { 092 constructionSelection = new ParallelConstruction<V, T>(properties, constructionSelection); 093 } 094 iConstructionPhase.add(constructionSelection); 095 } catch (Exception e) { 096 iLog.error("Unable to use " + construction + ": " + e.getMessage()); 097 } 098 } 099 } 100 String incompletes = properties.getProperty("MetaHeuristic.IncompleteClass"); 101 if (incompletes != null) { 102 for (String incomplete: incompletes.split(",")) { 103 try { 104 boolean pc = false; 105 if (incomplete.endsWith("@PC")) { 106 pc = true; 107 incomplete = incomplete.substring(0, incomplete.length() - 3); 108 } 109 if (incomplete.isEmpty() || "null".equalsIgnoreCase(incomplete)) { 110 iIncompletePhase.add(null); 111 continue; 112 } 113 @SuppressWarnings("unchecked") 114 Class<NeighbourSelection<V, T>> incompleteClass = (Class<NeighbourSelection<V, T>>)Class.forName(incomplete); 115 NeighbourSelection<V, T> incompleteSelection = incompleteClass.getConstructor(DataProperties.class).newInstance(properties); 116 if (pc) { 117 incompleteSelection = new ParallelConstruction<V, T>(properties, incompleteSelection); 118 } 119 iIncompletePhase.add(incompleteSelection); 120 } catch (Exception e) { 121 iLog.error("Unable to use " + incomplete + ": " + e.getMessage()); 122 } 123 } 124 } 125 String hillClimbers = properties.getProperty("MetaHeuristic.HillClimberClass"); 126 if (hillClimbers != null) { 127 for (String hillClimber: hillClimbers.split(",")) { 128 try { 129 if (hillClimber.isEmpty() || "null".equalsIgnoreCase(hillClimber)) { 130 iHillClimberPhase.add(null); 131 continue; 132 } 133 @SuppressWarnings("unchecked") 134 Class<NeighbourSelection<V, T>> hillClimberClass = (Class<NeighbourSelection<V, T>>)Class.forName(hillClimber); 135 NeighbourSelection<V, T> hillClimberSelection = hillClimberClass.getConstructor(DataProperties.class).newInstance(properties); 136 iHillClimberPhase.add(hillClimberSelection); 137 } catch (Exception e) { 138 iLog.error("Unable to use " + hillClimber + ": " + e.getMessage()); 139 } 140 } 141 } 142 String improvements = properties.getProperty("MetaHeuristic.ImprovementClass"); 143 if (improvements != null) { 144 for (String improvement: improvements.split(",")) { 145 try { 146 if (improvement.isEmpty() || "null".equalsIgnoreCase(improvement)) { 147 iImprovementPhase.add(null); 148 continue; 149 } 150 @SuppressWarnings("unchecked") 151 Class<NeighbourSelection<V, T>> improvementClass = (Class<NeighbourSelection<V, T>>)Class.forName(improvement); 152 NeighbourSelection<V, T> improvementSelection = improvementClass.getConstructor(DataProperties.class).newInstance(properties); 153 iImprovementPhase.add(improvementSelection); 154 } catch (Exception e) { 155 iLog.error("Unable to use " + improvement + ": " + e.getMessage()); 156 } 157 } 158 } 159 } 160 161 private String getName(NeighbourSelection<V, T> selection) { 162 return selection.getClass().getSimpleName().replaceAll("(?<=[^A-Z])([A-Z])"," $1"); 163 } 164 165 /** 166 * Initialization 167 */ 168 @Override 169 public void init(Solver<V, T> solver) { 170 super.init(solver); 171 for (NeighbourSelection<V, T> ns: iConstructionPhase) 172 if (ns != null) ns.init(solver); 173 for (NeighbourSelection<V, T> ns: iIncompletePhase) 174 if (ns != null) ns.init(solver); 175 for (NeighbourSelection<V, T> ns: iHillClimberPhase) 176 if (ns != null) ns.init(solver); 177 for (NeighbourSelection<V, T> ns: iImprovementPhase) 178 if (ns != null) ns.init(solver); 179 iProgress = Progress.getInstance(solver.currentSolution().getModel()); 180 } 181 182 /** 183 * Neighbour selection. It consists of the following phases: 184 * <ul> 185 * <li>Construction phase until the construction neighbor selection is not exhausted (i.e., null is returned as the next neighbor), 186 * <li>Incomplete phase (e.g., {@link StandardNeighbourSelection}) until all variables are assigned (this heuristics is also used whenever the solution becomes incomplete, until it is complete again), 187 * <li>Hill-climbing phase (e.g., {@link HillClimber}) until the given number if idle iterations (this phase is optional) 188 * <li>Improvement phase (e.g., {@link GreatDeluge} or {@link SimulatedAnnealing}) until timeout is reached 189 * </ul> 190 */ 191 @SuppressWarnings("fallthrough") 192 @Override 193 public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) { 194 MetaHeuristicSearchContext context = getContext(solution.getAssignment()); 195 Neighbour<V, T> n = null; 196 switch (context.getPhase()) { 197 case -1: 198 context.setPhase(0); 199 iProgress.info("[" + Thread.currentThread().getName() + "] " + getName(context.getConstructionSelection()) + "..."); 200 case 0: 201 if (solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0) { 202 n = context.getConstructionSelection().selectNeighbour(solution); 203 if (n != null) 204 return n; 205 } 206 context.setPhase(1); 207 if (solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0) 208 iProgress.info("[" + Thread.currentThread().getName() + "] " + getName(context.getIncompleteSelection()) + "..."); 209 case 1: 210 if (solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0) { 211 return context.getIncompleteSelection().selectNeighbour(solution); 212 } 213 context.setPhase(2); 214 if (context.hasHillClimberSelection()) 215 iProgress.info("[" + Thread.currentThread().getName() + "] " + getName(context.getHillClimberSelection()) + "..."); 216 case 2: 217 if (solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0) 218 return context.getIncompleteSelection().selectNeighbour(solution); 219 if (context.hasHillClimberSelection()) { 220 n = context.getHillClimberSelection().selectNeighbour(solution); 221 if (n != null) return n; 222 } 223 context.setPhase(3); 224 iProgress.info("[" + Thread.currentThread().getName() + "] " + getName(context.getImprovementSelection()) + "..."); 225 case 3: 226 if (solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0) 227 return context.getIncompleteSelection().selectNeighbour(solution); 228 return context.getImprovementSelection().selectNeighbour(solution); 229 default: 230 return null; 231 } 232 } 233 234 @Override 235 public MetaHeuristicSearchContext createAssignmentContext(Assignment<V, T> assignment) { 236 return new MetaHeuristicSearchContext(assignment.getIndex() - 1); 237 } 238 239 public class MetaHeuristicSearchContext implements AssignmentContext { 240 private int iPhase = -1; 241 private NeighbourSelection<V, T> iConstructionSelection = null; 242 private NeighbourSelection<V, T> iIncompleteSelection = null; 243 private NeighbourSelection<V, T> iHillClimberSelection = null; 244 private NeighbourSelection<V, T> iImprovementSelection = null; 245 246 public MetaHeuristicSearchContext(int index) { 247 if (!iConstructionPhase.isEmpty()) { 248 if (index < 0) iConstructionSelection = iConstructionPhase.get(0); 249 iConstructionSelection = (index < 0 ? iConstructionPhase.get(0) : iConstructionPhase.get(index % iConstructionPhase.size())); 250 } 251 if (!iIncompletePhase.isEmpty()) { 252 if (index < 0) iIncompleteSelection = iIncompletePhase.get(0); 253 iIncompleteSelection = (index < 0 ? iIncompletePhase.get(0) : iIncompletePhase.get(index % iIncompletePhase.size())); 254 } 255 if (!iImprovementPhase.isEmpty()) { 256 if (index < 0) iImprovementSelection = iImprovementPhase.get(0); 257 iImprovementSelection = (index < 0 ? iImprovementPhase.get(0) : iImprovementPhase.get(index % iImprovementPhase.size())); 258 } 259 if (!iHillClimberPhase.isEmpty()) { 260 if (index < 0) iHillClimberSelection = iHillClimberPhase.get(0); 261 iHillClimberSelection = (index < 0 ? iHillClimberPhase.get(0) : iHillClimberPhase.get(index % iHillClimberPhase.size())); 262 } 263 if (iConstructionSelection == null) iConstructionSelection = iIncompleteSelection; 264 if (iIncompleteSelection == null) iIncompleteSelection = iConstructionSelection; 265 if (iImprovementSelection == null) iImprovementSelection = iIncompleteSelection; 266 iLog.info("Using " + iConstructionSelection.getClass().getSimpleName() + 267 " > " + iIncompleteSelection.getClass().getSimpleName() + 268 (iHillClimberSelection == null ? "" : " > " + iHillClimberSelection.getClass().getSimpleName()) + 269 " > " + iImprovementSelection.getClass().getSimpleName()); 270 } 271 272 public NeighbourSelection<V, T> getConstructionSelection() { 273 return iConstructionSelection; 274 } 275 276 public NeighbourSelection<V, T> getIncompleteSelection() { 277 return iIncompleteSelection; 278 } 279 280 public NeighbourSelection<V, T> getHillClimberSelection() { 281 return iHillClimberSelection; 282 } 283 284 public boolean hasHillClimberSelection() { 285 return iHillClimberSelection != null; 286 } 287 288 public NeighbourSelection<V, T> getImprovementSelection() { 289 return iImprovementSelection; 290 } 291 292 public int getPhase() { return iPhase; } 293 public void setPhase(int phase) { iPhase = phase; } 294 } 295}