- Timestamp:
- 04/14/10 03:52:07 (14 years ago)
- 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 107 107 <Compile Include="Manipulators\TranslocationInversionManipulator.cs" /> 108 108 <Compile Include="Manipulators\TranslocationManipulator.cs" /> 109 <Compile Include="Moves\PermutationMoveAttribute.cs" /> 109 110 <Compile Include="Moves\ThreeIndexMove.cs" /> 111 <Compile Include="Moves\ThreeOpt\TranslocationMoveAbsoluteAttribute.cs" /> 110 112 <Compile Include="Moves\ThreeOpt\ExhaustiveInsertionMoveGenerator.cs"> 111 113 <SubType>Code</SubType> 112 114 </Compile> 113 <Compile Include="Moves\ThreeOpt\PreventReaddAndRemovalTranslocationMoveTabuChecker.cs" />114 <Compile Include="Moves\ThreeOpt\PreventReaddTranslocationMoveTabuChecker.cs" />115 <Compile Include="Moves\ThreeOpt\PreventRemovalTranslocationMoveTabuChecker.cs" />116 115 <Compile Include="Moves\ThreeOpt\StochasticTranslocationMultiMoveGenerator.cs" /> 117 116 <Compile Include="Moves\ThreeOpt\StochasticTranslocationSingleMoveGenerator.cs" /> 118 117 <Compile Include="Moves\ThreeOpt\TranslocationMove.cs" /> 119 <Compile Include="Moves\ThreeOpt\TranslocationMoveAttribute.cs" />120 118 <Compile Include="Moves\ThreeOpt\TranslocationMoveGenerator.cs" /> 119 <Compile Include="Moves\ThreeOpt\TranslocationMoveHardTabuCriterion.cs" /> 121 120 <Compile Include="Moves\ThreeOpt\TranslocationMoveMaker.cs" /> 121 <Compile Include="Moves\ThreeOpt\TranslocationMoveRelativeAttribute.cs" /> 122 <Compile Include="Moves\ThreeOpt\TranslocationMoveSoftTabuCriterion.cs" /> 122 123 <Compile Include="Moves\ThreeOpt\TranslocationMoveTabuMaker.cs" /> 123 124 <Compile Include="Moves\TwoIndexMove.cs"> … … 127 128 <Compile Include="Moves\TwoOpt\ExhaustiveInversionMoveGenerator.cs" /> 128 129 <Compile Include="Moves\TwoOpt\InversionMove.cs" /> 130 <Compile Include="Moves\TwoOpt\InversionMoveHardTabuCriterion.cs" /> 129 131 <Compile Include="Moves\TwoOpt\InversionMoveRelativeAttribute.cs" /> 130 132 <Compile Include="Moves\TwoOpt\InversionMoveGenerator.cs" /> 131 133 <Compile Include="Moves\TwoOpt\InversionMoveMaker.cs" /> 134 <Compile Include="Moves\TwoOpt\InversionMoveSoftTabuCriterion.cs" /> 132 135 <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" />136 136 <Compile Include="Moves\TwoOpt\StochasticInversionMultiMoveGenerator.cs" /> 137 137 <Compile Include="Moves\TwoOpt\StochasticInversionSingleMoveGenerator.cs" /> -
trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Manipulators/InsertionManipulator.cs
r3160 r3340 30 30 /// It is implemented as described in Fogel, D.B. (1988). An Evolutionary Approach to the Traveling Salesman Problem, Biological Cybernetics, 60, pp. 139-144. 31 31 /// </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.")] 33 33 [StorableClass] 34 34 public class InsertionManipulator : PermutationManipulator { -
trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/ExhaustiveInsertionMoveGenerator.cs
r3232 r3340 34 34 public static TranslocationMove[] Apply(Permutation permutation) { 35 35 int length = permutation.Length; 36 TranslocationMove[] moves = n ew TranslocationMove[length * (length - 1)];36 TranslocationMove[] moves = null; 37 37 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 } 41 53 } 42 54 } 55 System.Diagnostics.Debug.Assert(count == moves.Length); 43 56 return moves; 44 57 } -
trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/StochasticTranslocationSingleMoveGenerator.cs
r3232 r3340 43 43 int length = permutation.Length; 44 44 int index1, index2, index3; 45 index1 = random.Next(length - 1);46 45 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)); 53 54 return new TranslocationMove(index1, index2, index3); 54 55 } -
trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/TranslocationMoveHardTabuCriterion.cs
r3307 r3340 29 29 30 30 namespace 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 34 If 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.")] 32 35 [StorableClass] 33 public class PreventReaddAndRemovalTranslocationMoveTabuChecker: SingleSuccessorOperator, IPermutationTranslocationMoveOperator, ITabuChecker {36 public class TranslocationMoveHardTabuCriterion : SingleSuccessorOperator, IPermutationTranslocationMoveOperator, ITabuChecker { 34 37 public override bool CanChangeName { 35 38 get { return false; } … … 47 50 get { return (ILookupParameter<BoolValue>)Parameters["MoveTabu"]; } 48 51 } 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"]; } 51 60 } 52 61 53 public PreventReaddAndRemovalTranslocationMoveTabuChecker() 62 public BoolValue UseAspirationCriterion { 63 get { return UseAspirationCriterionParameter.Value; } 64 set { UseAspirationCriterionParameter.Value = value; } 65 } 66 67 public TranslocationMoveHardTabuCriterion() 54 68 : base() { 55 69 Parameters.Add(new LookupParameter<TranslocationMove>("TranslocationMove", "The move to evaluate.")); … … 57 71 Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation.")); 58 72 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.")); 60 76 } 61 77 … … 65 81 Permutation permutation = PermutationParameter.ActualValue; 66 82 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 } 75 114 } 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 } 84 127 foreach (IItem tabuMove in tabuList) { 85 TranslocationMove Attribute attribute = (tabuMove as TranslocationMoveAttribute);128 TranslocationMoveRelativeAttribute attribute = (tabuMove as TranslocationMoveRelativeAttribute); 86 129 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 } 113 167 } 114 168 } -
trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/TranslocationMoveRelativeAttribute.cs
r3307 r3340 24 24 25 25 namespace HeuristicLab.Encodings.PermutationEncoding { 26 [Item("TranslocationMove Attribute", "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.")] 27 27 [StorableClass] 28 public class TranslocationMove Attribute : Item{28 public class TranslocationMoveRelativeAttribute : PermutationMoveAttribute { 29 29 [Storable] 30 30 public int Edge1Source { get; private set; } … … 41 41 42 42 [StorableConstructor] 43 private TranslocationMove Attribute(bool deserializing)43 private TranslocationMoveRelativeAttribute(bool deserializing) 44 44 : base() { 45 45 } 46 46 47 public TranslocationMove Attribute()48 : this(-1, -1, -1, -1, -1, -1 ) { }47 public TranslocationMoveRelativeAttribute() 48 : this(-1, -1, -1, -1, -1, -1, -1) { } 49 49 50 public TranslocationMove Attribute(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) { 52 52 Edge1Source = edge1Source; 53 53 Edge1Target = edge1Target; … … 59 59 60 60 public override IDeepCloneable Clone(Cloner cloner) { 61 TranslocationMove Attribute clone = (TranslocationMoveAttribute)base.Clone(cloner);61 TranslocationMoveRelativeAttribute clone = (TranslocationMoveRelativeAttribute)base.Clone(cloner); 62 62 clone.Edge1Source = Edge1Source; 63 63 clone.Edge1Target = Edge1Target; -
trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/TranslocationMoveSoftTabuCriterion.cs
r3307 r3340 29 29 30 30 namespace 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 34 If 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.")] 32 35 [StorableClass] 33 public class PreventReaddTranslocationMoveTabuChecker: SingleSuccessorOperator, IPermutationTranslocationMoveOperator, ITabuChecker {36 public class TranslocationMoveSoftTabuCriterion : SingleSuccessorOperator, IPermutationTranslocationMoveOperator, ITabuChecker { 34 37 public override bool CanChangeName { 35 38 get { return false; } … … 47 50 get { return (ILookupParameter<BoolValue>)Parameters["MoveTabu"]; } 48 51 } 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"]; } 51 60 } 52 61 53 public PreventReaddTranslocationMoveTabuChecker() 62 public BoolValue UseAspirationCriterion { 63 get { return UseAspirationCriterionParameter.Value; } 64 set { UseAspirationCriterionParameter.Value = value; } 65 } 66 67 public TranslocationMoveSoftTabuCriterion() 54 68 : base() { 55 69 Parameters.Add(new LookupParameter<TranslocationMove>("TranslocationMove", "The move to evaluate.")); … … 57 71 Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation.")); 58 72 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.")); 60 76 } 61 77 … … 65 81 Permutation permutation = PermutationParameter.ActualValue; 66 82 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 } 75 114 } 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 } 84 127 foreach (IItem tabuMove in tabuList) { 85 TranslocationMove Attribute attribute = (tabuMove as TranslocationMoveAttribute);128 TranslocationMoveRelativeAttribute attribute = (tabuMove as TranslocationMoveRelativeAttribute); 86 129 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 } 101 166 } 102 167 } -
trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/TranslocationMoveTabuMaker.cs
r3232 r3340 48 48 } 49 49 50 protected override IItem GetTabuAttribute( ) {50 protected override IItem GetTabuAttribute(bool maximization, double quality, double moveQuality) { 51 51 TranslocationMove move = TranslocationMoveParameter.ActualValue; 52 52 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 } 67 79 } 68 80 } -
trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/ExhaustiveInversionMoveGenerator.cs
r3233 r3340 31 31 public static InversionMove[] Apply(Permutation permutation) { 32 32 int length = permutation.Length; 33 int totalMoves = (length) * (length - 1) / 2; // - 3;34 InversionMove[] moves = n ew InversionMove[totalMoves];33 int totalMoves = (length) * (length - 1) / 2; 34 InversionMove[] moves = null; 35 35 int count = 0; 36 36 37 37 if (permutation.PermutationType == PermutationTypes.RelativeUndirected) { 38 moves = new InversionMove[totalMoves - 3]; 38 39 for (int i = 0; i < length - 1; i++) { 39 40 for (int j = i + 1; j < length; j++) { … … 44 45 } 45 46 } 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 } 50 52 } 51 53 return moves; -
trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/InversionMoveAbsoluteAttribute.cs
r3233 r3340 26 26 [Item("InversionMoveAbsoluteAttribute", "Specifies the tabu attributes for an inversion move (2-opt) on an absolute position permutation.")] 27 27 [StorableClass] 28 public class InversionMoveAbsoluteAttribute : Item{28 public class InversionMoveAbsoluteAttribute : PermutationMoveAttribute { 29 29 [Storable] 30 30 public int Index1 { get; private set; } … … 42 42 43 43 public InversionMoveAbsoluteAttribute() 44 : this(-1, -1, -1, -1 ) { }44 : this(-1, -1, -1, -1, -1) { } 45 45 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) { 48 48 Index1 = index1; 49 49 Number1 = number1; -
trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/InversionMoveHardTabuCriterion.cs
r3307 r3340 29 29 30 30 namespace 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 34 If 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.")] 32 35 [StorableClass] 33 public class PreventRemovalInversionMoveTabuChecker: SingleSuccessorOperator, IPermutationInversionMoveOperator, ITabuChecker {36 public class InversionMoveHardTabuCriterion : SingleSuccessorOperator, IPermutationInversionMoveOperator, ITabuChecker { 34 37 public override bool CanChangeName { 35 38 get { return false; } … … 47 50 get { return (ILookupParameter<BoolValue>)Parameters["MoveTabu"]; } 48 51 } 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"]; } 51 60 } 52 61 53 public PreventRemovalInversionMoveTabuChecker() 62 public BoolValue UseAspirationCriterion { 63 get { return UseAspirationCriterionParameter.Value; } 64 set { UseAspirationCriterionParameter.Value = value; } 65 } 66 67 public InversionMoveHardTabuCriterion() 54 68 : base() { 55 69 Parameters.Add(new LookupParameter<InversionMove>("InversionMove", "The move to evaluate.")); … … 57 71 Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation.")); 58 72 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.")); 60 76 } 61 77 … … 65 81 Permutation permutation = PermutationParameter.ActualValue; 66 82 int length = permutation.Length; 83 double moveQuality = MoveQualityParameter.ActualValue.Value; 84 bool maximization = MaximizationParameter.ActualValue.Value; 85 bool useAspiration = UseAspirationCriterion.Value; 67 86 bool isTabu = false; 87 68 88 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 } 83 108 } 84 109 } 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 == E1T95 || relAttrib.Edge1Source == E2S && relAttrib.Edge2Source == E2T96 // if previously added Edge1Target-Edge2Target is deleted97 || relAttrib.Edge1Target == E2S && relAttrib.Edge2Target == E2T98 || 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 } 100 125 } 101 126 } 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; 114 138 139 } 115 140 } 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 } 121 146 } 122 147 if (isTabu) break; -
trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/InversionMoveRelativeAttribute.cs
r3233 r3340 26 26 [Item("InversionMoveRelativeAttribute", "Specifies the tabu attributes for an inversion move (2-opt) on a relative position permutation.")] 27 27 [StorableClass] 28 public class InversionMoveRelativeAttribute : Item{28 public class InversionMoveRelativeAttribute : PermutationMoveAttribute { 29 29 [Storable] 30 30 public int Edge1Source { get; private set; } … … 42 42 43 43 public InversionMoveRelativeAttribute() 44 : this(-1, -1, -1, -1 ) { }44 : this(-1, -1, -1, -1, -1) { } 45 45 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) { 48 48 Edge1Source = edge1Source; 49 49 Edge1Target = edge1Target; -
trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/InversionMoveSoftTabuCriterion.cs
r3307 r3340 29 29 30 30 namespace 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 34 If 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.")] 32 35 [StorableClass] 33 public class PreventReaddInversionMoveTabuChecker: SingleSuccessorOperator, IPermutationInversionMoveOperator, ITabuChecker {36 public class InversionMoveSoftTabuCriterion : SingleSuccessorOperator, IPermutationInversionMoveOperator, ITabuChecker { 34 37 public override bool CanChangeName { 35 38 get { return false; } … … 47 50 get { return (ILookupParameter<BoolValue>)Parameters["MoveTabu"]; } 48 51 } 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"]; } 51 60 } 52 61 53 public PreventReaddInversionMoveTabuChecker() 62 public BoolValue UseAspirationCriterion { 63 get { return UseAspirationCriterionParameter.Value; } 64 set { UseAspirationCriterionParameter.Value = value; } 65 } 66 67 public InversionMoveSoftTabuCriterion() 54 68 : base() { 55 69 Parameters.Add(new LookupParameter<InversionMove>("InversionMove", "The move to evaluate.")); … … 57 71 Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation.")); 58 72 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.")); 60 76 } 61 77 … … 65 81 Permutation permutation = PermutationParameter.ActualValue; 66 82 int length = permutation.Length; 83 double moveQuality = MoveQualityParameter.ActualValue.Value; 84 bool maximization = MaximizationParameter.ActualValue.Value; 85 bool useAspiration = UseAspirationCriterion.Value; 67 86 bool isTabu = false; 87 68 88 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 } 84 109 } 85 110 } 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 == E2S96 || relAttrib.Edge1Source == E1T && relAttrib.Edge1Target == E2T97 // if previously deleted Edge2Source-Target is readded98 || relAttrib.Edge2Source == E1T && relAttrib.Edge2Target == E2T99 || 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 } 101 126 } 102 127 } 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; 115 139 140 } 116 141 } 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 } 122 147 } 123 148 if (isTabu) break; -
trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/InversionMoveTabuMaker.cs
r3233 r3340 29 29 30 30 namespace 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).")] 32 32 [StorableClass] 33 33 public class InversionMoveTabuMaker : TabuMaker, IPermutationInversionMoveOperator { … … 48 48 } 49 49 50 protected override IItem GetTabuAttribute( ) {50 protected override IItem GetTabuAttribute(bool maximization, double quality, double moveQuality) { 51 51 InversionMove move = InversionMoveParameter.ActualValue; 52 52 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 53 55 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); 55 57 else 56 58 return new InversionMoveRelativeAttribute(permutation.GetCircular(move.Index1 - 1), 57 59 permutation[move.Index1], 58 60 permutation[move.Index2], 59 permutation.GetCircular(move.Index2 + 1)); 61 permutation.GetCircular(move.Index2 + 1), 62 baseQuality); 60 63 } 61 64 }
Note: See TracChangeset
for help on using the changeset viewer.