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