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}