Changeset 15089


Ignore:
Timestamp:
06/29/17 14:11:04 (4 months ago)
Author:
bwerth
Message:

#2592 removed effectively unused field "rank" from Individual, removed non-dominated sorting

Location:
branches/MOCMAEvolutionStrategy/HeuristicLab.Algorithms.MOCMAEvolutionStrategy/3.3
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • branches/MOCMAEvolutionStrategy/HeuristicLab.Algorithms.MOCMAEvolutionStrategy/3.3/HeuristicLab.Algorithms.MOCMAEvolutionStrategy-3.3.csproj

    r15045 r15089  
    106106  </ItemGroup>
    107107  <ItemGroup>
     108    <Compile Include="IDominatingArchive.cs" />
    108109    <Compile Include="Indicators\MinimalDistanceIndicator.cs" />
    109110    <Compile Include="Indicators\CrowdingIndicator.cs" />
    110111    <Compile Include="Indicators\HypervolumeIndicator.cs" />
    111112    <Compile Include="IIndicator.cs" />
     113    <Compile Include="Archives\ListArchive.cs" />
    112114    <Compile Include="Individual.cs" />
    113115    <Compile Include="MOCMAEvolutionStrategy.cs" />
     
    116118    <Compile Include="DoubleMatrixHelper.cs" />
    117119  </ItemGroup>
     120  <ItemGroup />
    118121  <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
    119122  <PropertyGroup>
  • branches/MOCMAEvolutionStrategy/HeuristicLab.Algorithms.MOCMAEvolutionStrategy/3.3/Individual.cs

    r15045 r15089  
    6363    public bool Selected { get; set; }
    6464    [Storable]
    65     public double Rank { get; set; }
    66     [Storable]
    6765    public double SuccessProbability { get; set; }
    6866    #endregion
     
    112110      PenalizedFitness = other.PenalizedFitness != null ? other.PenalizedFitness.Select(x => x).ToArray() : null;
    113111      Selected = other.Selected;
    114       Rank = other.Rank;
    115112      SuccessProbability = other.SuccessProbability;
    116113    }
  • branches/MOCMAEvolutionStrategy/HeuristicLab.Algorithms.MOCMAEvolutionStrategy/3.3/MOCMAEvolutionStrategy.cs

    r15045 r15089  
    7777    [Storable]
    7878    private double successThreshold; //ptresh
     79
    7980    #endregion
    8081
     
    309310      random = cloner.Clone(original.random);
    310311      gauss = cloner.Clone(original.gauss);
    311       solutions = original.solutions.Select(cloner.Clone).ToArray();
     312      solutions = original.solutions != null ? original.solutions.Select(cloner.Clone).ToArray() : null;
    312313      stepSizeLearningRate = original.stepSizeLearningRate;
    313314      stepSizeDampeningFactor = original.stepSizeDampeningFactor;
     
    417418        }
    418419      }
     420
     421
    419422    }
    420423    private void Iterate() {
     
    478481    private void SelectParents(IReadOnlyList<Individual> parents, int length) {
    479482      //perform a nondominated sort to assign the rank to every element
    480       var fronts = NonDominatedSort(parents);
     483      int[] ranks;
     484      var fronts = DominationCalculator<Individual>.CalculateAllParetoFronts(parents.ToArray(), parents.Select(i => i.PenalizedFitness).ToArray(), Problem.Maximization, out ranks);
     485      // NonDominatedSort(parents, individual => individual.PenalizedFitness);
    481486
    482487      //deselect the highest rank fronts until we would end up with less or equal mu elements
     
    485490      while (popSize - fronts[rank].Count >= length) {
    486491        var front = fronts[rank];
    487         foreach (var i in front) i.Selected = false;
     492        foreach (var i in front) i.Item1.Selected = false;
    488493        popSize -= front.Count;
    489494        rank--;
     
    491496
    492497      //now use the indicator to deselect the approximatingly worst elements of the last selected front
    493       var front1 = fronts[rank].OrderBy(x => x.PenalizedFitness[0]).ToList();
     498      var front1 = fronts[rank].OrderBy(x => x.Item1.PenalizedFitness[0]).ToList();
    494499      for (; popSize > length; popSize--) {
    495         var lc = Indicator.LeastContributer(front1, Problem);
    496         front1[lc].Selected = false;
     500        var lc = Indicator.LeastContributer(front1.Select(i => i.Item1).ToArray(), Problem);
     501        front1[lc].Item1.Selected = false;
    497502        front1.Swap(lc, front1.Count - 1);
    498503        front1.RemoveAt(front1.Count - 1);
     
    546551    }
    547552
    548     #region FastNonDominatedSort
    549     //blatantly stolen form HeuristicLab.Optimization.Operators.FastNonDominatedSort
    550     //however: Operators.FastNonDominatedSort does not return ranked fronts => rerank after sorting would not be sensible
    551 
    552     private enum DominationResult { Dominates, IsDominated, IsNonDominated };
    553     private List<List<Individual>> NonDominatedSort(IReadOnlyList<Individual> individuals) {
    554       const bool dominateOnEqualQualities = false;
    555       var maximization = Problem.Maximization;
    556       if (individuals == null) throw new InvalidOperationException(Name + ": No qualities found.");
    557       var populationSize = individuals.Count;
    558 
    559       var fronts = new List<List<Individual>>();
    560       var dominatedScopes = new Dictionary<Individual, List<int>>();
    561       var dominationCounter = new int[populationSize];
    562 
    563       for (var pI = 0; pI < populationSize - 1; pI++) {
    564         var p = individuals[pI];
    565         List<int> dominatedScopesByp;
    566         if (!dominatedScopes.TryGetValue(p, out dominatedScopesByp))
    567           dominatedScopes[p] = dominatedScopesByp = new List<int>();
    568         for (var qI = pI + 1; qI < populationSize; qI++) {
    569           var test = Dominates(individuals[pI], individuals[qI], maximization, dominateOnEqualQualities);
    570           if (test == DominationResult.Dominates) {
    571             dominatedScopesByp.Add(qI);
    572             dominationCounter[qI] += 1;
    573           } else if (test == DominationResult.IsDominated) {
    574             dominationCounter[pI] += 1;
    575             if (!dominatedScopes.ContainsKey(individuals[qI]))
    576               dominatedScopes.Add(individuals[qI], new List<int>());
    577             dominatedScopes[individuals[qI]].Add(pI);
    578           }
    579           if (pI == populationSize - 2
    580             && qI == populationSize - 1
    581             && dominationCounter[qI] == 0) {
    582             AddToFront(individuals[qI], fronts, 0);
    583           }
    584         }
    585         if (dominationCounter[pI] == 0) {
    586           AddToFront(p, fronts, 0);
    587         }
    588       }
    589       var i = 0;
    590       while (i < fronts.Count && fronts[i].Count > 0) {
    591         var nextFront = new List<Individual>();
    592         foreach (var p in fronts[i]) {
    593           List<int> dominatedScopesByp;
    594           if (!dominatedScopes.TryGetValue(p, out dominatedScopesByp)) continue;
    595           foreach (var dominatedScope in dominatedScopesByp) {
    596             dominationCounter[dominatedScope] -= 1;
    597             if (dominationCounter[dominatedScope] != 0) continue;
    598             nextFront.Add(individuals[dominatedScope]);
    599           }
    600         }
    601         i += 1;
    602         fronts.Add(nextFront);
    603       }
    604 
    605       for (i = 0; i < fronts.Count; i++) {
    606         foreach (var p in fronts[i]) {
    607           p.Rank = i;
    608         }
    609       }
    610       return fronts;
    611     }
    612     private static void AddToFront(Individual p, IList<List<Individual>> fronts, int i) {
    613       if (i == fronts.Count) fronts.Add(new List<Individual>());
    614       fronts[i].Add(p);
    615     }
    616     private static DominationResult Dominates(Individual left, Individual right, bool[] maximizations, bool dominateOnEqualQualities) {
    617       return Dominates(left.PenalizedFitness, right.PenalizedFitness, maximizations, dominateOnEqualQualities);
    618     }
    619     private static DominationResult Dominates(IReadOnlyList<double> left, IReadOnlyList<double> right, IReadOnlyList<bool> maximizations, bool dominateOnEqualQualities) {
    620       //mkommend Caution: do not use LINQ.SequenceEqual for comparing the two quality arrays (left and right) due to performance reasons
    621       if (dominateOnEqualQualities) {
    622         var equal = true;
    623         for (var i = 0; i < left.Count; i++) {
    624           if (left[i] != right[i]) {
    625             equal = false;
    626             break;
    627           }
    628         }
    629         if (equal) return DominationResult.Dominates;
    630       }
    631 
    632       bool leftIsBetter = false, rightIsBetter = false;
    633       for (var i = 0; i < left.Count; i++) {
    634         if (IsDominated(left[i], right[i], maximizations[i])) rightIsBetter = true;
    635         else if (IsDominated(right[i], left[i], maximizations[i])) leftIsBetter = true;
    636         if (leftIsBetter && rightIsBetter) break;
    637       }
    638 
    639       if (leftIsBetter && !rightIsBetter) return DominationResult.Dominates;
    640       if (!leftIsBetter && rightIsBetter) return DominationResult.IsDominated;
    641       return DominationResult.IsNonDominated;
    642     }
    643     private static bool IsDominated(double left, double right, bool maximization) {
    644       return maximization && left < right
    645         || !maximization && left > right;
    646     }
    647     #endregion
    648553  }
    649554}
Note: See TracChangeset for help on using the changeset viewer.