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