Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
08/25/15 10:38:20 (9 years ago)
Author:
gkronber
Message:

#2421 new version of artificial ant problem that uses SymbolicExpressionTreeEncoding

Location:
trunk/sources/HeuristicLab.Problems.ArtificialAnt/3.5
Files:
1 edited
1 copied

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.Problems.ArtificialAnt/3.5/ArtificialAntProblem.cs

    r12504 r12895  
    2222using System;
    2323using System.Collections.Generic;
     24using System.Diagnostics.Contracts;
    2425using System.Linq;
    2526using HeuristicLab.Common;
    … …  
    3738  [Creatable(CreatableAttribute.Categories.GeneticProgrammingProblems, Priority = 170)]
    3839  [StorableClass]
    39   public sealed class ArtificialAntProblem : SingleObjectiveHeuristicOptimizationProblem<Evaluator, ISymbolicExpressionTreeCreator>, IStorableContent {
     40  public sealed class ArtificialAntProblem : SingleObjectiveBasicProblem<SymbolicExpressionTreeEncoding>, IStorableContent {
    4041    public string Filename { get; set; }
    4142
    4243    #region constant for default world (Santa Fe)
    43     private readonly bool[,] santaFeAntTrail = new bool[,] {
    44       {false, true, true, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
    45       {false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
    46       {false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, true, true, false, false, false, false},
    47       {false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, true, false, false},
    48       {false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, true, false, false},
    49       {false, false, false, true, true, true, true, false, true, true, true, true, true, false, false, false, false, false, false, false, false, true, true, false, false, false, false, false, false, false, false, false},
    50       {false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false},
    51       {false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false},
    52       {false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false},
    53       {false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, true, false, false},
    54       {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false},
    55       {false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
    56       {false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false},
    57       {false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false},
    58       {false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, true, true, true, false, false, false},
    59       {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false},
    60       {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
    61       {false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
    62       {false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false},
    63       {false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false},
    64       {false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
    65       {false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
    66       {false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false},
    67       {false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false},
    68       {false, false, false, true, true, false, false, true, true, true, true, true, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
    69       {false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
    70       {false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
    71       {false, true, false, false, false, false, false, false, true, true, true, true, true, true, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
    72       {false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
    73       {false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
    74       {false, false, true, true, true, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false },
    75       {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false }
     44
     45    private static readonly char[][] santaFeAntTrail = new[] {
     46      " ###                            ".ToCharArray(),
     47      "   #                            ".ToCharArray(),
     48      "   #                    .###..  ".ToCharArray(),
     49      "   #                    #    #  ".ToCharArray(),
     50      "   #                    #    #  ".ToCharArray(),
     51      "   ####.#####       .##..    .  ".ToCharArray(),
     52      "            #       .        #  ".ToCharArray(),
     53      "            #       #        .  ".ToCharArray(),
     54      "            #       #        .  ".ToCharArray(),
     55      "            #       #        #  ".ToCharArray(),
     56      "            .       #        .  ".ToCharArray(),
     57      "            #       .        .  ".ToCharArray(),
     58      "            #       .        #  ".ToCharArray(),
     59      "            #       #        .  ".ToCharArray(),
     60      "            #       #  ...###.  ".ToCharArray(),
     61      "            .   .#...  #        ".ToCharArray(),
     62      "            .   .      .        ".ToCharArray(),
     63      "            #   .      .        ".ToCharArray(),
     64      "            #   #      .#...    ".ToCharArray(),
     65      "            #   #          #    ".ToCharArray(),
     66      "            #   #          .    ".ToCharArray(),
     67      "            #   #          .    ".ToCharArray(),
     68      "            #   .      ...#.    ".ToCharArray(),
     69      "            #   .      #        ".ToCharArray(),
     70      " ..##..#####.   #               ".ToCharArray(),
     71      " #              #               ".ToCharArray(),
     72      " #              #               ".ToCharArray(),
     73      " #     .#######..               ".ToCharArray(),
     74      " #     #                        ".ToCharArray(),
     75      " .     #                        ".ToCharArray(),
     76      " .####..                        ".ToCharArray(),
     77      "                                ".ToCharArray()
    7678    };
     79
     80
    7781    #endregion
    7882
    7983    #region Parameter Properties
    80     public IValueParameter<ISymbolicExpressionGrammar> ArtificialAntExpressionGrammarParameter {
    81       get { return (IValueParameter<ISymbolicExpressionGrammar>)Parameters["ArtificialAntExpressionGrammar"]; }
    82     }
    83     public IValueParameter<IntValue> MaxExpressionLengthParameter {
    84       get { return (IValueParameter<IntValue>)Parameters["MaximumExpressionLength"]; }
    85     }
    86     public IValueParameter<IntValue> MaxExpressionDepthParameter {
    87       get { return (IValueParameter<IntValue>)Parameters["MaximumExpressionDepth"]; }
    88     }
    89     public IValueParameter<IntValue> MaxFunctionDefinitionsParameter {
    90       get { return (IValueParameter<IntValue>)Parameters["MaximumFunctionDefinitions"]; }
    91     }
    92     public IValueParameter<IntValue> MaxFunctionArgumentsParameter {
    93       get { return (ValueParameter<IntValue>)Parameters["MaximumFunctionArguments"]; }
    94     }
    9584    public IValueParameter<BoolMatrix> WorldParameter {
    9685      get { return (IValueParameter<BoolMatrix>)Parameters["World"]; }
    … …  
    11099      set { MaxTimeStepsParameter.Value = value; }
    111100    }
    112     public IntValue MaxExpressionLength {
    113       get { return MaxExpressionLengthParameter.Value; }
    114       set { MaxExpressionLengthParameter.Value = value; }
    115     }
    116     public IntValue MaxExpressionDepth {
    117       get { return MaxExpressionDepthParameter.Value; }
    118       set { MaxExpressionDepthParameter.Value = value; }
    119     }
    120     public IntValue MaxFunctionDefinitions {
    121       get { return MaxFunctionDefinitionsParameter.Value; }
    122       set { MaxFunctionDefinitionsParameter.Value = value; }
    123     }
    124     public IntValue MaxFunctionArguments {
    125       get { return MaxFunctionArgumentsParameter.Value; }
    126       set { MaxFunctionArgumentsParameter.Value = value; }
    127     }
    128     public ArtificialAntExpressionGrammar ArtificialAntExpressionGrammar {
    129       get { return (ArtificialAntExpressionGrammar)ArtificialAntExpressionGrammarParameter.Value; }
    130     }
    131     public IEnumerable<IAntTrailAnalyzer> AntTrailAnalyzers {
    132       get { return Operators.OfType<IAntTrailAnalyzer>(); }
    133     }
    134     #endregion
    135 
    136     // BackwardsCompatibility3.3
    137     #region Backwards compatible code, remove with 3.4
    138     [Obsolete]
    139     [Storable(Name = "operators")]
    140     private IEnumerable<IOperator> oldOperators {
    141       get { return null; }
    142       set {
    143         if (value != null && value.Any())
    144           Operators.AddRange(value);
    145       }
    146     }
    147     #endregion
    148 
     101    #endregion
     102
     103    public override bool Maximization {
     104      get { return true; }
     105    }
     106
     107    public ArtificialAntProblem()
     108      : base() {
     109      BoolMatrix world = new BoolMatrix(ToBoolMatrix(santaFeAntTrail));
     110      Parameters.Add(new ValueParameter<BoolMatrix>("World", "The world for the artificial ant with scattered food items.", world));
     111      Parameters.Add(new ValueParameter<IntValue>("MaximumTimeSteps", "The number of time steps the artificial ant has available to collect all food items.", new IntValue(600)));
     112
     113      base.BestKnownQuality = 89;
     114      var g = new SimpleSymbolicExpressionGrammar();
     115      g.AddSymbols(new string[] { "IfFoodAhead", "Prog2" }, 2, 2);
     116      g.AddSymbols(new string[] { "Prog3" }, 3, 3);
     117      g.AddTerminalSymbols(new string[] { "Left", "Right", "Move" });
     118      base.Encoding = new SymbolicExpressionTreeEncoding(g, 20, 10);
     119
     120      InitializeOperators();
     121      RegisterEventHandlers();
     122    }
     123
     124
     125    public override double Evaluate(Individual individual, IRandom random) {
     126      var interpreter = new AntInterpreter(individual.SymbolicExpressionTree(), World, MaxTimeSteps.Value);
     127      interpreter.Run();
     128      return interpreter.FoodEaten;
     129    }
     130
     131    // persistence
    149132    [StorableConstructor]
    150133    private ArtificialAntProblem(bool deserializing) : base(deserializing) { }
    … …  
    154137    }
    155138
     139    // cloning
    156140    private ArtificialAntProblem(ArtificialAntProblem original, Cloner cloner)
    157141      : base(original, cloner) {
    … …  
    161145      return new ArtificialAntProblem(this, cloner);
    162146    }
    163     public ArtificialAntProblem()
    164       : base(new Evaluator(), new ProbabilisticTreeCreator()) {
    165       BoolMatrix world = new BoolMatrix(santaFeAntTrail);
    166       Parameters.Add(new ValueParameter<IntValue>("MaximumExpressionLength", "Maximal length of the expression to control the artificial ant.", new IntValue(100)));
    167       Parameters.Add(new ValueParameter<IntValue>("MaximumExpressionDepth", "Maximal depth of the expression to control the artificial ant.", new IntValue(10)));
    168       Parameters.Add(new ValueParameter<IntValue>("MaximumFunctionDefinitions", "Maximal number of automatically defined functions in the expression to control the artificial ant.", new IntValue(3)));
    169       Parameters.Add(new ValueParameter<IntValue>("MaximumFunctionArguments", "Maximal number of arguments of automatically defined functions in the expression to control the artificial ant.", new IntValue(3)));
    170       Parameters.Add(new ValueParameter<ISymbolicExpressionGrammar>("ArtificialAntExpressionGrammar", "The grammar that should be used for artificial ant expressions.", new ArtificialAntExpressionGrammar()));
    171       Parameters.Add(new ValueParameter<BoolMatrix>("World", "The world for the artificial ant with scattered food items.", world));
    172       Parameters.Add(new ValueParameter<IntValue>("MaximumTimeSteps", "The number of time steps the artificial ant has available to collect all food items.", new IntValue(600)));
    173 
    174       Maximization.Value = true;
    175       MaximizationParameter.Hidden = true;
    176       BestKnownQuality = new DoubleValue(89);
    177       SolutionCreator.SymbolicExpressionTreeParameter.ActualName = "AntTrailSolution";
    178       ((ProbabilisticTreeCreator)SolutionCreator).SymbolicExpressionTreeGrammarParameter.ActualName = "ArtificialAntExpressionGrammar";
    179       Evaluator.QualityParameter.ActualName = "FoodEaten";
    180       InitializeOperators();
    181       RegisterEventHandlers();
    182 
    183       ArtificialAntExpressionGrammar.MaximumFunctionDefinitions = MaxFunctionDefinitions.Value;
    184       ArtificialAntExpressionGrammar.MaximumFunctionArguments = MaxFunctionArguments.Value;
    185     }
    186147
    187148    #region Events
    188149    protected override void OnSolutionCreatorChanged() {
    189150      base.OnSolutionCreatorChanged();
    190       SolutionCreator.SymbolicExpressionTreeParameter.ActualName = "AntTrailSolution";
    191       var grammarBased = SolutionCreator as ISymbolicExpressionTreeGrammarBasedOperator;
    192       if (grammarBased != null)
    193         grammarBased.SymbolicExpressionTreeGrammarParameter.ActualName = "ArtificialAntExpressionGrammar";
    194 
    195       SolutionCreator.SymbolicExpressionTreeParameter.ActualNameChanged += new EventHandler(SolutionCreator_SymbolicExpressionTreeParameter_ActualNameChanged);
    196151      ParameterizeAnalyzers();
    197152      ParameterizeOperators();
    … …  
    199154    protected override void OnEvaluatorChanged() {
    200155      base.OnEvaluatorChanged();
    201       Evaluator.QualityParameter.ActualName = "FoodEaten";
    202       Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
    203156      ParameterizeAnalyzers();
    204157      ParameterizeOperators();
    … …  
    216169    #region Helpers
    217170    private void RegisterEventHandlers() {
    218       SolutionCreator.SymbolicExpressionTreeParameter.ActualNameChanged += new EventHandler(SolutionCreator_SymbolicExpressionTreeParameter_ActualNameChanged);
     171      Encoding.SolutionCreator.SymbolicExpressionTreeParameter.ActualNameChanged += new EventHandler(SolutionCreator_SymbolicExpressionTreeParameter_ActualNameChanged);
    219172      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
    220       MaxFunctionArgumentsParameter.ValueChanged += new EventHandler(MaxFunctionArgumentsParameter_ValueChanged);
    221       MaxFunctionArguments.ValueChanged += new EventHandler(MaxFunctionArgumentsParameter_ValueChanged);
    222       MaxFunctionDefinitionsParameter.ValueChanged += new EventHandler(MaxFunctionDefinitionsParameter_ValueChanged);
    223       MaxFunctionDefinitions.ValueChanged += new EventHandler(MaxFunctionDefinitionsParameter_ValueChanged);
    224     }
    225 
    226     private void MaxFunctionDefinitionsParameter_ValueChanged(object sender, EventArgs e) {
    227       ArtificialAntExpressionGrammar.MaximumFunctionDefinitions = MaxFunctionDefinitions.Value;
    228       ParameterizeOperators();
    229       ParameterizeAnalyzers();
    230     }
    231     private void MaxFunctionArgumentsParameter_ValueChanged(object sender, EventArgs e) {
    232       ArtificialAntExpressionGrammar.MaximumFunctionArguments = MaxFunctionArguments.Value;
    233       ParameterizeOperators();
    234       ParameterizeAnalyzers();
    235173    }
    236174
    237175    private void InitializeOperators() {
    238       Operators.AddRange(ApplicationManager.Manager.GetInstances<ISymbolicExpressionTreeOperator>().OfType<IOperator>());
    239176      Operators.Add(new BestAntTrailAnalyzer());
    240       Operators.Add(new MinAverageMaxSymbolicExpressionTreeLengthAnalyzer());
    241       Operators.Add(new SymbolicExpressionSymbolFrequencyAnalyzer());
    242177      ParameterizeAnalyzers();
    243178      ParameterizeOperators();
    … …  
    245180
    246181    private void ParameterizeAnalyzers() {
    247       foreach (IAntTrailAnalyzer analyzer in AntTrailAnalyzers) {
     182      foreach (var analyzer in Operators.OfType<BestAntTrailAnalyzer>()) {
    248183        analyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
    249         analyzer.SymbolicExpressionTreeParameter.ActualName = SolutionCreator.SymbolicExpressionTreeParameter.ActualName;
     184        analyzer.SymbolicExpressionTreeParameter.ActualName = Encoding.SolutionCreator.SymbolicExpressionTreeParameter.ActualName;
    250185        analyzer.WorldParameter.ActualName = WorldParameter.Name;
    251186        analyzer.MaxTimeStepsParameter.ActualName = MaxTimeStepsParameter.Name;
    252187      }
    253       foreach (ISymbolicExpressionTreeAnalyzer analyzer in Operators.OfType<ISymbolicExpressionTreeAnalyzer>()) {
    254         analyzer.SymbolicExpressionTreeParameter.ActualName = SolutionCreator.SymbolicExpressionTreeParameter.ActualName;
     188    }
     189
     190    private void ParameterizeOperators() {
     191      // no problem-specific operators to parameterize
     192    }
     193
     194    private bool[,] ToBoolMatrix(char[][] ch) {
     195      var rows = ch.Length;
     196      var cols = ch[0].Length;
     197      var b = new bool[rows, cols];
     198      for (int r = 0; r < rows; r++) {
     199        Contract.Assert(ch[r].Length == cols); // all rows must have the same number of columns
     200        for (int c = 0; c < cols; c++) {
     201          b[r, c] = ch[r][c] == '#';
     202        }
    255203      }
    256     }
    257 
    258     private void ParameterizeOperators() {
    259       var operators = Parameters.OfType<IValueParameter>().Select(p => p.Value).OfType<IOperator>().Union(Operators);
    260 
    261       foreach (ISymbolicExpressionTreeGrammarBasedOperator op in operators.OfType<ISymbolicExpressionTreeGrammarBasedOperator>()) {
    262         op.SymbolicExpressionTreeGrammarParameter.ActualName = ArtificialAntExpressionGrammarParameter.Name;
    263       }
    264       foreach (ISymbolicExpressionTreeSizeConstraintOperator op in operators.OfType<ISymbolicExpressionTreeSizeConstraintOperator>()) {
    265         op.MaximumSymbolicExpressionTreeDepthParameter.ActualName = MaxExpressionDepthParameter.Name;
    266         op.MaximumSymbolicExpressionTreeLengthParameter.ActualName = MaxExpressionLengthParameter.Name;
    267 
    268       }
    269       foreach (Evaluator op in operators.OfType<Evaluator>()) {
    270         op.SymbolicExpressionTreeParameter.ActualName = SolutionCreator.SymbolicExpressionTreeParameter.ActualName;
    271         op.MaxTimeStepsParameter.ActualName = MaxTimeStepsParameter.Name;
    272         op.WorldParameter.ActualName = WorldParameter.Name;
    273       }
    274       foreach (ISymbolicExpressionTreeCrossover op in operators.OfType<ISymbolicExpressionTreeCrossover>()) {
    275         op.ParentsParameter.ActualName = SolutionCreator.SymbolicExpressionTreeParameter.ActualName;
    276         op.SymbolicExpressionTreeParameter.ActualName = SolutionCreator.SymbolicExpressionTreeParameter.ActualName;
    277       }
    278       foreach (ISymbolicExpressionTreeManipulator op in operators.OfType<ISymbolicExpressionTreeManipulator>()) {
    279         op.SymbolicExpressionTreeParameter.ActualName = SolutionCreator.SymbolicExpressionTreeParameter.ActualName;
    280       }
    281       foreach (ISymbolicExpressionTreeArchitectureAlteringOperator op in operators.OfType<ISymbolicExpressionTreeArchitectureAlteringOperator>()) {
    282         op.MaximumFunctionDefinitionsParameter.ActualName = MaxFunctionDefinitionsParameter.Name;
    283         op.MaximumFunctionArgumentsParameter.ActualName = MaxFunctionArgumentsParameter.Name;
    284       }
     204      return b;
    285205    }
    286206    #endregion
Note: See TracChangeset for help on using the changeset viewer.