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