Changeset 12261


Ignore:
Timestamp:
03/26/15 16:14:52 (5 years ago)
Author:
apolidur
Message:

#2221: Fixing MoveEvaluators after running unit tests

Location:
branches/PTSP
Files:
7 edited

Legend:

Unmodified
Added
Removed
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/EstimatedPTSP.cs

    r12228 r12261  
    1010using HeuristicLab.Parameters;
    1111using HeuristicLab.Data;
     12using HeuristicLab.Random;
    1213using System;
    1314using System.Linq;
    14 using HeuristicLab.Problems.PTSP.MoveEvaluators.OneShift;
    1515
    1616namespace HeuristicLab.Problems.PTSP {
     
    3636      Permutation p = individual.Permutation();
    3737      // Estimation-based evaluation
    38       Random r = new Random();
     38      MersenneTwister r = new MersenneTwister();
    3939      double estimatedSum = 0;
    4040      for (int i = 0; i < realizations.Count; i++) {
    41         int singleRealization = -1;
     41        int singleRealization = -1, firstNode = -1;
    4242        for (int j = 0; j < realizations[i].Count; j++) {
    43           if (realizations[i][j].Value == 1) {
     43          if (realizations[i][p[j]].Value == 1) {
    4444            if (singleRealization != -1) {
    4545              estimatedSum += DistanceMatrix[singleRealization, p[j]];
     46            } else {
     47              firstNode = p[j];
    4648            }
    4749            singleRealization = p[j];
    4850          }
    4951        }
     52        if (singleRealization != -1) {
     53          estimatedSum += DistanceMatrix[singleRealization, firstNode];
     54        }
    5055      }
    5156      return estimatedSum / SampleSize.Value;
     57    }
     58
     59    public double[] EvaluateWithParams(DistanceMatrix distances, DoubleArray probabilities, ItemList<ItemList<IntValue>> realizations, Permutation individual ) {
     60      // Estimation-based evaluation
     61      MersenneTwister r = new MersenneTwister();
     62      double estimatedSum = 0;
     63      double[] partialSums = new double[realizations.Count];
     64      for (int i = 0; i < realizations.Count; i++) {
     65        partialSums[i] = 0;
     66        int singleRealization = -1, firstNode = -1;
     67        for (int j = 0; j < realizations[i].Count; j++) {
     68          if (realizations[i][individual[j]].Value == 1) {
     69            if (singleRealization != -1) {
     70              partialSums[i] += distances[singleRealization, individual[j]];
     71            } else {
     72              firstNode = individual[j];
     73            }
     74            singleRealization = individual[j];
     75          }
     76        }
     77        if (singleRealization != -1) {
     78          partialSums[i] += distances[singleRealization, firstNode];
     79        }
     80        estimatedSum += partialSums[i];
     81      }
     82      double mean = estimatedSum / realizations.Count;
     83      double variance = 0;
     84      for (int i = 0; i < realizations.Count; i++) {
     85        variance += Math.Pow((partialSums[i] - mean), 2);
     86      }
     87      variance = variance / realizations.Count;
     88      return new double[] {mean,variance};
    5289    }
    5390
     
    6198    }
    6299
     100    private int Ttest(int ProblemSize) {
     101      MersenneTwister random = new MersenneTwister();
     102      Permutation p1 = new Permutation(PermutationTypes.RelativeUndirected, ProblemSize, random);
     103      Permutation p2 = new Permutation(PermutationTypes.RelativeUndirected, ProblemSize, random);
     104      ItemList<ItemList<IntValue>> realizations = new ItemList<ItemList<IntValue>>();
     105      int index = -1;
     106      while (true) {
     107        for (int i = index+1; i < index+5; i++) {
     108          realizations.Add(new ItemList<IntValue>());
     109          for (int j = 0; j < ProblemSize; j++) {
     110            if (ProbabilityMatrix[j] > random.NextDouble()) {
     111              realizations.ElementAt(i).Add(new IntValue(1));
     112            } else {
     113              realizations.ElementAt(i).Add(new IntValue(0));
     114            }
     115          }
     116        }
     117        index += 4;
     118        double[] eval1 = EvaluateWithParams(DistanceMatrix, ProbabilityMatrix, realizations, p1);
     119        double[] eval2 = EvaluateWithParams(DistanceMatrix, ProbabilityMatrix, realizations, p2);
     120        double sx1x2 = Math.Sqrt((eval1[1]+eval2[1])/2);
     121        int degrees = 2 * realizations.Count - 2;
     122        double t = (eval1[0]-eval2[0])/(sx1x2*Math.Sqrt(2.0/(double)realizations.Count));
     123      }
     124    }
     125
    63126    public override void Load(TSPData data) {
    64127      base.Load(data);
    65128      // For now uses sample size of 20 but should use Student's t-test
    66       SampleSize = new IntValue(20);
     129      //Ttest(data.Dimension);
     130      SampleSize = new IntValue(25);
     131      MersenneTwister r = new MersenneTwister();
     132      int countOnes = 0;
    67133      realizations = new ItemList<ItemList<IntValue>>(SampleSize.Value);
    68       Random r = new Random();
    69134      for (int i = 0; i < SampleSize.Value; i++) {
    70         realizations.Add(new ItemList<IntValue>());
    71         for (int j = 0; j < data.Dimension; j++) {
    72           if (ProbabilityMatrix[j] > r.NextDouble()) {
    73             realizations.ElementAt(i).Add(new IntValue(1));
    74           } else {
    75             realizations.ElementAt(i).Add(new IntValue(0));
     135        ItemList<IntValue> newRealization = new ItemList<IntValue>();
     136        while (countOnes < 4) { //only generate realizations with at least 4 cities visited
     137          countOnes = 0;
     138          newRealization.Clear();
     139          for (int j = 0; j < data.Dimension; j++) {
     140            if (ProbabilityMatrix[j] > r.NextDouble()) {
     141              newRealization.Add(new IntValue(1));
     142              countOnes++;
     143            } else {
     144              newRealization.Add(new IntValue(0));
     145            }
    76146          }
    77147        }
    78        
     148        countOnes = 0;
     149        realizations.Add(newRealization);
    79150      }
    80151
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/HeuristicLab.Problems.PTSP-3.3.csproj

    r12228 r12261  
    9898      <Private>False</Private>
    9999    </Reference>
     100    <Reference Include="HeuristicLab.Random-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     101      <SpecificVersion>False</SpecificVersion>
     102      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Random-3.3.dll</HintPath>
     103    </Reference>
    100104    <Reference Include="System" />
    101105    <Reference Include="System.Core" />
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Improvers/PTSPExhaustiveInsertionLocalImprovement.cs

    r12228 r12261  
    3030using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    3131using System.Threading;
    32 using HeuristicLab.Problems.PTSP.MoveEvaluators.OneShift;
    3332
    3433namespace HeuristicLab.Problems.PTSP {
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/OneShift/PTSPEstimatedInsertionEvaluator.cs

    r12219 r12261  
    1 using HeuristicLab.Common;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
     22using HeuristicLab.Common;
    223using HeuristicLab.Core;
    324using HeuristicLab.Data;
     
    728using System;
    829
    9 namespace HeuristicLab.Problems.PTSP.MoveEvaluators.OneShift {
    10   class PTSPEstimatedInsertionEvaluator : PTSPPathMoveEvaluator, IPermutationTranslocationMoveOperator {
     30namespace HeuristicLab.Problems.PTSP {
     31  [Item("PTSPEstimatedInsertionEvaluator", "Evaluates an insertion move (1-shift)")]
     32  [StorableClass]
     33  public class PTSPEstimatedInsertionEvaluator : PTSPPathMoveEvaluator, IPermutationTranslocationMoveOperator {
    1134
    1235    public override Type EvaluatorType {
    13       get { return typeof(PTSPEstimatedInversionMovePathEvaluator); }
     36      get { return typeof(PTSPEstimatedInsertionEvaluator); }
    1437    }
    1538    public ILookupParameter<TranslocationMove> TranslocationMoveParameter {
     
    5477
    5578    public static double EvaluateByDistanceMatrix(Permutation permutation, TranslocationMove move, DistanceMatrix distanceMatrix, ItemList<ItemList<IntValue>> realizations) {
    56       //permutation = new Permutation(PermutationTypes.Absolute, new int[]{0,1,2,3,4,5,6,7}); TODO remove test
    57       //move = new TranslocationMove(0, 0, 4); TODO remove test
     79      Permutation afterMove = new Permutation(PermutationTypes.RelativeUndirected,permutation);
     80      TranslocationManipulator.Apply(afterMove, move.Index1, move.Index1, move.Index3);
    5881      double moveQuality = 0;
    5982      int[] edges = new int[12];
    6083      int[] indices = new int[12];
    6184      edges[0] = permutation.GetCircular(move.Index1 - 1);
    62       edges[6] = edges[0];
    63       indices[0] = move.Index1-1;
    64       if (indices[0] == -1) indices[0] = permutation.Length - 1;
    65       indices[6] = indices[0];
     85      indices[0] = decreaseCircularIndex(permutation.Length, move.Index1);
    6686      edges[1] = permutation[move.Index1];
    6787      indices[1] = move.Index1;
    68       edges[2] = edges[1];
    69       indices[2] = indices[1];
    70       edges[9] = edges[1];
    71       indices[9] = indices[1];
    72       edges[10] = edges[1];
    73       indices[10] = indices[1];
     88      edges[2] = permutation[move.Index1];
     89      indices[2] = move.Index1;
    7490      edges[3] = permutation.GetCircular(move.Index1 + 1);
    75       edges[7] = edges[3];
    76       indices[3] = move.Index1+1;
    77       if (indices[3] == permutation.Length + 1) indices[3] = 0;
    78       indices[7] = indices[3];
    79       edges[4] = permutation[move.Index3];
    80       indices[4] = move.Index3;
    81       edges[8] = edges[4];
    82       indices[8] = indices[4];
    83       edges[5] = permutation.GetCircular(move.Index3 + 1);
    84       edges[11] = edges[5];
    85       indices[5] = move.Index3+1;
    86       if (indices[5] == permutation.Length + 1) indices[5] = 0;
    87       indices[11] = indices[5];
     91      indices[3] = increaseCircularIndex(permutation.Length, move.Index1);
     92
     93      edges[6] = afterMove.GetCircular(move.Index3 - 1);
     94      indices[6] = decreaseCircularIndex(afterMove.Length, move.Index3);
     95      edges[7] = afterMove[move.Index3];
     96      indices[7] = move.Index3;
     97      edges[8] = afterMove[move.Index3];
     98      indices[8] = move.Index3;
     99      edges[9] = afterMove.GetCircular(move.Index3 + 1);
     100      indices[9] = increaseCircularIndex(afterMove.Length, move.Index3);
     101
     102      if (move.Index3 > move.Index1) {
     103        edges[4] = permutation[move.Index3];
     104        indices[4] = move.Index3;
     105        edges[5] = permutation.GetCircular(move.Index3 + 1);
     106        indices[5] = indices[9];
     107        edges[10] = afterMove.GetCircular(move.Index1 - 1);
     108        indices[10] = indices[0];
     109        edges[11] = afterMove[move.Index1];
     110        indices[11] = move.Index1;
     111      } else {
     112        edges[4] = permutation.GetCircular(move.Index3 - 1);
     113        indices[4] = indices[6];
     114        edges[5] = permutation[move.Index3];
     115        indices[5] = move.Index3;
     116        edges[10] = afterMove[move.Index1];
     117        indices[10] = move.Index1;
     118        edges[11] = afterMove.GetCircular(move.Index1 + 1);
     119        indices[11] = indices[3];
     120      }
    88121      int[] aPosteriori = new int[12];
     122      Permutation tempPermutation;
    89123      foreach (ItemList<IntValue> realization in realizations) {
    90         //int[] realization2 = new int[] { 1, 0, 1, 1, 0, 0, 1, 1 }; TODO remove test
    91124        for (int i = 0; i < edges.Length; i++) {
     125          if (i < 6) {
     126            tempPermutation = permutation;
     127          } else {
     128            tempPermutation = afterMove;
     129          }
    92130          if (realization[edges[i]].Value == 1) {
    93131            aPosteriori[i] = edges[i];
     
    96134            if (i%2==0) {
    97135              // find nearest predecessor in realization if source edge
    98               while(realization[permutation.GetCircular(indices[i]-j)].Value == 0) {
    99                 j--;
     136              while (realization[tempPermutation.GetCircular(indices[i] - j)].Value == 0) {
     137                j++;
    100138              }
    101               aPosteriori[i] = permutation.GetCircular(indices[i] - j);
     139              aPosteriori[i] = tempPermutation.GetCircular(indices[i] - j);
    102140            } else {
    103141              // find nearest successor in realization if target edge
    104               while(realization[permutation.GetCircular(indices[i]+j)].Value == 0) {
     142              while (realization[tempPermutation.GetCircular(indices[i] + j)].Value == 0) {
    105143                j++;
    106144              }
    107               aPosteriori[i] = permutation.GetCircular(indices[i] + j);
     145              aPosteriori[i] = tempPermutation.GetCircular(indices[i] + j);
    108146            }
    109147          }
    110148        }
    111         // compute cost difference between the two a posteriori solutions
    112         moveQuality += distanceMatrix[aPosteriori[6], aPosteriori[7]] + distanceMatrix[aPosteriori[8], aPosteriori[9]] + distanceMatrix[aPosteriori[10], aPosteriori[11]];
    113         moveQuality -= distanceMatrix[aPosteriori[0], aPosteriori[1]] - distanceMatrix[aPosteriori[2], aPosteriori[3]] - distanceMatrix[aPosteriori[4], aPosteriori[5]];
     149        if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3]) &&
     150          !(aPosteriori[0] == aPosteriori[4] && aPosteriori[1] == aPosteriori[5]) &&
     151          !(aPosteriori[2] == aPosteriori[4] && aPosteriori[3] == aPosteriori[5])) {
     152          // compute cost difference between the two a posteriori solutions
     153          moveQuality = moveQuality + distanceMatrix[aPosteriori[6], aPosteriori[7]] + distanceMatrix[aPosteriori[8], aPosteriori[9]] + distanceMatrix[aPosteriori[10], aPosteriori[11]];
     154          moveQuality = moveQuality - distanceMatrix[aPosteriori[0], aPosteriori[1]] - distanceMatrix[aPosteriori[2], aPosteriori[3]] - distanceMatrix[aPosteriori[4], aPosteriori[5]];
     155        }
     156        Array.Clear(aPosteriori, 0, aPosteriori.Length);
    114157      }
    115158      // return average of cost differences
    116       return moveQuality / realizations.Capacity;
     159      return Math.Abs(moveQuality) / realizations.Capacity;
     160    }
     161
     162    private static int decreaseCircularIndex(int length, int index) {
     163      int result = index - 1;
     164      if (result == -1) {
     165        result = length - 1;
     166      }
     167      return result;
     168    }
     169
     170    private static int increaseCircularIndex(int length, int index) {
     171      int result = index + 1;
     172      if (result == length + 1) {
     173        result = 0;
     174      }
     175      return result;
    117176    }
    118177
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/TwoOpt/PTSPEstimatedInversionMovePathEvaluator.cs

    r12219 r12261  
    100100              // find nearest predecessor in realization if source edge
    101101              while(realization[permutation.GetCircular(indices[i]-j)].Value==0) {
    102                 j--;
     102                j++;
    103103              }
    104104              aPosteriori[i] = permutation.GetCircular(indices[i] - j);
     
    113113        }
    114114        // compute cost difference between the two a posteriori solutions
    115         moveQuality += distanceMatrix[aPosteriori[0], aPosteriori[2]] + distanceMatrix[aPosteriori[1], aPosteriori[3]];
    116         moveQuality -= distanceMatrix[aPosteriori[0], aPosteriori[1]] - distanceMatrix[aPosteriori[2], aPosteriori[3]];
     115        if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3])) {
     116          moveQuality = moveQuality + distanceMatrix[aPosteriori[0], aPosteriori[2]] + distanceMatrix[aPosteriori[1], aPosteriori[3]] - distanceMatrix[aPosteriori[0], aPosteriori[1]] - distanceMatrix[aPosteriori[2], aPosteriori[3]];
     117        }
     118        Array.Clear(aPosteriori, 0, aPosteriori.Length);
    117119      }
    118120      // return average of cost differences
    119       return moveQuality / realizations.Capacity;
     121      return Math.Abs(moveQuality) / realizations.Capacity;
    120122    }
    121123
  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/PTSP.cs

    r12228 r12261  
    3434using HeuristicLab.Parameters;
    3535using HeuristicLab.Data;
     36using HeuristicLab.Random;
    3637
    3738namespace HeuristicLab.Problems.PTSP {
     
    133134      Description = data.Description;
    134135
     136      // Get Probabilities of cities using random with seed from hash function on the Name of the instance
     137      double[] tempMatrix = new double[data.Dimension];
     138      MersenneTwister r = new MersenneTwister((uint)data.Name.GetHashCode());
     139      for (int i = 0; i < data.Dimension; i++) {
     140        tempMatrix[i] = r.NextDouble();
     141      }
     142      ProbabilityMatrix = new DoubleArray(tempMatrix);
     143
     144      if (data.BestKnownTour != null) {
     145        BestKnownSolution = new Permutation(PermutationTypes.RelativeUndirected, data.BestKnownTour);
     146      }
     147     
    135148      bool clearCoordinates = false, clearDistanceMatrix = false;
    136149      if (data.Coordinates != null && data.Coordinates.GetLength(0) > 0)
     
    143156
    144157      DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
    145       // Get Probabilities of cities using random with seed from hash function on the Name of the instance
    146       ProbabilityMatrix = new DoubleArray(data.Dimension);
    147       Random r = new Random(data.Name.GetHashCode());
    148       for (int i = 0; i < data.Dimension; i++) {
    149         ProbabilityMatrix[i] = r.NextDouble();
    150       }
     158     
    151159      Encoding.Length = data.Dimension;
    152160
  • branches/PTSP/PTSP.sln

    r12228 r12261  
    77EndProject
    88Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.PTSP.Views-3.3", "HeuristicLab.Problems.PTSP.Views\3.3\HeuristicLab.Problems.PTSP.Views-3.3.csproj", "{90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}"
     9EndProject
     10Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.PTSP.Tests-3.3", "HeuristicLab.Problems.PTSP.Tests-3.3\HeuristicLab.Problems.PTSP.Tests-3.3.csproj", "{CBEC171A-F7EC-460D-94E2-D58625811D99}"
    911EndProject
    1012Global
     
    2224    {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Release|Any CPU.ActiveCfg = Release|Any CPU
    2325    {90B6CA12-9791-4430-B2D7-CD3ED7F75E2B}.Release|Any CPU.Build.0 = Release|Any CPU
     26    {CBEC171A-F7EC-460D-94E2-D58625811D99}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
     27    {CBEC171A-F7EC-460D-94E2-D58625811D99}.Debug|Any CPU.Build.0 = Debug|Any CPU
     28    {CBEC171A-F7EC-460D-94E2-D58625811D99}.Release|Any CPU.ActiveCfg = Release|Any CPU
     29    {CBEC171A-F7EC-460D-94E2-D58625811D99}.Release|Any CPU.Build.0 = Release|Any CPU
    2430  EndGlobalSection
    2531  GlobalSection(SolutionProperties) = preSolution
Note: See TracChangeset for help on using the changeset viewer.