Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
03/26/10 00:04:24 (15 years ago)
Author:
abeham
Message:

updated permutation moves, fixed 3-opt #889

Location:
trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt
Files:
1 added
8 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/ExhaustiveTwoOptMoveGenerator.cs

    r3098 r3221  
    2626
    2727namespace HeuristicLab.Encodings.PermutationEncoding {
    28   [Item("ExhaustiveTwoOptMoveGenerator", "Generates all possible 2-opt moves from a given permutation.")]
     28  [Item("ExhaustiveTwoOptMoveGenerator", "Generates all possible 2-opt moves (inversion) from a given permutation.")]
    2929  [StorableClass]
    3030  public class ExhaustiveTwoOptMoveGenerator : TwoOptMoveGenerator, IExhaustiveMoveGenerator {
    3131    public static TwoOptMove[] Apply(Permutation permutation) {
    3232      int length = permutation.Length;
    33       int totalMoves = (length) * (length - 1) / 2 - 3;
     33      int totalMoves = (length) * (length - 1) / 2; // - 3;
    3434      TwoOptMove[] moves = new TwoOptMove[totalMoves];
    3535      int count = 0;
     
    3737        for (int j = i + 1; j < length; j++) {
    3838          // doesn't make sense to inverse the whole permutation or the whole but one
    39           if (i == 0 && j >= length - 2) continue;
    40           else if (i == 1 && j >= length - 1) continue;
     39          /*if (i == 0 && j >= length - 2) continue;
     40          else if (i == 1 && j >= length - 1) continue;*/
    4141          moves[count++] = new TwoOptMove(i, j);
    4242        }
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/PreventReaddDeleteTwoOptTabuMoveEvaluator.cs

    r3104 r3221  
    2929
    3030namespace HeuristicLab.Encodings.PermutationEncoding {
    31   [Item("PreventReaddDeleteTwoOptTabuMoveEvaluator", "Prevents readding of previously deleted edges as well as deleting previously added edges.")]
     31  [Item("TwoOptPreventEdgeRemovalAndReadding", "Prevents readding of previously deleted edges as well as deleting previously added edges.")]
    3232  [StorableClass]
    3333  public class PreventReaddDeleteTwoOptTabuMoveEvaluator : SingleSuccessorOperator, ITwoOptPermutationMoveOperator, ITabuMoveEvaluator {
     34    public override bool CanChangeName {
     35      get { return false; }
     36    }
    3437    public ILookupParameter<TwoOptMove> TwoOptMoveParameter {
    3538      get { return (LookupParameter<TwoOptMove>)Parameters["TwoOptMove"]; }
     
    6669      int E2S = permutation[move.Index2];
    6770      int E2T = permutation.GetCircular(move.Index2 + 1);
    68       bool isTabu = false;
    69       foreach (IItem tabuMove in tabuList) {
    70         TwoOptTabuMoveAttribute attribute = (tabuMove as TwoOptTabuMoveAttribute);
    71         if (attribute != null) {
    72           // if previously deleted Edge1Source-Target is readded
    73           if (attribute.Edge1Source == E1S && attribute.Edge1Target == E2S || attribute.Edge1Source == E2S && attribute.Edge1Target == E1S
    74             || attribute.Edge1Source == E1T && attribute.Edge1Target == E2T || attribute.Edge1Source == E2T && attribute.Edge1Target == E1T
    75             // if previously deleted Edge2Source-Target is readded
    76             || attribute.Edge2Source == E1T && attribute.Edge2Target == E2T || attribute.Edge2Source == E2T && attribute.Edge2Target == E1T
    77             || attribute.Edge2Source == E1S && attribute.Edge2Target == E2S || attribute.Edge2Source == E2S && attribute.Edge2Target == E1S
    78             // if previously added Edge1Source-Edge2Source is deleted
    79             || attribute.Edge1Source == E1S && attribute.Edge2Source == E1T || attribute.Edge1Source == E1T && attribute.Edge2Source == E1S
    80             || attribute.Edge1Source == E2S && attribute.Edge2Source == E2T || attribute.Edge1Source == E2T && attribute.Edge2Source == E2S
    81             // if previously added Edge1Target-Edge2Target is deleted
    82             || attribute.Edge1Target == E2S && attribute.Edge2Target == E2T || attribute.Edge1Target == E2T && attribute.Edge2Target == E2S
    83             || attribute.Edge1Target == E1S && attribute.Edge2Target == E1T || attribute.Edge1Target == E1T && attribute.Edge2Target == E1S) {
    84             isTabu = true;
    85             break;
     71      bool isTabu = (move.Index2 - move.Index1 >= length - 2); // doesn't change the solution;
     72      if (!isTabu) {
     73        foreach (IItem tabuMove in tabuList) {
     74          TwoOptTabuMoveAttribute attribute = (tabuMove as TwoOptTabuMoveAttribute);
     75          if (attribute != null) {
     76            // if previously deleted Edge1Source-Target is readded
     77            if (attribute.Edge1Source == E1S && attribute.Edge1Target == E2S || attribute.Edge1Source == E2S && attribute.Edge1Target == E1S
     78              || attribute.Edge1Source == E1T && attribute.Edge1Target == E2T || attribute.Edge1Source == E2T && attribute.Edge1Target == E1T
     79              // if previously deleted Edge2Source-Target is readded
     80              || attribute.Edge2Source == E1T && attribute.Edge2Target == E2T || attribute.Edge2Source == E2T && attribute.Edge2Target == E1T
     81              || attribute.Edge2Source == E1S && attribute.Edge2Target == E2S || attribute.Edge2Source == E2S && attribute.Edge2Target == E1S
     82              // if previously added Edge1Source-Edge2Source is deleted
     83              || attribute.Edge1Source == E1S && attribute.Edge2Source == E1T || attribute.Edge1Source == E1T && attribute.Edge2Source == E1S
     84              || attribute.Edge1Source == E2S && attribute.Edge2Source == E2T || attribute.Edge1Source == E2T && attribute.Edge2Source == E2S
     85              // if previously added Edge1Target-Edge2Target is deleted
     86              || attribute.Edge1Target == E2S && attribute.Edge2Target == E2T || attribute.Edge1Target == E2T && attribute.Edge2Target == E2S
     87              || attribute.Edge1Target == E1S && attribute.Edge2Target == E1T || attribute.Edge1Target == E1T && attribute.Edge2Target == E1S) {
     88              isTabu = true;
     89              break;
     90            }
    8691          }
    8792        }
     
    9095      return base.Apply();
    9196    }
    92 
    93     public override bool CanChangeName {
    94       get { return false; }
    95     }
    9697  }
    9798}
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/PreventReaddTwoOptTabuMoveEvaluator.cs

    r3104 r3221  
    2929
    3030namespace HeuristicLab.Encodings.PermutationEncoding {
    31   [Item("PreventReaddTwoOptTabuMoveEvaluator", "Prevents readding of previously deleted edges, but allows deleting previously added edges.")]
     31  [Item("TwoOptPreventEdgeReadding", "Prevents readding of previously deleted edges, but allows deleting previously added edges.")]
    3232  [StorableClass]
    3333  public class PreventReaddTwoOptTabuMoveEvaluator : SingleSuccessorOperator, ITwoOptPermutationMoveOperator, ITabuMoveEvaluator {
     34    public override bool CanChangeName {
     35      get { return false; }
     36    }
    3437    public ILookupParameter<TwoOptMove> TwoOptMoveParameter {
    3538      get { return (LookupParameter<TwoOptMove>)Parameters["TwoOptMove"]; }
     
    6669      int E2S = permutation[move.Index2];
    6770      int E2T = permutation.GetCircular(move.Index2 + 1);
    68       bool isTabu = false;
    69       foreach (IItem tabuMove in tabuList) {
    70         TwoOptTabuMoveAttribute attribute = (tabuMove as TwoOptTabuMoveAttribute);
    71         if (attribute != null) {
    72           // if previously deleted Edge1Source-Target is readded
    73           if (attribute.Edge1Source == E1S && attribute.Edge1Target == E2S || attribute.Edge1Source == E2S && attribute.Edge1Target == E1S
    74             || attribute.Edge1Source == E1T && attribute.Edge1Target == E2T || attribute.Edge1Source == E2T && attribute.Edge1Target == E1T
    75             // if previously deleted Edge2Source-Target is readded
    76             || attribute.Edge2Source == E1T && attribute.Edge2Target == E2T || attribute.Edge2Source == E2T && attribute.Edge2Target == E1T
    77             || attribute.Edge2Source == E1S && attribute.Edge2Target == E2S || attribute.Edge2Source == E2S && attribute.Edge2Target == E1S) {
    78             isTabu = true;
    79             break;
     71      bool isTabu = (move.Index2 - move.Index1 >= length - 2); // doesn't change the solution;
     72      if (!isTabu) {
     73        foreach (IItem tabuMove in tabuList) {
     74          TwoOptTabuMoveAttribute attribute = (tabuMove as TwoOptTabuMoveAttribute);
     75          if (attribute != null) {
     76            // if previously deleted Edge1Source-Target is readded
     77            if (attribute.Edge1Source == E1S && attribute.Edge1Target == E2S || attribute.Edge1Source == E2S && attribute.Edge1Target == E1S
     78              || attribute.Edge1Source == E1T && attribute.Edge1Target == E2T || attribute.Edge1Source == E2T && attribute.Edge1Target == E1T
     79              // if previously deleted Edge2Source-Target is readded
     80              || attribute.Edge2Source == E1T && attribute.Edge2Target == E2T || attribute.Edge2Source == E2T && attribute.Edge2Target == E1T
     81              || attribute.Edge2Source == E1S && attribute.Edge2Target == E2S || attribute.Edge2Source == E2S && attribute.Edge2Target == E1S) {
     82              isTabu = true;
     83              break;
     84            }
    8085          }
    8186        }
     
    8489      return base.Apply();
    8590    }
    86 
    87     public override bool CanChangeName {
    88       get { return false; }
    89     }
    9091  }
    9192}
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/StochasticTwoOptMultiMoveGenerator.cs

    r3101 r3221  
    2828
    2929namespace HeuristicLab.Encodings.PermutationEncoding {
    30   [Item("StochasticTwoOptMultiMoveGenerator", "Randomly samples n from all possible 2-opt moves from a given permutation.")]
     30  [Item("StochasticTwoOptMultiMoveGenerator", "Randomly samples n from all possible 2-opt moves (inversion) from a given permutation.")]
    3131  [StorableClass]
    32   public class StochasticTwoOptMultiMoveGenerator : StochasticTwoOptSingleMoveGenerator, IMultiMoveGenerator {
     32  public class StochasticTwoOptMultiMoveGenerator : TwoOptMoveGenerator, IMultiMoveGenerator, IStochasticOperator {
     33    public ILookupParameter<IRandom> RandomParameter {
     34      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
     35    }
    3336    public IValueLookupParameter<IntValue> SampleSizeParameter {
    3437      get { return (IValueLookupParameter<IntValue>)Parameters["SampleSize"]; }
     
    4245    public StochasticTwoOptMultiMoveGenerator()
    4346      : base() {
     47      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator."));
    4448      Parameters.Add(new ValueLookupParameter<IntValue>("SampleSize", "The number of moves to generate."));
    4549    }
     
    4953      TwoOptMove[] moves = new TwoOptMove[sampleSize];
    5054      for (int i = 0; i < sampleSize; i++) {
    51         moves[i] = Apply(permutation, random);
     55        moves[i] = StochasticTwoOptSingleMoveGenerator.Apply(permutation, random);
    5256      }
    5357      return moves;
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/StochasticTwoOptSingleMoveGenerator.cs

    r3098 r3221  
    2828
    2929namespace HeuristicLab.Encodings.PermutationEncoding {
    30   [Item("StochasticTwoOptSingleMoveGenerator", "Randomly samples a single from all possible 2-opt moves from a given permutation.")]
     30  [Item("StochasticTwoOptSingleMoveGenerator", "Randomly samples a single from all possible 2-opt moves (inversion) from a given permutation.")]
    3131  [StorableClass]
    3232  public class StochasticTwoOptSingleMoveGenerator : TwoOptMoveGenerator, IStochasticOperator, ISingleMoveGenerator {
     
    4242    public static TwoOptMove Apply(Permutation permutation, IRandom random) {
    4343      int length = permutation.Length;
    44       int index1 = random.Next(length - 1), index2;
    45       if (index1 >= 2)
    46         index2 = random.Next(index1 + 1, length);
    47       else index2 = random.Next(index1 + 1, length - (2 - index1));
     44      int index1 = random.Next(length - 1);
     45      int index2 = random.Next(index1 + 1, length);
    4846      return new TwoOptMove(index1, index2);;
    4947    }
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/TwoOptMoveGenerator.cs

    r3074 r3221  
    3131  [StorableClass]
    3232  public abstract class TwoOptMoveGenerator : SingleSuccessorOperator, ITwoOptPermutationMoveOperator, IMoveGenerator {
     33    public override bool CanChangeName {
     34      get { return false; }
     35    }
    3336    public ILookupParameter<Permutation> PermutationParameter {
    3437      get { return (ILookupParameter<Permutation>)Parameters["Permutation"]; }
     
    6164
    6265    protected abstract TwoOptMove[] GenerateMoves(Permutation permutation);
    63 
    64     public override bool CanChangeName {
    65       get { return false; }
    66     }
    6766  }
    6867}
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/TwoOptMoveMaker.cs

    r3074 r3221  
    3232  [StorableClass]
    3333  public class TwoOptMoveMaker : SingleSuccessorOperator, ITwoOptPermutationMoveOperator, IMoveMaker {
     34    public override bool CanChangeName {
     35      get { return false; }
     36    }
    3437    public ILookupParameter<DoubleValue> QualityParameter {
    3538      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
     
    6467      return base.Apply();
    6568    }
    66 
    67     public override bool CanChangeName {
    68       get { return false; }
    69     }
    7069  }
    7170}
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/TwoOptTabuMoveMaker.cs

    r3104 r3221  
    3232  [StorableClass]
    3333  public class TwoOptTabuMoveMaker : TabuMoveMaker, ITwoOptPermutationMoveOperator {
     34    public override bool CanChangeName {
     35      get { return false; }
     36    }
    3437    public ILookupParameter<Permutation> PermutationParameter {
    3538      get { return (ILookupParameter<Permutation>)Parameters["Permutation"]; }
     
    5356        permutation.GetCircular(move.Index2 + 1));
    5457    }
    55 
    56     public override bool CanChangeName {
    57       get { return false; }
    58     }
    5958  }
    6059}
Note: See TracChangeset for help on using the changeset viewer.