001package org.cpsolver.ifs.algorithms; 002 003import java.text.DecimalFormat; 004 005import org.cpsolver.ifs.assignment.Assignment; 006import org.cpsolver.ifs.heuristics.NeighbourSelection; 007import org.cpsolver.ifs.model.Model; 008import org.cpsolver.ifs.model.Neighbour; 009import org.cpsolver.ifs.model.Value; 010import org.cpsolver.ifs.model.Variable; 011import org.cpsolver.ifs.solution.Solution; 012import org.cpsolver.ifs.util.DataProperties; 013import org.cpsolver.ifs.util.JProf; 014 015 016/** 017 * Great deluge. In each iteration, one of the given neighbourhoods is selected first, 018 * then a neighbour is generated and it is accepted if the value of the new 019 * solution is below certain bound. This bound is initialized to the 020 * GreatDeluge.UpperBoundRate × value of the best solution ever found. 021 * After each iteration, the bound is decreased by GreatDeluge.CoolRate (new 022 * bound equals to old bound × GreatDeluge.CoolRate). If the bound gets 023 * bellow GreatDeluge.LowerBoundRate × value of the best solution ever 024 * found, it is changed back to GreatDeluge.UpperBoundRate × value of the 025 * best solution ever found. 026 * <br><br> 027 * If there was no improvement found between the bounds, the new bounds are 028 * changed to GreatDeluge.UpperBoundRate^2 and GreatDeluge.LowerBoundRate^2, 029 * GreatDeluge.UpperBoundRate^3 and GreatDeluge.LowerBoundRate^3, etc. till 030 * there is an improvement found. <br> 031 * <br> 032 * Custom neighbours can be set using GreatDeluge.Neighbours property that should 033 * contain semicolon separated list of {@link NeighbourSelection}. By default, 034 * each neighbour selection is selected with the same probability (each has 1 point in 035 * a roulette wheel selection). It can be changed by adding @n at the end 036 * of the name of the class, for example: 037 * <pre><code> 038 * GreatDeluge.Neighbours=org.cpsolver.ifs.algorithms.neighbourhoods.RandomMove;org.cpsolver.ifs.algorithms.neighbourhoods.RandomSwapMove@0.1 039 * </code></pre> 040 * Selector RandomSwapMove is 10× less probable to be selected than other selectors. 041 * When GreatDeluge.Random is true, all selectors are selected with the same probability, ignoring these weights. 042 * <br><br> 043 * When GreatDeluge.Update is true, {@link NeighbourSelector#update(Assignment, Neighbour, long)} is called 044 * after each iteration (on the selector that was used) and roulette wheel selection 045 * that is using {@link NeighbourSelector#getPoints()} is used to pick a selector in each iteration. 046 * See {@link NeighbourSelector} for more details. 047 * <br> 048 * 049 * @version IFS 1.3 (Iterative Forward Search)<br> 050 * Copyright (C) 2014 Tomáš Müller<br> 051 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 052 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 053 * <br> 054 * This library is free software; you can redistribute it and/or modify 055 * it under the terms of the GNU Lesser General Public License as 056 * published by the Free Software Foundation; either version 3 of the 057 * License, or (at your option) any later version. <br> 058 * <br> 059 * This library is distributed in the hope that it will be useful, but 060 * WITHOUT ANY WARRANTY; without even the implied warranty of 061 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 062 * Lesser General Public License for more details. <br> 063 * <br> 064 * You should have received a copy of the GNU Lesser General Public 065 * License along with this library; if not see 066 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 067 * @param <V> Variable 068 * @param <T> Value 069 */ 070public class GreatDeluge<V extends Variable<V, T>, T extends Value<V, T>> extends NeighbourSearch<V, T> { 071 private DecimalFormat sDF2 = new DecimalFormat("0.00"); 072 private DecimalFormat sDF5 = new DecimalFormat("0.00000"); 073 private double iCoolRate = 0.9999999; 074 private double iUpperBoundRate = 1.05; 075 private double iLowerBoundRate = 0.95; 076 private Double[] iCoolRateAdjusts = null; 077 078 /** 079 * Constructor. Following problem properties are considered: 080 * <ul> 081 * <li>GreatDeluge.CoolRate ... bound cooling rate (default 0.99999995) 082 * <li>GreatDeluge.UpperBoundRate ... bound upper bound relative to best solution ever found (default 1.05) 083 * <li>GreatDeluge.LowerBoundRate ... bound lower bound relative to best solution ever found (default 0.95) 084 * <li>GreatDeluge.Neighbours ... semicolon separated list of classes implementing {@link NeighbourSelection} 085 * <li>GreatDeluge.AdditionalNeighbours ... semicolon separated list of classes implementing {@link NeighbourSelection} 086 * <li>GreatDeluge.Random ... when true, a neighbour selector is selected randomly 087 * <li>GreatDeluge.Update ... when true, a neighbour selector is selected using {@link NeighbourSelector#getPoints()} weights (roulette wheel selection) 088 * </ul> 089 * 090 * @param properties 091 * problem properties 092 */ 093 public GreatDeluge(DataProperties properties) { 094 super(properties); 095 iCoolRate = properties.getPropertyDouble(getParameterBaseName() + ".CoolRate", iCoolRate); 096 iUpperBoundRate = properties.getPropertyDouble(getParameterBaseName() + ".UpperBoundRate", iUpperBoundRate); 097 iLowerBoundRate = properties.getPropertyDouble(getParameterBaseName() + ".LowerBoundRate", iLowerBoundRate); 098 iCoolRateAdjusts = properties.getPropertyDoubleArry(getParameterBaseName() + ".CoolRateAdjustments", null); 099 } 100 101 @Override 102 public String getParameterBaseName() { return "GreatDeluge"; } 103 104 @Override 105 public NeighbourSearchContext createAssignmentContext(Assignment<V, T> assignment) { 106 return new GreatDelugeContext(); 107 } 108 109 public class GreatDelugeContext extends NeighbourSearchContext { 110 private int iMoves = 0; 111 private int iAcceptedMoves = 0; 112 private int iNrIdle = 0; 113 private long iLastImprovingIter = 0; 114 private double iBestValue = 0; 115 private double iBound = 0.0; 116 private double iUpperBound; 117 118 /** Accept the given neighbour if it does not worsen the current solution or when the new solution is below the bound */ 119 @Override 120 protected boolean accept(Assignment<V, T> assignment, Model<V, T> model, Neighbour<V, T> neighbour, double value, boolean lazy) { 121 iMoves ++; 122 if (value <= 0.0 || (lazy ? model.getTotalValue(assignment) : value + model.getTotalValue(assignment)) < iBound) { 123 iAcceptedMoves ++; 124 return true; 125 } 126 return false; 127 } 128 129 /** Setup the bound */ 130 @Override 131 protected void activate(Solution<V, T> solution) { 132 super.activate(solution); 133 iNrIdle = 0; 134 iLastImprovingIter = 0; 135 iBound = (solution.getBestValue() > 0.0 ? iUpperBoundRate * solution.getBestValue() : solution.getBestValue() / iUpperBoundRate); 136 iUpperBound = iBound; 137 } 138 139 protected double getCoolRate(int idx) { 140 if (idx < 0 || iCoolRateAdjusts == null || idx >= iCoolRateAdjusts.length || iCoolRateAdjusts[idx] == null) return iCoolRate; 141 return iCoolRate * iCoolRateAdjusts[idx]; 142 } 143 144 /** Increment iteration count, update bound */ 145 @Override 146 protected void incIteration(Solution<V, T> solution) { 147 super.incIteration(solution); 148 if (solution.getBestValue() >= 0.0) 149 iBound *= getCoolRate(solution.getAssignment().getIndex() - 1); 150 else 151 iBound /= getCoolRate(solution.getAssignment().getIndex() - 1); 152 if (iIter % 10000 == 0) { 153 info("Iter=" + iIter / 1000 + "k, NonImpIter=" + sDF2.format((iIter - iLastImprovingIter) / 1000.0) 154 + "k, Speed=" + sDF2.format(1000.0 * iIter / (JProf.currentTimeMillis() - iT0)) + " it/s"); 155 info("Bound is " + sDF2.format(iBound) + ", " + "best value is " + sDF2.format(solution.getBestValue()) 156 + " (" + sDF2.format(100.0 * iBound / solution.getBestValue()) + "%), " + "current value is " 157 + sDF2.format(solution.getModel().getTotalValue(solution.getAssignment())) + " (" 158 + sDF2.format(100.0 * iBound / solution.getModel().getTotalValue(solution.getAssignment())) + "%), " + "#idle=" + iNrIdle 159 + ", " + "Pacc=" + sDF5.format(100.0 * iAcceptedMoves / iMoves) + "%"); 160 logNeibourStatus(); 161 iAcceptedMoves = iMoves = 0; 162 } 163 if (isMaster(solution)) { 164 double upperBound = Math.max(solution.getBestValue() + 2.0,(solution.getBestValue() >= 0.0 ? 165 Math.pow(iUpperBoundRate, 1 + iNrIdle) * solution.getBestValue() : 166 solution.getBestValue() / Math.pow(iUpperBoundRate, 1 + iNrIdle))); 167 double lowerBound = (solution.getBestValue() >= 0.0 168 ? Math.pow(iLowerBoundRate, 1 + iNrIdle) * solution.getBestValue() 169 : solution.getBestValue() / Math.pow(iLowerBoundRate, 1 + iNrIdle)); 170 if (iBound > upperBound) { 171 iBound = upperBound; 172 } else if (iBound < lowerBound) { 173 iNrIdle++; 174 iBound = upperBound; 175 iUpperBound = iBound; 176 setProgressPhase("Great Deluge [" + (1 + iNrIdle) + "]..."); 177 } 178 setProgress(100 - Math.round(100.0 * (iBound - lowerBound) / (iUpperBound - lowerBound))); 179 } 180 iMoves++; 181 } 182 183 /** Update last improving iteration count */ 184 @Override 185 public void bestSaved(Solution<V, T> solution) { 186 super.bestSaved(solution); 187 if (Math.abs(iBestValue - solution.getBestValue()) >= 1.0) { 188 iLastImprovingIter = iIter; 189 iNrIdle = 0; 190 iBestValue = solution.getBestValue(); 191 } 192 } 193 } 194}