001package org.cpsolver.ifs.algorithms; 002 003import org.cpsolver.ifs.assignment.Assignment; 004import org.cpsolver.ifs.heuristics.NeighbourSelection; 005import org.cpsolver.ifs.model.Model; 006import org.cpsolver.ifs.model.Neighbour; 007import org.cpsolver.ifs.model.Value; 008import org.cpsolver.ifs.model.Variable; 009import org.cpsolver.ifs.solution.Solution; 010import org.cpsolver.ifs.solver.Solver; 011import org.cpsolver.ifs.util.DataProperties; 012 013/** 014 * Hill climber. In each iteration, one of the given neighbourhoods is selected first, 015 * then a neighbour is generated and it is accepted if its value 016 * {@link Neighbour#value(Assignment)} is below or equal to zero. The search is 017 * stopped after a given amount of idle iterations ( can be defined by problem 018 * property HillClimber.MaxIdle). <br> 019 * <br> 020 * Custom neighbours can be set using HillClimber.Neighbours property that should 021 * contain semicolon separated list of {@link NeighbourSelection}. By default, 022 * each neighbour selection is selected with the same probability (each has 1 point in 023 * a roulette wheel selection). It can be changed by adding @n at the end 024 * of the name of the class, for example: 025 * <pre><code> 026 * HillClimber.Neighbours=org.cpsolver.ifs.algorithms.neighbourhoods.RandomMove;org.cpsolver.ifs.algorithms.neighbourhoods.RandomSwapMove@0.1 027 * </code></pre> 028 * Selector RandomSwapMove is 10× less probable to be selected than other selectors. 029 * When HillClimber.Random is true, all selectors are selected with the same probability, ignoring these weights. 030 * <br><br> 031 * When HillClimber.Update is true, {@link NeighbourSelector#update(Assignment, Neighbour, long)} is called 032 * after each iteration (on the selector that was used) and roulette wheel selection 033 * that is using {@link NeighbourSelector#getPoints()} is used to pick a selector in each iteration. 034 * See {@link NeighbourSelector} for more details. 035 * <br> 036 * 037 * @version IFS 1.3 (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 * @param <V> Variable 056 * @param <T> Value 057 */ 058public class HillClimber<V extends Variable<V, T>, T extends Value<V, T>> extends NeighbourSearch<V, T> { 059 protected int iMaxIdleIters = 10000; 060 protected boolean iSetHCMode = false; 061 protected static double sEPS = 0.00001; 062 063 /** 064 * Constructor 065 * <ul> 066 * <li>HillClimber.MaxIdle ... maximum number of idle iterations (default is 200000) 067 * <li>HillClimber.Neighbours ... semicolon separated list of classes implementing {@link NeighbourSelection} 068 * <li>HillClimber.AdditionalNeighbours ... semicolon separated list of classes implementing {@link NeighbourSelection} 069 * <li>HillClimber.Random ... when true, a neighbour selector is selected randomly 070 * <li>HillClimber.Update ... when true, a neighbour selector is selected using {@link NeighbourSelector#getPoints()} weights (roulette wheel selection) 071 * </ul> 072 * @param properties solver configuration 073 */ 074 public HillClimber(DataProperties properties) { 075 super(properties); 076 iMaxIdleIters = properties.getPropertyInt(getParameterBaseName() + ".MaxIdle", iMaxIdleIters); 077 iSetHCMode = properties.getPropertyBoolean(getParameterBaseName() + ".SetHCMode", iSetHCMode); 078 } 079 080 /** 081 * Set progress phase name 082 * @param phase name of the phase in which the hill climber is used (for logging purposes) 083 */ 084 public void setPhase(String phase) { 085 iPhase = phase; 086 } 087 088 /** 089 * Initialization 090 */ 091 @Override 092 public void init(Solver<V, T> solver) { 093 super.init(solver); 094 if (iSetHCMode) 095 setHCMode(true); 096 } 097 098 /** 099 * All parameters start with HillClimber base name, e.g., HillClimber.MaxIdle 100 */ 101 @Override 102 public String getParameterBaseName() { return "HillClimber"; } 103 104 @Override 105 public NeighbourSearchContext createAssignmentContext(Assignment<V, T> assignment) { 106 return new HillClimberContext(); 107 } 108 109 public class HillClimberContext extends NeighbourSearchContext { 110 protected int iLastImprovingIter = 0; 111 112 /** 113 * Increase iteration counter 114 */ 115 @Override 116 protected void incIteration(Solution<V, T> solution) { 117 super.incIteration(solution); 118 if (iIter % 10000 == 0) { 119 info("Iter=" + (iIter / 1000)+"k, NonImpIter=" + iDF2.format((iIter-iLastImprovingIter)/1000.0)+"k, Speed="+iDF2.format(1000.0*iIter/getTimeMillis())+" it/s"); 120 logNeibourStatus(); 121 } 122 setProgress(Math.round(100.0 * (iIter - iLastImprovingIter) / iMaxIdleIters)); 123 } 124 125 /** 126 * Stop the search after a given number of idle (not improving) iterations 127 */ 128 @Override 129 protected boolean canContinue(Solution<V, T> solution) { 130 return iIter - iLastImprovingIter < iMaxIdleIters; 131 } 132 133 /** 134 * Reset the idle iterations counter 135 */ 136 @Override 137 protected void activate(Solution<V, T> solution) { 138 super.activate(solution); 139 iLastImprovingIter = iIter; 140 } 141 142 /** 143 * Accept any move that does not worsen the solution (value <= 0) 144 */ 145 @Override 146 protected boolean accept(Assignment<V, T> assignment, Model<V, T> model, Neighbour<V, T> neighbour, double value, boolean lazy) { 147 if (value < -sEPS) iLastImprovingIter = iIter; 148 return value <= 0; 149 } 150 } 151}