001package net.sf.cpsolver.ifs.algorithms; 002 003import net.sf.cpsolver.ifs.heuristics.NeighbourSelection; 004import net.sf.cpsolver.ifs.model.Model; 005import net.sf.cpsolver.ifs.model.Neighbour; 006import net.sf.cpsolver.ifs.model.Value; 007import net.sf.cpsolver.ifs.model.Variable; 008import net.sf.cpsolver.ifs.solution.Solution; 009import net.sf.cpsolver.ifs.solver.Solver; 010import net.sf.cpsolver.ifs.util.DataProperties; 011 012/** 013 * Hill climber. In each iteration, one of the given neighbourhoods is selected first, 014 * then a neighbour is generated and it is accepted if its value 015 * {@link Neighbour#value()} is below or equal to zero. The search is 016 * stopped after a given amount of idle iterations ( can be defined by problem 017 * property HillClimber.MaxIdle). <br> 018 * <br> 019 * Custom neighbours can be set using HillClimber.Neighbours property that should 020 * contain semicolon separated list of {@link NeighbourSelection}. By default, 021 * each neighbour selection is selected with the same probability (each has 1 point in 022 * a roulette wheel selection). It can be changed by adding @n at the end 023 * of the name of the class, for example:<br> 024 * <code> 025 * HillClimber.Neighbours=net.sf.cpsolver.ifs.algorithms.neighbourhoods.RandomMove;net.sf.cpsolver.ifs.algorithms.neighbourhoods.RandomSwapMove@0.1 026 * </code> 027 * <br> 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(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.2 (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 */ 056public class HillClimber<V extends Variable<V, T>, T extends Value<V, T>> extends NeighbourSearch<V, T> { 057 protected int iMaxIdleIters = 10000; 058 protected int iLastImprovingIter = 0; 059 protected double iBestValue = 0; 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 */ 072 public HillClimber(DataProperties properties) { 073 super(properties); 074 iMaxIdleIters = properties.getPropertyInt(getParameterBaseName() + ".MaxIdle", iMaxIdleIters); 075 iSetHCMode = properties.getPropertyBoolean(getParameterBaseName() + ".SetHCMode", iSetHCMode); 076 } 077 078 /** 079 * Set progress phase name 080 */ 081 public void setPhase(String phase) { 082 iPhase = phase; 083 } 084 085 /** 086 * Initialization 087 */ 088 @Override 089 public void init(Solver<V, T> solver) { 090 super.init(solver); 091 if (iSetHCMode) 092 setHCMode(true); 093 } 094 095 /** 096 * Increase iteration counter 097 */ 098 @Override 099 protected void incIteration(Solution<V, T> solution) { 100 super.incIteration(solution); 101 if (iIter % 10000 == 0) { 102 iLog.info("Iter=" + (iIter / 1000)+"k, NonImpIter=" + iDF2.format((iIter-iLastImprovingIter)/1000.0)+"k, Speed="+iDF2.format(1000.0*iIter/getTimeMillis())+" it/s"); 103 logNeibourStatus(); 104 } 105 iProgress.setProgress(Math.round(100.0 * (iIter - iLastImprovingIter) / iMaxIdleIters)); 106 } 107 108 /** 109 * Stop the search after a given number of idle (not improving) iterations 110 */ 111 @Override 112 protected boolean canContinue(Solution<V, T> solution) { 113 return iIter - iLastImprovingIter < iMaxIdleIters; 114 } 115 116 /** 117 * Reset the idle iterations counter 118 */ 119 @Override 120 protected void activate(Solution<V, T> solution) { 121 super.activate(solution); 122 iLastImprovingIter = iIter; 123 } 124 125 /** 126 * Memorize the iteration when the last best solution was found. 127 */ 128 @Override 129 public void bestSaved(Solution<V, T> solution) { 130 if (Math.abs(iBestValue - solution.getBestValue()) >= 1.0) { 131 iLastImprovingIter = iIter; 132 iBestValue = solution.getBestValue(); 133 } 134 } 135 136 /** 137 * Accept any move that does not worsen the solution (value <= 0) 138 */ 139 @Override 140 protected boolean accept(Model<V, T> model, Neighbour<V, T> neighbour, double value, boolean lazy) { 141 return value <= 0; 142 } 143 144 /** 145 * All parameters start with HillClimber base name, e.g., HillClimber.MaxIdle 146 */ 147 @Override 148 public String getParameterBaseName() { return "HillClimber"; } 149}