001package net.sf.cpsolver.ifs.heuristics; 002 003import java.util.ArrayList; 004import java.util.List; 005 006import net.sf.cpsolver.ifs.model.Neighbour; 007import net.sf.cpsolver.ifs.model.Value; 008import net.sf.cpsolver.ifs.model.Variable; 009import net.sf.cpsolver.ifs.solution.Solution; 010import net.sf.cpsolver.ifs.solver.Solver; 011import net.sf.cpsolver.ifs.util.DataProperties; 012 013import org.apache.log4j.Logger; 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.2 (Student Sectioning)<br> 030 * Copyright (C) 2007 - 2010 Tomáš Müller<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 049public class RoundRobinNeighbourSelection<V extends Variable<V, T>, T extends Value<V, T>> extends 050 StandardNeighbourSelection<V, T> { 051 private 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 private Solver<V, T> iSolver = null; 055 056 /** 057 * Constructor 058 * 059 * @param properties 060 * configuration 061 * @throws Exception 062 */ 063 public RoundRobinNeighbourSelection(DataProperties properties) throws Exception { 064 super(properties); 065 } 066 067 /** Register a neighbour selection */ 068 public void registerSelection(NeighbourSelection<V, T> selection) { 069 iSelections.add(selection); 070 } 071 072 /** Initialization */ 073 @Override 074 public void init(Solver<V, T> solver) { 075 super.init(solver); 076 iSolver = solver; 077 } 078 079 /** 080 * Select neighbour. A first registered selections is initialized and used 081 * until it returns null, then the second registered selections is 082 * initialized and used and vice versa. 083 */ 084 @Override 085 public Neighbour<V, T> selectNeighbour(Solution<V, T> solution) { 086 if (iSelectionIdx == -1) { 087 iSelectionIdx = 0; 088 iSelections.get(iSelectionIdx).init(iSolver); 089 } 090 while (true) { 091 NeighbourSelection<V, T> selection = iSelections.get(iSelectionIdx); 092 Neighbour<V, T> neighbour = selection.selectNeighbour(solution); 093 if (neighbour != null) 094 return neighbour; 095 changeSelection(solution); 096 } 097 } 098 099 /** Change selection */ 100 public void changeSelection(Solution<V, T> solution) { 101 iSelectionIdx = (1 + iSelectionIdx) % iSelections.size(); 102 sLogger.debug("Phase changed to " + (iSelectionIdx + 1)); 103 if (solution.getBestInfo() == null || iSolver.getSolutionComparator().isBetterThanBestSolution(solution)) 104 solution.saveBest(); 105 iSelections.get(iSelectionIdx).init(iSolver); 106 } 107}