Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
04/14/10 03:52:07 (15 years ago)
Author:
abeham
Message:

Updated Tabu search, permutation move operators, real vector move operators, binary vector move operators #840
Added a Tabu Search TSP workbench

Location:
trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3
Files:
2 added
2 deleted
9 edited
5 moved

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/HeuristicLab.Encodings.PermutationEncoding-3.3.csproj

    r3233 r3340  
    107107    <Compile Include="Manipulators\TranslocationInversionManipulator.cs" />
    108108    <Compile Include="Manipulators\TranslocationManipulator.cs" />
     109    <Compile Include="Moves\PermutationMoveAttribute.cs" />
    109110    <Compile Include="Moves\ThreeIndexMove.cs" />
     111    <Compile Include="Moves\ThreeOpt\TranslocationMoveAbsoluteAttribute.cs" />
    110112    <Compile Include="Moves\ThreeOpt\ExhaustiveInsertionMoveGenerator.cs">
    111113      <SubType>Code</SubType>
    112114    </Compile>
    113     <Compile Include="Moves\ThreeOpt\PreventReaddAndRemovalTranslocationMoveTabuChecker.cs" />
    114     <Compile Include="Moves\ThreeOpt\PreventReaddTranslocationMoveTabuChecker.cs" />
    115     <Compile Include="Moves\ThreeOpt\PreventRemovalTranslocationMoveTabuChecker.cs" />
    116115    <Compile Include="Moves\ThreeOpt\StochasticTranslocationMultiMoveGenerator.cs" />
    117116    <Compile Include="Moves\ThreeOpt\StochasticTranslocationSingleMoveGenerator.cs" />
    118117    <Compile Include="Moves\ThreeOpt\TranslocationMove.cs" />
    119     <Compile Include="Moves\ThreeOpt\TranslocationMoveAttribute.cs" />
    120118    <Compile Include="Moves\ThreeOpt\TranslocationMoveGenerator.cs" />
     119    <Compile Include="Moves\ThreeOpt\TranslocationMoveHardTabuCriterion.cs" />
    121120    <Compile Include="Moves\ThreeOpt\TranslocationMoveMaker.cs" />
     121    <Compile Include="Moves\ThreeOpt\TranslocationMoveRelativeAttribute.cs" />
     122    <Compile Include="Moves\ThreeOpt\TranslocationMoveSoftTabuCriterion.cs" />
    122123    <Compile Include="Moves\ThreeOpt\TranslocationMoveTabuMaker.cs" />
    123124    <Compile Include="Moves\TwoIndexMove.cs">
     
    127128    <Compile Include="Moves\TwoOpt\ExhaustiveInversionMoveGenerator.cs" />
    128129    <Compile Include="Moves\TwoOpt\InversionMove.cs" />
     130    <Compile Include="Moves\TwoOpt\InversionMoveHardTabuCriterion.cs" />
    129131    <Compile Include="Moves\TwoOpt\InversionMoveRelativeAttribute.cs" />
    130132    <Compile Include="Moves\TwoOpt\InversionMoveGenerator.cs" />
    131133    <Compile Include="Moves\TwoOpt\InversionMoveMaker.cs" />
     134    <Compile Include="Moves\TwoOpt\InversionMoveSoftTabuCriterion.cs" />
    132135    <Compile Include="Moves\TwoOpt\InversionMoveTabuMaker.cs" />
    133     <Compile Include="Moves\TwoOpt\PreventReaddAndRemovalInversionMoveTabuChecker.cs" />
    134     <Compile Include="Moves\TwoOpt\PreventReaddInversionMoveTabuChecker.cs" />
    135     <Compile Include="Moves\TwoOpt\PreventRemovalInversionMoveTabuChecker.cs" />
    136136    <Compile Include="Moves\TwoOpt\StochasticInversionMultiMoveGenerator.cs" />
    137137    <Compile Include="Moves\TwoOpt\StochasticInversionSingleMoveGenerator.cs" />
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Manipulators/InsertionManipulator.cs

    r3160 r3340  
    3030  /// It is implemented as described in Fogel, D.B. (1988). An Evolutionary Approach to the Traveling Salesman Problem, Biological Cybernetics, 60, pp. 139-144.
    3131  /// </remarks>
    32   [Item("InsertionManipulator", "An operator which moves randomly one element to another position in the permutation. It is implemented as described in Fogel, D.B. (1988). An Evolutionary Approach to the Traveling Salesman Problem, Biological Cybernetics, 60, pp. 139-144.")]
     32  [Item("InsertionManipulator", "An operator which moves randomly one element to another position in the permutation (Insertion is a special case of Translocation). It is implemented as described in Fogel, D.B. (1988). An Evolutionary Approach to the Traveling Salesman Problem, Biological Cybernetics, 60, pp. 139-144.")]
    3333  [StorableClass]
    3434  public class InsertionManipulator : PermutationManipulator {
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/ExhaustiveInsertionMoveGenerator.cs

    r3232 r3340  
    3434    public static TranslocationMove[] Apply(Permutation permutation) {
    3535      int length = permutation.Length;
    36       TranslocationMove[] moves = new TranslocationMove[length * (length - 1)];
     36      TranslocationMove[] moves = null;
    3737      int count = 0;
    38       for (int i = 0; i < length; i++) {
    39         for (int j = 1; j <= length - 1; j++) {
    40           moves[count++] = new TranslocationMove(i, i, (i + j) % length);
     38      if (permutation.PermutationType == PermutationTypes.Absolute) {
     39        moves = new TranslocationMove[length * (length - 1)];
     40        for (int i = 0; i < length; i++) {
     41          for (int j = 1; j <= length - 1; j++) {
     42            moves[count++] = new TranslocationMove(i, i, (i + j) % length);
     43          }
     44        }
     45      } else {
     46        moves = new TranslocationMove[length * (length - 1) - 2];
     47        for (int i = 0; i < length; i++) {
     48          for (int j = 1; j <= length - 1; j++) {
     49            if (i == 0 && j == length - 1
     50              || i == length - 1 && j == 1) continue;
     51            moves[count++] = new TranslocationMove(i, i, (i + j) % length);
     52          }
    4153        }
    4254      }
     55      System.Diagnostics.Debug.Assert(count == moves.Length);
    4356      return moves;
    4457    }
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/StochasticTranslocationSingleMoveGenerator.cs

    r3232 r3340  
    4343      int length = permutation.Length;
    4444      int index1, index2, index3;
    45       index1 = random.Next(length - 1);
    4645      do {
    47         index2 = random.Next(index1, length);
    48       } while (index2 - index1 >= length - 2);
    49       do {
    50         index3 = random.Next(length - index2 + index1);
    51       } while (index3 == index1);
    52      
     46        index1 = random.Next(length);
     47        do {
     48          index2 = random.Next(index1, length);
     49        } while (index2 - index1 >= length - 2);
     50        do {
     51          index3 = random.Next(length - index2 + index1);
     52        } while (index3 == index1);
     53      } while (permutation.PermutationType != PermutationTypes.Absolute && (index1 == 0 && index3 == length - 1 || index1 == length - 1 && index3 == 0));
    5354      return new TranslocationMove(index1, index2, index3);
    5455    }
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/TranslocationMoveHardTabuCriterion.cs

    r3307 r3340  
    2929
    3030namespace HeuristicLab.Encodings.PermutationEncoding {
    31   [Item("PreventReaddAndRemovalTranslocationMoveTabuChecker", "Prevents readding of previously deleted edges as well as deleting previously added edges.")]
     31  [Item("TranslocationMoveHardTabuCriterion", @"For relative postion encoded permutations it prevents readding of previously deleted edges as well as deleting previously added edges.
     32  For absolute position encoded permutations it prevents moving a number if it was previously moved.
     33
     34If the aspiration condition is activated, a move will not be considered tabu against a move in the tabu list if it leads to a better solution than the quality recorded with the move in the tabu list.")]
    3235  [StorableClass]
    33   public class PreventReaddAndRemovalTranslocationMoveTabuChecker : SingleSuccessorOperator, IPermutationTranslocationMoveOperator, ITabuChecker {
     36  public class TranslocationMoveHardTabuCriterion : SingleSuccessorOperator, IPermutationTranslocationMoveOperator, ITabuChecker {
    3437    public override bool CanChangeName {
    3538      get { return false; }
     
    4750      get { return (ILookupParameter<BoolValue>)Parameters["MoveTabu"]; }
    4851    }
    49     private ScopeParameter CurrentScopeParameter {
    50       get { return (ScopeParameter)Parameters["CurrentScope"]; }
     52    public IValueLookupParameter<BoolValue> MaximizationParameter {
     53      get { return (IValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
     54    }
     55    public ILookupParameter<DoubleValue> MoveQualityParameter {
     56      get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
     57    }
     58    public ValueParameter<BoolValue> UseAspirationCriterionParameter {
     59      get { return (ValueParameter<BoolValue>)Parameters["UseAspirationCriterion"]; }
    5160    }
    5261
    53     public PreventReaddAndRemovalTranslocationMoveTabuChecker()
     62    public BoolValue UseAspirationCriterion {
     63      get { return UseAspirationCriterionParameter.Value; }
     64      set { UseAspirationCriterionParameter.Value = value; }
     65    }
     66
     67    public TranslocationMoveHardTabuCriterion()
    5468      : base() {
    5569      Parameters.Add(new LookupParameter<TranslocationMove>("TranslocationMove", "The move to evaluate."));
     
    5771      Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation."));
    5872      Parameters.Add(new LookupParameter<ItemList<IItem>>("TabuList", "The tabu list."));
    59       Parameters.Add(new ScopeParameter("CurrentScope", "The current scope."));
     73      Parameters.Add(new ValueParameter<BoolValue>("UseAspirationCriterion", "Whether to use the aspiration criterion or not.", new BoolValue(true)));
     74      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, else if it is a minimization problem."));
     75      Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The quality of the current move."));
    6076    }
    6177
     
    6581      Permutation permutation = PermutationParameter.ActualValue;
    6682      int length = permutation.Length;
    67       int E1S = permutation.GetCircular(move.Index1 - 1);
    68       int E1T = permutation[move.Index1];
    69       int E2S = permutation[move.Index2];
    70       int E2T = permutation.GetCircular(move.Index2 + 1);
    71       int E3S, E3T;
    72       if (move.Index3 > move.Index1) {
    73         E3S = permutation.GetCircular(move.Index3 + move.Index2 - move.Index1);
    74         E3T = permutation.GetCircular(move.Index3 + move.Index2 - move.Index1 + 1);
     83      double moveQuality = MoveQualityParameter.ActualValue.Value;
     84      bool maximization = MaximizationParameter.ActualValue.Value;
     85      bool useAspiration = UseAspirationCriterion.Value;
     86      bool isTabu = false;
     87
     88      if (permutation.PermutationType == PermutationTypes.Absolute) {
     89        int count = move.Index2 - move.Index1 + 1;
     90        int[] numbers = new int[count];
     91        for (int i = move.Index1; i <= move.Index2; i++)
     92          numbers[i - move.Index1] = permutation[i];
     93
     94        foreach (IItem tabuMove in tabuList) {
     95          TranslocationMoveAbsoluteAttribute attribute = (tabuMove as TranslocationMoveAbsoluteAttribute);
     96          if (attribute != null) {
     97            if (!useAspiration
     98              || maximization && moveQuality <= attribute.MoveQuality
     99              || !maximization && moveQuality >= attribute.MoveQuality) { // if the move quality is improving beyond what was recorded when the move in the tabu list was recorded the move is regarded as okay
     100
     101              for (int i = 0; i < count; i++) {
     102                for (int j = 0; j < attribute.Number.Length; j++) {
     103                  if (attribute.Number[j] == numbers[i]) {
     104                    isTabu = true;
     105                    break;
     106                  }
     107                }
     108                if (isTabu) break;
     109              }
     110            }
     111          }
     112          if (isTabu) break;
     113        }
    75114      } else {
    76         E3S = permutation.GetCircular(move.Index3 - 1);
    77         E3T = permutation[move.Index3];
    78       }
    79       bool isTabu = (move.Index1 == move.Index3
    80         || move.Index2 - move.Index1 >= permutation.Length - 2
    81         || move.Index1 == permutation.Length - 1 && move.Index3 == 0
    82         || move.Index3 == permutation.Length - 1 && move.Index1 == 0);
    83       if (!isTabu) {
     115        int E1S = permutation.GetCircular(move.Index1 - 1);
     116        int E1T = permutation[move.Index1];
     117        int E2S = permutation[move.Index2];
     118        int E2T = permutation.GetCircular(move.Index2 + 1);
     119        int E3S, E3T;
     120        if (move.Index3 > move.Index1) {
     121          E3S = permutation.GetCircular(move.Index3 + move.Index2 - move.Index1);
     122          E3T = permutation.GetCircular(move.Index3 + move.Index2 - move.Index1 + 1);
     123        } else {
     124          E3S = permutation.GetCircular(move.Index3 - 1);
     125          E3T = permutation[move.Index3];
     126        }
    84127        foreach (IItem tabuMove in tabuList) {
    85           TranslocationMoveAttribute attribute = (tabuMove as TranslocationMoveAttribute);
     128          TranslocationMoveRelativeAttribute attribute = (tabuMove as TranslocationMoveRelativeAttribute);
    86129          if (attribute != null) {
    87             // if previously deleted Edge1Source-Target is readded
    88             if (attribute.Edge1Source == E3S && attribute.Edge1Target == E1T || attribute.Edge1Source == E1T && attribute.Edge1Target == E3S
    89               || attribute.Edge1Source == E2S && attribute.Edge1Target == E3T || attribute.Edge1Source == E3T && attribute.Edge1Target == E2S
    90               || attribute.Edge1Source == E1S && attribute.Edge1Target == E2T || attribute.Edge1Source == E2T && attribute.Edge1Target == E1S
    91               // if previously deleted Edge2Source-Target is readded
    92               || attribute.Edge2Source == E3S && attribute.Edge2Target == E1T || attribute.Edge2Source == E1T && attribute.Edge2Target == E3S
    93               || attribute.Edge2Source == E2S && attribute.Edge2Target == E3T || attribute.Edge2Source == E3T && attribute.Edge2Target == E2S
    94               || attribute.Edge2Source == E1S && attribute.Edge2Target == E2T || attribute.Edge2Source == E2T && attribute.Edge2Target == E1S
    95               // if previously deleted Edge3Source-Target is readded
    96               || attribute.Edge3Source == E3S && attribute.Edge3Target == E1T || attribute.Edge3Source == E1T && attribute.Edge3Target == E3S
    97               || attribute.Edge3Source == E2S && attribute.Edge3Target == E3T || attribute.Edge3Source == E3T && attribute.Edge3Target == E2S
    98               || attribute.Edge3Source == E1S && attribute.Edge3Target == E2T || attribute.Edge3Source == E2T && attribute.Edge3Target == E1S
    99               // if previously added Edge3Source-Edge1Target is deleted
    100               || attribute.Edge3Source == E1S && attribute.Edge1Target == E1T || attribute.Edge3Source == E1T && attribute.Edge1Target == E1S
    101               || attribute.Edge3Source == E2S && attribute.Edge1Target == E2T || attribute.Edge3Source == E2T && attribute.Edge1Target == E2S
    102               || attribute.Edge3Source == E3S && attribute.Edge1Target == E3T || attribute.Edge3Source == E3T && attribute.Edge1Target == E3S
    103               // if previously added Edge2Source-Edge3Target is deleted
    104               || attribute.Edge2Source == E1S && attribute.Edge3Target == E1T || attribute.Edge2Source == E1T && attribute.Edge3Target == E1S
    105               || attribute.Edge2Source == E2S && attribute.Edge3Target == E2T || attribute.Edge2Source == E2T && attribute.Edge3Target == E2S
    106               || attribute.Edge2Source == E3S && attribute.Edge3Target == E3T || attribute.Edge2Source == E3T && attribute.Edge3Target == E3S
    107               // if previously added Edge1Source-Edge2Target is deleted
    108               || attribute.Edge1Source == E1S && attribute.Edge2Target == E1T || attribute.Edge1Source == E1T && attribute.Edge2Target == E1S
    109               || attribute.Edge1Source == E2S && attribute.Edge2Target == E2T || attribute.Edge1Source == E2T && attribute.Edge2Target == E2S
    110               || attribute.Edge1Source == E3S && attribute.Edge2Target == E3T || attribute.Edge1Source == E3T && attribute.Edge2Target == E3S) {
    111               isTabu = true;
    112               break;
     130            if (!useAspiration
     131              || maximization && moveQuality <= attribute.MoveQuality
     132              || !maximization && moveQuality >= attribute.MoveQuality) {
     133
     134              if (permutation.PermutationType == PermutationTypes.RelativeUndirected) {
     135                if (// if previously added Edge3Source-Edge1Target is deleted
     136                  attribute.Edge3Source == E1S && attribute.Edge1Target == E1T || attribute.Edge3Source == E1T && attribute.Edge1Target == E1S
     137                  || attribute.Edge3Source == E2S && attribute.Edge1Target == E2T || attribute.Edge3Source == E2T && attribute.Edge1Target == E2S
     138                  || attribute.Edge3Source == E3S && attribute.Edge1Target == E3T || attribute.Edge3Source == E3T && attribute.Edge1Target == E3S
     139                  // if previously added Edge2Source-Edge3Target is deleted
     140                  || attribute.Edge2Source == E1S && attribute.Edge3Target == E1T || attribute.Edge2Source == E1T && attribute.Edge3Target == E1S
     141                  || attribute.Edge2Source == E2S && attribute.Edge3Target == E2T || attribute.Edge2Source == E2T && attribute.Edge3Target == E2S
     142                  || attribute.Edge2Source == E3S && attribute.Edge3Target == E3T || attribute.Edge2Source == E3T && attribute.Edge3Target == E3S
     143                  // if previously added Edge1Source-Edge2Target is deleted
     144                  || attribute.Edge1Source == E1S && attribute.Edge2Target == E1T || attribute.Edge1Source == E1T && attribute.Edge2Target == E1S
     145                  || attribute.Edge1Source == E2S && attribute.Edge2Target == E2T || attribute.Edge1Source == E2T && attribute.Edge2Target == E2S
     146                  || attribute.Edge1Source == E3S && attribute.Edge2Target == E3T || attribute.Edge1Source == E3T && attribute.Edge2Target == E3S) {
     147                  isTabu = true;
     148                  break;
     149                }
     150              } else {
     151                if (// if previously added Edge3Source-Edge1Target is deleted
     152                  attribute.Edge3Source == E1S && attribute.Edge1Target == E1T
     153                  || attribute.Edge3Source == E2S && attribute.Edge1Target == E2T
     154                  || attribute.Edge3Source == E3S && attribute.Edge1Target == E3T
     155                  // if previously added Edge2Source-Edge3Target is deleted
     156                  || attribute.Edge2Source == E1S && attribute.Edge3Target == E1T
     157                  || attribute.Edge2Source == E2S && attribute.Edge3Target == E2T
     158                  || attribute.Edge2Source == E3S && attribute.Edge3Target == E3T
     159                  // if previously added Edge1Source-Edge2Target is deleted
     160                  || attribute.Edge1Source == E1S && attribute.Edge2Target == E1T
     161                  || attribute.Edge1Source == E2S && attribute.Edge2Target == E2T
     162                  || attribute.Edge1Source == E3S && attribute.Edge2Target == E3T) {
     163                  isTabu = true;
     164                  break;
     165                }
     166              }
    113167            }
    114168          }
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/TranslocationMoveRelativeAttribute.cs

    r3307 r3340  
    2424
    2525namespace HeuristicLab.Encodings.PermutationEncoding {
    26   [Item("TranslocationMoveAttribute", "Specifies the tabu attributes for a translocation and insertion move (3-opt).")]
     26  [Item("TranslocationMoveRelativeAttribute", "Specifies the tabu attributes for a translocation and insertion move (3-opt) on relative permutation encodings.")]
    2727  [StorableClass]
    28   public class TranslocationMoveAttribute : Item {
     28  public class TranslocationMoveRelativeAttribute : PermutationMoveAttribute {
    2929    [Storable]
    3030    public int Edge1Source { get; private set; }
     
    4141
    4242    [StorableConstructor]
    43     private TranslocationMoveAttribute(bool deserializing)
     43    private TranslocationMoveRelativeAttribute(bool deserializing)
    4444      : base() {
    4545    }
    4646
    47     public TranslocationMoveAttribute()
    48       : this(-1, -1, -1, -1, -1, -1) { }
     47    public TranslocationMoveRelativeAttribute()
     48      : this(-1, -1, -1, -1, -1, -1, -1) { }
    4949
    50     public TranslocationMoveAttribute(int edge1Source, int edge1Target, int edge2Source, int edge2Target, int edge3Source, int edge3Target)
    51       : base() {
     50    public TranslocationMoveRelativeAttribute(int edge1Source, int edge1Target, int edge2Source, int edge2Target, int edge3Source, int edge3Target, double moveQuality)
     51      : base(moveQuality) {
    5252      Edge1Source = edge1Source;
    5353      Edge1Target = edge1Target;
     
    5959
    6060    public override IDeepCloneable Clone(Cloner cloner) {
    61       TranslocationMoveAttribute clone = (TranslocationMoveAttribute)base.Clone(cloner);
     61      TranslocationMoveRelativeAttribute clone = (TranslocationMoveRelativeAttribute)base.Clone(cloner);
    6262      clone.Edge1Source = Edge1Source;
    6363      clone.Edge1Target = Edge1Target;
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/TranslocationMoveSoftTabuCriterion.cs

    r3307 r3340  
    2929
    3030namespace HeuristicLab.Encodings.PermutationEncoding {
    31   [Item("PreventReaddTranslocationMoveTabuChecker", "Prevents readding of previously deleted edges.")]
     31  [Item("TranslocationMoveSoftTabuCriterion", @"For relative postion encoded permutations it just prevents readding of previously deleted edges, but allows deleting previously added edges.
     32  For absolute position encoded permutations it prevents moving a number to a position it has previously occupied.
     33
     34If the aspiration condition is activated, a move will not be considered tabu against a move in the tabu list if it leads to a better solution than the quality recorded with the move in the tabu list.")]
    3235  [StorableClass]
    33   public class PreventReaddTranslocationMoveTabuChecker : SingleSuccessorOperator, IPermutationTranslocationMoveOperator, ITabuChecker {
     36  public class TranslocationMoveSoftTabuCriterion : SingleSuccessorOperator, IPermutationTranslocationMoveOperator, ITabuChecker {
    3437    public override bool CanChangeName {
    3538      get { return false; }
     
    4750      get { return (ILookupParameter<BoolValue>)Parameters["MoveTabu"]; }
    4851    }
    49     private ScopeParameter CurrentScopeParameter {
    50       get { return (ScopeParameter)Parameters["CurrentScope"]; }
     52    public IValueLookupParameter<BoolValue> MaximizationParameter {
     53      get { return (IValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
     54    }
     55    public ILookupParameter<DoubleValue> MoveQualityParameter {
     56      get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
     57    }
     58    public ValueParameter<BoolValue> UseAspirationCriterionParameter {
     59      get { return (ValueParameter<BoolValue>)Parameters["UseAspirationCriterion"]; }
    5160    }
    5261
    53     public PreventReaddTranslocationMoveTabuChecker()
     62    public BoolValue UseAspirationCriterion {
     63      get { return UseAspirationCriterionParameter.Value; }
     64      set { UseAspirationCriterionParameter.Value = value; }
     65    }
     66
     67    public TranslocationMoveSoftTabuCriterion()
    5468      : base() {
    5569      Parameters.Add(new LookupParameter<TranslocationMove>("TranslocationMove", "The move to evaluate."));
     
    5771      Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation."));
    5872      Parameters.Add(new LookupParameter<ItemList<IItem>>("TabuList", "The tabu list."));
    59       Parameters.Add(new ScopeParameter("CurrentScope", "The current scope."));
     73      Parameters.Add(new ValueParameter<BoolValue>("UseAspirationCriterion", "Whether to use the aspiration criterion or not.", new BoolValue(true)));
     74      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, else if it is a minimization problem."));
     75      Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The quality of the current move."));
    6076    }
    6177
     
    6581      Permutation permutation = PermutationParameter.ActualValue;
    6682      int length = permutation.Length;
    67       int E1S = permutation.GetCircular(move.Index1 - 1);
    68       int E1T = permutation[move.Index1];
    69       int E2S = permutation[move.Index2];
    70       int E2T = permutation.GetCircular(move.Index2 + 1);
    71       int E3S, E3T;
    72       if (move.Index3 > move.Index1) {
    73         E3S = permutation.GetCircular(move.Index3 + move.Index2 - move.Index1);
    74         E3T = permutation.GetCircular(move.Index3 + move.Index2 - move.Index1 + 1);
     83      double moveQuality = MoveQualityParameter.ActualValue.Value;
     84      bool maximization = MaximizationParameter.ActualValue.Value;
     85      bool useAspiration = UseAspirationCriterion.Value;
     86      bool isTabu = false;
     87
     88      if (permutation.PermutationType == PermutationTypes.Absolute) {
     89        int count = move.Index2 - move.Index1 + 1;
     90        int[] numbers = new int[count];
     91        for (int i = move.Index1; i <= move.Index2; i++)
     92          numbers[i - move.Index1] = permutation[i];
     93
     94        foreach (IItem tabuMove in tabuList) {
     95          TranslocationMoveAbsoluteAttribute attribute = (tabuMove as TranslocationMoveAbsoluteAttribute);
     96          if (attribute != null) {
     97            if (!useAspiration
     98              || maximization && moveQuality <= attribute.MoveQuality
     99              || !maximization && moveQuality >= attribute.MoveQuality) { // if the move quality is improving beyond what was recorded when the move in the tabu list was recorded the move is regarded as okay
     100
     101              for (int i = 0; i < count; i++) {
     102                for (int j = 0; j < attribute.Number.Length; j++) {
     103                  if (attribute.Number[j] == numbers[i] && attribute.OldPosition + j == move.Index3 + i) {
     104                    isTabu = true;
     105                    break;
     106                  }
     107                }
     108                if (isTabu) break;
     109              }
     110            }
     111          }
     112          if (isTabu) break;
     113        }
    75114      } else {
    76         E3S = permutation.GetCircular(move.Index3 - 1);
    77         E3T = permutation[move.Index3];
    78       }
    79       bool isTabu = (move.Index1 == move.Index3
    80         || move.Index2 - move.Index1 >= permutation.Length - 2
    81         || move.Index1 == permutation.Length - 1 && move.Index3 == 0
    82         || move.Index3 == permutation.Length - 1 && move.Index1 == 0);
    83       if (!isTabu) {
     115        int E1S = permutation.GetCircular(move.Index1 - 1);
     116        int E1T = permutation[move.Index1];
     117        int E2S = permutation[move.Index2];
     118        int E2T = permutation.GetCircular(move.Index2 + 1);
     119        int E3S, E3T;
     120        if (move.Index3 > move.Index1) {
     121          E3S = permutation.GetCircular(move.Index3 + move.Index2 - move.Index1);
     122          E3T = permutation.GetCircular(move.Index3 + move.Index2 - move.Index1 + 1);
     123        } else {
     124          E3S = permutation.GetCircular(move.Index3 - 1);
     125          E3T = permutation[move.Index3];
     126        }
    84127        foreach (IItem tabuMove in tabuList) {
    85           TranslocationMoveAttribute attribute = (tabuMove as TranslocationMoveAttribute);
     128          TranslocationMoveRelativeAttribute attribute = (tabuMove as TranslocationMoveRelativeAttribute);
    86129          if (attribute != null) {
    87             // if previously deleted Edge1Source-Target is readded
    88             if (attribute.Edge1Source == E3S && attribute.Edge1Target == E1T || attribute.Edge1Source == E1T && attribute.Edge1Target == E3S
    89               || attribute.Edge1Source == E2S && attribute.Edge1Target == E3T || attribute.Edge1Source == E3T && attribute.Edge1Target == E2S
    90               || attribute.Edge1Source == E1S && attribute.Edge1Target == E2T || attribute.Edge1Source == E2T && attribute.Edge1Target == E1S
    91               // if previously deleted Edge2Source-Target is readded
    92               || attribute.Edge2Source == E3S && attribute.Edge2Target == E1T || attribute.Edge2Source == E1T && attribute.Edge2Target == E3S
    93               || attribute.Edge2Source == E2S && attribute.Edge2Target == E3T || attribute.Edge2Source == E3T && attribute.Edge2Target == E2S
    94               || attribute.Edge2Source == E1S && attribute.Edge2Target == E2T || attribute.Edge2Source == E2T && attribute.Edge2Target == E1S
    95               // if previously deleted Edge3Source-Target is readded
    96               || attribute.Edge3Source == E3S && attribute.Edge3Target == E1T || attribute.Edge3Source == E1T && attribute.Edge3Target == E3S
    97               || attribute.Edge3Source == E2S && attribute.Edge3Target == E3T || attribute.Edge3Source == E3T && attribute.Edge3Target == E2S
    98               || attribute.Edge3Source == E1S && attribute.Edge3Target == E2T || attribute.Edge3Source == E2T && attribute.Edge3Target == E1S) {
    99               isTabu = true;
    100               break;
     130            if (!useAspiration
     131              || maximization && moveQuality <= attribute.MoveQuality
     132              || !maximization && moveQuality >= attribute.MoveQuality) {
     133
     134              // if previously deleted Edge1Source-Target is readded
     135              if (permutation.PermutationType == PermutationTypes.RelativeUndirected) {
     136                if (attribute.Edge1Source == E3S && attribute.Edge1Target == E1T || attribute.Edge1Source == E1T && attribute.Edge1Target == E3S
     137                  || attribute.Edge1Source == E2S && attribute.Edge1Target == E3T || attribute.Edge1Source == E3T && attribute.Edge1Target == E2S
     138                  || attribute.Edge1Source == E1S && attribute.Edge1Target == E2T || attribute.Edge1Source == E2T && attribute.Edge1Target == E1S
     139                  // if previously deleted Edge2Source-Target is readded
     140                  || attribute.Edge2Source == E3S && attribute.Edge2Target == E1T || attribute.Edge2Source == E1T && attribute.Edge2Target == E3S
     141                  || attribute.Edge2Source == E2S && attribute.Edge2Target == E3T || attribute.Edge2Source == E3T && attribute.Edge2Target == E2S
     142                  || attribute.Edge2Source == E1S && attribute.Edge2Target == E2T || attribute.Edge2Source == E2T && attribute.Edge2Target == E1S
     143                  // if previously deleted Edge3Source-Target is readded
     144                  || attribute.Edge3Source == E3S && attribute.Edge3Target == E1T || attribute.Edge3Source == E1T && attribute.Edge3Target == E3S
     145                  || attribute.Edge3Source == E2S && attribute.Edge3Target == E3T || attribute.Edge3Source == E3T && attribute.Edge3Target == E2S
     146                  || attribute.Edge3Source == E1S && attribute.Edge3Target == E2T || attribute.Edge3Source == E2T && attribute.Edge3Target == E1S) {
     147                  isTabu = true;
     148                  break;
     149                }
     150              } else {
     151                if (attribute.Edge1Source == E3S && attribute.Edge1Target == E1T
     152                  || attribute.Edge1Source == E2S && attribute.Edge1Target == E3T
     153                  || attribute.Edge1Source == E1S && attribute.Edge1Target == E2T
     154                  // if previously deleted Edge2Source-Target is readded
     155                  || attribute.Edge2Source == E3S && attribute.Edge2Target == E1T
     156                  || attribute.Edge2Source == E2S && attribute.Edge2Target == E3T
     157                  || attribute.Edge2Source == E1S && attribute.Edge2Target == E2T
     158                  // if previously deleted Edge3Source-Target is readded
     159                  || attribute.Edge3Source == E3S && attribute.Edge3Target == E1T
     160                  || attribute.Edge3Source == E2S && attribute.Edge3Target == E3T
     161                  || attribute.Edge3Source == E1S && attribute.Edge3Target == E2T) {
     162                  isTabu = true;
     163                  break;
     164                }
     165              }
    101166            }
    102167          }
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/TranslocationMoveTabuMaker.cs

    r3232 r3340  
    4848    }
    4949
    50     protected override IItem GetTabuAttribute() {
     50    protected override IItem GetTabuAttribute(bool maximization, double quality, double moveQuality) {
    5151      TranslocationMove move = TranslocationMoveParameter.ActualValue;
    5252      Permutation permutation = PermutationParameter.ActualValue;
    53       if (move.Index3 > move.Index1)
    54         return new TranslocationMoveAttribute(permutation.GetCircular(move.Index1 - 1),
    55         permutation[move.Index1],
    56         permutation[move.Index2],
    57         permutation.GetCircular(move.Index2 + 1),
    58         permutation.GetCircular(move.Index3 + move.Index2 - move.Index1),
    59         permutation.GetCircular(move.Index3 + move.Index2 - move.Index1 + 1));
    60       else
    61         return new TranslocationMoveAttribute(permutation.GetCircular(move.Index1 - 1),
    62         permutation[move.Index1],
    63         permutation[move.Index2],
    64         permutation.GetCircular(move.Index2 + 1),
    65         permutation.GetCircular(move.Index3 - 1),
    66         permutation.GetCircular(move.Index3));
     53      double baseQuality = moveQuality;
     54      if (maximization && quality > moveQuality || !maximization && quality < moveQuality) baseQuality = quality; // we make an uphill move, the lower bound is the solution quality
     55      if (permutation.PermutationType == PermutationTypes.Absolute) {
     56        int[] numbers = new int[move.Index2 - move.Index1 + 1];
     57        for (int i = 0; i < numbers.Length; i++) {
     58          numbers[i] = permutation[i + move.Index1];
     59        }
     60        return new TranslocationMoveAbsoluteAttribute(numbers, move.Index1, move.Index3, baseQuality); ;
     61      } else {
     62        if (move.Index3 > move.Index1)
     63          return new TranslocationMoveRelativeAttribute(permutation.GetCircular(move.Index1 - 1),
     64          permutation[move.Index1],
     65          permutation[move.Index2],
     66          permutation.GetCircular(move.Index2 + 1),
     67          permutation.GetCircular(move.Index3 + move.Index2 - move.Index1),
     68          permutation.GetCircular(move.Index3 + move.Index2 - move.Index1 + 1),
     69          baseQuality);
     70        else
     71          return new TranslocationMoveRelativeAttribute(permutation.GetCircular(move.Index1 - 1),
     72          permutation[move.Index1],
     73          permutation[move.Index2],
     74          permutation.GetCircular(move.Index2 + 1),
     75          permutation.GetCircular(move.Index3 - 1),
     76          permutation.GetCircular(move.Index3),
     77          baseQuality);
     78      }
    6779    }
    6880  }
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/ExhaustiveInversionMoveGenerator.cs

    r3233 r3340  
    3131    public static InversionMove[] Apply(Permutation permutation) {
    3232      int length = permutation.Length;
    33       int totalMoves = (length) * (length - 1) / 2; // - 3;
    34       InversionMove[] moves = new InversionMove[totalMoves];
     33      int totalMoves = (length) * (length - 1) / 2;
     34      InversionMove[] moves = null;
    3535      int count = 0;
    3636
    3737      if (permutation.PermutationType == PermutationTypes.RelativeUndirected) {
     38        moves = new InversionMove[totalMoves - 3];
    3839        for (int i = 0; i < length - 1; i++) {
    3940          for (int j = i + 1; j < length; j++) {
     
    4445        }
    4546      } else {
    46           for (int i = 0; i < length - 1; i++)
    47             for (int j = i + 1; j < length; j++) {
    48               moves[count++] = new InversionMove(i, j);
    49             }
     47        moves = new InversionMove[totalMoves];
     48        for (int i = 0; i < length - 1; i++)
     49          for (int j = i + 1; j < length; j++) {
     50            moves[count++] = new InversionMove(i, j);
     51          }
    5052      }
    5153      return moves;
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/InversionMoveAbsoluteAttribute.cs

    r3233 r3340  
    2626  [Item("InversionMoveAbsoluteAttribute", "Specifies the tabu attributes for an inversion move (2-opt) on an absolute position permutation.")]
    2727  [StorableClass]
    28   public class InversionMoveAbsoluteAttribute : Item {
     28  public class InversionMoveAbsoluteAttribute : PermutationMoveAttribute {
    2929    [Storable]
    3030    public int Index1 { get; private set; }
     
    4242
    4343    public InversionMoveAbsoluteAttribute()
    44       : this(-1, -1, -1, -1) { }
     44      : this(-1, -1, -1, -1, -1) { }
    4545
    46     public InversionMoveAbsoluteAttribute(int index1, int number1, int index2, int number2)
    47       : base() {
     46    public InversionMoveAbsoluteAttribute(int index1, int number1, int index2, int number2, double moveQuality)
     47      : base(moveQuality) {
    4848      Index1 = index1;
    4949      Number1 = number1;
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/InversionMoveHardTabuCriterion.cs

    r3307 r3340  
    2929
    3030namespace HeuristicLab.Encodings.PermutationEncoding {
    31   [Item("PreventRemovalInversionMoveTabuChecker", "Prevents deleting of previously added edges.")]
     31  [Item("InversionMoveHardTabuCriterion", @"For relative postion encoded permutations it prevents readding of previously deleted edges as well as deleting previously added edges.
     32  For absolute position encoded permutations it prevents moving a number if it was previously moved.
     33
     34If the aspiration condition is activated, a move will not be considered tabu against a move in the tabu list if it leads to a better solution than the quality recorded with the move in the tabu list.")]
    3235  [StorableClass]
    33   public class PreventRemovalInversionMoveTabuChecker : SingleSuccessorOperator, IPermutationInversionMoveOperator, ITabuChecker {
     36  public class InversionMoveHardTabuCriterion : SingleSuccessorOperator, IPermutationInversionMoveOperator, ITabuChecker {
    3437    public override bool CanChangeName {
    3538      get { return false; }
     
    4750      get { return (ILookupParameter<BoolValue>)Parameters["MoveTabu"]; }
    4851    }
    49     private ScopeParameter CurrentScopeParameter {
    50       get { return (ScopeParameter)Parameters["CurrentScope"]; }
     52    public IValueLookupParameter<BoolValue> MaximizationParameter {
     53      get { return (IValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
     54    }
     55    public ILookupParameter<DoubleValue> MoveQualityParameter {
     56      get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
     57    }
     58    public ValueParameter<BoolValue> UseAspirationCriterionParameter {
     59      get { return (ValueParameter<BoolValue>)Parameters["UseAspirationCriterion"]; }
    5160    }
    5261
    53     public PreventRemovalInversionMoveTabuChecker()
     62    public BoolValue UseAspirationCriterion {
     63      get { return UseAspirationCriterionParameter.Value; }
     64      set { UseAspirationCriterionParameter.Value = value; }
     65    }
     66
     67    public InversionMoveHardTabuCriterion()
    5468      : base() {
    5569      Parameters.Add(new LookupParameter<InversionMove>("InversionMove", "The move to evaluate."));
     
    5771      Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation."));
    5872      Parameters.Add(new LookupParameter<ItemList<IItem>>("TabuList", "The tabu list."));
    59       Parameters.Add(new ScopeParameter("CurrentScope", "The current scope."));
     73      Parameters.Add(new ValueParameter<BoolValue>("UseAspirationCriterion", "Whether to use the aspiration criterion or not.", new BoolValue(true)));
     74      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, else if it is a minimization problem."));
     75      Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The quality of the current move."));
    6076    }
    6177
     
    6581      Permutation permutation = PermutationParameter.ActualValue;
    6682      int length = permutation.Length;
     83      double moveQuality = MoveQualityParameter.ActualValue.Value;
     84      bool maximization = MaximizationParameter.ActualValue.Value;
     85      bool useAspiration = UseAspirationCriterion.Value;
    6786      bool isTabu = false;
     87
    6888      foreach (IItem tabuMove in tabuList) {
    69         switch (permutation.PermutationType) {
    70           case PermutationTypes.RelativeUndirected: {
    71               int E1S = permutation.GetCircular(move.Index1 - 1);
    72               int E1T = permutation[move.Index1];
    73               int E2S = permutation[move.Index2];
    74               int E2T = permutation.GetCircular(move.Index2 + 1);
    75               InversionMoveRelativeAttribute relAttrib = (tabuMove as InversionMoveRelativeAttribute);
    76               if (relAttrib != null) {
    77                 if (relAttrib.Edge1Source == E1S && relAttrib.Edge2Source == E1T || relAttrib.Edge1Source == E1T && relAttrib.Edge2Source == E1S
    78                   || relAttrib.Edge1Source == E2S && relAttrib.Edge2Source == E2T || relAttrib.Edge1Source == E2T && relAttrib.Edge2Source == E2S
    79                   // if previously added Edge1Target-Edge2Target is deleted
    80                   || relAttrib.Edge1Target == E2S && relAttrib.Edge2Target == E2T || relAttrib.Edge1Target == E2T && relAttrib.Edge2Target == E2S
    81                   || relAttrib.Edge1Target == E1S && relAttrib.Edge2Target == E1T || relAttrib.Edge1Target == E1T && relAttrib.Edge2Target == E1S) {
    82                   isTabu = true;
     89        PermutationMoveAttribute attrib = (tabuMove as PermutationMoveAttribute);
     90        if (!useAspiration
     91          || maximization && moveQuality <= attrib.MoveQuality
     92          || !maximization && moveQuality >= attrib.MoveQuality) {
     93          switch (permutation.PermutationType) {
     94            case PermutationTypes.RelativeUndirected: {
     95                int E1S = permutation.GetCircular(move.Index1 - 1);
     96                int E1T = permutation[move.Index1];
     97                int E2S = permutation[move.Index2];
     98                int E2T = permutation.GetCircular(move.Index2 + 1);
     99                InversionMoveRelativeAttribute relAttrib = (attrib as InversionMoveRelativeAttribute);
     100                if (relAttrib != null) {
     101                  if (relAttrib.Edge1Source == E1S && relAttrib.Edge2Source == E1T || relAttrib.Edge1Source == E1T && relAttrib.Edge2Source == E1S
     102                    || relAttrib.Edge1Source == E2S && relAttrib.Edge2Source == E2T || relAttrib.Edge1Source == E2T && relAttrib.Edge2Source == E2S
     103                    // if previously added Edge1Target-Edge2Target is deleted
     104                    || relAttrib.Edge1Target == E2S && relAttrib.Edge2Target == E2T || relAttrib.Edge1Target == E2T && relAttrib.Edge2Target == E2S
     105                    || relAttrib.Edge1Target == E1S && relAttrib.Edge2Target == E1T || relAttrib.Edge1Target == E1T && relAttrib.Edge2Target == E1S) {
     106                    isTabu = true;
     107                  }
    83108                }
    84109              }
    85             }
    86             break;
    87           case PermutationTypes.RelativeDirected: {
    88               int E1S = permutation.GetCircular(move.Index1 - 1);
    89               int E1T = permutation[move.Index1];
    90               int E2S = permutation[move.Index2];
    91               int E2T = permutation.GetCircular(move.Index2 + 1);
    92               InversionMoveRelativeAttribute relAttrib = (tabuMove as InversionMoveRelativeAttribute);
    93               if (relAttrib != null) {
    94                 if (relAttrib.Edge1Source == E1S && relAttrib.Edge2Source == E1T
    95                   || relAttrib.Edge1Source == E2S && relAttrib.Edge2Source == E2T
    96                   // if previously added Edge1Target-Edge2Target is deleted
    97                   || relAttrib.Edge1Target == E2S && relAttrib.Edge2Target == E2T
    98                   || relAttrib.Edge1Target == E1S && relAttrib.Edge2Target == E1T) {
    99                   isTabu = true;
     110              break;
     111            case PermutationTypes.RelativeDirected: {
     112                int E1S = permutation.GetCircular(move.Index1 - 1);
     113                int E1T = permutation[move.Index1];
     114                int E2S = permutation[move.Index2];
     115                int E2T = permutation.GetCircular(move.Index2 + 1);
     116                InversionMoveRelativeAttribute relAttrib = (attrib as InversionMoveRelativeAttribute);
     117                if (relAttrib != null) {
     118                  if (relAttrib.Edge1Source == E1S && relAttrib.Edge2Source == E1T
     119                    || relAttrib.Edge1Source == E2S && relAttrib.Edge2Source == E2T
     120                    // if previously added Edge1Target-Edge2Target is deleted
     121                    || relAttrib.Edge1Target == E2S && relAttrib.Edge2Target == E2T
     122                    || relAttrib.Edge1Target == E1S && relAttrib.Edge2Target == E1T) {
     123                    isTabu = true;
     124                  }
    100125                }
    101126              }
    102             }
    103             break;
    104           case PermutationTypes.Absolute: {
    105               int i1 = move.Index1;
    106               int n1 = permutation[move.Index1];
    107               int i2 = move.Index2;
    108               int n2 = permutation[move.Index2];
    109               InversionMoveAbsoluteAttribute absAttrib = (tabuMove as InversionMoveAbsoluteAttribute);
    110               if (absAttrib != null) {
    111                 if (absAttrib.Number1 == n1 || absAttrib.Number1 == n2
    112                   || absAttrib.Number2 == n2 || absAttrib.Number2 == n1)
    113                   isTabu = true;
     127              break;
     128            case PermutationTypes.Absolute: {
     129                int i1 = move.Index1;
     130                int n1 = permutation[move.Index1];
     131                int i2 = move.Index2;
     132                int n2 = permutation[move.Index2];
     133                InversionMoveAbsoluteAttribute absAttrib = (attrib as InversionMoveAbsoluteAttribute);
     134                if (absAttrib != null) {
     135                  if (absAttrib.Number1 == n1 || absAttrib.Number1 == n2
     136                    || absAttrib.Number2 == n2 || absAttrib.Number2 == n1)
     137                    isTabu = true;
    114138
     139                }
    115140              }
    116             }
    117             break;
    118           default: {
    119               throw new InvalidOperationException(Name + ": Unknown permutation type.");
    120             }
     141              break;
     142            default: {
     143                throw new InvalidOperationException(Name + ": Unknown permutation type.");
     144              }
     145          }
    121146        }
    122147        if (isTabu) break;
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/InversionMoveRelativeAttribute.cs

    r3233 r3340  
    2626  [Item("InversionMoveRelativeAttribute", "Specifies the tabu attributes for an inversion move (2-opt) on a relative position permutation.")]
    2727  [StorableClass]
    28   public class InversionMoveRelativeAttribute : Item {
     28  public class InversionMoveRelativeAttribute : PermutationMoveAttribute {
    2929    [Storable]
    3030    public int Edge1Source { get; private set; }
     
    4242
    4343    public InversionMoveRelativeAttribute()
    44       : this(-1, -1, -1, -1) { }
     44      : this(-1, -1, -1, -1, -1) { }
    4545
    46     public InversionMoveRelativeAttribute(int edge1Source, int edge1Target, int edge2Source, int edge2Target)
    47       : base() {
     46    public InversionMoveRelativeAttribute(int edge1Source, int edge1Target, int edge2Source, int edge2Target, double moveQuality)
     47      : base(moveQuality) {
    4848      Edge1Source = edge1Source;
    4949      Edge1Target = edge1Target;
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/InversionMoveSoftTabuCriterion.cs

    r3307 r3340  
    2929
    3030namespace HeuristicLab.Encodings.PermutationEncoding {
    31   [Item("PreventReaddInversionMoveTabuChecker", "Prevents readding of previously deleted edges, but allows deleting previously added edges.")]
     31  [Item("InversionMoveSoftTabuCriterion", @"For relative postion encoded permutations it just prevents readding of previously deleted edges, but allows deleting previously added edges.
     32  For absolute position encoded permutations it prevents moving a number to a position it has previously occupied.
     33
     34If the aspiration condition is activated, a move will not be considered tabu against a move in the tabu list if it leads to a better solution than the quality recorded with the move in the tabu list.")]
    3235  [StorableClass]
    33   public class PreventReaddInversionMoveTabuChecker : SingleSuccessorOperator, IPermutationInversionMoveOperator, ITabuChecker {
     36  public class InversionMoveSoftTabuCriterion : SingleSuccessorOperator, IPermutationInversionMoveOperator, ITabuChecker {
    3437    public override bool CanChangeName {
    3538      get { return false; }
     
    4750      get { return (ILookupParameter<BoolValue>)Parameters["MoveTabu"]; }
    4851    }
    49     private ScopeParameter CurrentScopeParameter {
    50       get { return (ScopeParameter)Parameters["CurrentScope"]; }
     52    public IValueLookupParameter<BoolValue> MaximizationParameter {
     53      get { return (IValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
     54    }
     55    public ILookupParameter<DoubleValue> MoveQualityParameter {
     56      get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
     57    }
     58    public ValueParameter<BoolValue> UseAspirationCriterionParameter {
     59      get { return (ValueParameter<BoolValue>)Parameters["UseAspirationCriterion"]; }
    5160    }
    5261
    53     public PreventReaddInversionMoveTabuChecker()
     62    public BoolValue UseAspirationCriterion {
     63      get { return UseAspirationCriterionParameter.Value; }
     64      set { UseAspirationCriterionParameter.Value = value; }
     65    }
     66
     67    public InversionMoveSoftTabuCriterion()
    5468      : base() {
    5569      Parameters.Add(new LookupParameter<InversionMove>("InversionMove", "The move to evaluate."));
     
    5771      Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation."));
    5872      Parameters.Add(new LookupParameter<ItemList<IItem>>("TabuList", "The tabu list."));
    59       Parameters.Add(new ScopeParameter("CurrentScope", "The current scope."));
     73      Parameters.Add(new ValueParameter<BoolValue>("UseAspirationCriterion", "Whether to use the aspiration criterion or not.", new BoolValue(true)));
     74      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, else if it is a minimization problem."));
     75      Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The quality of the current move."));
    6076    }
    6177
     
    6581      Permutation permutation = PermutationParameter.ActualValue;
    6682      int length = permutation.Length;
     83      double moveQuality = MoveQualityParameter.ActualValue.Value;
     84      bool maximization = MaximizationParameter.ActualValue.Value;
     85      bool useAspiration = UseAspirationCriterion.Value;
    6786      bool isTabu = false;
     87
    6888      foreach (IItem tabuMove in tabuList) {
    69         switch (permutation.PermutationType) {
    70           case PermutationTypes.RelativeUndirected: {
    71               int E1S = permutation.GetCircular(move.Index1 - 1);
    72               int E1T = permutation[move.Index1];
    73               int E2S = permutation[move.Index2];
    74               int E2T = permutation.GetCircular(move.Index2 + 1);
    75               InversionMoveRelativeAttribute relAttrib = (tabuMove as InversionMoveRelativeAttribute);
    76               if (relAttrib != null) {
    77                 // if previously deleted Edge1Source-Target is readded
    78                 if (relAttrib.Edge1Source == E1S && relAttrib.Edge1Target == E2S || relAttrib.Edge1Source == E2S && relAttrib.Edge1Target == E1S
    79                   || relAttrib.Edge1Source == E1T && relAttrib.Edge1Target == E2T || relAttrib.Edge1Source == E2T && relAttrib.Edge1Target == E1T
    80                   // if previously deleted Edge2Source-Target is readded
    81                   || relAttrib.Edge2Source == E1T && relAttrib.Edge2Target == E2T || relAttrib.Edge2Source == E2T && relAttrib.Edge2Target == E1T
    82                   || relAttrib.Edge2Source == E1S && relAttrib.Edge2Target == E2S || relAttrib.Edge2Source == E2S && relAttrib.Edge2Target == E1S) {
    83                   isTabu = true;
     89        PermutationMoveAttribute attrib = (tabuMove as PermutationMoveAttribute);
     90        if (!useAspiration
     91          || maximization && moveQuality <= attrib.MoveQuality
     92          || !maximization && moveQuality >= attrib.MoveQuality) {
     93          switch (permutation.PermutationType) {
     94            case PermutationTypes.RelativeUndirected: {
     95                int E1S = permutation.GetCircular(move.Index1 - 1);
     96                int E1T = permutation[move.Index1];
     97                int E2S = permutation[move.Index2];
     98                int E2T = permutation.GetCircular(move.Index2 + 1);
     99                InversionMoveRelativeAttribute relAttrib = (attrib as InversionMoveRelativeAttribute);
     100                if (relAttrib != null) {
     101                  // if previously deleted Edge1Source-Target is readded
     102                  if (relAttrib.Edge1Source == E1S && relAttrib.Edge1Target == E2S || relAttrib.Edge1Source == E2S && relAttrib.Edge1Target == E1S
     103                    || relAttrib.Edge1Source == E1T && relAttrib.Edge1Target == E2T || relAttrib.Edge1Source == E2T && relAttrib.Edge1Target == E1T
     104                    // if previously deleted Edge2Source-Target is readded
     105                    || relAttrib.Edge2Source == E1T && relAttrib.Edge2Target == E2T || relAttrib.Edge2Source == E2T && relAttrib.Edge2Target == E1T
     106                    || relAttrib.Edge2Source == E1S && relAttrib.Edge2Target == E2S || relAttrib.Edge2Source == E2S && relAttrib.Edge2Target == E1S) {
     107                    isTabu = true;
     108                  }
    84109                }
    85110              }
    86             }
    87             break;
    88           case PermutationTypes.RelativeDirected: {
    89               int E1S = permutation.GetCircular(move.Index1 - 1);
    90               int E1T = permutation[move.Index1];
    91               int E2S = permutation[move.Index2];
    92               int E2T = permutation.GetCircular(move.Index2 + 1);
    93               InversionMoveRelativeAttribute relAttrib = (tabuMove as InversionMoveRelativeAttribute);
    94               if (relAttrib != null) {
    95                 if (relAttrib.Edge1Source == E1S && relAttrib.Edge1Target == E2S
    96                   || relAttrib.Edge1Source == E1T && relAttrib.Edge1Target == E2T
    97                   // if previously deleted Edge2Source-Target is readded
    98                   || relAttrib.Edge2Source == E1T && relAttrib.Edge2Target == E2T
    99                   || relAttrib.Edge2Source == E1S && relAttrib.Edge2Target == E2S) {
    100                   isTabu = true;
     111              break;
     112            case PermutationTypes.RelativeDirected: {
     113                int E1S = permutation.GetCircular(move.Index1 - 1);
     114                int E1T = permutation[move.Index1];
     115                int E2S = permutation[move.Index2];
     116                int E2T = permutation.GetCircular(move.Index2 + 1);
     117                InversionMoveRelativeAttribute relAttrib = (attrib as InversionMoveRelativeAttribute);
     118                if (relAttrib != null) {
     119                  if (relAttrib.Edge1Source == E1S && relAttrib.Edge1Target == E2S
     120                    || relAttrib.Edge1Source == E1T && relAttrib.Edge1Target == E2T
     121                    // if previously deleted Edge2Source-Target is readded
     122                    || relAttrib.Edge2Source == E1T && relAttrib.Edge2Target == E2T
     123                    || relAttrib.Edge2Source == E1S && relAttrib.Edge2Target == E2S) {
     124                    isTabu = true;
     125                  }
    101126                }
    102127              }
    103             }
    104             break;
    105           case PermutationTypes.Absolute: {
    106               int i1 = move.Index1;
    107               int n1 = permutation[move.Index1];
    108               int i2 = move.Index2;
    109               int n2 = permutation[move.Index2];
    110               InversionMoveAbsoluteAttribute absAttrib = (tabuMove as InversionMoveAbsoluteAttribute);
    111               if (absAttrib != null) {
    112                 if ((absAttrib.Index1 == i1 || absAttrib.Index1 == i2) && (absAttrib.Number1 == n1 || absAttrib.Number1 == n2)
    113                   || (absAttrib.Index2 == i2 || absAttrib.Index2 == i1) && (absAttrib.Number2 == n2 || absAttrib.Number2 == n1))
    114                   isTabu = true;
     128              break;
     129            case PermutationTypes.Absolute: {
     130                int i1 = move.Index1;
     131                int n1 = permutation[move.Index1];
     132                int i2 = move.Index2;
     133                int n2 = permutation[move.Index2];
     134                InversionMoveAbsoluteAttribute absAttrib = (attrib as InversionMoveAbsoluteAttribute);
     135                if (absAttrib != null) {
     136                  if ((absAttrib.Index1 == i1 || absAttrib.Index1 == i2) && (absAttrib.Number1 == n1 || absAttrib.Number1 == n2)
     137                    || (absAttrib.Index2 == i2 || absAttrib.Index2 == i1) && (absAttrib.Number2 == n2 || absAttrib.Number2 == n1))
     138                    isTabu = true;
    115139
     140                }
    116141              }
    117             }
    118             break;
    119           default: {
    120               throw new InvalidOperationException(Name + ": Unknown permutation type.");
    121             }
     142              break;
     143            default: {
     144                throw new InvalidOperationException(Name + ": Unknown permutation type.");
     145              }
     146          }
    122147        }
    123148        if (isTabu) break;
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/InversionMoveTabuMaker.cs

    r3233 r3340  
    2929
    3030namespace HeuristicLab.Encodings.PermutationEncoding {
    31   [Item("InversionMoveTabuMaker", "Declares a given inversion move (2-opt) as tabu, by adding its attributes to the tabu list.")]
     31  [Item("InversionMoveTabuMaker", "Declares a given inversion move (2-opt) as tabu, by adding its attributes to the tabu list and also store the solution quality or the move quality (whichever is better).")]
    3232  [StorableClass]
    3333  public class InversionMoveTabuMaker : TabuMaker, IPermutationInversionMoveOperator {
     
    4848    }
    4949
    50     protected override IItem GetTabuAttribute() {
     50    protected override IItem GetTabuAttribute(bool maximization, double quality, double moveQuality) {
    5151      InversionMove move = InversionMoveParameter.ActualValue;
    5252      Permutation permutation = PermutationParameter.ActualValue;
     53      double baseQuality = moveQuality;
     54      if (maximization && quality > moveQuality || !maximization && quality < moveQuality) baseQuality = quality; // we make an uphill move, the lower bound is the solution quality
    5355      if (permutation.PermutationType == PermutationTypes.Absolute)
    54         return new InversionMoveAbsoluteAttribute(move.Index1, permutation[move.Index1], move.Index2, permutation[move.Index2]);
     56        return new InversionMoveAbsoluteAttribute(move.Index1, permutation[move.Index1], move.Index2, permutation[move.Index2], baseQuality);
    5557      else
    5658        return new InversionMoveRelativeAttribute(permutation.GetCircular(move.Index1 - 1),
    5759          permutation[move.Index1],
    5860          permutation[move.Index2],
    59           permutation.GetCircular(move.Index2 + 1));
     61          permutation.GetCircular(move.Index2 + 1),
     62          baseQuality);
    6063    }
    6164  }
Note: See TracChangeset for help on using the changeset viewer.