001 package net.sf.cpsolver.exam.heuristics; 002 003 import java.util.Collection; 004 import java.util.Map; 005 006 import net.sf.cpsolver.exam.model.Exam; 007 import net.sf.cpsolver.exam.model.ExamPlacement; 008 import net.sf.cpsolver.exam.neighbours.ExamRandomMove; 009 import net.sf.cpsolver.exam.neighbours.ExamRoomMove; 010 import net.sf.cpsolver.exam.neighbours.ExamSimpleNeighbour; 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.Progress; 019 import net.sf.cpsolver.ifs.util.ToolBox; 020 021 /** 022 * Hill climber. In each iteration, one of the following three neighbourhoods is 023 * selected first 024 * <ul> 025 * <li>random move ({@link ExamRandomMove}) 026 * <li>period swap ({@link ExamTimeMove}) 027 * <li>room swap ({@link ExamRoomMove}) 028 * </ul> 029 * , then a neighbour is generated and it is accepted if its value 030 * {@link ExamSimpleNeighbour#value()} is below or equal to zero. The search is 031 * stopped after a given amount of idle iterations ( can be defined by problem 032 * property HillClimber.MaxIdle). <br> 033 * <br> 034 * 035 * @version ExamTT 1.2 (Examination Timetabling)<br> 036 * Copyright (C) 2008 - 2010 Tomas Muller<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 */ 054 public class ExamHillClimbing implements NeighbourSelection<Exam, ExamPlacement>, SolutionListener<Exam, ExamPlacement> { 055 private NeighbourSelection<Exam, ExamPlacement>[] iNeighbours = null; 056 private int iMaxIdleIters = 25000; 057 private int iLastImprovingIter = 0; 058 private double iBestValue = 0; 059 private int iIter = 0; 060 private Progress iProgress = null; 061 private boolean iActive; 062 private String iName = "Hill climbing"; 063 064 /** 065 * Constructor 066 * 067 * @param properties 068 * problem properties (use HillClimber.MaxIdle to set maximum 069 * number of idle iterations) 070 */ 071 public ExamHillClimbing(DataProperties properties) { 072 this(properties, "Hill Climbing"); 073 } 074 075 /** 076 * Constructor 077 * 078 * @param properties 079 * problem properties (use HillClimber.MaxIdle to set maximum 080 * number of idle iterations) 081 */ 082 @SuppressWarnings("unchecked") 083 public ExamHillClimbing(DataProperties properties, String name) { 084 iMaxIdleIters = properties.getPropertyInt("HillClimber.MaxIdle", iMaxIdleIters); 085 iNeighbours = new NeighbourSelection[] { new ExamRandomMove(properties), new ExamRoomMove(properties), 086 new ExamTimeMove(properties) }; 087 iName = name; 088 } 089 090 /** 091 * Initialization 092 */ 093 @Override 094 public void init(Solver<Exam, ExamPlacement> solver) { 095 solver.currentSolution().addSolutionListener(this); 096 for (int i = 0; i < iNeighbours.length; i++) 097 iNeighbours[i].init(solver); 098 solver.setUpdateProgress(false); 099 iProgress = Progress.getInstance(solver.currentSolution().getModel()); 100 iActive = false; 101 } 102 103 /** 104 * Select one of the given neighbourhoods randomly, select neighbour, return 105 * it if its value is below or equal to zero (continue with the next 106 * selection otherwise). Return null when the given number of idle 107 * iterations is reached. 108 */ 109 @Override 110 public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) { 111 if (!iActive) { 112 iProgress.setPhase(iName + "..."); 113 iActive = true; 114 } 115 while (true) { 116 iIter++; 117 iProgress.setProgress(Math.round(100.0 * (iIter - iLastImprovingIter) / iMaxIdleIters)); 118 if (iIter - iLastImprovingIter >= iMaxIdleIters) 119 break; 120 NeighbourSelection<Exam, ExamPlacement> ns = iNeighbours[ToolBox.random(iNeighbours.length)]; 121 Neighbour<Exam, ExamPlacement> n = ns.selectNeighbour(solution); 122 if (n != null && n.value() <= 0) 123 return n; 124 } 125 iIter = 0; 126 iLastImprovingIter = 0; 127 iActive = false; 128 return null; 129 } 130 131 /** 132 * Memorize the iteration when the last best solution was found. 133 */ 134 @Override 135 public void bestSaved(Solution<Exam, ExamPlacement> solution) { 136 if (Math.abs(iBestValue - solution.getBestValue()) >= 1.0) { 137 iLastImprovingIter = iIter; 138 iBestValue = solution.getBestValue(); 139 } 140 } 141 142 @Override 143 public void solutionUpdated(Solution<Exam, ExamPlacement> solution) { 144 } 145 146 @Override 147 public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info) { 148 } 149 150 @Override 151 public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info, Collection<Exam> variables) { 152 } 153 154 @Override 155 public void bestCleared(Solution<Exam, ExamPlacement> solution) { 156 } 157 158 @Override 159 public void bestRestored(Solution<Exam, ExamPlacement> solution) { 160 } 161 }