001package org.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;
011import org.cpsolver.ifs.algorithms.neighbourhoods.HillClimberSelection;
012import org.cpsolver.ifs.algorithms.neighbourhoods.RandomMove;
013import org.cpsolver.ifs.algorithms.neighbourhoods.RandomSwapMove;
014import org.cpsolver.ifs.algorithms.neighbourhoods.SuggestionMove;
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.Value;
023import org.cpsolver.ifs.model.Variable;
024import org.cpsolver.ifs.model.LazyNeighbour.LazyNeighbourAcceptanceCriterion;
025import org.cpsolver.ifs.solution.Solution;
026import org.cpsolver.ifs.solution.SolutionListener;
027import org.cpsolver.ifs.solver.Solver;
028import org.cpsolver.ifs.util.DataProperties;
029import org.cpsolver.ifs.util.JProf;
030import org.cpsolver.ifs.util.Progress;
031import org.cpsolver.ifs.util.ToolBox;
032
033
034/**
035 * Base class for the search techniques like hill climber, great deluge, or simulated annealing.
036 * It implements the {@link SolutionListener} and the variable neighbourhood selection.
037 * 
038 * <br>
039 * 
040 * @version IFS 1.3 (Iterative Forward Search)<br>
041 *          Copyright (C) 2014 Tomáš Müller<br>
042 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
043 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
044 * <br>
045 *          This library is free software; you can redistribute it and/or modify
046 *          it under the terms of the GNU Lesser General Public License as
047 *          published by the Free Software Foundation; either version 3 of the
048 *          License, or (at your option) any later version. <br>
049 * <br>
050 *          This library is distributed in the hope that it will be useful, but
051 *          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. <br>
054 * <br>
055 *          You should have received a copy of the GNU Lesser General Public
056 *          License along with this library; if not see
057 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
058 * @param <V> Variable
059 * @param <T> Value
060 **/
061public abstract class NeighbourSearch<V extends Variable<V, T>, T extends Value<V, T>> extends NeighbourSelectionWithContext<V, T, NeighbourSearch<V, T>.NeighbourSearchContext> implements LazyNeighbourAcceptanceCriterion<V, T>, SolutionListener<V, T> {
062    private Logger iLog;
063    protected DecimalFormat iDF2 = new DecimalFormat("0.00");
064    
065    private Progress iProgress = null;
066    protected String iPhase = null;
067
068    private List<NeighbourSelector<V, T>> iNeighbours = null;
069    private boolean iRandomSelection = false;
070    private boolean iUpdatePoints = false;
071    private double iTotalBonus;
072    private Solver<V, T> iSolver = null;
073
074    @SuppressWarnings("unchecked")
075    public NeighbourSearch(DataProperties properties) {
076        iPhase = getClass().getSimpleName().replaceAll("(?<=[^A-Z])([A-Z])"," $1");
077        iLog = Logger.getLogger(getClass());
078        iRandomSelection = properties.getPropertyBoolean(getParameterBaseName() + ".Random", iRandomSelection);
079        iUpdatePoints = properties.getPropertyBoolean(getParameterBaseName() + ".Update", iUpdatePoints);
080        String neighbours = properties.getProperty(getParameterBaseName() + ".Neighbours",
081                RandomMove.class.getName() + ";" + RandomSwapMove.class.getName() + "@0.01;" + SuggestionMove.class.getName() + "@0.01");
082        neighbours += ";" + properties.getProperty(getParameterBaseName() + ".AdditionalNeighbours", "");
083        iNeighbours = new ArrayList<NeighbourSelector<V,T>>();
084        for (String neighbour: neighbours.split("\\;")) {
085            if (neighbour == null || neighbour.isEmpty()) continue;
086            try {
087                double bonus = 1.0;
088                if (neighbour.indexOf('@')>=0) {
089                    bonus = Double.parseDouble(neighbour.substring(neighbour.indexOf('@') + 1));
090                    neighbour = neighbour.substring(0, neighbour.indexOf('@'));
091                }
092                Class<NeighbourSelection<V, T>> clazz = (Class<NeighbourSelection<V, T>>)Class.forName(neighbour);
093                NeighbourSelection<V, T> selection = clazz.getConstructor(DataProperties.class).newInstance(properties);
094                addNeighbourSelection(selection, bonus);
095            } catch (Exception e) {
096                iLog.error("Unable to use " + neighbour + ": " + e.getMessage());
097            }
098        }
099    }
100    
101    /**
102     * Prints a message into the log
103     * @param message a message to log
104     */
105    protected void info(String message) {
106        iProgress.debug("[" + Thread.currentThread().getName() + "] " + iPhase + "> " + message);
107    }
108    
109    /**
110     * Set search progress
111     * @param progress between 0 and 100
112     */
113    protected void setProgress(long progress) {
114        // iProgress.setProgress(progress);
115    }
116    
117    /**
118     * Set search progress phase
119     * @param phase a progress phase to set
120     */
121    protected void setProgressPhase(String phase) {
122        iProgress.info("[" + Thread.currentThread().getName() + "] " + phase);
123        // iProgress.setPhase(phase);
124    }
125    
126    /**
127     * Add neighbour selection
128     * @param ns a selection
129     * @param bonus execution bonus (more bonus means more executions of this neighbour selection, see {@link NeighbourSelector})
130     */
131    protected void addNeighbourSelection(NeighbourSelection<V,T> ns, double bonus) {
132        iNeighbours.add(new NeighbourSelector<V,T>(ns, bonus, iUpdatePoints));
133    }
134    
135    private double totalPoints() {
136        if (!iUpdatePoints) return iTotalBonus;
137        double total = 0;
138        for (NeighbourSelector<V,T> ns: iNeighbours)
139            total += ns.getPoints();
140        return total;
141    }
142    
143    /**
144     * Set HC mode for all the neighbour selections that support the {@link HillClimberSelection} interface. 
145     * @param hcMode true if the search is a hill climber (worsening moves are always rejected)
146     */
147    protected void setHCMode(boolean hcMode) {
148        for (NeighbourSelector<V,T> s: iNeighbours) {
149            if (s.selection() instanceof HillClimberSelection)
150                ((HillClimberSelection)s.selection()).setHcMode(hcMode);
151        }
152    }
153    
154    /**
155     * Return list of neighbour selections
156     * @return list of neighbour selections
157     */
158    protected List<? extends NeighbourSelection<V, T>> getNeighbours() {
159        return iNeighbours;
160    }
161
162    @Override
163    public void init(Solver<V, T> solver) {
164        super.init(solver);
165        iProgress = Progress.getInstance(solver.currentSolution().getModel());
166        iSolver = solver;
167        solver.currentSolution().addSolutionListener(this);
168        // solver.setUpdateProgress(false);
169        for (NeighbourSelection<V, T> neighbour: iNeighbours)
170            neighbour.init(solver);
171        iTotalBonus = 0;
172        for (NeighbourSelector<V,T> s: iNeighbours) {
173            s.init(solver);
174            iTotalBonus += s.getBonus();
175        }
176    }
177    
178    /**
179     * Generate and return next neighbour selection
180     * @return next neighbour selection to use
181     */
182    protected NeighbourSelection<V,T> nextNeighbourSelection() {
183        NeighbourSelector<V,T> ns = null;
184        if (iRandomSelection) {
185            ns = ToolBox.random(iNeighbours);
186        } else {
187            double points = (ToolBox.random() * totalPoints());
188            for (Iterator<NeighbourSelector<V,T>> i = iNeighbours.iterator(); i.hasNext(); ) {
189                ns = i.next();
190                points -= (iUpdatePoints ? ns.getPoints() : ns.getBonus());
191                if (points <= 0) break;
192            }
193        }
194        return ns;
195    }
196    
197    /**
198     * Log some information about neigbour selections once in a while
199     */
200    protected void logNeibourStatus() {
201        if (iUpdatePoints)
202            for (NeighbourSelector<V,T> ns: iNeighbours)
203                iLog.info("  "+ns+" ("+iDF2.format(ns.getPoints())+" pts, "+iDF2.format(100.0*(iUpdatePoints?ns.getPoints():ns.getBonus())/totalPoints())+"%)");
204    }
205
206    /**
207     * Generate a random move
208     * @param solution current solution
209     * @return generated neighbour
210     */
211    public Neighbour<V, T> generateMove(Solution<V, T> solution) {
212        return nextNeighbourSelection().selectNeighbour(solution);
213    }
214
215    @Override
216    public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) {
217        NeighbourSearchContext context = getContext(solution.getAssignment());
218        context.activateIfNeeded(solution);
219        while (context.canContinue(solution)) {
220            if (iSolver != null && iSolver.isStop()) return null;
221            context.incIteration(solution);
222            Neighbour<V,T> n = generateMove(solution);
223            if (n != null && accept(context, solution, n))
224                return n;
225        }
226        context.deactivateIfNeeded(solution);
227        return null;
228    }
229    
230    /**
231     * True if the generated move is to be accepted.
232     * @param context search context
233     * @param solution current solution
234     * @param neighbour a generated move
235     * @return true if the generated move should be assigned
236     */
237    protected boolean accept(NeighbourSearchContext context, Solution<V, T> solution, Neighbour<V, T> neighbour) {
238        if (neighbour instanceof LazyNeighbour) {
239            ((LazyNeighbour<V, T>)neighbour).setAcceptanceCriterion(this);
240            return true;
241        }
242        return context.accept(solution.getAssignment(), solution.getModel(), neighbour, neighbour.value(solution.getAssignment()), false);
243    }
244    
245    /** Accept lazy neighbour -- calling the acceptance criterion with lazy = true. */
246    @Override
247    public boolean accept(Assignment<V, T> assignment, LazyNeighbour<V, T> neighbour, double value) {
248        return getContext(assignment).accept(assignment, neighbour.getModel(), neighbour, value, true);
249    }
250
251    /**
252     * Parameter base name. This can be used to distinguish between parameters of different search algorithms.
253     * @return solver parameter base name for this search technique
254     */
255    public abstract String getParameterBaseName();
256    
257    @Override
258    public void bestSaved(Solution<V, T> solution) {
259        getContext(solution.getAssignment()).bestSaved(solution);
260    }
261
262    @Override
263    public void solutionUpdated(Solution<V, T> solution) {
264        getContext(solution.getAssignment()).solutionUpdated(solution);
265    }
266
267    @Override
268    public void getInfo(Solution<V, T> solution, Map<String, String> info) {
269        getContext(solution.getAssignment()).getInfo(solution, info);
270    }
271
272    @Override
273    public void getInfo(Solution<V, T> solution, Map<String, String> info, Collection<V> variables) {
274        getContext(solution.getAssignment()).getInfo(solution, info, variables);
275    }
276
277    @Override
278    public void bestCleared(Solution<V, T> solution) {
279        getContext(solution.getAssignment()).bestCleared(solution);
280    }
281
282    @Override
283    public void bestRestored(Solution<V, T> solution) {
284        getContext(solution.getAssignment()).bestRestored(solution);
285    }
286    
287    /**
288     * In single solution multiple threads environments return true if the given solution is of the first thread
289     * @param solution current solution
290     * @return if the current thread is master (can alter bound etc.)
291     */
292    public boolean isMaster(Solution<V, T> solution) {
293        return !hasContextOverride() || solution.getAssignment().getIndex() <= 1;
294    }
295    
296    /**
297     * Search context
298     */
299    public abstract class NeighbourSearchContext implements AssignmentContext, SolutionListener<V, T> {
300        protected long iT0 = -1;
301        protected int iIter = 0;
302
303        /** Called just before the neighbourhood search is called for the first time. 
304         * @param solution current solution
305         **/
306        protected void activate(Solution<V, T> solution) {
307            iT0 = JProf.currentTimeMillis();
308            iIter = 0;
309            setProgressPhase(iPhase + "...");
310        }
311        
312        private synchronized void activateIfNeeded(Solution<V, T> solution) {
313            if (iT0 < 0) activate(solution);
314        }
315        
316        /** Called when the search cannot continue, just before a null neighbour is returned 
317         * @param solution current solution
318         **/
319        protected void deactivate(Solution<V, T> solution) {
320            iT0 = -1;
321        }
322        
323        private synchronized void deactivateIfNeeded(Solution<V, T> solution) {
324            if (isMaster(solution)) deactivate(solution);
325        }
326        
327        /**
328         * Increment iteration counters etc.
329         * @param solution current solution
330         */
331        protected void incIteration(Solution<V, T> solution) {
332            iIter++;
333        }
334
335        /**
336         * Running time in milliseconds (since the last call of activate)
337         * @return running time
338         */
339        protected long getTimeMillis() { return JProf.currentTimeMillis() - iT0; }
340
341        /**
342         * Return false if the search is to be stopped. Null neighbour is returned when this method returns false.
343         * @param solution current solution
344         * @return true if can continue
345         */
346        protected boolean canContinue(Solution<V, T> solution) {
347            return true;
348        }
349        
350        /** Acceptance criterion. If lazy, current assignment already contains the given neighbour.  
351         * @param assignment current assignment
352         * @param model problem model
353         * @param neighbour a generated move
354         * @param value value of the generated move (i.e., its impact on the solution value)
355         * @param lazy true if lazy move
356         * @return true if the generated move is to be assigned 
357         **/
358        protected abstract boolean accept(Assignment<V, T> assignment, Model<V, T> model, Neighbour<V, T> neighbour, double value, boolean lazy);
359        
360        @Override
361        public void bestSaved(Solution<V, T> solution) {
362        }
363
364        @Override
365        public void solutionUpdated(Solution<V, T> solution) {
366        }
367
368        @Override
369        public void getInfo(Solution<V, T> solution, Map<String, String> info) {
370        }
371
372        @Override
373        public void getInfo(Solution<V, T> solution, Map<String, String> info, Collection<V> variables) {
374        }
375
376        @Override
377        public void bestCleared(Solution<V, T> solution) {
378        }
379
380        @Override
381        public void bestRestored(Solution<V, T> solution) {
382        }
383    }
384}