001package net.sf.cpsolver.ifs.algorithms; 002 003import net.sf.cpsolver.ifs.model.Model; 004import net.sf.cpsolver.ifs.model.Neighbour; 005import net.sf.cpsolver.ifs.model.Value; 006import net.sf.cpsolver.ifs.model.Variable; 007import net.sf.cpsolver.ifs.solution.Solution; 008import net.sf.cpsolver.ifs.util.DataProperties; 009 010/** 011 * Step counting hill climber. Unlike with the ordinary hill climber, there is a bound. 012 * The bound is updated (to the value of the current solution) after a given number of 013 * moves. Based on the given mode, either all moves, only accepted moves, or only improving 014 * moves are counted. 015 * <br> 016 * 017 * @version IFS 1.2 (Iterative Forward Search)<br> 018 * Copyright (C) 2014 Tomáš Müller<br> 019 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 020 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 021 * <br> 022 * This library is free software; you can redistribute it and/or modify 023 * it under the terms of the GNU Lesser General Public License as 024 * published by the Free Software Foundation; either version 3 of the 025 * License, or (at your option) any later version. <br> 026 * <br> 027 * This library is distributed in the hope that it will be useful, but 028 * WITHOUT ANY WARRANTY; without even the implied warranty of 029 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 030 * Lesser General Public License for more details. <br> 031 * <br> 032 * You should have received a copy of the GNU Lesser General Public 033 * License along with this library; if not see 034 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 035 */ 036public class StepCountingHillClimber<V extends Variable<V, T>, T extends Value<V, T>> extends HillClimber<V, T> { 037 public static enum Mode { 038 ALL, 039 ACCEPTED, 040 IMPROVING 041 } 042 protected Double iBound = null; 043 protected int iCounter = 0; 044 protected int iCounterLimit = 100; 045 protected Mode iCounterMode = Mode.ACCEPTED; 046 047 /** 048 * Constructor 049 * <ul> 050 * <li>HillClimber.CounterLimit ... number of moves after which the bound is reset (defaults to 1000) 051 * <li>HillClimber.CounterMode ... counter mode (all: count all moves, accepted: count accepted moves, improving: count improving moves) 052 * </ul> 053 */ 054 public StepCountingHillClimber(DataProperties properties, String name) { 055 super(properties); 056 iSetHCMode = false; 057 } 058 059 /** 060 * Reset the bound and the steps counter. 061 */ 062 @Override 063 public void activate(Solution<V, T> solution) { 064 super.activate(solution); 065 iBound = solution.getModel().getTotalValue(); 066 iCounter = 0; 067 } 068 069 /** 070 * Increase iteration number, also update bound when the given number of steps is reached. 071 */ 072 @Override 073 public void incIteration(Solution<V, T> solution) { 074 iIter++; 075 if (iIter % 10000 == 0) { 076 iLog.info("Iter=" + (iIter / 1000)+"k, NonImpIter=" + iDF2.format((iIter-iLastImprovingIter)/1000.0)+"k, Speed="+iDF2.format(1000.0*iIter/getTimeMillis())+" it/s, Bound=" + iDF2.format(iBound)); 077 logNeibourStatus(); 078 } 079 iProgress.setProgress(Math.round(100.0 * (iIter - iLastImprovingIter) / iMaxIdleIters)); 080 if (iCounter >= iCounterLimit) { 081 iBound = solution.getModel().getTotalValue(); 082 iCounter = 0; 083 } 084 } 085 086 /** 087 * Accept any move that does not worsen the solution (value <= 0) or that is below the bound. Also increase the step counter. 088 */ 089 @Override 090 protected boolean accept(Model<V,T> model, Neighbour<V, T> neighbour, double value, boolean lazy) { 091 boolean accept = (value <= 0.0 || (lazy ? model.getTotalValue() : value + model.getTotalValue()) < iBound); 092 switch (iCounterMode) { 093 case ALL: 094 iCounter ++; 095 break; 096 case ACCEPTED: 097 if (accept) iCounter ++; 098 break; 099 case IMPROVING: 100 if (value < 0) iCounter ++; 101 break; 102 } 103 return accept; 104 } 105 106 /** 107 * Stop the search when the number of idle iterations is reached and the bound is no longer decreasing 108 */ 109 @Override 110 protected boolean canContinue(Solution<V, T> solution) { 111 return super.canContinue(solution) || iCounter < iCounterLimit || solution.getModel().getTotalValue() < iBound; 112 } 113}