001package net.sf.cpsolver.exam.heuristics; 002 003import java.util.ArrayList; 004import java.util.Collection; 005import java.util.List; 006import java.util.Map; 007 008import org.apache.log4j.Logger; 009 010import net.sf.cpsolver.exam.model.Exam; 011import net.sf.cpsolver.exam.model.ExamPlacement; 012import net.sf.cpsolver.exam.neighbours.ExamRandomMove; 013import net.sf.cpsolver.exam.neighbours.ExamRoomMove; 014import net.sf.cpsolver.exam.neighbours.ExamSimpleNeighbour; 015import net.sf.cpsolver.exam.neighbours.ExamTimeMove; 016import net.sf.cpsolver.ifs.heuristics.NeighbourSelection; 017import net.sf.cpsolver.ifs.model.LazyNeighbour; 018import net.sf.cpsolver.ifs.model.Neighbour; 019import net.sf.cpsolver.ifs.model.LazyNeighbour.LazyNeighbourAcceptanceCriterion; 020import net.sf.cpsolver.ifs.solution.Solution; 021import net.sf.cpsolver.ifs.solution.SolutionListener; 022import net.sf.cpsolver.ifs.solver.Solver; 023import net.sf.cpsolver.ifs.util.DataProperties; 024import net.sf.cpsolver.ifs.util.Progress; 025import net.sf.cpsolver.ifs.util.ToolBox; 026 027/** 028 * Hill climber. In each iteration, one of the following three neighbourhoods is 029 * selected first 030 * <ul> 031 * <li>random move ({@link ExamRandomMove}) 032 * <li>period swap ({@link ExamTimeMove}) 033 * <li>room swap ({@link ExamRoomMove}) 034 * </ul> 035 * , then a neighbour is generated and it is accepted if its value 036 * {@link ExamSimpleNeighbour#value()} is below or equal to zero. The search is 037 * stopped after a given amount of idle iterations ( can be defined by problem 038 * property HillClimber.MaxIdle). <br> 039 * <br> 040 * 041 * @version ExamTT 1.2 (Examination Timetabling)<br> 042 * Copyright (C) 2008 - 2010 Tomáš Müller<br> 043 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 044 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 045 * <br> 046 * This library is free software; you can redistribute it and/or modify 047 * it under the terms of the GNU Lesser General Public License as 048 * published by the Free Software Foundation; either version 3 of the 049 * License, or (at your option) any later version. <br> 050 * <br> 051 * This library is distributed in the hope that it will be useful, but 052 * WITHOUT ANY WARRANTY; without even the implied warranty of 053 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 054 * Lesser General Public License for more details. <br> 055 * <br> 056 * You should have received a copy of the GNU Lesser General Public 057 * License along with this library; if not see 058 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 059 */ 060public class ExamHillClimbing implements NeighbourSelection<Exam, ExamPlacement>, SolutionListener<Exam, ExamPlacement>, LazyNeighbourAcceptanceCriterion<Exam, ExamPlacement> { 061 private static Logger sLog = Logger.getLogger(ExamHillClimbing.class); 062 private List<NeighbourSelection<Exam, ExamPlacement>> iNeighbours = null; 063 private int iMaxIdleIters = 25000; 064 private int iLastImprovingIter = 0; 065 private double iBestValue = 0; 066 private int iIter = 0; 067 private Progress iProgress = null; 068 private boolean iActive; 069 private String iName = "Hill climbing"; 070 071 /** 072 * Constructor 073 * 074 * @param properties 075 * problem properties (use HillClimber.MaxIdle to set maximum 076 * number of idle iterations) 077 */ 078 public ExamHillClimbing(DataProperties properties) { 079 this(properties, "Hill Climbing"); 080 } 081 082 /** 083 * Constructor 084 * 085 * @param properties 086 * problem properties (use HillClimber.MaxIdle to set maximum 087 * number of idle iterations) 088 */ 089 @SuppressWarnings("unchecked") 090 public ExamHillClimbing(DataProperties properties, String name) { 091 iMaxIdleIters = properties.getPropertyInt("HillClimber.MaxIdle", iMaxIdleIters); 092 String neighbours = properties.getProperty("HillClimber.Neighbours", 093 ExamRandomMove.class.getName() + ";" + 094 ExamRoomMove.class.getName() + ";" + 095 ExamTimeMove.class.getName()); 096 neighbours += ";" + properties.getProperty("HillClimber.AdditionalNeighbours", ""); 097 iNeighbours = new ArrayList<NeighbourSelection<Exam,ExamPlacement>>(); 098 for (String neighbour: neighbours.split("\\;")) { 099 if (neighbour == null || neighbour.isEmpty()) continue; 100 try { 101 Class<NeighbourSelection<Exam, ExamPlacement>> clazz = (Class<NeighbourSelection<Exam, ExamPlacement>>)Class.forName(neighbour); 102 iNeighbours.add(clazz.getConstructor(DataProperties.class).newInstance(properties)); 103 } catch (Exception e) { 104 sLog.error("Unable to use " + neighbour + ": " + e.getMessage()); 105 } 106 } 107 iName = name; 108 } 109 110 /** 111 * Initialization 112 */ 113 @Override 114 public void init(Solver<Exam, ExamPlacement> solver) { 115 solver.currentSolution().addSolutionListener(this); 116 for (NeighbourSelection<Exam, ExamPlacement> neighbour: iNeighbours) 117 neighbour.init(solver); 118 solver.setUpdateProgress(false); 119 iProgress = Progress.getInstance(solver.currentSolution().getModel()); 120 iActive = false; 121 } 122 123 /** 124 * Select one of the given neighbourhoods randomly, select neighbour, return 125 * it if its value is below or equal to zero (continue with the next 126 * selection otherwise). Return null when the given number of idle 127 * iterations is reached. 128 */ 129 @Override 130 public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) { 131 if (!iActive) { 132 iProgress.setPhase(iName + "..."); 133 iActive = true; 134 } 135 while (true) { 136 iIter++; 137 iProgress.setProgress(Math.round(100.0 * (iIter - iLastImprovingIter) / iMaxIdleIters)); 138 if (iIter - iLastImprovingIter >= iMaxIdleIters) 139 break; 140 NeighbourSelection<Exam, ExamPlacement> ns = iNeighbours.get(ToolBox.random(iNeighbours.size())); 141 Neighbour<Exam, ExamPlacement> n = ns.selectNeighbour(solution); 142 if (n != null) { 143 if (n instanceof LazyNeighbour) { 144 ((LazyNeighbour<Exam,ExamPlacement>)n).setAcceptanceCriterion(this); 145 return n; 146 } else if (n.value() <= 0.0) return n; 147 } 148 } 149 iIter = 0; 150 iLastImprovingIter = 0; 151 iActive = false; 152 return null; 153 } 154 155 /** 156 * Memorize the iteration when the last best solution was found. 157 */ 158 @Override 159 public void bestSaved(Solution<Exam, ExamPlacement> solution) { 160 if (Math.abs(iBestValue - solution.getBestValue()) >= 1.0) { 161 iLastImprovingIter = iIter; 162 iBestValue = solution.getBestValue(); 163 } 164 } 165 166 @Override 167 public void solutionUpdated(Solution<Exam, ExamPlacement> solution) { 168 } 169 170 @Override 171 public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info) { 172 } 173 174 @Override 175 public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info, Collection<Exam> variables) { 176 } 177 178 @Override 179 public void bestCleared(Solution<Exam, ExamPlacement> solution) { 180 } 181 182 @Override 183 public void bestRestored(Solution<Exam, ExamPlacement> solution) { 184 } 185 186 /** Accept lazy neighbour */ 187 @Override 188 public boolean accept(LazyNeighbour<Exam, ExamPlacement> neighbour, double value) { 189 return value <= 0.0; 190 } 191}