Free cookie consent management tool by TermsFeed Policy Generator

Changeset 15718


Ignore:
Timestamp:
02/04/18 21:06:14 (6 years ago)
Author:
abeham
Message:

#1614:

  • Scale directed walk fitness values
  • Performance improvements to RLD view
  • Changed CPLEX to use a single thread only
  • Set the context to null when algorithm is stopped
Location:
branches/1614_GeneralizedQAP
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • branches/1614_GeneralizedQAP/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/DoubleMatrixCharacteristicCalculator.cs

    r14678 r15718  
    2020#endregion
    2121
     22using System;
     23using System.Linq;
    2224using HeuristicLab.Common;
    2325using HeuristicLab.Data;
    24 using System;
    25 using System.Linq;
    2626
    2727namespace HeuristicLab.Analysis.FitnessLandscape {
     
    3030      var avg = m.Average();
    3131      var stdDev = m.StandardDeviation();
     32      return stdDev / avg;
     33    }
     34
     35    public static double CoeffVariationNonZeroes(DoubleMatrix m) {
     36      var nonzeroes = m.Where(x => !x.IsAlmost(0));
     37      var avg = nonzeroes.Average();
     38      var stdDev = nonzeroes.StandardDeviation();
    3239      return stdDev / avg;
    3340    }
  • branches/1614_GeneralizedQAP/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/GQAP/GQAPCharacteristicCalculator.cs

    r15713 r15718  
    6666          yield return new Result(chara, new DoubleValue(inst.Capacities.Length / (double)inst.Demands.Length));
    6767        if (chara == "FlowDominance")
    68           yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.CoeffVariation(inst.Weights)));
     68          yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.CoeffVariationNonZeroes(inst.Weights)));
    6969        if (chara == "DistanceDominance")
    70           yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.CoeffVariation(inst.Distances)));
     70          yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.CoeffVariationNonZeroes(inst.Distances)));
    7171        if (chara == "FlowSparsity")
    7272          yield return new Result(chara, new DoubleValue(DoubleMatrixCharacteristicCalculator.Sparsity(inst.Weights)));
  • branches/1614_GeneralizedQAP/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/GQAP/GQAPDirectedWalk.cs

    r15713 r15718  
    134134    public static IEnumerable<List<Tuple<IntegerVector, double>>> Run(IRandom random, GQAP gqap, IEnumerable<IntegerVector> points, bool bestImprovement = true) {
    135135      var iter = points.GetEnumerator();
    136       if (!iter.MoveNext()) yield break;
     136      if (!iter.MoveNext()) return new List<Tuple<IntegerVector, double>>[0];
    137137
    138138      var start = iter.Current;
     139      var walks = new List<List<Tuple<IntegerVector, double>>>();
    139140      while (iter.MoveNext()) {
    140141        var end = iter.Current;
    141142
    142143        var walk = (bestImprovement ? BestDirectedWalk(gqap, start, end) : FirstDirectedWalk(random, gqap, start, end)).ToList();
    143         yield return walk.ToList();
     144        walks.Add(walk);
    144145        start = end;
    145146      } // end paths
     147
     148      var min = walks.SelectMany(x => x.Select(y => y.Item2)).Min();
     149      var max = walks.SelectMany(x => x.Select(y => y.Item2)).Max();
     150
     151      if (min == max) max = min + 1;
     152      return walks.Select(w => w.Select(x => Tuple.Create(x.Item1, (x.Item2 - min) / (max - min))).ToList());
    146153    }
    147154
  • branches/1614_GeneralizedQAP/HeuristicLab.Optimization.Views/3.3/RunCollectionViews/RunCollectionRLDView.cs

    r15713 r15718  
    3131using HeuristicLab.Analysis;
    3232using HeuristicLab.Collections;
     33using HeuristicLab.Common;
    3334using HeuristicLab.Core;
    3435using HeuristicLab.Core.Views;
     
    146147        return;
    147148      }
     149      if (updateInProgress) return;
    148150      try {
    149151        updateInProgress = true;
    150         UpdateGroupAndProblemComboBox();
    151         UpdateDataTableComboBox();
     152        UpdateComboBoxes();
    152153        GroupRuns();
    153154      } finally { updateInProgress = false; }
     
    160161        return;
    161162      }
     163      if (updateInProgress) return;
    162164      try {
    163165        updateInProgress = true;
    164         UpdateGroupAndProblemComboBox();
    165         UpdateDataTableComboBox();
     166        UpdateComboBoxes();
    166167        GroupRuns();
    167168      } finally { updateInProgress = false; }
     
    175176        return;
    176177      }
     178      if (updateInProgress) return;
    177179      try {
    178180        updateInProgress = true;
    179         UpdateGroupAndProblemComboBox();
    180         UpdateDataTableComboBox();
     181        UpdateComboBoxes();
    181182        GroupRuns();
    182183      } finally { updateInProgress = false; }
     
    194195      suppressContentEvents = Content.UpdateOfRunsInProgress;
    195196      if (!suppressContentEvents) {
     197        if (updateInProgress) return;
    196198        try {
    197199          updateInProgress = true;
    198           UpdateGroupAndProblemComboBox();
    199           UpdateDataTableComboBox();
     200          UpdateComboBoxes();
    200201          GroupRuns();
    201202        } finally { updateInProgress = false; }
     
    215216      } else {
    216217        if (e.PropertyName == "Visible") {
     218          if (updateInProgress) return;
    217219          try {
    218220            updateInProgress = true;
     
    238240        try {
    239241          updateInProgress = true;
    240           UpdateGroupAndProblemComboBox();
    241           UpdateDataTableComboBox();
     242          UpdateComboBoxes();
    242243          UpdateRuns();
    243244        } finally { updateInProgress = false; }
     
    246247
    247248
    248     private void UpdateGroupAndProblemComboBox() {
     249    private void UpdateComboBoxes() {
    249250      var selectedGroupItem = (string)groupComboBox.SelectedItem;
    250251
     
    259260      }
    260261
     262      string selectedDataTable = (string)dataTableComboBox.SelectedItem;
     263
     264      dataTableComboBox.Items.Clear();
     265      var dataTables = (from run in Content
     266                        from result in run.Results
     267                        where result.Value is IndexedDataTable<double>
     268                        select result.Key).Distinct().ToArray();
     269
     270      dataTableComboBox.Items.AddRange(dataTables);
     271      if (selectedDataTable != null && dataTableComboBox.Items.Contains(selectedDataTable)) {
     272        dataTableComboBox.SelectedItem = selectedDataTable;
     273      } else if (dataTableComboBox.Items.Count > 0) {
     274        dataTableComboBox.SelectedItem = dataTableComboBox.Items[0];
     275      }
     276
    261277      var selectedProblemItem = (ProblemInstance)problemComboBox.SelectedItem;
    262278     
     
    271287
    272288      SetEnabledStateOfControls();
    273     }
    274 
    275     private void UpdateDataTableComboBox() {
    276       string selectedItem = (string)dataTableComboBox.SelectedItem;
    277 
    278       dataTableComboBox.Items.Clear();
    279       var dataTables = (from run in Content
    280                         from result in run.Results
    281                         where result.Value is IndexedDataTable<double>
    282                         select result.Key).Distinct().ToArray();
    283 
    284       dataTableComboBox.Items.AddRange(dataTables);
    285       if (selectedItem != null && dataTableComboBox.Items.Contains(selectedItem)) {
    286         dataTableComboBox.SelectedItem = selectedItem;
    287       } else if (dataTableComboBox.Items.Count > 0) {
    288         dataTableComboBox.SelectedItem = dataTableComboBox.Items[0];
    289       }
    290 
    291       UpdateProblemInstances();
    292289    }
    293290
     
    318315                            && r.Visible
    319316                            && selectedProblem.Match(r)
    320                             && r.Results.ContainsKey(table)
    321                             && r.Results[table] is IndexedDataTable<double>
    322                           let key = selectedGroup == AllInstances ? AllInstances : r.Parameters[selectedGroup].ToString()
     317                          let key = selectedGroup == AllInstances
     318                            ? AllInstances : r.Parameters[selectedGroup].ToString()
    323319                          group r by key into g
    324320                          select g) {
    325         var trials = from run in alg
    326                      from pd in problems
    327                      where pd.Equals(new ProblemInstance(run))
    328                      let cgraph = ((IndexedDataTable<double>)run.Results[table])
    329                      where cgraph.Rows.Count > 0 && cgraph.Rows.First().Values.Count > 0
     321        var trials = (from run in alg
     322                     from pd in problems.Skip(1) // exclude artificial match all
     323                     where pd.Match(run) && run.Results.ContainsKey(table)
     324                     let cgraph = run.Results[table] as IndexedDataTable<double>
     325                     where cgraph != null && cgraph.Rows.Count > 0
     326                        && cgraph.Rows.First().Values.Count > 0
    330327                     group cgraph by pd into g
    331                      select g;
    332 
     328                     select g).ToList();
     329
     330        if (trials.Count == 0) continue;
    333331        groups.Add(new AlgorithmInstance(alg.Key, trials));
    334332      }
     
    339337        problems.Clear();
    340338        var table = (string)dataTableComboBox.SelectedItem;
    341         if (string.IsNullOrEmpty(table)) return;
    342 
     339       
    343340        var problemDict = CalculateBestTargetPerProblemInstance(table);
    344341
     
    350347
    351348        problems.Add(ProblemInstance.MatchAll);
    352         foreach (var p in problemDict.ToList()) {
     349        foreach (var p in problemDict.OrderBy(x => x.Key.ProblemName, new NaturalStringComparer()).ToList()) {
    353350          p.Key.BestKnownQuality = p.Value;
    354351          p.Key.DisplayProblemType = problemTypesDifferent;
     
    394391          misses[alg.Name] = epdfMisses = new SortedList<double, int>();
    395392        }
    396         foreach (var problem in alg.GetCases()) {
    397           var max = problem.IsMaximization();
     393        foreach (var problem in alg.GetCases().Where(x => x.Maximization.HasValue)) {
     394          var max = problem.Maximization.Value;
    398395          var absTargets = GetAbsoluteTargets(problem).ToArray();
    399396          foreach (var run in alg.GetTrials(problem)) {
     
    450447      foreach (var list in hits) {
    451448        var row = new Series(list.Key) {
    452           ChartType = SeriesChartType.StepLine,
     449          ChartType = list.Value.Count > 1000 ? SeriesChartType.FastLine : SeriesChartType.StepLine,
    453450          BorderWidth = 3,
    454451          Color = colors[colorCount],
     
    603600    private IEnumerable<double> GetAbsoluteTargets(ProblemInstance pInstance) {
    604601      if (!targetsAreRelative) return targets;
    605 
    606       var maximization = pInstance.IsMaximization();
     602      if (!pInstance.Maximization.HasValue) throw new ArgumentException("Problem doesn't specify if it is to be maximized or minimized.");
     603
     604      var maximization = pInstance.Maximization.Value;
    607605      var bestKnown = pInstance.BestKnownQuality;
    608606      if (double.IsNaN(bestKnown)) throw new ArgumentException("Problem instance does not have a defined best - known quality.");
     
    621619    private double[] GetAbsoluteTargetsWorstToBest(ProblemInstance pInstance) {
    622620      if (targetsAreRelative && double.IsNaN(pInstance.BestKnownQuality)) throw new ArgumentException("Problem instance does not have a defined best-known quality.");
     621      if (!pInstance.Maximization.HasValue) throw new ArgumentException("Problem doesn't specify if it is to be maximized or minimized.");
    623622      var absTargets = GetAbsoluteTargets(pInstance);
    624       return (pInstance.IsMaximization()
     623      return (pInstance.Maximization.Value
    625624        ? absTargets.OrderBy(x => x) : absTargets.OrderByDescending(x => x)).ToArray();
    626625    }
     
    663662      var problems = groups.SelectMany(x => x.GetCases()).Distinct().ToList();
    664663
    665       foreach (var problem in problems) {
    666         if (double.IsNaN(problem.BestKnownQuality)) continue;
     664      foreach (var problem in problems.OrderBy(x => x.ProblemName, new NaturalStringComparer())) {
     665        if (double.IsNaN(problem.BestKnownQuality) || !problem.Maximization.HasValue) continue;
    667666        rowNames.Add(problem.ToString());
    668         var max = problem.IsMaximization();
     667        var max = problem.Maximization.Value;
    669668        var absTargets = GetAbsoluteTargetsWorstToBest(problem);
    670669        if (targetsAreRelative) {
     
    776775
    777776    private void CalculateHitsForEachBudget(Dictionary<string, SortedList<double, double>> hits, ConvergenceGraph cgraph, ProblemInstance problem, string groupName) {
    778       var max = problem.IsMaximization();
     777      var max = problem.Maximization.Value;
    779778      var prevIndex = 0;
    780779      foreach (var b in budgets) {
     
    897896        updateInProgress = true;
    898897        var pd = (ProblemInstance)problemComboBox.SelectedItem;
    899         if (!double.IsNaN(pd.BestKnownQuality)) {
    900           var max = pd.IsMaximization();
     898        if (!double.IsNaN(pd.BestKnownQuality) && pd.Maximization.HasValue) {
     899          var max = pd.Maximization.Value;
    901900          if (targetsAreRelative) targets = GetAbsoluteTargets(pd).ToArray();
    902901          else {
     
    957956        var values = resultsTable.Rows.First().Values;
    958957        var pd = new ProblemInstance(run);
     958        if (!pd.Maximization.HasValue) continue;
    959959        pd = problems.Single(x => x.Equals(pd));
    960960        if (targetsAreRelative && double.IsNaN(pd.BestKnownQuality)) continue;
    961961
    962         var max = pd.IsMaximization();
     962        var max = pd.Maximization.Value;
    963963        var absTargets = GetAbsoluteTargetsWorstToBest(pd);
    964964        var cgraph = new ConvergenceGraph(resultsTable, max);
     
    10711071        var values = resultsTable.Rows.First().Values;
    10721072        var pd = new ProblemInstance(run);
     1073        if (!pd.Maximization.HasValue) continue;
    10731074        pd = problems.Single(x => x.Equals(pd));
    1074         var max = pd.IsMaximization();
     1075        var max = pd.Maximization.Value;
    10751076        var cgraph = new ConvergenceGraph(resultsTable, max);
    10761077        var prevIndex = 0;
     
    10821083          }
    10831084          var v = values[index];
    1084           var tgt = targetsAreRelative ? CalculateRelativeDifference(pd.IsMaximization(), pd.BestKnownQuality, v.Item2) : v.Item2;
     1085          var tgt = targetsAreRelative ? CalculateRelativeDifference(max, pd.BestKnownQuality, v.Item2) : v.Item2;
    10851086          run.Results[table + (targetsAreRelative ? ".CostForRelTarget " : ".CostForAbsTarget ") + b] = new DoubleValue(tgt);
    10861087          prevIndex = index;
     
    11091110      var dict = new Dictionary<ProblemInstance, double>();
    11101111      foreach (var k in from r in Content where r.Visible let pd = new ProblemInstance(r) group r by pd into g select new { Problem = g.Key, Runs = g.ToList() }) {
    1111         var pd = new ProblemInstance(k.Runs[0]);
     1112        var pd = k.Problem;
     1113        if (!pd.Maximization.HasValue) continue;
    11121114        var values = GetQualityValues(k.Runs, table).ToList();
    11131115        var target = double.NaN;
    11141116        if (values.Count > 0) {
    1115           target = pd.IsMaximization() ? values.Max() : values.Min();
     1117          target = pd.Maximization.Value ? values.Max() : values.Min();
    11161118        }
    11171119        dict[pd] = target;
     
    11331135            var last = dt.Rows.First().Values.Last().Item2;
    11341136            if (!double.IsNaN(last))
    1135               yield return last;
     1137              yield return Math.Round(last, 10);
    11361138          }
    11371139        }
     
    12961298        performanceData = new Dictionary<ProblemInstance, List<ConvergenceGraph>>();
    12971299        foreach (var t in trials) {
    1298           if (double.IsNaN(t.Key.BestKnownQuality)) continue;
    1299           var max = t.Key.IsMaximization();
    1300           performanceData[t.Key] = t.Select(c => new ConvergenceGraph(c, max)).ToList();
     1300          if (double.IsNaN(t.Key.BestKnownQuality) || !t.Key.Maximization.HasValue) continue;
     1301          performanceData[t.Key] = t.Select(c => new ConvergenceGraph(c, t.Key.Maximization.Value)).ToList();
    13011302        }
    13021303      }
     
    13291330        ProblemName = string.Empty;
    13301331        Evaluator = string.Empty;
    1331         Maximization = string.Empty;
     1332        Maximization = null;
    13321333        DisplayProblemType = false;
    13331334        DisplayProblemName = false;
     
    13421343        ProblemName = GetStringValueOrEmpty(run, "Problem Name");
    13431344        Evaluator = GetStringValueOrEmpty(run, "Evaluator");
    1344         Maximization = GetMaximizationValueOrEmpty(run, "Maximization");
     1345        Maximization = GetBoolValueOrEmpty(run, "Maximization");
    13451346        DisplayProblemType = !string.IsNullOrEmpty(ProblemType);
    13461347        DisplayProblemName = !string.IsNullOrEmpty(ProblemName);
    13471348        DisplayEvaluator = !string.IsNullOrEmpty(Evaluator);
    1348         DisplayMaximization = !string.IsNullOrEmpty(Maximization);
     1349        DisplayMaximization = Maximization.HasValue;
    13491350        matchAll = false;
    13501351        BestKnownQuality = GetDoubleValueOrNaN(run, "BestKnownQuality");
     
    14141415        }
    14151416      }
    1416       private string maximization;
    1417       public string Maximization {
     1417      private bool? maximization;
     1418      public bool? Maximization {
    14181419        get { return maximization; }
    14191420        set {
     
    14331434      }
    14341435
    1435       public bool IsMaximization() {
    1436         return Maximization == "MAX";
    1437       }
    1438 
    14391436      public bool Match(IRun run) {
    14401437        return matchAll ||
    1441                GetStringValueOrEmpty(run, "Problem Type") == ProblemType
     1438               (GetStringValueOrEmpty(run, "Problem Type") == ProblemType
    14421439               && GetStringValueOrEmpty(run, "Problem Name") == ProblemName
    14431440               && GetStringValueOrEmpty(run, "Evaluator") == Evaluator
    1444                && GetMaximizationValueOrEmpty(run, "Maximization") == Maximization;
     1441               && GetBoolValueOrEmpty(run, "Maximization") == Maximization);
    14451442      }
    14461443
     
    14631460      }
    14641461
    1465       private string GetMaximizationValueOrEmpty(IRun run, string key) {
     1462      private bool? GetBoolValueOrEmpty(IRun run, string key) {
    14661463        IItem param;
    14671464        if (run.Parameters.TryGetValue(key, out param)) {
    14681465          var bv = param as BoolValue;
    1469           return bv != null ? (bv.Value ? "MAX" : "MIN") : string.Empty;
    1470         }
    1471         return string.Empty;
     1466          if (bv != null) return bv.Value;
     1467        }
     1468        return null;
    14721469      }
    14731470
     
    14901487          (DisplayProblemName ? ProblemName : string.Empty),
    14911488          (DisplayEvaluator ? Evaluator : string.Empty),
    1492           (DisplayMaximization ? Maximization : string.Empty),
     1489          (DisplayMaximization && Maximization.HasValue ? (Maximization.Value ? "MAX" : "MIN") : string.Empty),
    14931490          !double.IsNaN(BestKnownQuality) ? BestKnownQuality.ToString(CultureInfo.CurrentCulture.NumberFormat) : string.Empty }.Where(x => !string.IsNullOrEmpty(x)));
    14941491      }
  • branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/CPLEX/CplexSolver.cs

    r15713 r15718  
    6363      cplex.Use(new LogCallback(this, cancellationToken));
    6464      cplex.SetParam(Cplex.DoubleParam.TiLim, MaximumRuntime.TotalSeconds);
     65      cplex.SetParam(Cplex.IntParam.Threads, 1);
    6566      var dataSource = new GQAPDataSource(factory, Problem.ProblemInstance);
    6667      using (var settings = factory.CreateOplSettings(factory.CreateOplErrorHandler()))
  • branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/Infrastructure/Algorithms/ContextAlgorithm.cs

    r15704 r15718  
    205205          firstHitGraph.Values[firstHitGraph.Values.Count - 1] = Tuple.Create(elapsed.TotalSeconds, Context.BestQuality);
    206206      }
     207      context = null;
    207208      // base call must be done last as the results will be cloned and a run is created
    208209      base.OnStopped();
Note: See TracChangeset for help on using the changeset viewer.