    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}