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 Tomas Muller<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 while (true) { 093 int selectionIndex = getSelectionIndex(); 094 NeighbourSelection<V, T> selection = iSelections.get(selectionIndex % iSelections.size()); 095 Neighbour<V, T> neighbour = selection.selectNeighbour(solution); 096 if (neighbour != null) 097 return neighbour; 098 changeSelection(selectionIndex); 099 } 100 } 101 102 public int getSelectionIndex() { 103 if (iSelectionIdx == -1) changeSelection(-1); 104 iSolver.currentSolution().getLock().readLock().lock(); 105 try { 106 return iSelectionIdx; 107 } finally { 108 iSolver.currentSolution().getLock().readLock().unlock(); 109 } 110 } 111 112 /** Change selection 113 * @param selectionIndex current selection index 114 **/ 115 @SuppressWarnings("unchecked") 116 public void changeSelection(int selectionIndex) { 117 iSolver.currentSolution().getLock().writeLock().lock(); 118 try { 119 Progress progress = Progress.getInstance(iSolver.currentSolution().getModel()); 120 int newSelectionIndex = 1 + selectionIndex; 121 if (newSelectionIndex <= iSelectionIdx) return; // already changed 122 iSelectionIdx = newSelectionIndex; 123 if (selectionIndex >= 0) { 124 try { 125 NeighbourSelection<V, T> selection = iSelections.get(selectionIndex % iSelections.size()); 126 if (selection instanceof InfoProvider) { 127 Map<String, String> info = new HashMap<String, String>(); 128 ((InfoProvider<V, T>)selection).getInfo(iSolver.currentSolution().getAssignment(), info); 129 if (!info.isEmpty()) 130 for (Map.Entry<String, String> e: info.entrySet()) 131 progress.debug(e.getKey() + ": " + e.getValue()); 132 } 133 } catch (Exception e) {} 134 } 135 sLogger.info("Phase changed to " + ((newSelectionIndex % iSelections.size()) + 1)); 136 progress.debug(iSolver.currentSolution().toString()); 137 if (iSolver.currentSolution().getBestInfo() == null || iSolver.getSolutionComparator().isBetterThanBestSolution(iSolver.currentSolution())) 138 iSolver.currentSolution().saveBest(); 139 iSelections.get(iSelectionIdx % iSelections.size()).init(iSolver); 140 } finally { 141 iSolver.currentSolution().getLock().writeLock().unlock(); 142 } 143 } 144 145 public NeighbourSelection<V, T> getSelection() { 146 return iSelections.get(getSelectionIndex() % iSelections.size()); 147 } 148}