Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
02/23/17 10:42:58 (8 years ago)
Author:
abeham
Message:

#2457: working on identification of problem instances

File:
1 edited

Legend:

Unmodified
Added
Removed

  • branches/PerformanceComparison/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/QAP/QAPDirectedWalk.cs

    r14690 r14691  
    7979    private QAPDirectedWalk(QAPDirectedWalk original, Cloner cloner) : base(original, cloner) { }
    8080    public QAPDirectedWalk() {
    81       characteristics.AddRange(new[] { "Swap2.Sharpness", "Swap2.Bumpiness", "Swap2.Flatness", "Swap2.Steadiness" }
     81      characteristics.AddRange(new[] { "Swap2.Sharpness", "Swap2.Bumpiness", "Swap2.Flatness", /*"Swap2.Steadiness"*/ }
    8282        .Select(x => new StringValue(x)).ToList());
    8383      Parameters.Add(new FixedValueParameter<IntValue>("Paths", "The number of paths to explore (a path is a set of solutions that connect two randomly chosen solutions).", new IntValue(50)));
    … …  
    118118
    119119      var trajectories = Run(random, (QuadraticAssignmentProblem)Problem, permutations, BestImprovement).ToList();
    120       var firstDerivatives = trajectories.Select(path => ApproximateDerivative(path).ToList()).ToList();
    121       var secondDerivatives = firstDerivatives.Select(d1 => ApproximateDerivative(d1).ToList()).ToList();
     120      var result = PermutationPathAnalysis.GetCharacteristics(trajectories);
    122121     
    123       var props = GetCharacteristics(trajectories, firstDerivatives, secondDerivatives).ToDictionary(x => x.Item1, x => x.Item2);
    124122      foreach (var chara in characteristics.CheckedItems.Select(x => x.Value.Value)) {
    125         if (chara == "Swap2.Sharpness") yield return new Result("Swap2.Sharpness", new DoubleValue(props["Sharpness"]));
    126         if (chara == "Swap2.Bumpiness") yield return new Result("Swap2.Bumpiness", new DoubleValue(props["Bumpiness"]));
    127         if (chara == "Swap2.Flatness") yield return new Result("Swap2.Flatness", new DoubleValue(props["Flatness"]));
    128         if (chara == "Swap2.Steadiness") yield return new Result("Swap2.Steadiness", new DoubleValue(props["Steadiness"]));
    129       }
    130     }
    131 
    132     public static IEnumerable<IResult> Calculate(List<List<Tuple<Permutation, double>>> trajectories) {
    133       var firstDerivatives = trajectories.Select(path => ApproximateDerivative(path).ToList()).ToList();
    134       var secondDerivatives = firstDerivatives.Select(d1 => ApproximateDerivative(d1).ToList()).ToList();
    135 
    136       var props = GetCharacteristics(trajectories, firstDerivatives, secondDerivatives).ToDictionary(x => x.Item1, x => x.Item2);
    137       yield return new Result("Swap2.Sharpness", new DoubleValue(props["Sharpness"]));
    138       yield return new Result("Swap2.Bumpiness", new DoubleValue(props["Bumpiness"]));
    139       yield return new Result("Swap2.Flatness", new DoubleValue(props["Flatness"]));
    140       yield return new Result("Swap2.Steadiness", new DoubleValue(props["Steadiness"]));
     123        if (chara == "Swap2.Sharpness") yield return new Result("Swap2.Sharpness", new DoubleValue(result.Sharpness));
     124        if (chara == "Swap2.Bumpiness") yield return new Result("Swap2.Bumpiness", new DoubleValue(result.Bumpiness));
     125        if (chara == "Swap2.Flatness") yield return new Result("Swap2.Flatness", new DoubleValue(result.Flatness));
     126      }
    141127    }
    142128
    … …  
    158144    }
    159145
    160     private static IEnumerable<Tuple<string, double>> GetCharacteristics(List<List<Tuple<Permutation, double>>> f, List<List<Tuple<Permutation, double>>> f1, List<List<Tuple<Permutation, double>>> f2) {
    161       var sharpness = f2.Average(x => Area(x));
    162       var bumpiness = 0.0;
    163       var flatness = 0.0;
    164       var downPointing = f1.Where(x => x.Min(y => y.Item2) < 0).ToList();
    165 
    166       var steadiness = 0.0;
    167       foreach (var path in downPointing) {
    168         steadiness += ComBelowZero(path);
    169       }
    170       if (downPointing.Count > 0) steadiness /= downPointing.Count;
    171 
    172       for (var p = 0; p < f2.Count; p++) {
    173         if (f2[p].Count <= 2) continue;
    174         var bump = 0;
    175         var flat = 0;
    176         for (var i = 0; i < f2[p].Count - 1; i++) {
    177           if ((f2[p][i].Item2 > 0 && f2[p][i + 1].Item2 < 0) || (f2[p][i].Item2 < 0 && f2[p][i + 1].Item2 > 0)) {
    178             bump++;
    179           } else if (f2[p][i].Item2 == 0) {
    180             flat++;
    181           }
    182         }
    183         bumpiness += bump / (f2[p].Count - 1.0);
    184         flatness += flat / (f2[p].Count - 1.0);
    185       }
    186       bumpiness /= f2.Count;
    187       flatness /= f2.Count;
    188       return new[] {
    189       Tuple.Create("Sharpness", sharpness),
    190       Tuple.Create("Bumpiness", bumpiness),
    191       Tuple.Create("Flatness", flatness),
    192       Tuple.Create("Steadiness", steadiness)
    193     };
    194     }
    195 
    196     public static IEnumerable<Tuple<Permutation, double>> BestDirectedWalk(QuadraticAssignmentProblem qap, Permutation start, Permutation end) {
     146    private static IEnumerable<Tuple<Permutation, double>> BestDirectedWalk(QuadraticAssignmentProblem qap, Permutation start, Permutation end) {
    197147      var N = qap.Weights.Rows;
    198148      var sol = start;
    … …  
    225175    }
    226176
    227     public static IEnumerable<Tuple<Permutation, double>> FirstDirectedWalk(IRandom random, QuadraticAssignmentProblem qap, Permutation start, Permutation end) {
     177    private static IEnumerable<Tuple<Permutation, double>> FirstDirectedWalk(IRandom random, QuadraticAssignmentProblem qap, Permutation start, Permutation end) {
    228178      var N = qap.Weights.Rows;
    229179      var sol = start;
    … …  
    260210    }
    261211
    262     private static double Area(IEnumerable<Tuple<Permutation, double>> path) {
    263       var iter = path.GetEnumerator();
    264       if (!iter.MoveNext()) return 0.0;
    265       var area = 0.0;
    266       var prev = iter.Current;
    267       while (iter.MoveNext()) {
    268         area += TrapezoidArea(prev, iter.Current);
    269         prev = iter.Current;
    270       }
    271       return area;
    272     }
    273 
    274     private static double TrapezoidArea(Tuple<Permutation, double> a, Tuple<Permutation, double> b) {
    275       var area = 0.0;
    276       var dist = Dist(a.Item1, b.Item1);
    277       if ((a.Item2 <= 0 && b.Item2 <= 0) || (a.Item2 >= 0 && b.Item2 >= 0))
    278         area += dist * (Math.Abs(a.Item2) + Math.Abs(b.Item2)) / 2.0;
    279       else {
    280         var k = (b.Item2 - a.Item2) / dist;
    281         var d = a.Item2;
    282         var x = -d / k;
    283         area += Math.Abs(x * a.Item2 / 2.0);
    284         area += Math.Abs((dist - x) * b.Item2 / 2.0);
    285       }
    286       return area;
    287     }
    288 
    289     // Center-of-Mass
    290     private static double ComBelowZero(IEnumerable<Tuple<Permutation, double>> path) {
    291       var area = 0.0;
    292       var com = 0.0;
    293       var nwalkDist = 0.0;
    294       Tuple<Permutation, double> prev = null;
    295       var iter = path.GetEnumerator();
    296       while (iter.MoveNext()) {
    297         var c = iter.Current;
    298         if (prev != null) {
    299           var ndist = Dist(prev.Item1, c.Item1) / (double)c.Item1.Length;
    300           nwalkDist += ndist;
    301           if (prev.Item2 < 0 || c.Item2 < 0) {
    302             var a = TrapezoidArea(prev, c) / (double)c.Item1.Length;
    303             area += a;
    304             com += (nwalkDist - (ndist / 2.0)) * a;
    305           }
    306         }
    307         prev = c;
    308       }
    309       return com / area;
    310     }
    311 
    312     private static IEnumerable<Tuple<Permutation, double>> ApproximateDerivative(IEnumerable<Tuple<Permutation, double>> data) {
    313       Tuple<Permutation, double> prev = null, prev2 = null;
    314       foreach (var d in data) {
    315         if (prev == null) {
    316           prev = d;
    317           continue;
    318         }
    319         if (prev2 == null) {
    320           prev2 = prev;
    321           prev = d;
    322           continue;
    323         }
    324         var dist = Dist(prev2.Item1, d.Item1);
    325         yield return Tuple.Create(prev.Item1, (d.Item2 - prev2.Item2) / (double)dist);
    326         prev2 = prev;
    327         prev = d;
    328       }
    329     }
    330 
    331     private static double Dist(Permutation a, Permutation b) {
    332       var dist = 0;
    333       for (var i = 0; i < a.Length; i++)
    334         if (a[i] != b[i]) dist++;
    335       return dist;
    336     }
    337 
    338212    private static int[] GetInverse(Permutation p) {
    339213      var inv = new int[p.Length];
Note: See TracChangeset for help on using the changeset viewer.