001package org.cpsolver.ifs.heuristics; 002 003import java.util.ArrayList; 004import java.util.HashMap; 005import java.util.List; 006import java.util.Map; 007 008import org.apache.log4j.Logger; 009import org.cpsolver.ifs.model.InfoProvider; 010import org.cpsolver.ifs.model.Neighbour; 011import org.cpsolver.ifs.model.Value; 012import org.cpsolver.ifs.model.Variable; 013import org.cpsolver.ifs.solution.Solution; 014import org.cpsolver.ifs.solver.Solver; 015import org.cpsolver.ifs.util.DataProperties; 016import org.cpsolver.ifs.util.Progress; 017 018/** 019 * A round robin neighbour selection. Two or more {@link NeighbourSelection} 020 * needs to be registered within the selection. This selection criterion takes 021 * the registered neighbour selections one by one and performs 022 * {@link NeighbourSelection#init(Solver)} and then it is using 023 * {@link NeighbourSelection#selectNeighbour(Solution)} to select a neighbour. 024 * When null is returned by the underlaying selection, next registered neighbour 025 * selection is initialized and used for the following selection(s). If the last 026 * registered selection returns null, the selection is returned to the first 027 * registered neighbour selection (it is initialized before used again). 028 * 029 * <br> 030 * <br> 031 * 032 * @version StudentSct 1.3 (Student Sectioning)<br> 033 * Copyright (C) 2007 - 2014 Tomáš Müller<br> 034 * <a href="mailto:muller@unitime.org">muller@unitime.org</a><br> 035 * <a href="http://muller.unitime.org">http://muller.unitime.org</a><br> 036 * <br> 037 * This library is free software; you can redistribute it and/or modify 038 * it under the terms of the GNU Lesser General Public License as 039 * published by the Free Software Foundation; either version 3 of the 040 * License, or (at your option) any later version. <br> 041 * <br> 042 * This library is distributed in the hope that it will be useful, but 043 * WITHOUT ANY WARRANTY; without even the implied warranty of 044 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 045 * Lesser General Public License for more details. <br> 046 * <br> 047 * You should have received a copy of the GNU Lesser General Public 048 * License along with this library; if not see 049 * <a href='http://www.gnu.org/licenses/'>http://www.gnu.org/licenses/</a>. 050 * 051 * @param <V> Variable 052 * @param <T> Value 053 */ 054public class RoundRobinNeighbourSelection<V extends Variable<V, T>, T extends Value<V, T>> extends StandardNeighbourSelection<V, T> { 055 protected static Logger sLogger = Logger.getLogger(RoundRobinNeighbourSelection.class); 056 private int iSelectionIdx = -1; 057 private List<NeighbourSelection<V, T>> iSelections = new ArrayList<NeighbourSelection<V, T>>(); 058 protected Solver<V, T> iSolver = null; 059 060 /** 061 * Constructor 062 * 063 * @param properties 064 * configuration 065 * @throws Exception thrown when initialization fails 066 */ 067 public RoundRobinNeighbourSelection(DataProperties properties) throws Exception { 068 super(properties); 069 } 070 071 /** Register a neighbour selection 072 * @param selection a neighbour selection to include in the selection 073 **/ 074 public void registerSelection(NeighbourSelection<V, T> selection) { 075 iSelections.add(selection); 076 } 077 078 /** Initialization */ 079 @Override 080 public void init(Solver<V, T> solver) { 081 super.init(solver); 082 iSolver = solver; 083 } 084 085 /** 086 * Select neighbour. A first registered selections is initialized and used 087 * until it returns null, then the second registered selections is 088 * initialized and used and vice versa. 089 */ 090 @Override 091 public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) { 092 int nrChanges = 0; 093 while (nrChanges <= iSelections.size()) { 094 int selectionIndex = getSelectionIndex(); 095 NeighbourSelection<V, T> selection = iSelections.get(selectionIndex % iSelections.size()); 096 Neighbour<V, T> neighbour = selection.selectNeighbour(solution); 097 if (neighbour != null) 098 return neighbour; 099 changeSelection(selectionIndex); 100 nrChanges ++; 101 } 102 return null; 103 } 104 105 public int getSelectionIndex() { 106 if (iSelectionIdx == -1) changeSelection(-1); 107 iSolver.currentSolution().getLock().readLock().lock(); 108 try { 109 return iSelectionIdx; 110 } finally { 111 iSolver.currentSolution().getLock().readLock().unlock(); 112 } 113 } 114 115 /** Change selection 116 * @param selectionIndex current selection index 117 **/ 118 @SuppressWarnings("unchecked") 119 public void changeSelection(int selectionIndex) { 120 iSolver.currentSolution().getLock().writeLock().lock(); 121 try { 122 Progress progress = Progress.getInstance(iSolver.currentSolution().getModel()); 123 int newSelectionIndex = 1 + selectionIndex; 124 if (newSelectionIndex <= iSelectionIdx) return; // already changed 125 if (selectionIndex == -1 && iSelectionIdx >= 0) return; // already changed 126 iSelectionIdx = newSelectionIndex; 127 if (selectionIndex >= 0) { 128 try { 129 NeighbourSelection<V, T> selection = iSelections.get(selectionIndex % iSelections.size()); 130 if (selection instanceof InfoProvider) { 131 Map<String, String> info = new HashMap<String, String>(); 132 ((InfoProvider<V, T>)selection).getInfo(iSolver.currentSolution().getAssignment(), info); 133 if (!info.isEmpty()) 134 for (Map.Entry<String, String> e: info.entrySet()) 135 progress.debug(e.getKey() + ": " + e.getValue()); 136 } 137 } catch (Exception e) {} 138 } 139 sLogger.info("Phase changed to " + ((newSelectionIndex % iSelections.size()) + 1)); 140 progress.debug(iSolver.currentSolution().toString()); 141 if (iSolver.currentSolution().getBestInfo() == null || iSolver.getSolutionComparator().isBetterThanBestSolution(iSolver.currentSolution())) 142 iSolver.currentSolution().saveBest(); 143 iSelections.get(iSelectionIdx % iSelections.size()).init(iSolver); 144 } finally { 145 iSolver.currentSolution().getLock().writeLock().unlock(); 146 } 147 } 148 149 public NeighbourSelection<V, T> getSelection() { 150 return iSelections.get(getSelectionIndex() % iSelections.size()); 151 } 152}