    001package org.cpsolver.ifs.algorithms;
    002
    003import java.util.ArrayList;
    004import java.util.List;
    005
    006import org.apache.log4j.Logger;
    007import org.cpsolver.ifs.assignment.Assignment;
    008import org.cpsolver.ifs.assignment.context.AssignmentContext;
    009import org.cpsolver.ifs.assignment.context.NeighbourSelectionWithContext;
    010import org.cpsolver.ifs.heuristics.NeighbourSelection;
    011import org.cpsolver.ifs.heuristics.StandardNeighbourSelection;
    012import org.cpsolver.ifs.model.Neighbour;
    013import org.cpsolver.ifs.model.Value;
    014import org.cpsolver.ifs.model.Variable;
    015import org.cpsolver.ifs.solution.Solution;
    016import org.cpsolver.ifs.solver.Solver;
    017import org.cpsolver.ifs.util.DataProperties;
    018import org.cpsolver.ifs.util.Progress;
    019
    020/**
    021 * Meta-heuristic search neighbor selection. <br>
    022 * <br>
    023 * It consists of the following (up to four) phases:
    024 * <ul>
    025 * <li>Construction phase until the construction neighbor selection is not exhausted (i.e., null is returned as the next neighbor),
    026 * <li>Incomplete phase (e.g., {@link StandardNeighbourSelection}) until all variables are assigned (this heuristics is also used whenever the solution becomes incomplete, until it is complete again),
    027 * <li>Hill-climbing phase (e.g., {@link HillClimber}) until the given number if idle iterations (this phase is optional)
    028 * <li>Improvement phase (e.g., {@link GreatDeluge} or {@link SimulatedAnnealing}) until timeout is reached
    029 * </ul>
    030 * The search is based on the {@link SimpleSearch}, however each phase can be customized by providing the appropriate neighbor selection.
    031 * Also, a different selection can be used in each thread.
    032 * <br>
    033 * <br>
    034 *
    035 * @version IFS 1.3 (Iterative Forward Search)<br>
    036 *          Copyright (C) 2014 Tomáš Müller<br>
    037 *          <a href="mailto:muller@unitime.org">muller@unitime.org</a><br>
    038 *          <a href="http://muller.unitime.org">http://muller.unitime.org</a><br>
    039 * <br>
    040 *          This library is free software; you can redistribute it and/or modify
    041 *          it under the terms of the GNU Lesser General Public License as
    042 *          published by the Free Software Foundation; either version 3 of the
    043 *          License, or (at your option) any later version. <br>
    044 * <br>
    045 *          This library is distributed in the hope that it will be useful, but
    046 *          WITHOUT ANY WARRANTY; without even the implied warranty of
    047 *          MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
    048 *          Lesser General Public License for more details. <br>
    049 * <br>
    050 *          You should have received a copy of the GNU Lesser General Public
    051 *          License along with this library; if not see
    052 *          <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>.
    053 * @param <V> Variable
    054 * @param <T> Value
    055 */
    056public class MetaHeuristicSearch<V extends Variable<V, T>, T extends Value<V, T>> extends NeighbourSelectionWithContext<V,T,MetaHeuristicSearch<V,T>.MetaHeuristicSearchContext> {
    057    private Logger iLog = Logger.getLogger(SimpleSearch.class);
    058    private List<NeighbourSelection<V, T>> iConstructionPhase = new ArrayList<NeighbourSelection<V,T>>();
    059    private List<NeighbourSelection<V, T>> iIncompletePhase = new ArrayList<NeighbourSelection<V,T>>();
    060    private List<NeighbourSelection<V, T>> iHillClimberPhase = new ArrayList<NeighbourSelection<V,T>>();
    061    private List<NeighbourSelection<V, T>> iImprovementPhase = new ArrayList<NeighbourSelection<V,T>>();
    062    private Progress iProgress = null;
    063
    064    /**
    065     * Constructor
    066     * <ul>
    067     * <li>MetaHeuristic.ConstructionClass ... construction heuristics (if needed)
    068     * <li>MetaHeuristic.IncompleteClass ... incomplete heuristics (e.g., {@link StandardNeighbourSelection})
    069     * <li>MetaHeuristic.HillClimberClass ... hill-climber heuristics (e.g., {@link HillClimber} or {@link StepCountingHillClimber})
    070     * <li>MetaHeuristic.ImprovementClass ... improvement heuristics (e.g., {@link SimulatedAnnealing} or {@link GreatDeluge})
    071     * </ul>
    072     * @param properties problem configuration
    073     */
    074    public MetaHeuristicSearch(DataProperties properties) {
    075        String constructions = properties.getProperty("MetaHeuristic.ConstructionClass");
    076        if (constructions != null) {
    077            for (String construction: constructions.split(",")) {
    078                try {
    079                    boolean pc = false;
    080                    if (construction.endsWith("@PC")) {
    081                        pc = true;
    082                        construction = construction.substring(0, construction.length() - 3);
    083                    }
    084                    if (construction.isEmpty() || "null".equalsIgnoreCase(construction)) {
    085                        iConstructionPhase.add(null);
    086                        continue;
    087                    }
    088                    @SuppressWarnings("unchecked")
    089                    Class<NeighbourSelection<V, T>> constructionClass = (Class<NeighbourSelection<V, T>>)Class.forName(construction);
    090                    NeighbourSelection<V, T> constructionSelection = constructionClass.getConstructor(DataProperties.class).newInstance(properties);
    091                    if (pc) {
    092                        constructionSelection = new ParallelConstruction<V, T>(properties, constructionSelection);
    093                    }
    094                    iConstructionPhase.add(constructionSelection);
    095                } catch (Exception e) {
    096                    iLog.error("Unable to use " + construction + ": " + e.getMessage());
    097                }
    098            }
    099        }
    100        String incompletes = properties.getProperty("MetaHeuristic.IncompleteClass");
    101        if (incompletes != null) {
    102            for (String incomplete: incompletes.split(",")) {
    103                try {
    104                    boolean pc = false;
    105                    if (incomplete.endsWith("@PC")) {
    106                        pc = true;
    107                        incomplete = incomplete.substring(0, incomplete.length() - 3);
    108                    }
    109                    if (incomplete.isEmpty() || "null".equalsIgnoreCase(incomplete)) {
    110                        iIncompletePhase.add(null);
    111                        continue;
    112                    }
    113                    @SuppressWarnings("unchecked")
    114                    Class<NeighbourSelection<V, T>> incompleteClass = (Class<NeighbourSelection<V, T>>)Class.forName(incomplete);
    115                    NeighbourSelection<V, T> incompleteSelection = incompleteClass.getConstructor(DataProperties.class).newInstance(properties);
    116                    if (pc) {
    117                        incompleteSelection = new ParallelConstruction<V, T>(properties, incompleteSelection);
    118                    }
    119                    iIncompletePhase.add(incompleteSelection);
    120                } catch (Exception e) {
    121                    iLog.error("Unable to use " + incomplete + ": " + e.getMessage());
    122                }
    123            }
    124        }
    125        String hillClimbers = properties.getProperty("MetaHeuristic.HillClimberClass");
    126        if (hillClimbers != null) {
    127            for (String hillClimber: hillClimbers.split(",")) {
    128                try {
    129                    if (hillClimber.isEmpty() || "null".equalsIgnoreCase(hillClimber)) {
    130                        iHillClimberPhase.add(null);
    131                        continue;
    132                    }
    133                    @SuppressWarnings("unchecked")
    134                    Class<NeighbourSelection<V, T>> hillClimberClass = (Class<NeighbourSelection<V, T>>)Class.forName(hillClimber);
    135                    NeighbourSelection<V, T> hillClimberSelection = hillClimberClass.getConstructor(DataProperties.class).newInstance(properties);
    136                    iHillClimberPhase.add(hillClimberSelection);
    137                } catch (Exception e) {
    138                    iLog.error("Unable to use " + hillClimber + ": " + e.getMessage());
    139                }
    140            }
    141        }
    142        String improvements = properties.getProperty("MetaHeuristic.ImprovementClass");
    143        if (improvements != null) {
    144            for (String improvement: improvements.split(",")) {
    145                try {
    146                    if (improvement.isEmpty() || "null".equalsIgnoreCase(improvement)) {
    147                        iImprovementPhase.add(null);
    148                        continue;
    149                    }
    150                    @SuppressWarnings("unchecked")
    151                    Class<NeighbourSelection<V, T>> improvementClass = (Class<NeighbourSelection<V, T>>)Class.forName(improvement);
    152                    NeighbourSelection<V, T> improvementSelection = improvementClass.getConstructor(DataProperties.class).newInstance(properties);
    153                    iImprovementPhase.add(improvementSelection);
    154                } catch (Exception e) {
    155                    iLog.error("Unable to use " + improvement + ": " + e.getMessage());
    156                }
    157            }
    158        }
    159    }
    160
    161    private String getName(NeighbourSelection<V, T> selection) {
    162        return selection.getClass().getSimpleName().replaceAll("(?<=[^A-Z])([A-Z])"," $1");
    163    }
    164
    165    /**
    166     * Initialization
    167     */
    168    @Override
    169    public void init(Solver<V, T> solver) {
    170        super.init(solver);
    171        for (NeighbourSelection<V, T> ns: iConstructionPhase)
    172            if (ns != null) ns.init(solver);
    173        for (NeighbourSelection<V, T> ns: iIncompletePhase)
    174            if (ns != null) ns.init(solver);
    175        for (NeighbourSelection<V, T> ns: iHillClimberPhase)
    176            if (ns != null) ns.init(solver);
    177        for (NeighbourSelection<V, T> ns: iImprovementPhase)
    178            if (ns != null) ns.init(solver);
    179        iProgress = Progress.getInstance(solver.currentSolution().getModel());
    180    }
    181
    182    /**
    183     * Neighbour selection. It consists of the following phases:
    184     * <ul>
    185     * <li>Construction phase until the construction neighbor selection is not exhausted (i.e., null is returned as the next neighbor),
    186     * <li>Incomplete phase (e.g., {@link StandardNeighbourSelection}) until all variables are assigned (this heuristics is also used whenever the solution becomes incomplete, until it is complete again),
    187     * <li>Hill-climbing phase (e.g., {@link HillClimber}) until the given number if idle iterations (this phase is optional)
    188     * <li>Improvement phase (e.g., {@link GreatDeluge} or {@link SimulatedAnnealing}) until timeout is reached
    189     * </ul>
    190     */
    191    @SuppressWarnings("fallthrough")
    192    @Override
    193    public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) {
    194        MetaHeuristicSearchContext context = getContext(solution.getAssignment());
    195        Neighbour<V, T> n = null;
    196        switch (context.getPhase()) {
    197            case -1:
    198                context.setPhase(0);
    199                iProgress.info("[" + Thread.currentThread().getName() + "] " + getName(context.getConstructionSelection()) + "...");
    200            case 0:
    201                if (solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0) {
    202                    n = context.getConstructionSelection().selectNeighbour(solution);
    203                    if (n != null)
    204                        return n;
    205                }
    206                context.setPhase(1);
    207                if (solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0)
    208                    iProgress.info("[" + Thread.currentThread().getName() + "] " + getName(context.getIncompleteSelection()) + "...");
    209            case 1:
    210                if (solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0) {
    211                    return context.getIncompleteSelection().selectNeighbour(solution);
    212                }
    213                context.setPhase(2);
    214                if (context.hasHillClimberSelection())
    215                    iProgress.info("[" + Thread.currentThread().getName() + "] " + getName(context.getHillClimberSelection()) + "...");
    216            case 2:
    217                if (solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0)
    218                    return context.getIncompleteSelection().selectNeighbour(solution);
    219                if (context.hasHillClimberSelection()) {
    220                    n = context.getHillClimberSelection().selectNeighbour(solution);
    221                    if (n != null) return n;
    222                }
    223                context.setPhase(3);
    224                iProgress.info("[" + Thread.currentThread().getName() + "] " + getName(context.getImprovementSelection()) + "...");
    225            case 3:
    226                if (solution.getModel().nrUnassignedVariables(solution.getAssignment()) > 0)
    227                    return context.getIncompleteSelection().selectNeighbour(solution);
    228                return context.getImprovementSelection().selectNeighbour(solution);
    229            default:
    230                return null;
    231        }
    232    }
    233
    234    @Override
    235    public MetaHeuristicSearchContext createAssignmentContext(Assignment<V, T> assignment) {
    236        return new MetaHeuristicSearchContext(assignment.getIndex() - 1);
    237    }
    238
    239    public class MetaHeuristicSearchContext implements AssignmentContext {
    240        private int iPhase = -1;
    241        private NeighbourSelection<V, T> iConstructionSelection = null;
    242        private NeighbourSelection<V, T> iIncompleteSelection = null;
    243        private NeighbourSelection<V, T> iHillClimberSelection = null;
    244        private NeighbourSelection<V, T> iImprovementSelection = null;
    245
    246        public MetaHeuristicSearchContext(int index) {
    247            if (!iConstructionPhase.isEmpty()) {
    248                if (index < 0) iConstructionSelection = iConstructionPhase.get(0);
    249                iConstructionSelection = (index < 0 ? iConstructionPhase.get(0) : iConstructionPhase.get(index % iConstructionPhase.size()));
    250            }
    251            if (!iIncompletePhase.isEmpty()) {
    252                if (index < 0) iIncompleteSelection = iIncompletePhase.get(0);
    253                iIncompleteSelection = (index < 0 ? iIncompletePhase.get(0) : iIncompletePhase.get(index % iIncompletePhase.size()));
    254            }
    255            if (!iImprovementPhase.isEmpty()) {
    256                if (index < 0) iImprovementSelection = iImprovementPhase.get(0);
    257                iImprovementSelection = (index < 0 ? iImprovementPhase.get(0) : iImprovementPhase.get(index % iImprovementPhase.size()));
    258            }
    259            if (!iHillClimberPhase.isEmpty()) {
    260                if (index < 0) iHillClimberSelection = iHillClimberPhase.get(0);
    261                iHillClimberSelection = (index < 0 ? iHillClimberPhase.get(0) : iHillClimberPhase.get(index % iHillClimberPhase.size()));
    262            }
    263            if (iConstructionSelection == null) iConstructionSelection = iIncompleteSelection;
    264            if (iIncompleteSelection == null) iIncompleteSelection = iConstructionSelection;
    265            if (iImprovementSelection == null) iImprovementSelection = iIncompleteSelection;
    266            iLog.info("Using " + iConstructionSelection.getClass().getSimpleName() +
    267                    " > " + iIncompleteSelection.getClass().getSimpleName() +
    268                    (iHillClimberSelection == null ? "" : " > " + iHillClimberSelection.getClass().getSimpleName()) +
    269                    " > " + iImprovementSelection.getClass().getSimpleName());
    270        }
    271
    272        public NeighbourSelection<V, T> getConstructionSelection() {
    273            return iConstructionSelection;
    274        }
    275
    276        public NeighbourSelection<V, T> getIncompleteSelection() {
    277            return iIncompleteSelection;
    278        }
    279
    280        public NeighbourSelection<V, T> getHillClimberSelection() {
    281            return iHillClimberSelection;
    282        }
    283
    284        public boolean hasHillClimberSelection() {
    285            return iHillClimberSelection != null;
    286        }
    287
    288        public NeighbourSelection<V, T> getImprovementSelection() {
    289            return iImprovementSelection;
    290        }
    291
    292        public int getPhase() { return iPhase; }
    293        public void setPhase(int phase) { iPhase = phase; }
    294    }
    295}