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 * @author Tomáš Müller 050 * @version IFS 1.3 (Iterative Forward Search)<br> 051 * Copyright (C) 2014 Tomáš Müller<br> 052 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 053 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 054 * <br> 055 * This library is free software; you can redistribute it and/or modify 056 * it under the terms of the GNU Lesser General Public License as 057 * published by the Free Software Foundation; either version 3 of the 058 * License, or (at your option) any later version. <br> 059 * <br> 060 * This library is distributed in the hope that it will be useful, but 061 * WITHOUT ANY WARRANTY; without even the implied warranty of 062 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 063 * Lesser General Public License for more details. <br> 064 * <br> 065 * You should have received a copy of the GNU Lesser General Public 066 * License along with this library; if not see 067 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 068 * @param <V> Variable 069 * @param <T> Value 070 */ 071public class GreatDeluge<V extends Variable<V, T>, T extends Value<V, T>> extends NeighbourSearch<V, T> { 072 private DecimalFormat sDF2 = new DecimalFormat("0.00"); 073 private DecimalFormat sDF5 = new DecimalFormat("0.00000"); 074 private double iCoolRate = 0.9999999; 075 private double iUpperBoundRate = 1.05; 076 private double iLowerBoundRate = 0.95; 077 private Double[] iCoolRateAdjusts = null; 078 079 /** 080 * Constructor. Following problem properties are considered: 081 * <ul> 082 * <li>GreatDeluge.CoolRate ... bound cooling rate (default 0.99999995) 083 * <li>GreatDeluge.UpperBoundRate ... bound upper bound relative to best solution ever found (default 1.05) 084 * <li>GreatDeluge.LowerBoundRate ... bound lower bound relative to best solution ever found (default 0.95) 085 * <li>GreatDeluge.Neighbours ... semicolon separated list of classes implementing {@link NeighbourSelection} 086 * <li>GreatDeluge.AdditionalNeighbours ... semicolon separated list of classes implementing {@link NeighbourSelection} 087 * <li>GreatDeluge.Random ... when true, a neighbour selector is selected randomly 088 * <li>GreatDeluge.Update ... when true, a neighbour selector is selected using {@link NeighbourSelector#getPoints()} weights (roulette wheel selection) 089 * </ul> 090 * 091 * @param properties 092 * problem properties 093 */ 094 public GreatDeluge(DataProperties properties) { 095 super(properties); 096 iCoolRate = properties.getPropertyDouble(getParameterBaseName() + ".CoolRate", iCoolRate); 097 iUpperBoundRate = properties.getPropertyDouble(getParameterBaseName() + ".UpperBoundRate", iUpperBoundRate); 098 iLowerBoundRate = properties.getPropertyDouble(getParameterBaseName() + ".LowerBoundRate", iLowerBoundRate); 099 iCoolRateAdjusts = properties.getPropertyDoubleArry(getParameterBaseName() + ".CoolRateAdjustments", null); 100 } 101 102 @Override 103 public String getParameterBaseName() { return "GreatDeluge"; } 104 105 @Override 106 public NeighbourSearchContext createAssignmentContext(Assignment<V, T> assignment) { 107 return new GreatDelugeContext(); 108 } 109 110 public class GreatDelugeContext extends NeighbourSearchContext { 111 private int iMoves = 0; 112 private int iAcceptedMoves = 0; 113 private int iNrIdle = 0; 114 private long iLastImprovingIter = 0; 115 private double iBestValue = 0; 116 private double iBound = 0.0; 117 private double iUpperBound; 118 119 /** Accept the given neighbour if it does not worsen the current solution or when the new solution is below the bound */ 120 @Override 121 protected boolean accept(Assignment<V, T> assignment, Model<V, T> model, Neighbour<V, T> neighbour, double value, boolean lazy) { 122 iMoves ++; 123 if (value <= 0.0 || (lazy ? model.getTotalValue(assignment) : value + model.getTotalValue(assignment)) < iBound) { 124 iAcceptedMoves ++; 125 return true; 126 } 127 return false; 128 } 129 130 /** Setup the bound */ 131 @Override 132 protected void activate(Solution<V, T> solution) { 133 super.activate(solution); 134 iNrIdle = 0; 135 iLastImprovingIter = 0; 136 iBound = (solution.getBestValue() > 0.0 ? iUpperBoundRate * solution.getBestValue() : solution.getBestValue() / iUpperBoundRate); 137 iUpperBound = iBound; 138 } 139 140 protected double getCoolRate(int idx) { 141 if (idx < 0 || iCoolRateAdjusts == null || idx >= iCoolRateAdjusts.length || iCoolRateAdjusts[idx] == null) return iCoolRate; 142 return iCoolRate * iCoolRateAdjusts[idx]; 143 } 144 145 /** Increment iteration count, update bound */ 146 @Override 147 protected void incIteration(Solution<V, T> solution) { 148 super.incIteration(solution); 149 if (solution.getBestValue() >= 0.0) 150 iBound *= getCoolRate(solution.getAssignment().getIndex() - 1); 151 else 152 iBound /= getCoolRate(solution.getAssignment().getIndex() - 1); 153 if (iIter % 10000 == 0) { 154 info("Iter=" + iIter / 1000 + "k, NonImpIter=" + sDF2.format((iIter - iLastImprovingIter) / 1000.0) 155 + "k, Speed=" + sDF2.format(1000.0 * iIter / (JProf.currentTimeMillis() - iT0)) + " it/s"); 156 info("Bound is " + sDF2.format(iBound) + ", " + "best value is " + sDF2.format(solution.getBestValue()) 157 + " (" + sDF2.format(100.0 * iBound / solution.getBestValue()) + "%), " + "current value is " 158 + sDF2.format(solution.getModel().getTotalValue(solution.getAssignment())) + " (" 159 + sDF2.format(100.0 * iBound / solution.getModel().getTotalValue(solution.getAssignment())) + "%), " + "#idle=" + iNrIdle 160 + ", " + "Pacc=" + sDF5.format(100.0 * iAcceptedMoves / iMoves) + "%"); 161 logNeibourStatus(); 162 iAcceptedMoves = iMoves = 0; 163 } 164 if (isMaster(solution)) { 165 double upperBound = Math.max(solution.getBestValue() + 2.0,(solution.getBestValue() >= 0.0 ? 166 Math.pow(iUpperBoundRate, 1 + iNrIdle) * solution.getBestValue() : 167 solution.getBestValue() / Math.pow(iUpperBoundRate, 1 + iNrIdle))); 168 double lowerBound = (solution.getBestValue() >= 0.0 169 ? Math.pow(iLowerBoundRate, 1 + iNrIdle) * solution.getBestValue() 170 : solution.getBestValue() / Math.pow(iLowerBoundRate, 1 + iNrIdle)); 171 if (iBound > upperBound) { 172 iBound = upperBound; 173 } else if (iBound < lowerBound) { 174 iNrIdle++; 175 iBound = upperBound; 176 iUpperBound = iBound; 177 setProgressPhase("Great Deluge [" + (1 + iNrIdle) + "]..."); 178 } 179 setProgress(100 - Math.round(100.0 * (iBound - lowerBound) / (iUpperBound - lowerBound))); 180 } 181 iMoves++; 182 } 183 184 /** Update last improving iteration count */ 185 @Override 186 public void bestSaved(Solution<V, T> solution) { 187 super.bestSaved(solution); 188 if (Math.abs(iBestValue - solution.getBestValue()) >= 1.0) { 189 iLastImprovingIter = iIter; 190 iNrIdle = 0; 191 iBestValue = solution.getBestValue(); 192 } 193 } 194 } 195}