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.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 * @version ExamTT 1.3 (Examination Timetabling)<br>
046 *          Copyright (C) 2008 - 2014 Tomáš Müller<br>
047 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
048 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
049 * <br>
050 *          This library is free software; you can redistribute it and/or modify
051 *          it under the terms of the GNU Lesser General Public License as
052 *          published by the Free Software Foundation; either version 3 of the
053 *          License, or (at your option) any later version. <br>
054 * <br>
055 *          This library is distributed in the hope that it will be useful, but
056 *          WITHOUT ANY WARRANTY; without even the implied warranty of
057 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
058 *          Lesser General Public License for more details. <br>
059 * <br>
060 *          You should have received a copy of the GNU Lesser General Public
061 *          License along with this library; if not see
062 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
063 */
064@Deprecated
065public class ExamHillClimbing extends NeighbourSelectionWithContext<Exam, ExamPlacement, ExamHillClimbing.Context> implements SolutionListener<Exam, ExamPlacement>, LazyNeighbourAcceptanceCriterion<Exam, ExamPlacement> {
066    private static Logger sLog = Logger.getLogger(ExamHillClimbing.class);
067    private List<NeighbourSelection<Exam, ExamPlacement>> iNeighbours = null;
068    private int iMaxIdleIters = 25000;
069    private Progress iProgress = null;
070    private String iName = "Hill climbing";
071
072    /**
073     * Constructor
074     * 
075     * @param properties
076     *            problem properties (use HillClimber.MaxIdle to set maximum
077     *            number of idle iterations)
078     */
079    public ExamHillClimbing(DataProperties properties) {
080        this(properties, "Hill Climbing");
081    }
082
083    /**
084     * Constructor
085     * 
086     * @param properties
087     *            problem properties (use HillClimber.MaxIdle to set maximum
088     *            number of idle iterations)
089     * @param name solver search phase name
090     */
091    @SuppressWarnings("unchecked")
092    public ExamHillClimbing(DataProperties properties, String name) {
093        iMaxIdleIters = properties.getPropertyInt("HillClimber.MaxIdle", iMaxIdleIters);
094        String neighbours = properties.getProperty("HillClimber.Neighbours", 
095                ExamRandomMove.class.getName() + ";" +
096                ExamRoomMove.class.getName() + ";" +
097                ExamTimeMove.class.getName());
098        neighbours += ";" + properties.getProperty("HillClimber.AdditionalNeighbours", "");
099        iNeighbours = new ArrayList<NeighbourSelection<Exam,ExamPlacement>>();
100        for (String neighbour: neighbours.split("\\;")) {
101            if (neighbour == null || neighbour.isEmpty()) continue;
102            try {
103                Class<NeighbourSelection<Exam, ExamPlacement>> clazz = (Class<NeighbourSelection<Exam, ExamPlacement>>)Class.forName(neighbour);
104                iNeighbours.add(clazz.getConstructor(DataProperties.class).newInstance(properties));
105            } catch (Exception e) {
106                sLog.error("Unable to use " + neighbour + ": " + e.getMessage());
107            }
108        }
109        iName = name;
110    }
111
112    /**
113     * Initialization
114     */
115    @Override
116    public void init(Solver<Exam, ExamPlacement> solver) {
117        super.init(solver);
118        solver.currentSolution().addSolutionListener(this);
119        for (NeighbourSelection<Exam, ExamPlacement> neighbour: iNeighbours)
120            neighbour.init(solver);
121        solver.setUpdateProgress(false);
122        iProgress = Progress.getInstance(solver.currentSolution().getModel());
123        getContext(solver.currentSolution().getAssignment()).reset();
124    }
125
126    /**
127     * Select one of the given neighbourhoods randomly, select neighbour, return
128     * it if its value is below or equal to zero (continue with the next
129     * selection otherwise). Return null when the given number of idle
130     * iterations is reached.
131     */
132    @Override
133    public Neighbour<Exam, ExamPlacement> selectNeighbour(Solution<Exam, ExamPlacement> solution) {
134        Context context = getContext(solution.getAssignment());
135        context.activateIfNeeded();
136        while (true) {
137            if (context.incIter(solution)) break;
138            NeighbourSelection<Exam, ExamPlacement> ns = iNeighbours.get(ToolBox.random(iNeighbours.size()));
139            Neighbour<Exam, ExamPlacement> n = ns.selectNeighbour(solution);
140            if (n != null) {
141                if (n instanceof LazyNeighbour) {
142                    ((LazyNeighbour<Exam,ExamPlacement>)n).setAcceptanceCriterion(this);
143                    return n;
144                } else if (n.value(solution.getAssignment()) <= 0.0) return n;
145            }
146        }
147        context.reset();
148        return null;
149    }
150
151    /**
152     * Memorize the iteration when the last best solution was found.
153     */
154    @Override
155    public void bestSaved(Solution<Exam, ExamPlacement> solution) {
156        getContext(solution.getAssignment()).bestSaved(solution.getModel());
157    }
158
159    @Override
160    public void solutionUpdated(Solution<Exam, ExamPlacement> solution) {
161    }
162
163    @Override
164    public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info) {
165    }
166
167    @Override
168    public void getInfo(Solution<Exam, ExamPlacement> solution, Map<String, String> info, Collection<Exam> variables) {
169    }
170
171    @Override
172    public void bestCleared(Solution<Exam, ExamPlacement> solution) {
173    }
174
175    @Override
176    public void bestRestored(Solution<Exam, ExamPlacement> solution) {
177    }
178
179    /** Accept lazy neighbour */
180    @Override
181    public boolean accept(Assignment<Exam, ExamPlacement> assignment, LazyNeighbour<Exam, ExamPlacement> neighbour, double value) {
182        return value <= 0.0;
183    }
184
185    @Override
186    public Context createAssignmentContext(Assignment<Exam, ExamPlacement> assignment) {
187        return new Context();
188    }
189
190    public class Context implements AssignmentContext {
191        private int iLastImprovingIter = 0;
192        private double iBestValue = 0;
193        private int iIter = 0;
194        private boolean iActive;
195
196        protected void reset() {
197            iIter = 0;
198            iLastImprovingIter = 0;
199            iActive = false;
200        }
201
202        protected void activateIfNeeded() {
203            if (!iActive) {
204                iProgress.setPhase(iName + "...");
205                iActive = true;
206            }
207        }
208        
209        protected boolean incIter(Solution<Exam, ExamPlacement> solution) {
210            iIter++;
211            iProgress.setProgress(Math.round(100.0 * (iIter - iLastImprovingIter) / iMaxIdleIters));
212            if (iIter - iLastImprovingIter >= iMaxIdleIters) return true;
213            return false;
214        }
215        
216        protected void bestSaved(Model<Exam, ExamPlacement> model) {
217            if (Math.abs(iBestValue - model.getBestValue()) >= 1.0) {
218                iLastImprovingIter = iIter;
219                iBestValue = model.getBestValue();
220            }
221        }
222    }
223}