    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}