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