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