Ignore:
Timestamp:
04/16/18 08:35:59 (4 years ago)
Author:
bburlacu
Message:

#1772: Refactoring and speed optimization of diversification operators

File:
1 edited

Legend:

Unmodified
Added
Removed

  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SchemaDiversification/SchemaCreator.cs

    r15482 r15906  
    3939  public class SchemaCreator : EvolutionTrackingOperator<ISymbolicExpressionTree> {
    4040    #region parameter names
     41    // criteria to trigger schema-based diversification
    4142    private const string MinimumSchemaLengthParameterName = "MinimumSchemaLength";
    4243    private const string MinimumSchemaFrequencyParameterName = "MinimumSchemaFrequency";
    4344    private const string MinimumPhenotypicSimilarityParameterName = "MinimumPhenotypicSimilarity";
    44     private const string ReplacementRatioParameterName = "ReplacementRatio";
    45     private const string RandomReplacementParameterName = "RandomReplacement";
     45    // parameters controlling the diversification strategy
     46    private const string UseAdaptiveMutationRateParameterName = "UseAdaptiveMutationRate"; // dynamically control mutation rate
     47    private const string MutationRateUpdateRuleParameterName = "ReplacementRatioUpdateRule";
     48    private const string MutationRateParameterName = "MutationRate"; // fixed mutation rate when not using adaptive update
     49    private const string ExclusiveMatchingParameterName = "ExclusiveMatching"; // an individual can belong to only 1 schema
     50    private const string ParentsRatio = "ParentsRatio"; // use best % parents to generate schemas from
     51    private const string StrictSchemaMatchingParameterName = "StrictSchemaMatching"; // use strict node comparison (for constant values and variable weights)
     52    private const string SchemaDefinitionParameterName = "SchemaDefinition"; // which schema definition to use: {=}, {#} or {=,#}
     53    private const string SchemaManipulatorParameterName = "SchemaManipulator"; // mutation operator to apply within schemas
     54
     55    // control parallel behaviour
    4656    private const string ExecuteInParallelParameterName = "ExecuteInParallel";
    4757    private const string MaxDegreeOfParalellismParameterName = "MaxDegreeOfParallelism";
    48     private const string PercentageOfPopulationParameterName = "PercentageOfPopulationToDiversify";
    4958    private const string ScaleEstimatedValuesParameterName = "ScaleEstimatedValues";
    50     private const string ExclusiveMatchingParameterName = "ExclusiveMatching";
     59
     60    private const string UpdateCounterParameterName = "UpdateCounter";
     61    private const string UpdateIntervalParameterName = "UpdateInterval";
     62
     63    #region information parameters
    5164    private const string NumberOfChangedTreesParameterName = "NumberOfChangedTrees";
    5265    private const string NumberOfSchemasParameterName = "NumberOfSchemas";
    5366    private const string AverageSchemaLengthParameterName = "AverageSchemaLength";
    54     private const string UseAdaptiveReplacementRatioParameterName = "UseAdaptiveReplacementRatio";
    55     private const string ReplacementRatioUpdateRuleParameterName = "ReplacementRatioUpdateRule";
    56     private const string StrictSchemaMatchingParameterName = "StrictSchemaMatching";
    57     private const string SchemaDefinitionParameterName = "SchemaDefinition";
    58     private const string SchemaManipulatorParameterName = "SchemaManipulator";
     67    #endregion
    5968    #endregion
    6069
    … …  
    6675      get { return (IConstrainedValueParameter<StringValue>)Parameters[SchemaDefinitionParameterName]; }
    6776    }
    68     public IConstrainedValueParameter<StringValue> ReplacementRatioUpdateRuleParameter {
    69       get { return (IConstrainedValueParameter<StringValue>)Parameters[ReplacementRatioUpdateRuleParameterName]; }
    70     }
    71     public IFixedValueParameter<BoolValue> UseAdaptiveReplacementRatioParameter {
    72       get { return (IFixedValueParameter<BoolValue>)Parameters[UseAdaptiveReplacementRatioParameterName]; }
     77    public IConstrainedValueParameter<StringValue> MutationRateUpdateRuleParameter {
     78      get { return (IConstrainedValueParameter<StringValue>)Parameters[MutationRateUpdateRuleParameterName]; }
     79    }
     80    public IFixedValueParameter<BoolValue> UseAdaptiveMutationRateParameter {
     81      get { return (IFixedValueParameter<BoolValue>)Parameters[UseAdaptiveMutationRateParameterName]; }
    7382    }
    7483    public IFixedValueParameter<BoolValue> StrictSchemaMatchingParameter {
    … …  
    8190      get { return (IFixedValueParameter<BoolValue>)Parameters[ScaleEstimatedValuesParameterName]; }
    8291    }
    83     public IFixedValueParameter<PercentValue> PercentageOfPopulationParameter {
    84       get { return (IFixedValueParameter<PercentValue>)Parameters[PercentageOfPopulationParameterName]; }
     92    public IFixedValueParameter<PercentValue> ParentsRatioParameter {
     93      get { return (IFixedValueParameter<PercentValue>)Parameters[ParentsRatio]; }
    8594    }
    8695    public IFixedValueParameter<IntValue> MinimumSchemaLengthParameter {
    … …  
    99108      get { return (IFixedValueParameter<PercentValue>)Parameters[MinimumPhenotypicSimilarityParameterName]; }
    100109    }
    101     public IFixedValueParameter<PercentValue> ReplacementRatioParameter {
    102       get { return (IFixedValueParameter<PercentValue>)Parameters[ReplacementRatioParameterName]; }
     110    public IFixedValueParameter<PercentValue> MutationRateParameter {
     111      get { return (IFixedValueParameter<PercentValue>)Parameters[MutationRateParameterName]; }
    103112    }
    104113    public IValueParameter<IntValue> NumberOfSchemasParameter {
    … …  
    110119    public IValueParameter<IntValue> NumberOfChangedTreesParameter {
    111120      get { return (IValueParameter<IntValue>)Parameters[NumberOfChangedTreesParameterName]; }
     121    }
     122    public IFixedValueParameter<IntValue> UpdateCounterParameter {
     123      get { return (IFixedValueParameter<IntValue>)Parameters[UpdateCounterParameterName]; }
     124    }
     125    public IFixedValueParameter<IntValue> UpdateIntervalParameter {
     126      get { return (IFixedValueParameter<IntValue>)Parameters[UpdateIntervalParameterName]; }
    112127    }
    113128    #endregion
    … …  
    117132    public int MaxDegreeOfParallelism { get { return MaxDegreeOfParallelismParameter.Value.Value; } }
    118133    public bool ExecuteInParallel { get { return ExecuteInParallelParameter.Value.Value; } }
    119     public double PercentageOfPopulation { get { return PercentageOfPopulationParameter.Value.Value; } }
     134    public double PercentageOfPopulation { get { return ParentsRatioParameter.Value.Value; } }
    120135    public bool StrictSchemaMatching { get { return StrictSchemaMatchingParameter.Value.Value; } }
     136    public IntValue UpdateCounter { get { return UpdateCounterParameter.Value; } }
     137    public IntValue UpdateInterval { get { return UpdateIntervalParameter.Value; } }
     138
    121139    #endregion
    122140
    123141    private UpdateQualityOperator updateQualityOperator;
    124142    private DiversificationStatisticsOperator diversificationStatisticsOperator;
     143
     144    public override void InitializeState() {
     145      base.InitializeState();
     146      NumberOfChangedTreesParameter.Value.Value = 0;
     147      NumberOfChangedTreesParameter.Value.Value = 0;
     148      AverageSchemaLengthParameter.Value.Value = 0;
     149      UpdateCounter.Value = 0;
     150    }
    125151
    126152    public override void ClearState() {
    … …  
    128154      NumberOfChangedTreesParameter.Value.Value = 0;
    129155      AverageSchemaLengthParameter.Value.Value = 0;
     156      UpdateCounter.Value = 0;
    130157      base.ClearState();
    131158    }
    … …  
    136163      Parameters.Add(new FixedValueParameter<PercentValue>(MinimumSchemaFrequencyParameterName, new PercentValue(0.01)));
    137164      Parameters.Add(new FixedValueParameter<PercentValue>(MinimumPhenotypicSimilarityParameterName, new PercentValue(0.9)));
    138       Parameters.Add(new FixedValueParameter<PercentValue>(ReplacementRatioParameterName, new PercentValue(0.9)));
    139       Parameters.Add(new FixedValueParameter<PercentValue>(PercentageOfPopulationParameterName, new PercentValue(1)));
    140       Parameters.Add(new FixedValueParameter<BoolValue>(RandomReplacementParameterName, new BoolValue(false)));
     165      Parameters.Add(new FixedValueParameter<PercentValue>(MutationRateParameterName, new PercentValue(0.9)));
     166      Parameters.Add(new FixedValueParameter<PercentValue>(ParentsRatio, new PercentValue(1)));
    141167      Parameters.Add(new FixedValueParameter<BoolValue>(ExecuteInParallelParameterName, new BoolValue(false)));
    142168      Parameters.Add(new FixedValueParameter<IntValue>(MaxDegreeOfParalellismParameterName, new IntValue(-1)));
    … …  
    147173      Parameters.Add(new ValueParameter<IntValue>(NumberOfSchemasParameterName, new IntValue(0)));
    148174      Parameters.Add(new ValueParameter<DoubleValue>(AverageSchemaLengthParameterName, new DoubleValue(0)));
    149       Parameters.Add(new FixedValueParameter<BoolValue>(UseAdaptiveReplacementRatioParameterName, new BoolValue(true)));
     175      Parameters.Add(new FixedValueParameter<BoolValue>(UseAdaptiveMutationRateParameterName, new BoolValue(true)));
     176      Parameters.Add(new FixedValueParameter<IntValue>(UpdateCounterParameterName, new IntValue(0)));
     177      Parameters.Add(new FixedValueParameter<IntValue>(UpdateIntervalParameterName, new IntValue(1)));
    150178
    151179      // add update rules
    152       var replacementRatioUpdateRules = new ItemSet<StringValue>(new[] {
     180      var mutationRateUpdateRules = new ItemSet<StringValue>(new[] {
    153181        new StringValue("f(x) = x"),
    154182        new StringValue("f(x) = tanh(x)"),
    … …  
    158186        new StringValue("f(x) = 1-sqrt(1-x)")
    159187      });
    160       var replacementRatioUpdateRuleParameter = new ConstrainedValueParameter<StringValue>(ReplacementRatioUpdateRuleParameterName, replacementRatioUpdateRules);
    161       replacementRatioUpdateRuleParameter.Value = replacementRatioUpdateRules.First();
    162       Parameters.Add(replacementRatioUpdateRuleParameter);
     188      var mutationRateUpdateRuleParameter = new ConstrainedValueParameter<StringValue>(MutationRateUpdateRuleParameterName, mutationRateUpdateRules);
     189      mutationRateUpdateRuleParameter.Value = mutationRateUpdateRules.First();
     190      Parameters.Add(mutationRateUpdateRuleParameter);
    163191
    164192      // add schema definitions
    … …  
    208236
    209237    public override IOperation Apply() {
     238      UpdateCounter.Value++;
     239      if (UpdateCounter.Value != UpdateInterval.Value)
     240        return base.Apply();
     241      UpdateCounter.Value = 0;
     242
    210243      // apply only when at least one generation has passed
    211244      var gen = Generations.Value;
    … …  
    213246        return base.Apply();
    214247
    215       var n = (int)Math.Round(ExecutionContext.Scope.SubScopes.Count * PercentageOfPopulation);
    216248
    217249      var updateEstimatedValues = new OperationCollection { Parallel = true };
    … …  
    219251        updateQualityOperator = new UpdateQualityOperator();
    220252
    221       foreach (var s in ExecutionContext.Scope.SubScopes.Where(s => !s.Variables.ContainsKey("EstimatedValues"))) {
     253      var scope = ExecutionContext.Scope;
     254
     255      foreach (var s in scope.SubScopes.Where(s => !s.Variables.ContainsKey("EstimatedValues"))) {
    222256        updateEstimatedValues.Add(ExecutionContext.CreateChildOperation(updateQualityOperator, s));
    223257      }
    224258
    225       var replacementRule = ReplacementRatioUpdateRuleParameter.Value.Value;
     259      var updateRule = MutationRateUpdateRuleParameter.Value.Value;
    226260      var schemaManipulator = SchemaManipulatorParameter.Value;
    227261
    228262      var evaluateSchemas = new OperationCollection();
    229263
     264      Func<IScope, double> getQuality = s => ((DoubleValue)s.Variables["Quality"].Value).Value;
     265
     266      var bestN = (int)Math.Round(scope.SubScopes.Count * PercentageOfPopulation);
     267      var scopes = new ScopeList(scope.SubScopes.OrderByDescending(getQuality).Take(bestN));
    230268      // for now, only consider crossover offspring
    231       var scopes = new ScopeList(ExecutionContext.Scope.SubScopes.OrderByDescending(x => ((DoubleValue)x.Variables["Quality"].Value).Value).Take(n));
    232269      var vertices = from s in scopes
    233270                     let t = (ISymbolicExpressionTree)s.Variables["SymbolicExpressionTree"].Value
    … …  
    236273                     select v;
    237274
    238       List<ISymbolicExpressionTree> schemas;
     275      IEnumerable<ISymbolicExpressionTree> schemas;
    239276      switch (SchemaDefinitionParameter.Value.Value) {
    240277        case "=":
    241           schemas = GenerateAnyNodeSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching).ToList();
     278          schemas = GenerateAnyNodeSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching);
    242279          break;
    243280        case "#":
    244           schemas = GenerateAnySubtreeSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching).ToList();
     281          schemas = GenerateAnySubtreeSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching);
    245282          break;
    246283        case "=,#":
    247           schemas = GenerateCombinedSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching).ToList();
     284          schemas = GenerateCombinedSchemas(vertices, MinimumSchemaLength, 0, StrictSchemaMatching);
    248285          break;
    249286        default:
    … …  
    255292
    256293      #region create schemas and add subscopes representing the individuals
     294      double avgLength = 0;
     295      int count = 0;
    257296      foreach (var schema in schemas) {
    258         evaluateSchemas.Add(ExecutionContext.CreateChildOperation(new SchemaEvaluator { Schema = schema, ReplacementRule = replacementRule, SchemaManipulator = schemaManipulator }, ExecutionContext.Scope));
     297        avgLength += schema.Length;
     298        ++count;
     299        evaluateSchemas.Add(ExecutionContext.CreateChildOperation(new SchemaEvaluator { Schema = schema, MutationRateUpdateRule = updateRule, SchemaManipulator = schemaManipulator }, scope));
    259300      }
     301      avgLength /= count;
    260302      #endregion
     303
     304      // set parameters for statistics
     305      AverageSchemaLengthParameter.Value = new DoubleValue(avgLength);
     306      NumberOfSchemasParameter.Value = new IntValue(count);
     307      NumberOfChangedTreesParameter.Value = new IntValue(0);
    261308
    262309      if (diversificationStatisticsOperator == null)
    … …  
    264311
    265312      var calculateStatistics = ExecutionContext.CreateChildOperation(diversificationStatisticsOperator);
    266 
    267       // set parameters for statistics
    268       AverageSchemaLengthParameter.Value = new DoubleValue(schemas.Average(x => x.Length));
    269       NumberOfSchemasParameter.Value = new IntValue(schemas.Count);
    270       NumberOfChangedTreesParameter.Value = new IntValue(0);
    271313
    272314      // return an operation collection containing all the scope operations + base.Apply()
Note: See TracChangeset for help on using the changeset viewer.