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