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