Changeset 4432


Ignore:
Timestamp:
09/19/10 01:38:09 (9 years ago)
Author:
swinkler
Message:

Worked on population diversity analyzer for TSP. (#1188)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.DiversityAnalysis/HeuristicLab.Problems.TravelingSalesman/3.3/Analyzers/TSPPopulationDiversityAnalyzer.cs

    r4420 r4432  
    4040    // TODO:
    4141    // - iterations sampling
    42     // - decide whether old results shall be stored or disposed
    4342    // - view
    44     // - check results for identical solutions
    4543
    4644    public ScopeTreeLookupParameter<Permutation> PermutationParameter {
     
    5048      get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
    5149    }
    52     public LookupParameter<ItemList<DoubleMatrix>> SimilaritiesParameter {
    53       get { return (LookupParameter<ItemList<DoubleMatrix>>)Parameters["Similarities"]; }
     50    public ValueParameter<BoolValue> StoreCompleteHistoryParameter {
     51      get { return (ValueParameter<BoolValue>)Parameters["StoreCompleteHistory"]; }
    5452    }
    55     public LookupParameter<ItemList<DoubleArray>> MaximumSimilaritiesParameter {
    56       get { return (LookupParameter<ItemList<DoubleArray>>)Parameters["MaximumSimilarities"]; }
     53    public ValueParameter<ItemList<DoubleMatrix>> SimilaritiesParameter {
     54      get { return (ValueParameter<ItemList<DoubleMatrix>>)Parameters["Similarities"]; }
    5755    }
    58     public LookupParameter<ItemList<DoubleValue>> AverageMaximumSimilaritiesParameter {
    59       get { return (LookupParameter<ItemList<DoubleValue>>)Parameters["AverageMaximumSimilarities"]; }
     56    public ValueParameter<ItemList<DoubleArray>> MaximumSimilaritiesParameter {
     57      get { return (ValueParameter<ItemList<DoubleArray>>)Parameters["MaximumSimilarities"]; }
    6058    }
    61     public LookupParameter<ItemList<DoubleValue>> AverageSimilaritiesParameter {
    62       get { return (LookupParameter<ItemList<DoubleValue>>)Parameters["AverageSimilarities"]; }
     59    public ValueParameter<ItemList<DoubleValue>> AverageMaximumSimilaritiesParameter {
     60      get { return (ValueParameter<ItemList<DoubleValue>>)Parameters["AverageMaximumSimilarities"]; }
    6361    }
    64 
    65     [NonSerialized]
    66     private int[] rxData, ryData;
    67     [NonSerialized]
    68     private Permutation lastX, lastY;
     62    public ValueParameter<ItemList<DoubleValue>> AverageSimilaritiesParameter {
     63      get { return (ValueParameter<ItemList<DoubleValue>>)Parameters["AverageSimilarities"]; }
     64    }
    6965
    7066    public TSPPopulationDiversityAnalyzer()
     
    7268      Parameters.Add(new ScopeTreeLookupParameter<Permutation>("Permutation", "The TSP solutions given in path representation from which the best solution should be analyzed."));
    7369      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The qualities of the TSP solutions which should be analyzed."));
    74       Parameters.Add(new LookupParameter<ItemList<DoubleMatrix>>("Similarities", "The similarities of the TSP solutions which should be analyzed."));
    75       Parameters.Add(new LookupParameter<ItemList<DoubleArray>>("MaximumSimilarities", "The maximum similarities of the TSP solutions which should be analyzed."));
    76       Parameters.Add(new LookupParameter<ItemList<DoubleValue>>("AverageMaximumSimilarities", "The average maximum similarities of the TSP solutions which should be analyzed."));
    77       Parameters.Add(new LookupParameter<ItemList<DoubleValue>>("AverageSimilarities", "The average similarities of the TSP solutions which should be analyzed."));
    78       rxData = null;
    79       ryData = null;
    80       lastX = null;
    81       lastY = null;
     70      Parameters.Add(new ValueParameter<BoolValue>("StoreCompleteHistory", "Flag that denotes whether the complete history of similarity values shall be stored.", new BoolValue(true)));
     71      Parameters.Add(new ValueParameter<ItemList<DoubleMatrix>>("Similarities", "The similarities of the TSP solutions which should be analyzed."));
     72      Parameters.Add(new ValueParameter<ItemList<DoubleArray>>("MaximumSimilarities", "The maximum similarities of the TSP solutions which should be analyzed."));
     73      Parameters.Add(new ValueParameter<ItemList<DoubleValue>>("AverageMaximumSimilarities", "The average maximum similarities of the TSP solutions which should be analyzed."));
     74      Parameters.Add(new ValueParameter<ItemList<DoubleValue>>("AverageSimilarities", "The average similarities of the TSP solutions which should be analyzed."));
    8275    }
    8376
    8477    public override IOperation Apply() {
     78
     79      #region testing
     80      /*
     81      Permutation permutationA = new Permutation(PermutationTypes.Absolute, new int[] { 0, 5, 4, 3, 2, 1 });
     82      Permutation permutationB = new Permutation(PermutationTypes.Absolute, new int[] { 0, 3, 2, 4, 5, 1 });
     83      Permutation permutationC = new Permutation(PermutationTypes.Absolute, new int[] { 3, 2, 4, 5, 1, 0 });
     84      Permutation permutationD = new Permutation(PermutationTypes.Absolute, new int[] { 3, 2, 4, 5, 0, 1 });
     85      int[] edgesA = CalculateEdgesVector(permutationA);
     86      int[] edgesB = CalculateEdgesVector(permutationB);
     87      int[] edgesC = CalculateEdgesVector(permutationC);
     88      int[] edgesD = CalculateEdgesVector(permutationD);
     89      double s = CalculateSimilarity(edgesA, edgesB);
     90      s = CalculateSimilarity(edgesA, edgesA);
     91      s = CalculateSimilarity(edgesB, edgesB);
     92      s = CalculateSimilarity(edgesC, edgesC);
     93      s = CalculateSimilarity(edgesD, edgesD);
     94      s = CalculateSimilarity(edgesB, edgesC);
     95      s = CalculateSimilarity(edgesC, edgesD);
     96      */
     97      #endregion
    8598
    8699      ItemArray<Permutation> permutations = PermutationParameter.ActualValue;
     
    107120      #endregion
    108121
     122      int[][] edges = new int[cities][];
     123      for (int i = 0; i < cities; i++)
     124        edges[i] = CalculateEdgesVector(permutationsArray[i]);
     125
    109126      DoubleMatrix similarities = new DoubleMatrix(cities, cities);
    110127      DoubleArray maxSimilarities = new DoubleArray(cities);
     
    113130      for (int i = 0; i < cities; i++) {
    114131        similarities[i, i] = 1;
    115         // for (int j = (i + 1); j < cities; j++) {
    116         for (int j = (i); j < cities; j++) {
    117           double similarity = CalculateSimilarity(permutationsArray[i], permutationsArray[j]);
     132        for (int j = (i + 1); j < cities; j++) {
     133          double similarity = CalculateSimilarity(edges[i], edges[j]);
    118134          avgSimilarity += similarity;
    119135          n++;
     
    129145      DoubleValue averageSimilarity = new DoubleValue(avgSimilarity / n);
    130146
    131       if (SimilaritiesParameter.ActualValue == null) {
    132         SimilaritiesParameter.ActualValue = new ItemList<DoubleMatrix>();
    133         MaximumSimilaritiesParameter.ActualValue = new ItemList<DoubleArray>();
    134         AverageMaximumSimilaritiesParameter.ActualValue = new ItemList<DoubleValue>();
    135         AverageSimilaritiesParameter.ActualValue = new ItemList<DoubleValue>();
     147      if (SimilaritiesParameter.Value == null) {
     148        SimilaritiesParameter.Value = new ItemList<DoubleMatrix>();
     149        MaximumSimilaritiesParameter.Value = new ItemList<DoubleArray>();
     150        AverageMaximumSimilaritiesParameter.Value = new ItemList<DoubleValue>();
     151        AverageSimilaritiesParameter.Value = new ItemList<DoubleValue>();
    136152      }
    137       SimilaritiesParameter.ActualValue.Add(similarities);
    138       MaximumSimilaritiesParameter.ActualValue.Add(maxSimilarities);
    139       AverageMaximumSimilaritiesParameter.ActualValue.Add(averageMaximumSimilarity);
    140       AverageSimilaritiesParameter.ActualValue.Add(averageSimilarity);
     153      if (!StoreCompleteHistoryParameter.Value.Value && SimilaritiesParameter.Value.Count > 0) {
     154        SimilaritiesParameter.Value[SimilaritiesParameter.Value.Count - 1] = null;
     155        MaximumSimilaritiesParameter.Value[MaximumSimilaritiesParameter.Value.Count - 1] = null;
     156      }
     157      SimilaritiesParameter.Value.Add(similarities);
     158      MaximumSimilaritiesParameter.Value.Add(maxSimilarities);
     159      AverageMaximumSimilaritiesParameter.Value.Add(averageMaximumSimilarity);
     160      AverageSimilaritiesParameter.Value.Add(averageSimilarity);
    141161
    142162      return base.Apply();
    143163    }
    144164
    145     private double CalculateSimilarity(Permutation x, Permutation y) {
     165    private static int[] CalculateEdgesVector(Permutation permutation) {
     166      int cities = permutation.Length;
     167      int[] edgesVector = new int[cities];
     168      for (int i = 0; i < (cities - 1); i++)
     169        edgesVector[permutation[i]] = permutation[i + 1];
     170      edgesVector[permutation[cities - 1]] = permutation[0];
     171      return edgesVector;
     172    }
    146173
    147       int cities = x.Length;
    148       if (rxData == null || rxData.Length != cities) {
    149         rxData = new int[cities];
    150         ryData = new int[cities];
    151       }
    152 
    153       if (x.Length != y.Length) throw new InvalidOperationException("ERROR in " + Name + ": Similarity can only be calculated between instances of an equal number of cities");
    154       #region Performance savings when calling the function with at least one parameter identical to the last call
    155       if (x == lastX) { // if Solution1 stayed the same
    156         if (y != lastY) { // and Solution2 changed
    157           for (int i = 0; i < y.Length; i++)
    158             ryData[y[i]] = i;
    159         }
    160       } else {
    161         if (y == lastX && x == lastY) { // if Solution1 and Solution2 were reversed the call before
    162           int[] h = ryData;
    163           ryData = rxData;
    164           rxData = h;
    165         } else if (y == lastX) { // or if just Solution1 is different now
    166           ryData = rxData;
    167           rxData = new int[x.Length];
    168           for (int i = 0; i < x.Length; i++)
    169             rxData[x[i]] = i;
    170         } else if (x == lastY) { // or just Solution2 is different now
    171           rxData = ryData;
    172           ryData = new int[y.Length];
    173           for (int i = 0; i < y.Length; i++)
    174             ryData[y[i]] = i;
    175         } else if (y != lastY) { // or none are the same
    176           for (int i = 0; i < x.Length; i++) {
    177             rxData[x[i]] = i;
    178             ryData[y[i]] = i;
    179           }
    180         } else { // or just Solution2 is the same
    181           for (int i = 0; i < x.Length; i++)
    182             rxData[x[i]] = i;
    183         }
    184       }
    185       lastX = x;
    186       lastY = y;
    187       #endregion
     174    private double CalculateSimilarity(int[] edgesA, int[] edgesB) {
     175      if (edgesA.Length != edgesB.Length)
     176        throw new InvalidOperationException("ERROR in " + Name + ": Similarity can only be calculated between instances of an equal number of cities");
     177      int cities = edgesA.Length;
    188178      int similarEdges = 0;
    189       for (int i = 1; i <= x.Length; i++) {
    190         if (Math.Abs(ryData[x[(i < x.Length) ? (i) : (0)]] - ryData[x[i - 1]]) == 1
    191           || Math.Abs(ryData[x[(i < x.Length) ? (i) : (0)]] - ryData[x[i - 1]]) == x.Length)
     179      for (int i = 0; i < edgesA.Length; i++) {
     180        if (edgesA[i] == edgesB[i] || edgesA[edgesB[i]] == i)
    192181          similarEdges++;
    193182      }
    194       return (double)similarEdges / (double)x.Length;
    195 
     183      return (double)(similarEdges) / cities;
    196184    }
    197185
Note: See TracChangeset for help on using the changeset viewer.