Free cookie consent management tool by TermsFeed Policy Generator

Changeset 15080


Ignore:
Timestamp:
06/28/17 22:05:14 (8 years ago)
Author:
abeham
Message:

#2783: Moved pareto front calculation from MultiObjectiveBasicProblem to a new class DominationCalculator<T>. Changed FastNonDominatedSort to use the new class.

Location:
trunk/sources
Files:
2 added
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.Optimization.Operators/3.3/MultiObjective/FastNonDominatedSort.cs

    r14185 r15080  
    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

  • trunk/sources/HeuristicLab.Optimization/3.3/BasicProblems/MultiObjectiveBasicProblem.cs

    r15051 r15080  
    5959    public abstract double[] Evaluate(Individual individual, IRandom random);
    6060    public virtual void Analyze(Individual[] individuals, double[][] qualities, ResultCollection results, IRandom random) { }
    61 
    62     protected List<List<Tuple<Individual, double[]>>> GetParetoFronts(Individual[] individuals, double[][] qualities, bool dominateOnEqualQualities = true) {
    63       return GetParetoFronts(individuals, qualities, Maximization, dominateOnEqualQualities);
    64     }
    65     public static List<List<Tuple<Individual, double[]>>> GetParetoFronts(Individual[] individuals, double[][] qualities, bool[] maximization, bool dominateOnEqualQualities = true) {
    66       int populationSize = individuals.Length;
    67 
    68       var fronts = new List<List<Tuple<Individual, double[]>>>();
    69       fronts.Add(new List<Tuple<Individual, double[]>>());
    70       Dictionary<Individual, List<int>> dominatedIndividuals = new Dictionary<Individual, List<int>>();
    71       int[] dominationCounter = new int[populationSize];
    72       ItemArray<IntValue> rank = new ItemArray<IntValue>(populationSize);
    73 
    74       for (int pI = 0; pI < populationSize - 1; pI++) {
    75         var p = individuals[pI];
    76         List<int> dominatedIndividualsByp;
    77         if (!dominatedIndividuals.TryGetValue(p, out dominatedIndividualsByp))
    78           dominatedIndividuals[p] = dominatedIndividualsByp = new List<int>();
    79         for (int qI = pI + 1; qI < populationSize; qI++) {
    80           var test = Dominates(qualities[pI], qualities[qI], maximization, dominateOnEqualQualities);
    81           if (test == 1) {
    82             dominatedIndividualsByp.Add(qI);
    83             dominationCounter[qI] += 1;
    84           } else if (test == -1) {
    85             dominationCounter[pI] += 1;
    86             if (!dominatedIndividuals.ContainsKey(individuals[qI]))
    87               dominatedIndividuals.Add(individuals[qI], new List<int>());
    88             dominatedIndividuals[individuals[qI]].Add(pI);
    89           }
    90           if (pI == populationSize - 2
    91             && qI == populationSize - 1
    92             && dominationCounter[qI] == 0) {
    93             rank[qI] = new IntValue(0);
    94             fronts[0].Add(Tuple.Create(individuals[qI], qualities[qI]));
    95           }
    96         }
    97         if (dominationCounter[pI] == 0) {
    98           rank[pI] = new IntValue(0);
    99           fronts[0].Add(Tuple.Create(p, qualities[pI]));
    100         }
    101       }
    102       int i = 0;
    103       while (i < fronts.Count && fronts[i].Count > 0) {
    104         var nextFront = new List<Tuple<Individual, double[]>>();
    105         foreach (var p in fronts[i]) {
    106           List<int> dominatedIndividualsByp;
    107           if (dominatedIndividuals.TryGetValue(p.Item1, out dominatedIndividualsByp)) {
    108             for (int k = 0; k < dominatedIndividualsByp.Count; k++) {
    109               int dominatedIndividual = dominatedIndividualsByp[k];
    110               dominationCounter[dominatedIndividual] -= 1;
    111               if (dominationCounter[dominatedIndividual] == 0) {
    112                 rank[dominatedIndividual] = new IntValue(i + 1);
    113                 nextFront.Add(Tuple.Create(individuals[dominatedIndividual], qualities[dominatedIndividual]));
    114               }
    115             }
    116           }
    117         }
    118         i += 1;
    119         fronts.Add(nextFront);
    120       }
    121       return fronts;
    122     }
    123 
    124     private static int Dominates(double[] left, double[] right, bool[] maximizations, bool dominateOnEqualQualities) {
    125       //mkommend Caution: do not use LINQ.SequenceEqual for comparing the two quality arrays (left and right) due to performance reasons
    126       if (dominateOnEqualQualities) {
    127         var equal = true;
    128         for (int i = 0; i < left.Length; i++) {
    129           if (left[i] != right[i]) {
    130             equal = false;
    131             break;
    132           }
    133         }
    134         if (equal) return 1;
    135       }
    136 
    137       bool leftIsBetter = false, rightIsBetter = false;
    138       for (int i = 0; i < left.Length; i++) {
    139         if (IsDominated(left[i], right[i], maximizations[i])) rightIsBetter = true;
    140         else if (IsDominated(right[i], left[i], maximizations[i])) leftIsBetter = true;
    141         if (leftIsBetter && rightIsBetter) break;
    142       }
    143 
    144       if (leftIsBetter && !rightIsBetter) return 1;
    145       if (!leftIsBetter && rightIsBetter) return -1;
    146       return 0;
    147     }
    148 
    149     private static bool IsDominated(double left, double right, bool maximization) {
    150       return maximization && left < right
    151         || !maximization && left > right;
    152     }
    153 
     61   
    15462    protected override void OnOperatorsChanged() {
    15563      base.OnOperatorsChanged();

  • trunk/sources/HeuristicLab.Optimization/3.3/HeuristicLab.Optimization-3.3.csproj

    r14071 r15080  
    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" />
Note: See TracChangeset for help on using the changeset viewer.