001package net.sf.cpsolver.ifs.algorithms;
002
003import java.text.DecimalFormat;
004import java.util.ArrayList;
005import java.util.Collection;
006import java.util.Iterator;
007import java.util.List;
008import java.util.Map;
009
010import org.apache.log4j.Logger;
011
012import net.sf.cpsolver.ifs.algorithms.neighbourhoods.HillClimberSelection;
013import net.sf.cpsolver.ifs.algorithms.neighbourhoods.RandomMove;
014import net.sf.cpsolver.ifs.algorithms.neighbourhoods.RandomSwapMove;
015import net.sf.cpsolver.ifs.algorithms.neighbourhoods.SuggestionMove;
016import net.sf.cpsolver.ifs.heuristics.NeighbourSelection;
017import net.sf.cpsolver.ifs.model.LazyNeighbour;
018import net.sf.cpsolver.ifs.model.Model;
019import net.sf.cpsolver.ifs.model.Neighbour;
020import net.sf.cpsolver.ifs.model.Value;
021import net.sf.cpsolver.ifs.model.Variable;
022import net.sf.cpsolver.ifs.model.LazyNeighbour.LazyNeighbourAcceptanceCriterion;
023import net.sf.cpsolver.ifs.solution.Solution;
024import net.sf.cpsolver.ifs.solution.SolutionListener;
025import net.sf.cpsolver.ifs.solver.Solver;
026import net.sf.cpsolver.ifs.util.DataProperties;
027import net.sf.cpsolver.ifs.util.JProf;
028import net.sf.cpsolver.ifs.util.Progress;
029import net.sf.cpsolver.ifs.util.ToolBox;
030
031/**
032 * Base class for the search techniques like hill climber, great deluge, or simulated annealing.
033 * It implements the {@link SolutionListener} and the variable neighbourhood selection.
034 * 
035 * <br>
036 * 
037 * @version IFS 1.2 (Iterative Forward Search)<br>
038 *          Copyright (C) 2014 Tomáš Müller<br>
039 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
040 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
041 * <br>
042 *          This library is free software; you can redistribute it and/or modify
043 *          it under the terms of the GNU Lesser General Public License as
044 *          published by the Free Software Foundation; either version 3 of the
045 *          License, or (at your option) any later version. <br>
046 * <br>
047 *          This library is distributed in the hope that it will be useful, but
048 *          WITHOUT ANY WARRANTY; without even the implied warranty of
049 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
050 *          Lesser General Public License for more details. <br>
051 * <br>
052 *          You should have received a copy of the GNU Lesser General Public
053 *          License along with this library; if not see
054 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
055 **/
056public abstract class NeighbourSearch<V extends Variable<V, T>, T extends Value<V, T>> implements NeighbourSelection<V, T>, SolutionListener<V, T>, LazyNeighbourAcceptanceCriterion<V, T> {
057    protected Logger iLog;
058    protected DecimalFormat iDF2 = new DecimalFormat("0.00");
059    
060    protected long iT0 = -1;
061    protected int iIter = 0;
062    protected String iPhase = null;
063    protected Progress iProgress = null;
064    
065    private List<NeighbourSelector<V, T>> iNeighbours = null;
066    private boolean iRandomSelection = false;
067    private boolean iUpdatePoints = false;
068    private double iTotalBonus;
069
070    @SuppressWarnings("unchecked")
071    public NeighbourSearch(DataProperties properties) {
072        iPhase = getClass().getSimpleName().replaceAll("(?<=[^A-Z])([A-Z])"," $1");
073        iLog = Logger.getLogger(getClass());
074        iRandomSelection = properties.getPropertyBoolean(getParameterBaseName() + ".Random", iRandomSelection);
075        iUpdatePoints = properties.getPropertyBoolean(getParameterBaseName() + ".Update", iUpdatePoints);
076        String neighbours = properties.getProperty(getParameterBaseName() + ".Neighbours",
077                RandomMove.class.getName() + ";" + RandomSwapMove.class.getName() + "@0.01;" + SuggestionMove.class.getName() + "@0.01");
078        neighbours += ";" + properties.getProperty(getParameterBaseName() + ".AdditionalNeighbours", "");
079        iNeighbours = new ArrayList<NeighbourSelector<V,T>>();
080        for (String neighbour: neighbours.split("\\;")) {
081            if (neighbour == null || neighbour.isEmpty()) continue;
082            try {
083                double bonus = 1.0;
084                if (neighbour.indexOf('@')>=0) {
085                    bonus = Double.parseDouble(neighbour.substring(neighbour.indexOf('@') + 1));
086                    neighbour = neighbour.substring(0, neighbour.indexOf('@'));
087                }
088                Class<NeighbourSelection<V, T>> clazz = (Class<NeighbourSelection<V, T>>)Class.forName(neighbour);
089                NeighbourSelection<V, T> selection = clazz.getConstructor(DataProperties.class).newInstance(properties);
090                addNeighbourSelection(selection, bonus);
091            } catch (Exception e) {
092                iLog.error("Unable to use " + neighbour + ": " + e.getMessage());
093            }
094        }
095    }
096    
097    /**
098     * Add neighbour selection
099     * @param bonus execution bonus (more bonus means more executions of this neighbour selection, see {@link NeighbourSelector})
100     */
101    protected void addNeighbourSelection(NeighbourSelection<V,T> ns, double bonus) {
102        iNeighbours.add(new NeighbourSelector<V,T>(ns, bonus, iUpdatePoints));
103    }
104    
105    private double totalPoints() {
106        if (!iUpdatePoints) return iTotalBonus;
107        double total = 0;
108        for (NeighbourSelector<V,T> ns: iNeighbours)
109            total += ns.getPoints();
110        return total;
111    }
112    
113    /**
114     * Set HC mode for all the neighbour selections that support the {@link HillClimberSelection} interface. 
115     */
116    protected void setHCMode(boolean hcMode) {
117        for (NeighbourSelector<V,T> s: iNeighbours) {
118            if (s.selection() instanceof HillClimberSelection)
119                ((HillClimberSelection)s.selection()).setHcMode(hcMode);
120        }
121    }
122    
123    /**
124     * Return list of neighbour selections
125     * @return
126     */
127    protected List<? extends NeighbourSelection<V, T>> getNeighbours() {
128        return iNeighbours;
129    }
130
131    @Override
132    public void init(Solver<V, T> solver) {
133        iProgress = Progress.getInstance(solver.currentSolution().getModel());
134        iT0 = -1;
135        solver.currentSolution().addSolutionListener(this);
136        solver.setUpdateProgress(false);
137        for (NeighbourSelection<V, T> neighbour: iNeighbours)
138            neighbour.init(solver);
139        solver.setUpdateProgress(false);
140        iTotalBonus = 0;
141        for (NeighbourSelector<V,T> s: iNeighbours) {
142            s.init(solver);
143            iTotalBonus += s.getBonus();
144        }
145    }
146    
147    /**
148     * Generate and return next neighbour selection
149     */
150    protected NeighbourSelection<V,T> nextNeighbourSelection() {
151        NeighbourSelector<V,T> ns = null;
152        if (iRandomSelection) {
153            ns = ToolBox.random(iNeighbours);
154        } else {
155            double points = (ToolBox.random() * totalPoints());
156            for (Iterator<NeighbourSelector<V,T>> i = iNeighbours.iterator(); i.hasNext(); ) {
157                ns = i.next();
158                points -= (iUpdatePoints ? ns.getPoints() : ns.getBonus());
159                if (points <= 0) break;
160            }
161        }
162        return ns;
163    }
164    
165    /**
166     * Log some information about neigbour selections once in a while
167     */
168    protected void logNeibourStatus() {
169        if (iUpdatePoints)
170            for (NeighbourSelector<V,T> ns: iNeighbours)
171                iLog.info("  "+ns+" ("+iDF2.format(ns.getPoints())+" pts, "+iDF2.format(100.0*(iUpdatePoints?ns.getPoints():ns.getBonus())/totalPoints())+"%)");
172    }
173
174    /**
175     * Generate a random move
176     */
177    public Neighbour<V, T> generateMove(Solution<V, T> solution) {
178        return nextNeighbourSelection().selectNeighbour(solution);
179    }
180
181    @Override
182    public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) {
183        if (iT0 < 0) activate(solution);
184        while (canContinue(solution)) {
185            incIteration(solution);
186            Neighbour<V,T> n = generateMove(solution);
187            if (n != null && accept(solution, n))
188                return n;
189        }
190        deactivate(solution);
191        return null;
192    }
193    
194    /**
195     * Return false if the search is to be stopped. Null neighbour is returned when this method returns false.
196     */
197    protected boolean canContinue(Solution<V, T> solution) {
198        return true;
199    }
200    
201    /**
202     * Increment iteration counters etc.
203     */
204    protected void incIteration(Solution<V, T> solution) {
205        iIter++;
206    }
207
208    /**
209     * Running time in milliseconds (since the last call of activate)
210     */
211    protected long getTimeMillis() { return JProf.currentTimeMillis() - iT0; }
212    
213    /**
214     * True if the generated move is to be accepted.
215     */
216    protected boolean accept(Solution<V, T> solution, Neighbour<V, T> neighbour) {
217        if (neighbour instanceof LazyNeighbour) {
218            ((LazyNeighbour<V, T>)neighbour).setAcceptanceCriterion(this);
219            return true;
220        }
221        return accept(solution.getModel(), neighbour, neighbour.value(), false);
222    }
223    
224    /** Accept lazy neighbour -- calling the acceptance criterion with lazy = true. */
225    @Override
226    public boolean accept(LazyNeighbour<V, T> neighbour, double value) {
227        return accept(neighbour.getModel(), neighbour, value, true);
228    }
229
230    /** Acceptance criterion. If lazy, current assignment already contains the given neighbour.  */
231    protected abstract boolean accept(Model<V, T> model, Neighbour<V, T> neighbour, double value, boolean lazy);
232    
233    /** Called just before the neighbourhood search is called for the first time. */
234    protected void activate(Solution<V, T> solution) {
235        iT0 = JProf.currentTimeMillis();
236        iIter = 0;
237        iProgress.setPhase(iPhase + "...");
238    }
239    
240    /** Called when the search cannot continue, just before a null neighbour is returned */
241    protected void deactivate(Solution<V, T> solution) {
242        iT0 = -1;
243    }
244
245    /**
246     * Parameter base name. This can be used to distinguish between parameters of different search algorithms.
247     */
248    public abstract String getParameterBaseName();
249    
250    @Override
251    public void bestSaved(Solution<V, T> solution) {
252    }
253
254    @Override
255    public void solutionUpdated(Solution<V, T> solution) {
256    }
257
258    @Override
259    public void getInfo(Solution<V, T> solution, Map<String, String> info) {
260    }
261
262    @Override
263    public void getInfo(Solution<V, T> solution, Map<String, String> info, Collection<V> variables) {
264    }
265
266    @Override
267    public void bestCleared(Solution<V, T> solution) {
268    }
269
270    @Override
271    public void bestRestored(Solution<V, T> solution) {
272    }
273
274}