Changeset 15109


Ignore:
Timestamp:
07/03/17 09:40:13 (4 months ago)
Author:
abeham
Message:

#2783: merged r15051,r15080,r15086,r15087 to stable

Location:
stable
Files:
8 edited
1 copied

Legend:

Unmodified
Added
Removed
  • stable

  • stable/HeuristicLab.Optimization

  • stable/HeuristicLab.Optimization.Operators/3.3/MultiObjective/FastNonDominatedSort.cs

    r14186 r15109  
    3939  [StorableClass]
    4040  public class FastNonDominatedSort : SingleSuccessorOperator, IMultiObjectiveOperator {
    41     private enum DominationResult { Dominates, IsDominated, IsNonDominated };
    4241
    4342    #region Parameter properties
     
    7574      int populationSize = scope.SubScopes.Count;
    7675
    77       List<ScopeList> fronts = new List<ScopeList>();
    78       Dictionary<IScope, List<int>> dominatedScopes = new Dictionary<IScope, List<int>>();
    79       int[] dominationCounter = new int[populationSize];
    80       ItemArray<IntValue> rank = new ItemArray<IntValue>(populationSize);
     76      int[] rank;
     77      var fronts = DominationCalculator<IScope>.CalculateAllParetoFronts(scope.SubScopes.ToArray(), qualities, maximization, out rank, dominateOnEqualQualities);
    8178
    82       for (int pI = 0; pI < populationSize - 1; pI++) {
    83         IScope p = scope.SubScopes[pI];
    84         List<int> dominatedScopesByp;
    85         if (!dominatedScopes.TryGetValue(p, out dominatedScopesByp))
    86           dominatedScopes[p] = dominatedScopesByp = new List<int>();
    87         for (int qI = pI + 1; qI < populationSize; qI++) {
    88           DominationResult test = Dominates(qualities[pI], qualities[qI], maximization, dominateOnEqualQualities);
    89           if (test == DominationResult.Dominates) {
    90             dominatedScopesByp.Add(qI);
    91             dominationCounter[qI] += 1;
    92           } else if (test == DominationResult.IsDominated) {
    93             dominationCounter[pI] += 1;
    94             if (!dominatedScopes.ContainsKey(scope.SubScopes[qI]))
    95               dominatedScopes.Add(scope.SubScopes[qI], new List<int>());
    96             dominatedScopes[scope.SubScopes[qI]].Add(pI);
    97           }
    98           if (pI == populationSize - 2
    99             && qI == populationSize - 1
    100             && dominationCounter[qI] == 0) {
    101             rank[qI] = new IntValue(0);
    102             AddToFront(scope.SubScopes[qI], fronts, 0);
    103           }
    104         }
    105         if (dominationCounter[pI] == 0) {
    106           rank[pI] = new IntValue(0);
    107           AddToFront(p, fronts, 0);
    108         }
    109       }
    110       int i = 0;
    111       while (i < fronts.Count && fronts[i].Count > 0) {
    112         ScopeList nextFront = new ScopeList();
    113         foreach (IScope p in fronts[i]) {
    114           List<int> dominatedScopesByp;
    115           if (dominatedScopes.TryGetValue(p, out dominatedScopesByp)) {
    116             for (int k = 0; k < dominatedScopesByp.Count; k++) {
    117               int dominatedScope = dominatedScopesByp[k];
    118               dominationCounter[dominatedScope] -= 1;
    119               if (dominationCounter[dominatedScope] == 0) {
    120                 rank[dominatedScope] = new IntValue(i + 1);
    121                 nextFront.Add(scope.SubScopes[dominatedScope]);
    122               }
    123             }
    124           }
    125         }
    126         i += 1;
    127         fronts.Add(nextFront);
    128       }
    129 
    130       RankParameter.ActualValue = rank;
     79      RankParameter.ActualValue = new ItemArray<IntValue>(rank.Select(x => new IntValue(x)));
    13180
    13281      scope.SubScopes.Clear();
    13382
    134       for (i = 0; i < fronts.Count; i++) {
     83      for (var i = 0; i < fronts.Count; i++) {
    13584        Scope frontScope = new Scope("Front " + i);
    13685        foreach (var p in fronts[i])
    137           frontScope.SubScopes.Add(p);
     86          frontScope.SubScopes.Add(p.Item1);
    13887        if (frontScope.SubScopes.Count > 0)
    13988          scope.SubScopes.Add(frontScope);
    14089      }
    14190      return base.Apply();
    142     }
    143 
    144     private static DominationResult Dominates(double[] left, double[] right, bool[] maximizations, bool dominateOnEqualQualities) {
    145       //mkommend Caution: do not use LINQ.SequenceEqual for comparing the two quality arrays (left and right) due to performance reasons
    146       if (dominateOnEqualQualities) {
    147         var equal = true;
    148         for (int i = 0; i < left.Length; i++) {
    149           if (left[i] != right[i]) {
    150             equal = false;
    151             break;
    152           }
    153         }
    154         if (equal) return DominationResult.Dominates;
    155       }
    156 
    157       bool leftIsBetter = false, rightIsBetter = false;
    158       for (int i = 0; i < left.Length; i++) {
    159         if (IsDominated(left[i], right[i], maximizations[i])) rightIsBetter = true;
    160         else if (IsDominated(right[i], left[i], maximizations[i])) leftIsBetter = true;
    161         if (leftIsBetter && rightIsBetter) break;
    162       }
    163 
    164       if (leftIsBetter && !rightIsBetter) return DominationResult.Dominates;
    165       if (!leftIsBetter && rightIsBetter) return DominationResult.IsDominated;
    166       return DominationResult.IsNonDominated;
    167     }
    168 
    169     private static bool IsDominated(double left, double right, bool maximization) {
    170       return maximization && left < right
    171         || !maximization && left > right;
    172     }
    173 
    174     private static void AddToFront(IScope p, List<ScopeList> fronts, int i) {
    175       if (i == fronts.Count) fronts.Add(new ScopeList());
    176       fronts[i].Add(p);
    17791    }
    17892
  • stable/HeuristicLab.Optimization/3.3/BasicProblems/MultiObjectiveBasicProblem.cs

    r15108 r15109  
    2020#endregion
    2121
     22using System;
     23using System.Collections.Generic;
    2224using System.Linq;
    2325using HeuristicLab.Common;
     
    5759    public abstract double[] Evaluate(Individual individual, IRandom random);
    5860    public virtual void Analyze(Individual[] individuals, double[][] qualities, ResultCollection results, IRandom random) { }
    59 
     61   
    6062    protected override void OnOperatorsChanged() {
    6163      base.OnOperatorsChanged();
  • stable/HeuristicLab.Optimization/3.3/BasicProblems/SingleObjectiveBasicProblem.cs

    r15108 r15109  
    2020#endregion
    2121
     22using System;
    2223using System.Collections.Generic;
    2324using System.Linq;
     
    8485    }
    8586
     87    protected Tuple<Individual, double> GetBestIndividual(Individual[] individuals, double[] qualities) {
     88      return GetBestIndividual(individuals, qualities, Maximization);
     89    }
     90    public static Tuple<Individual, double> GetBestIndividual(Individual[] individuals, double[] qualities, bool maximization) {
     91      var zipped = individuals.Zip(qualities, (i, q) => new { Individual = i, Quality = q });
     92      var best = (maximization ? zipped.OrderByDescending(z => z.Quality) : zipped.OrderBy(z => z.Quality)).First();
     93      return Tuple.Create(best.Individual, best.Quality);
     94    }
     95
    8696    protected override void OnOperatorsChanged() {
    8797      base.OnOperatorsChanged();
  • stable/HeuristicLab.Optimization/3.3/HeuristicLab.Optimization-3.3.csproj

    r15081 r15109  
    156156    <Compile Include="Interfaces\ILocalImprovementAlgorithmOperator.cs" />
    157157    <Compile Include="Interfaces\IMultiObjectiveOperator.cs" />
     158    <Compile Include="MultiObjective\DominationCalculator.cs" />
    158159    <Compile Include="Results\IResultParameter.cs" />
    159160    <Compile Include="Interfaces\ISingleObjectiveOperator.cs" />
  • stable/HeuristicLab.Optimization/3.3/MultiObjective/DominationCalculator.cs

    r15080 r15109  
    2222using System;
    2323using System.Collections.Generic;
    24 using HeuristicLab.Core;
    25 using HeuristicLab.Data;
    2624
    2725namespace HeuristicLab.Optimization {
     
    10098    }
    10199
    102     private static List<Tuple<T, double[]>> CalculateBestFront(T[] individuals, double[][] qualities, bool[] maximization, bool dominateOnEqualQualities, int populationSize, out Dictionary<T, List<int>> dominatedIndividuals, out int[] dominationCounter, out int[] rank) {
     100    private static List<Tuple<T, double[]>> CalculateBestFront(T[] solutions, double[][] qualities, bool[] maximization, bool dominateOnEqualQualities, int populationSize, out Dictionary<T, List<int>> dominatedIndividuals, out int[] dominationCounter, out int[] rank) {
    103101      var front = new List<Tuple<T, double[]>>();
    104102      dominatedIndividuals = new Dictionary<T, List<int>>();
     
    106104      rank = new int[populationSize];
    107105      for (int pI = 0; pI < populationSize - 1; pI++) {
    108         var p = individuals[pI];
     106        var p = solutions[pI];
    109107        List<int> dominatedIndividualsByp;
    110108        if (!dominatedIndividuals.TryGetValue(p, out dominatedIndividualsByp))
     
    117115          } else if (test == DominationResult.IsDominated) {
    118116            dominationCounter[pI] += 1;
    119             if (!dominatedIndividuals.ContainsKey(individuals[qI]))
    120               dominatedIndividuals.Add(individuals[qI], new List<int>());
    121             dominatedIndividuals[individuals[qI]].Add(pI);
     117            if (!dominatedIndividuals.ContainsKey(solutions[qI]))
     118              dominatedIndividuals.Add(solutions[qI], new List<int>());
     119            dominatedIndividuals[solutions[qI]].Add(pI);
    122120          }
    123121          if (pI == populationSize - 2
     
    125123            && dominationCounter[qI] == 0) {
    126124            rank[qI] = 0;
    127             front.Add(Tuple.Create(individuals[qI], qualities[qI]));
     125            front.Add(Tuple.Create(solutions[qI], qualities[qI]));
    128126          }
    129127        }
  • stable/HeuristicLab.Optimization/3.3/Results/ResultCollection.cs

    r14186 r15109  
    7575    }
    7676
     77    public void AddOrUpdateResult(string name, IItem value) {
     78      IResult res;
     79      if (!TryGetValue(name, out res)) {
     80        res = new Result(name, value);
     81        Add(res);
     82      } else res.Value = value;
     83    }
    7784  }
    7885}
Note: See TracChangeset for help on using the changeset viewer.