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