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