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 Tomas Muller<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 062 /** 063 * Constructor 064 * <ul> 065 * <li>HillClimber.MaxIdle ... maximum number of idle iterations (default is 200000) 066 * <li>HillClimber.Neighbours ... semicolon separated list of classes implementing {@link NeighbourSelection} 067 * <li>HillClimber.AdditionalNeighbours ... semicolon separated list of classes implementing {@link NeighbourSelection} 068 * <li>HillClimber.Random ... when true, a neighbour selector is selected randomly 069 * <li>HillClimber.Update ... when true, a neighbour selector is selected using {@link NeighbourSelector#getPoints()} weights (roulette wheel selection) 070 * </ul> 071 * @param properties solver configuration 072 */ 073 public HillClimber(DataProperties properties) { 074 super(properties); 075 iMaxIdleIters = properties.getPropertyInt(getParameterBaseName() + ".MaxIdle", iMaxIdleIters); 076 iSetHCMode = properties.getPropertyBoolean(getParameterBaseName() + ".SetHCMode", iSetHCMode); 077 } 078 079 /** 080 * Set progress phase name 081 * @param phase name of the phase in which the hill climber is used (for logging purposes) 082 */ 083 public void setPhase(String phase) { 084 iPhase = phase; 085 } 086 087 /** 088 * Initialization 089 */ 090 @Override 091 public void init(Solver<V, T> solver) { 092 super.init(solver); 093 if (iSetHCMode) 094 setHCMode(true); 095 } 096 097 /** 098 * All parameters start with HillClimber base name, e.g., HillClimber.MaxIdle 099 */ 100 @Override 101 public String getParameterBaseName() { return "HillClimber"; } 102 103 @Override 104 public NeighbourSearchContext createAssignmentContext(Assignment<V, T> assignment) { 105 return new HillClimberContext(); 106 } 107 108 public class HillClimberContext extends NeighbourSearchContext { 109 protected int iLastImprovingIter = 0; 110 111 /** 112 * Increase iteration counter 113 */ 114 @Override 115 protected void incIteration(Solution<V, T> solution) { 116 super.incIteration(solution); 117 if (iIter % 10000 == 0) { 118 info("Iter=" + (iIter / 1000)+"k, NonImpIter=" + iDF2.format((iIter-iLastImprovingIter)/1000.0)+"k, Speed="+iDF2.format(1000.0*iIter/getTimeMillis())+" it/s"); 119 logNeibourStatus(); 120 } 121 setProgress(Math.round(100.0 * (iIter - iLastImprovingIter) / iMaxIdleIters)); 122 } 123 124 /** 125 * Stop the search after a given number of idle (not improving) iterations 126 */ 127 @Override 128 protected boolean canContinue(Solution<V, T> solution) { 129 return iIter - iLastImprovingIter < iMaxIdleIters; 130 } 131 132 /** 133 * Reset the idle iterations counter 134 */ 135 @Override 136 protected void activate(Solution<V, T> solution) { 137 super.activate(solution); 138 iLastImprovingIter = iIter; 139 } 140 141 /** 142 * Accept any move that does not worsen the solution (value <= 0) 143 */ 144 @Override 145 protected boolean accept(Assignment<V, T> assignment, Model<V, T> model, Neighbour<V, T> neighbour, double value, boolean lazy) { 146 if (value < 0) iLastImprovingIter = iIter; 147 return value <= 0; 148 } 149 } 150}