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}