001 package net.sf.cpsolver.exam.heuristics; 002 003 import java.text.DecimalFormat; 004 import java.util.Collection; 005 import java.util.Map; 006 007 import net.sf.cpsolver.exam.model.Exam; 008 import net.sf.cpsolver.exam.model.ExamPlacement; 009 import net.sf.cpsolver.exam.neighbours.ExamRandomMove; 010 import net.sf.cpsolver.exam.neighbours.ExamRoomMove; 011 import net.sf.cpsolver.exam.neighbours.ExamTimeMove; 012 import net.sf.cpsolver.ifs.heuristics.NeighbourSelection; 013 import net.sf.cpsolver.ifs.model.Neighbour; 014 import net.sf.cpsolver.ifs.solution.Solution; 015 import net.sf.cpsolver.ifs.solution.SolutionListener; 016 import net.sf.cpsolver.ifs.solver.Solver; 017 import net.sf.cpsolver.ifs.util.DataProperties; 018 import net.sf.cpsolver.ifs.util.JProf; 019 import net.sf.cpsolver.ifs.util.Progress; 020 import net.sf.cpsolver.ifs.util.ToolBox; 021 022 import org.apache.log4j.Logger; 023 024 /** 025 * Greate deluge. In each iteration, one of the following three neighbourhoods 026 * is selected first 027 * <ul> 028 * <li>random move ({@link ExamRandomMove}) 029 * <li>period swap ({@link ExamTimeMove}) 030 * <li>room swap ({@link ExamRoomMove}) 031 * </ul> 032 * , then a neighbour is generated and it is accepted if the value of the new 033 * solution is below certain bound. This bound is initialized to the 034 * GreatDeluge.UpperBoundRate × value of the best solution ever found. 035 * After each iteration, the bound is decreased by GreatDeluge.CoolRate (new 036 * bound equals to old bound × GreatDeluge.CoolRate). If the bound gets 037 * bellow GreatDeluge.LowerBoundRate × value of the best solution ever 038 * found, it is changed back to GreatDeluge.UpperBoundRate × value of the 039 * best solution ever found. 040 * 041 * If there was no improvement found between the bounds, the new bounds are 042 * changed to GreatDeluge.UpperBoundRate^2 and GreatDeluge.LowerBoundRate^2, 043 * GreatDeluge.UpperBoundRate^3 and GreatDeluge.LowerBoundRate^3, etc. till 044 * there is an improvement found. <br> 045 * <br> 046 * 047 * @version ExamTT 1.2 (Examination Timetabling)<br> 048 * Copyright (C) 2008 - 2010 Tomas Muller<br> 049 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 050 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 051 * <br> 052 * This library is free software; you can redistribute it and/or modify 053 * it under the terms of the GNU Lesser General Public License as 054 * published by the Free Software Foundation; either version 3 of the 055 * License, or (at your option) any later version. <br> 056 * <br> 057 * This library is distributed in the hope that it will be useful, but 058 * WITHOUT ANY WARRANTY; without even the implied warranty of 059 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 060 * Lesser General Public License for more details. <br> 061 * <br> 062 * You should have received a copy of the GNU Lesser General Public 063 * License along with this library; if not see 064 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 065 */ 066 public class ExamGreatDeluge implements NeighbourSelection<Exam, ExamPlacement>, SolutionListener<Exam, ExamPlacement> { 067 private static Logger sLog = Logger.getLogger(ExamGreatDeluge.class); 068 private static DecimalFormat sDF2 = new DecimalFormat("0.00"); 069 private static DecimalFormat sDF5 = new DecimalFormat("0.00000"); 070 private double iBound = 0.0; 071 private double iCoolRate = 0.99999995; 072 private long iIter; 073 private double iUpperBound; 074 private double iUpperBoundRate = 1.05; 075 private double iLowerBoundRate = 0.95; 076 private int iMoves = 0; 077 private int iAcceptedMoves = 0; 078 private int iNrIdle = 0; 079 private long iT0 = -1; 080 private long iLastImprovingIter = 0; 081 private double iBestValue = 0; 082 private Progress iProgress = null; 083 084 private NeighbourSelection<Exam, ExamPlacement>[] iNeighbours = null; 085 086 /** 087 * Constructor. Following problem properties are considered: 088 * <ul> 089 * <li>GreatDeluge.CoolRate ... bound cooling rate (default 0.99999995) 090 * <li>GreatDeluge.UpperBoundRate ... bound upper bound relative to best 091 * solution ever found (default 1.05) 092 * <li>GreatDeluge.LowerBoundRate ... bound lower bound relative to best 093 * solution ever found (default 0.95) 094 * </ul> 095 * 096 * @param properties 097 * problem properties 098 */ 099 @SuppressWarnings("unchecked") 100 public ExamGreatDeluge(DataProperties properties) { 101 iCoolRate = properties.getPropertyDouble("GreatDeluge.CoolRate", iCoolRate); 102 iUpperBoundRate = properties.getPropertyDouble("GreatDeluge.UpperBoundRate", iUpperBoundRate); 103 iLowerBoundRate = properties.getPropertyDouble("GreatDeluge.LowerBoundRate", iLowerBoundRate); 104 iNeighbours = new NeighbourSelection[] { new ExamRandomMove(properties), new ExamRoomMove(properties), 105 new ExamTimeMove(properties) }; 106 } 107 108 /** Initialization */ 109 @Override 110 public void init(Solver<Exam, ExamPlacement> solver) { 111 iIter = -1; 112 solver.currentSolution().addSolutionListener(this); 113 for (int i = 0; i < iNeighbours.length; i++) 114 iNeighbours[i].init(solver); 115 solver.setUpdateProgress(false); 116 iProgress = Progress.getInstance(solver.currentSolution().getModel()); 117 } 118 119 /** Print some information */ 120 protected void info(Solution<Exam, ExamPlacement> solution) { 121 sLog.info("Iter=" + iIter / 1000 + "k, NonImpIter=" + sDF2.format((iIter - iLastImprovingIter) / 1000.0) 122 + "k, Speed=" + sDF2.format(1000.0 * iIter / (JProf.currentTimeMillis() - iT0)) + " it/s"); 123 sLog.info("Bound is " + sDF2.format(iBound) + ", " + "best value is " + sDF2.format(solution.getBestValue()) 124 + " (" + sDF2.format(100.0 * iBound / solution.getBestValue()) + "%), " + "current value is " 125 + sDF2.format(solution.getModel().getTotalValue()) + " (" 126 + sDF2.format(100.0 * iBound / solution.getModel().getTotalValue()) + "%), " + "#idle=" + iNrIdle 127 + ", " + "Pacc=" + sDF5.format(100.0 * iAcceptedMoves / iMoves) + "%"); 128 iAcceptedMoves = iMoves = 0; 129 } 130 131 /** 132 * Generate neighbour -- select neighbourhood randomly, select neighbour 133 */ 134 public Neighbour<Exam, ExamPlacement> genMove(Solution<Exam, ExamPlacement> solution) { 135 while (true) { 136 incIter(solution); 137 NeighbourSelection<Exam, ExamPlacement> ns = iNeighbours[ToolBox.random(iNeighbours.length)]; 138 Neighbour<Exam, ExamPlacement> n = ns.selectNeighbour(solution); 139 if (n != null) 140 return n; 141 } 142 } 143 144 /** Accept neighbour */ 145 protected boolean accept(Solution<Exam, ExamPlacement> solution, Neighbour<Exam, ExamPlacement> neighbour) { 146 return (neighbour.value() <= 0 || solution.getModel().getTotalValue() + neighbour.value() <= iBound); 147 } 148 149 /** Increment iteration count, update bound */ 150 protected void incIter(Solution<Exam, ExamPlacement> solution) { 151 if (iIter < 0) { 152 iIter = 0; 153 iLastImprovingIter = 0; 154 iT0 = JProf.currentTimeMillis(); 155 iBound = (solution.getBestValue() > 0.0 ? iUpperBoundRate * solution.getBestValue() : solution 156 .getBestValue() 157 / iUpperBoundRate); 158 iUpperBound = iBound; 159 iNrIdle = 0; 160 iProgress.setPhase("Great deluge [" + (1 + iNrIdle) + "]..."); 161 } else { 162 iIter++; 163 if (solution.getBestValue() >= 0.0) 164 iBound *= iCoolRate; 165 else 166 iBound /= iCoolRate; 167 } 168 if (iIter % 100000 == 0) { 169 info(solution); 170 } 171 double lowerBound = (solution.getBestValue() >= 0.0 ? Math.pow(iLowerBoundRate, 1 + iNrIdle) 172 * solution.getBestValue() : solution.getBestValue() / Math.pow(iLowerBoundRate, 1 + iNrIdle)); 173 if (iBound < lowerBound) { 174 iNrIdle++; 175 sLog.info(" -<[" + iNrIdle + "]>- "); 176 iBound = Math.max(solution.getBestValue() + 2.0, (solution.getBestValue() >= 0.0 ? Math.pow( 177 iUpperBoundRate, iNrIdle) 178 * solution.getBestValue() : solution.getBestValue() / Math.pow(iUpperBoundRate, iNrIdle))); 179 iUpperBound = iBound; 180 iProgress.setPhase("Great deluge [" + (1 + iNrIdle) + "]..."); 181 } 182 iProgress.setProgress(100 - Math.round(100.0 * (iBound - lowerBound) / (iUpperBound - lowerBound))); 183 } 184 185 /** 186 * A neighbour is generated randomly untill an acceptable one is found. 187 */ 188 @Override 189 public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) { 190 Neighbour<Exam, ExamPlacement> neighbour = null; 191 while ((neighbour = genMove(solution)) != null) { 192 iMoves++; 193 if (accept(solution, neighbour)) { 194 iAcceptedMoves++; 195 break; 196 } 197 } 198 return (neighbour == null ? null : neighbour); 199 } 200 201 /** Update last improving iteration count */ 202 @Override 203 public void bestSaved(Solution<Exam, ExamPlacement> solution) { 204 if (Math.abs(iBestValue - solution.getBestValue()) >= 1.0) { 205 iLastImprovingIter = iIter; 206 iNrIdle = 0; 207 iBestValue = solution.getBestValue(); 208 } 209 } 210 211 @Override 212 public void solutionUpdated(Solution<Exam, ExamPlacement> solution) { 213 } 214 215 @Override 216 public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info) { 217 } 218 219 @Override 220 public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info, Collection<Exam> variables) { 221 } 222 223 @Override 224 public void bestCleared(Solution<Exam, ExamPlacement> solution) { 225 } 226 227 @Override 228 public void bestRestored(Solution<Exam, ExamPlacement> solution) { 229 } 230 231 }