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