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