001package net.sf.cpsolver.ifs.algorithms.neighbourhoods; 002 003import java.util.ArrayList; 004import java.util.Collection; 005import java.util.HashMap; 006import java.util.Iterator; 007import java.util.List; 008import java.util.Map; 009import java.util.Set; 010 011import net.sf.cpsolver.ifs.heuristics.NeighbourSelection; 012import net.sf.cpsolver.ifs.model.Model; 013import net.sf.cpsolver.ifs.model.Neighbour; 014import net.sf.cpsolver.ifs.model.SimpleNeighbour; 015import net.sf.cpsolver.ifs.model.Value; 016import net.sf.cpsolver.ifs.model.Variable; 017import net.sf.cpsolver.ifs.solution.Solution; 018import net.sf.cpsolver.ifs.solver.Solver; 019import net.sf.cpsolver.ifs.util.DataProperties; 020import net.sf.cpsolver.ifs.util.JProf; 021import net.sf.cpsolver.ifs.util.ToolBox; 022 023/** 024 * Try to assign a variable with a new value. A variable is selected randomly, a 025 * different value is randomly selected for the variable -- the variable is 026 * assigned with the new value. If there is a conflict, it tries to resolve these 027 * conflicts by assigning conflicting variables to other values as well. 028 * <br> 029 * 030 * @version IFS 1.2 (Iterative Forward Search)<br> 031 * Copyright (C) 2014 Tomáš Müller<br> 032 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 033 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 034 * <br> 035 * This library is free software; you can redistribute it and/or modify 036 * it under the terms of the GNU Lesser General Public License as 037 * published by the Free Software Foundation; either version 3 of the 038 * License, or (at your option) any later version. <br> 039 * <br> 040 * This library is distributed in the hope that it will be useful, but 041 * WITHOUT ANY WARRANTY; without even the implied warranty of 042 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 043 * Lesser General Public License for more details. <br> 044 * <br> 045 * You should have received a copy of the GNU Lesser General Public 046 * License along with this library; if not see 047 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 048 */ 049public class RandomSwapMove<V extends Variable<V, T>, T extends Value<V, T>> implements NeighbourSelection<V, T>, HillClimberSelection { 050 protected int iMaxAttempts = 3; 051 protected boolean iHC = false; 052 protected int iTimeLimit = 200; 053 054 public RandomSwapMove(DataProperties config) { 055 iMaxAttempts = config.getPropertyInt("RandomSwap.MaxAttempts", iMaxAttempts); 056 iTimeLimit = config.getPropertyInt("RandomSwap.TimeLimit", iTimeLimit); 057 } 058 059 @Override 060 public void setHcMode(boolean hcMode) { 061 iHC = hcMode; 062 } 063 064 @Override 065 public void init(Solver<V, T> solver) { 066 } 067 068 @Override 069 public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) { 070 Model<V, T> model = solution.getModel(); 071 double total = model.getTotalValue(); 072 int varIdx = ToolBox.random(model.variables().size()); 073 for (int i = 0; i < model.variables().size(); i++) { 074 V variable = model.variables().get((i + varIdx) % model.variables().size()); 075 List<T> values = variable.values(); 076 if (values.isEmpty()) continue; 077 int valIdx = ToolBox.random(values.size()); 078 T old = variable.getAssignment(); 079 080 int attempts = 0; 081 long startTime = JProf.currentTimeMillis(); 082 for (int j = 0; j < values.size(); j++) { 083 T value = values.get((j + valIdx) % values.size()); 084 if (value.equals(old)) continue; 085 086 Set<T> conflicts = model.conflictValues(value); 087 if (conflicts.contains(value)) continue; 088 if (conflicts.isEmpty()) { 089 SimpleNeighbour<V, T> n = new SimpleNeighbour<V, T>(variable, value); 090 if (!iHC || n.value() <= 0) return n; 091 else continue; 092 } 093 094 Map<V, T> assignments = new HashMap<V, T>(); 095 assignments.put(variable, value); 096 097 for (T conflict: conflicts) 098 conflict.variable().unassign(solution.getIteration()); 099 variable.assign(solution.getIteration(), value); 100 101 Double v = resolve(solution, total, startTime, assignments, new ArrayList<T>(conflicts), 0); 102 if (!conflicts.isEmpty()) 103 attempts ++; 104 105 variable.unassign(solution.getIteration()); 106 for (T conflict: conflicts) 107 conflict.variable().assign(solution.getIteration(), conflict); 108 if (old != null) variable.assign(solution.getIteration(), old); 109 110 if (v != null) 111 return new SwapNeighbour(assignments.values(), v); 112 113 if (attempts >= iMaxAttempts) break; 114 } 115 } 116 return null; 117 } 118 119 /** 120 * Return true if the time limit was reached, number of attempts are limited to 1 in such a case. 121 */ 122 protected boolean isTimeLimitReached(long startTime) { 123 return iTimeLimit > 0 && (JProf.currentTimeMillis() - startTime) > iTimeLimit; 124 } 125 126 /** 127 * Try to resolve given conflicts. For each conflicting variable it tries to find a 128 * value with no conflict that is compatible with some other assignment 129 * of the other conflicting variables. 130 * @param solution current solution 131 * @param total original value of the current solution 132 * @param assignments re-assignments to be made 133 * @param conflicts list of conflicts to resolve 134 * @param index index in the list of conflicts 135 * @return value of the modified solution, null if cannot be resolved 136 */ 137 public Double resolve(Solution<V, T> solution, double total, long startTime, Map<V, T> assignments, List<T> conflicts, int index) { 138 if (index == conflicts.size()) return solution.getModel().getTotalValue() - total; 139 T conflict = conflicts.get(index); 140 V variable = conflict.variable(); 141 142 List<T> values = variable.values(); 143 if (values.isEmpty()) return null; 144 145 int valIdx = ToolBox.random(values.size()); 146 int attempts = 0; 147 for (int i = 0; i < values.size(); i++) { 148 T value = values.get((i + valIdx) % values.size()); 149 if (value.equals(conflict) || solution.getModel().inConflict(value)) continue; 150 151 variable.assign(solution.getIteration(), value); 152 Double v = resolve(solution, total, startTime, assignments, conflicts, 1 + index); 153 variable.unassign(solution.getIteration()); 154 attempts ++; 155 156 if (v != null && (!iHC || v <= 0)) { 157 assignments.put(variable, value); 158 return v; 159 } 160 if (attempts >= iMaxAttempts || isTimeLimitReached(startTime)) break; 161 } 162 163 return null; 164 } 165 166 public class SwapNeighbour extends Neighbour<V, T> { 167 private double iValue = 0; 168 private Collection<T> iAssignments = null; 169 170 public SwapNeighbour(Collection<T> assignments, double value) { 171 iAssignments = assignments; iValue = value; 172 } 173 174 @Override 175 public double value() { 176 return iValue; 177 } 178 179 @Override 180 public void assign(long iteration) { 181 for (T placement: iAssignments) 182 if (placement.variable().getAssignment() != null) 183 placement.variable().unassign(iteration); 184 for (T placement: iAssignments) 185 placement.variable().assign(iteration, placement); 186 } 187 188 @Override 189 public String toString() { 190 StringBuffer sb = new StringBuffer("Swap{" + iValue + ": "); 191 for (Iterator<T> i = iAssignments.iterator(); i.hasNext(); ) { 192 T p = i.next(); 193 sb.append("\n " + p.variable().getName() + " " + p.getName() + (i.hasNext() ? "," : "")); 194 } 195 sb.append("}"); 196 return sb.toString(); 197 } 198 } 199}