Free cookie consent management tool by TermsFeed Policy Generator

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

Updated inversion moves to respect different types of permutation #889

Location:
trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3
Files:
2 added
1 deleted
7 edited

Legend:

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

    r3232 r3233  
    124124      <SubType>Code</SubType>
    125125    </Compile>
     126    <Compile Include="Moves\TwoOpt\InversionMoveAbsoluteAttribute.cs" />
    126127    <Compile Include="Moves\TwoOpt\ExhaustiveInversionMoveGenerator.cs" />
    127128    <Compile Include="Moves\TwoOpt\InversionMove.cs" />
    128     <Compile Include="Moves\TwoOpt\InversionMoveAttribute.cs" />
     129    <Compile Include="Moves\TwoOpt\InversionMoveRelativeAttribute.cs" />
    129130    <Compile Include="Moves\TwoOpt\InversionMoveGenerator.cs" />
    130131    <Compile Include="Moves\TwoOpt\InversionMoveMaker.cs" />
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/ExhaustiveInversionMoveGenerator.cs

    r3232 r3233  
    3434      InversionMove[] moves = new InversionMove[totalMoves];
    3535      int count = 0;
    36       for (int i = 0; i < length - 1; i++)
    37         for (int j = i + 1; j < length; j++) {
    38           // 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;*/
    41           moves[count++] = new InversionMove(i, j);
     36
     37      if (permutation.PermutationType == PermutationTypes.RelativeUndirected) {
     38        for (int i = 0; i < length - 1; i++) {
     39          for (int j = i + 1; j < length; j++) {
     40            // doesn't make sense to inverse the whole permutation or the whole but one in case of relative undirected permutations
     41            if (j - i >= length - 2) continue;
     42            moves[count++] = new InversionMove(i, j);
     43          }
    4244        }
     45      } 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            }
     50      }
    4351      return moves;
    4452    }
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/InversionMoveTabuMaker.cs

    r3232 r3233  
    5151      InversionMove move = InversionMoveParameter.ActualValue;
    5252      Permutation permutation = PermutationParameter.ActualValue;
    53       return new InversionMoveAttribute( permutation.GetCircular(move.Index1 - 1),
    54         permutation[move.Index1],
    55         permutation[move.Index2],
    56         permutation.GetCircular(move.Index2 + 1));
     53      if (permutation.PermutationType == PermutationTypes.Absolute)
     54        return new InversionMoveAbsoluteAttribute(move.Index1, permutation[move.Index1], move.Index2, permutation[move.Index2]);
     55      else
     56        return new InversionMoveRelativeAttribute(permutation.GetCircular(move.Index1 - 1),
     57          permutation[move.Index1],
     58          permutation[move.Index2],
     59          permutation.GetCircular(move.Index2 + 1));
    5760    }
    5861  }
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/PreventReaddAndRemovalInversionMoveTabuChecker.cs

    r3232 r3233  
    6565      Permutation permutation = PermutationParameter.ActualValue;
    6666      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       bool isTabu = (move.Index2 - move.Index1 >= length - 2); // doesn't change the solution;
    72       if (!isTabu) {
    73         foreach (IItem tabuMove in tabuList) {
    74           InversionMoveAttribute attribute = (tabuMove as InversionMoveAttribute);
    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;
     67      bool isTabu = false;
     68      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                // if previously added Edge1Source-Edge2Source is deleted
     84                || relAttrib.Edge1Source == E1S && relAttrib.Edge2Source == E1T || relAttrib.Edge1Source == E1T && relAttrib.Edge2Source == E1S
     85                || relAttrib.Edge1Source == E2S && relAttrib.Edge2Source == E2T || relAttrib.Edge1Source == E2T && relAttrib.Edge2Source == E2S
     86                // if previously added Edge1Target-Edge2Target is deleted
     87                || relAttrib.Edge1Target == E2S && relAttrib.Edge2Target == E2T || relAttrib.Edge1Target == E2T && relAttrib.Edge2Target == E2S
     88                || relAttrib.Edge1Target == E1S && relAttrib.Edge2Target == E1T || relAttrib.Edge1Target == E1T && relAttrib.Edge2Target == E1S) {
     89                isTabu = true;
     90              }
    9091            }
    9192          }
     93          break;
     94          case PermutationTypes.RelativeDirected: {
     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 = (tabuMove as InversionMoveRelativeAttribute);
     100            if (relAttrib != null) {
     101              if (relAttrib.Edge1Source == E1S && relAttrib.Edge1Target == E2S
     102                || relAttrib.Edge1Source == E1T && relAttrib.Edge1Target == E2T
     103                // if previously deleted Edge2Source-Target is readded
     104                || relAttrib.Edge2Source == E1T && relAttrib.Edge2Target == E2T
     105                || relAttrib.Edge2Source == E1S && relAttrib.Edge2Target == E2S
     106                // if previously added Edge1Source-Edge2Source is deleted
     107                || relAttrib.Edge1Source == E1S && relAttrib.Edge2Source == E1T
     108                || relAttrib.Edge1Source == E2S && relAttrib.Edge2Source == E2T
     109                // if previously added Edge1Target-Edge2Target is deleted
     110                || relAttrib.Edge1Target == E2S && relAttrib.Edge2Target == E2T
     111                || relAttrib.Edge1Target == E1S && relAttrib.Edge2Target == E1T) {
     112                isTabu = true;
     113              }
     114            }
     115          }
     116          break;
     117          case PermutationTypes.Absolute: {
     118            int i1 = move.Index1;
     119            int n1 = permutation[move.Index1];
     120            int i2 = move.Index2;
     121            int n2 = permutation[move.Index2];
     122            InversionMoveAbsoluteAttribute absAttrib = (tabuMove as InversionMoveAbsoluteAttribute);
     123            if (absAttrib != null) {
     124              if (absAttrib.Number1 == n1 || absAttrib.Number1 == n2
     125                || absAttrib.Number2 == n2 || absAttrib.Number2 == n1)
     126                isTabu = true;
     127             
     128            }
     129          }
     130          break;
     131          default: {
     132            throw new InvalidOperationException(Name + ": Unknown permutation type.");
     133          }
    92134        }
     135        if (isTabu) break;
    93136      }
    94137      MoveTabuParameter.ActualValue = new BoolValue(isTabu);
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/PreventReaddInversionMoveTabuChecker.cs

    r3232 r3233  
    6565      Permutation permutation = PermutationParameter.ActualValue;
    6666      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       bool isTabu = (move.Index2 - move.Index1 >= length - 2); // doesn't change the solution;
    72       if (!isTabu) {
    73         foreach (IItem tabuMove in tabuList) {
    74           InversionMoveAttribute attribute = (tabuMove as InversionMoveAttribute);
    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;
     67      bool isTabu = false;
     68      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;
     84                }
     85              }
    8486            }
    85           }
     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;
     101                }
     102              }
     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;
     115
     116              }
     117            }
     118            break;
     119          default: {
     120              throw new InvalidOperationException(Name + ": Unknown permutation type.");
     121            }
    86122        }
     123        if (isTabu) break;
    87124      }
    88125      MoveTabuParameter.ActualValue = new BoolValue(isTabu);
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/PreventRemovalInversionMoveTabuChecker.cs

    r3232 r3233  
    6565      Permutation permutation = PermutationParameter.ActualValue;
    6666      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       bool isTabu = (move.Index2 - move.Index1 >= length - 2); // doesn't change the solution
    72       if (!isTabu) {
    73         foreach (IItem tabuMove in tabuList) {
    74           InversionMoveAttribute attribute = (tabuMove as InversionMoveAttribute);
    75           if (attribute != null) {
    76             // if previously added Edge1Source-Edge2Source is deleted
    77             if (attribute.Edge1Source == E1S && attribute.Edge2Source == E1T || attribute.Edge1Source == E1T && attribute.Edge2Source == E1S
    78               || attribute.Edge1Source == E2S && attribute.Edge2Source == E2T || attribute.Edge1Source == E2T && attribute.Edge2Source == E2S
    79               // if previously added Edge1Target-Edge2Target is deleted
    80               || attribute.Edge1Target == E2S && attribute.Edge2Target == E2T || attribute.Edge1Target == E2T && attribute.Edge2Target == E2S
    81               || attribute.Edge1Target == E1S && attribute.Edge2Target == E1T || attribute.Edge1Target == E1T && attribute.Edge2Target == E1S) {
    82               isTabu = true;
    83               break;
     67      bool isTabu = false;
     68      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;
     83                }
     84              }
    8485            }
    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;
     100                }
     101              }
     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;
     114
     115              }
     116            }
     117            break;
     118          default: {
     119              throw new InvalidOperationException(Name + ": Unknown permutation type.");
     120            }
    86121        }
     122        if (isTabu) break;
    87123      }
    88124      MoveTabuParameter.ActualValue = new BoolValue(isTabu);
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/StochasticInversionSingleMoveGenerator.cs

    r3232 r3233  
    4444      int index1 = random.Next(length - 1);
    4545      int index2 = random.Next(index1 + 1, length);
    46       return new InversionMove(index1, index2);;
     46      if (permutation.PermutationType == PermutationTypes.RelativeUndirected) {
     47        while (index2 - index1 >= length - 2)
     48          index2 = random.Next(index1 + 1, length);
     49      }
     50      return new InversionMove(index1, index2);
    4751    }
    4852
Note: See TracChangeset for help on using the changeset viewer.