source: branches/StackingProblems/HeuristicLab.Problems.BlocksWorldProblem/3.3/BlocksWorldProblem.cs @ 14278

Last change on this file since 14278 was 14278, checked in by mzehetho, 5 years ago

Initial Commit for ticket #2605

Implemented:

  • Encoding
  • Moves
  • Views
  • Blocks World Problem
  • Blocks Relocation Problem
  • Stacking Problem
File size: 18.6 KB
Line 
1using HeuristicLab.Analysis;
2using HeuristicLab.Common;
3using HeuristicLab.Core;
4using HeuristicLab.Data;
5using HeuristicLab.Data.MoveVectorData;
6using HeuristicLab.Data.MoveVectorData.Moves;
7using HeuristicLab.Encodings.MoveVectorEncoding;
8using HeuristicLab.Optimization;
9using HeuristicLab.Parameters;
10using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
11using System;
12using System.Collections.Generic;
13using System.Linq;
14
15namespace HeuristicLab.Problems.BlocksWorldProblem
16{
17
18    [Item("Blocks World Problem (BWP)", "Represents a Blocks World Problem.")]
19    [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 111)]
20    [StorableClass]
21    public class BlocksWorldProblem : SingleObjectiveBasicProblem<MoveVectorEncoding>
22    {
23        private const int INITIAL_WIDTH = 6;
24        private const int INITIAL_HEIGHT = 7;
25        private const double INITIAL_FILL_RATE = 0.5;
26
27        #region Parameter Properties
28        protected IValueParameter<IntValue> StackAreaWidthParameter
29        {
30            get { return (IValueParameter<IntValue>)Parameters["StackAreaWidth"]; }
31        }
32        protected IValueParameter<IntValue> StackAreaHeightParameter
33        {
34            get { return (IValueParameter<IntValue>)Parameters["StackAreaHeight"]; }
35        }
36        protected IValueParameter<IntValue> MaximumMovesParameter
37        {
38            get { return (IValueParameter<IntValue>)Parameters["MaximumMoves"]; }
39        }
40        protected IValueParameter<IntValue> InitSeedParameter
41        {
42            get { return (IValueParameter<IntValue>)Parameters["InitSeed"]; }
43        }
44        protected IValueParameter<DoubleValue> FillRateParameter
45        {
46            get { return (IValueParameter<DoubleValue>)Parameters["FillRate"]; }
47        }
48        protected IValueParameter<StackingArea> StartStackAreaParameter
49        {
50            get { return (IValueParameter<StackingArea>)Parameters["StartStackArea"]; }
51        }
52        protected IValueParameter<StackingArea> FinalStackAreaParameter
53        {
54            get { return (IValueParameter<StackingArea>)Parameters["FinalStackArea"]; }
55        }
56        protected IValueParameter<MoveVector> BestKnownSolutionParameter
57        {
58            get { return (IValueParameter<MoveVector>)Parameters["BestKnownSolution"]; }
59        }
60        protected IValueParameter<StackingArea> BestKnownStackAreaParameter
61        {
62            get { return (IValueParameter<StackingArea>)Parameters["BestKnownStackArea"]; }
63        }
64        protected IValueParameter<IntValue> BestKnownDislocatedParameter
65        {
66            get { return (IValueParameter<IntValue>)Parameters["BestKnownDislocated"]; }
67        }
68        protected IValueParameter<IntValue> BestKnownMovesParameter
69        {
70            get { return (IValueParameter<IntValue>)Parameters["BestKnownMoves"]; }
71        }
72        #endregion
73
74        #region Properties
75        public int StackAreaWidth
76        {
77            get { return StackAreaWidthParameter.Value.Value; }
78            set
79            {
80                StackAreaWidthParameter.Value.Value = value;
81                Encoding.Bounds[0, 0] = 0;
82                Encoding.Bounds[0, 1] = value;
83            }
84        }
85        public int StackAreaHeight
86        {
87            get { return StackAreaHeightParameter.Value.Value; }
88            set {
89                StackAreaHeightParameter.Value.Value = value;
90            }
91        }
92        public int MaximumMoves
93        {
94            get { return MaximumMovesParameter.Value.Value; }
95            set
96            {
97                MaximumMovesParameter.Value.Value = value;
98                Encoding.Length = value;
99            }
100        }
101        public int InitSeed
102        {
103            get { return InitSeedParameter.Value.Value; }
104            set { InitSeedParameter.Value.Value = value; }
105        }
106        public double FillRate
107        {
108            get { return FillRateParameter.Value.Value; }
109            set { FillRateParameter.Value.Value = value; }
110        }
111        public StackingArea StartStackArea
112        {
113            get { return StartStackAreaParameter.Value; }
114            set { StartStackAreaParameter.Value = value; }
115        }
116        public StackingArea FinalStackArea
117        {
118            get { return FinalStackAreaParameter.Value; }
119            set { FinalStackAreaParameter.Value = value; }
120        }
121        public MoveVector BestKnownSolution
122        {
123            get { return BestKnownSolutionParameter.Value; }
124            set { BestKnownSolutionParameter.Value = value; }
125        }
126        public StackingArea BestKnownStackArea
127        {
128            get { return BestKnownStackAreaParameter.Value; }
129            set { BestKnownStackAreaParameter.Value = value; }
130        }
131        public IntValue BestKnownDislocated
132        {
133            get { return BestKnownDislocatedParameter.Value; }
134            set { BestKnownDislocatedParameter.Value = value; }
135        }
136        public IntValue BestKnownMoves
137        {
138            get { return BestKnownMovesParameter.Value; }
139            set { BestKnownMovesParameter.Value = value; }
140        }
141        #endregion
142
143        #region Cloning
144        [StorableConstructor]
145        protected BlocksWorldProblem(bool deserializing) : base(deserializing) { }
146        public BlocksWorldProblem(BlocksWorldProblem alg, Cloner cloner) : base(alg, cloner)
147        {
148            RegisterEventHandlers();
149        }
150        public override IDeepCloneable Clone(Cloner cloner)
151        {
152            return new BlocksWorldProblem(this, cloner);
153        }
154        [StorableHook(HookType.AfterDeserialization)]
155        private void AfterDeserialization()
156        {
157            RegisterEventHandlers();
158        }
159        #endregion
160
161        private Dictionary<int, Tuple<int, int>> targetPositions;
162
163        public BlocksWorldProblem() {
164            Parameters.Add(new OptionalValueParameter<IntValue>("StackAreaWidth", "Defines the width of the stacking arew.", new IntValue(INITIAL_WIDTH)));
165            Parameters.Add(new OptionalValueParameter<IntValue>("StackAreaHeight", "Defines the maximum height of the stacking area.", new IntValue(INITIAL_HEIGHT)));
166            Parameters.Add(new OptionalValueParameter<IntValue>("MaximumMoves", "Defines the maximum ammount of move actions.", new IntValue(2 * INITIAL_WIDTH * INITIAL_HEIGHT)));
167            Parameters.Add(new OptionalValueParameter<IntValue>("InitSeed", "Seed for the random stacking area number generator.", new IntValue(Convert.ToInt32(DateTime.Now.Ticks % 10000))));
168            Parameters.Add(new OptionalValueParameter<DoubleValue>("FillRate", "How much containers are randomly generated in the stacking area.", new DoubleValue(INITIAL_FILL_RATE)));
169            Parameters.Add(new OptionalValueParameter<StackingArea>("StartStackArea", "Defines the status of the stacking area at the start of the computation.", new StackingArea(StackAreaWidth, StackAreaHeight)));
170            Parameters.Add(new OptionalValueParameter<StackingArea>("FinalStackArea", "Defines the should be status of the stacking area at the end of the computation.", new StackingArea(StackAreaWidth, StackAreaHeight)));
171            Parameters.Add(new OptionalValueParameter<StackingArea>("BestKnownStackArea", "Best known StackArea solution."));
172            Parameters.Add(new OptionalValueParameter<MoveVector>("BestKnownSolution", "Best Solution found."));
173            Parameters.Add(new OptionalValueParameter<IntValue>("BestKnownDislocated", "Best amount of dislocated containers found."));
174            Parameters.Add(new OptionalValueParameter<IntValue>("BestKnownMoves", "Best amount of moves found."));
175            Encoding = new MoveVectorEncoding(MaximumMoves, 0, StackAreaWidth);
176            Encoding.SolutionCreator.MoveTypes = new List<Type>() { typeof(TwoPointMove) };
177            RandomizeStackingAreas();
178            RegisterEventHandlers();
179        }
180
181        private void RandomizeStackingAreas()
182        {
183            StartStackArea.Randomize(FillRate, InitSeed);
184            FinalStackArea.Randomize(FillRate, InitSeed * 2);
185        }
186
187        public override bool Maximization { get { return false; } }
188
189        public override double Evaluate(Individual individual, IRandom random)
190        {
191            MoveVector moveVector = individual.MoveVector();
192            StackingArea copy = (StackingArea)StartStackArea.Clone();
193            int realMoves = 0;
194            int dislocated = 0;
195            int moves = StackingArea.ApplyMoves(ref copy, moveVector, out realMoves);
196
197            if(targetPositions == null)
198            {
199                targetPositions = new Dictionary<int, Tuple<int, int>>(StackAreaWidth * StackAreaHeight);
200                for (int i = 0; i < StackAreaWidth; i++)
201                {
202                    for (int j = 0; j < StackAreaHeight; j++)
203                    {
204                        if (FinalStackArea[j, i] != 0)
205                        {
206                            targetPositions.Add(FinalStackArea[j, i], new Tuple<int, int>(j, i));
207                        }
208                    }
209                }
210            }
211
212            int distances = 0;
213            for (int stack = 0; stack < StackAreaWidth; stack++)
214            {
215                int currentStackContainerCount = StackAreaHeight;
216
217                for (int row = StackAreaHeight - 1; row >= 0; row--)
218                {
219                    int currentValue = copy[row, stack];
220                    if (currentValue == 0)
221                    {
222                        currentStackContainerCount--;
223                    }
224                    else
225                    {
226                        if (FinalStackArea[row, stack] - currentValue != 0)
227                        {
228                            dislocated++;
229                            var targetPos = new Tuple<int, int>(row, stack);
230                            if (targetPositions.TryGetValue(currentValue, out targetPos))
231                            {
232                                int distanceBetweenStacks = Math.Abs(targetPos.Item2 - stack);
233                                int distanceAtopSource = currentStackContainerCount - row - 1; // -1 because current container doesn't count
234                                int distanceAtopTarget = Math.Abs(copy[targetPos.Item2].CurrentHeight - targetPos.Item1);
235                                int distance = 0;
236                                if (distanceBetweenStacks == 0)
237                                {
238                                    distance = distanceAtopSource + 1; // +1 because dislocated
239                                }
240                                else {
241                                    distance = distanceAtopSource + distanceAtopTarget + distanceBetweenStacks + 1;
242                                }
243                                distances = distances + distance;
244                            } else
245                            {
246                                throw new AccessViolationException("TryGetValue failed.");
247                            }
248                        }
249                    }
250                }
251
252                /*
253                for (int j = 0; j < StackAreaHeight; j++)
254                {
255                    if (FinalStackArea[j, i] - copy[j, i] != 0)
256                    {
257                        dislocated++;
258                        var near = new Tuple<int, int>(j, i);
259                        if(positions.TryGetValue(copy[j, i], out near))
260                        {
261                            int distanceAtopSource = StackAreaHeight - j;
262                            int distanceAtopTarget = StackAreaHeight - near.Item1;
263                            int distanceBetweenStacks = Math.Abs(near.Item2 - i);
264                            int distance = distanceAtopSource + distanceAtopTarget + distanceBetweenStacks + 1;
265                            distances = distances + distance;
266                        }
267                    }
268                }
269                */
270            }
271
272            double quality = moves + 10 * distances; //distances are 10 times more important than the ammount of moves
273
274            if (BestKnownQuality.Equals(double.NaN) || quality < BestKnownQuality)
275            {
276                BestKnownQuality = quality;
277                BestKnownSolution = moveVector;
278                BestKnownStackArea = copy;
279                BestKnownDislocated = new IntValue(dislocated);
280                BestKnownMoves = new IntValue(realMoves);
281            }
282            return quality;
283        }
284
285        public override IEnumerable<Individual> GetNeighbors(Individual individual, IRandom random)
286        {
287            var neighbours = new List<Individual>();
288            var currentSolution = individual.MoveVector();
289
290            for (int i = 0; i < currentSolution.Length; i++)
291            {
292                //change moves
293                var move = currentSolution[i];
294                foreach (var newMove in move.GenerateNeighbours(random, 0, StackAreaWidth - 1))
295                {
296                    var copy1 = individual.Copy();
297                    copy1.MoveVector()[i] = newMove;
298                    neighbours.Add(copy1);
299                }
300
301                //change position
302                if (currentSolution.Length > 1)
303                {
304                    var len = currentSolution.Length - 1;
305                    var right = individual.Copy();
306                    var r = right.MoveVector();
307                    var left = individual.Copy();
308                    var l = left.MoveVector();
309                    if (i == 0)
310                    {
311                        r[i].Enabled = true;
312                        Swap(r, i, i + 1);
313                        l[i].Enabled = true;
314                        Swap(l, i, len);
315                    }
316                    else if (i == len)
317                    {
318                        r[i].Enabled = true;
319                        Swap(r, i, 0);
320                        l[i].Enabled = true;
321                        Swap(l, i, i - 1);
322                    }
323                    else
324                    {
325                        r[i].Enabled = true;
326                        Swap(r, i, i + 1);
327                        l[i].Enabled = true;
328                        Swap(l, i, i - 1);
329                    }
330                    neighbours.Add(right);
331                    neighbours.Add(left);
332                }
333            }
334
335            neighbours.AddRange(base.GetNeighbors(individual, random));
336            return neighbours;
337        }
338
339        private static void Swap(MoveVector c, int index1, int index2)
340        {
341            var save = c[index1];
342            c[index1] = c[index2];
343            c[index2] = save;
344        }
345
346        public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random)
347        {
348            base.Analyze(individuals, qualities, results, random);
349
350            if (!results.ContainsKey("Move History"))
351            {
352                string description = "Shows move amount.";
353                Analysis.DataTable add;
354                add = new Analysis.DataTable("Amount of Moves", description);
355                add.VisualProperties.XAxisTitle = "Iteration";
356                add.VisualProperties.YAxisTitle = "Moves";
357                results.Add(new Result("Move History", description, add));
358            }
359
360            if (!results.ContainsKey("Dislocated History"))
361            {
362                string description = "Shows move amount.";
363                Analysis.DataTable add;
364                add = new Analysis.DataTable("Dislocated Containers", description);
365                add.VisualProperties.XAxisTitle = "Iteration";
366                add.VisualProperties.YAxisTitle = "Dislocated Containers";
367                results.Add(new Result("Dislocated History", description, add));
368            }
369
370            Analysis.DataTable moveHistory = (Analysis.DataTable)results["Move History"].Value;
371            Analysis.DataRow row;
372            if (!moveHistory.Rows.TryGetValue("MoveDistribution", out row))
373            {
374                row = new Analysis.DataRow("MoveDistribution");
375                row.VisualProperties.ChartType = DataRowVisualProperties.DataRowChartType.Line;
376                moveHistory.Rows.Add(row);
377            }
378            row.Values.Add(BestKnownMoves.Value);
379
380            Analysis.DataTable dislocatedHistory = (Analysis.DataTable)results["Dislocated History"].Value;
381            if (!dislocatedHistory.Rows.TryGetValue("DislocatedDistribution", out row))
382            {
383                row = new Analysis.DataRow("DislocatedDistribution");
384                row.VisualProperties.ChartType = DataRowVisualProperties.DataRowChartType.Line;
385                dislocatedHistory.Rows.Add(row);
386            }
387            row.Values.Add(BestKnownDislocated.Value);
388        }
389
390        #region EventHandlers
391        private void RegisterEventHandlers()
392        {
393            //this.Reset += StackingProblem_Reset;
394            StackAreaWidthParameter.Value.ValueChanged += StackAreaDimensions_Changed;
395            StackAreaHeightParameter.Value.ValueChanged += StackAreaDimensions_Changed;
396            MaximumMovesParameter.Value.ValueChanged += MaxiumumMoves_Changed;
397            InitSeedParameter.Value.ValueChanged += InitSeed_Changed;
398            FillRateParameter.Value.ValueChanged += FillRate_Changed;
399        }
400
401        private void FillRate_Changed(object sender, EventArgs e)
402        {
403            RandomizeStackingAreas();
404        }
405
406        private void InitSeed_Changed(object sender, EventArgs e)
407        {
408            RandomizeStackingAreas();
409        }
410
411        /*private void StackingProblem_Reset(object sender, EventArgs e)
412        {
413            positions = null;
414            BestKnownQualityParameter.Value = null;
415            BestKnownSolutionParameter.Value = null;
416            BestKnownStackAreaParameter.Value = null;
417        }*/
418
419        private void MaxiumumMoves_Changed(object sender, EventArgs e)
420        {
421            Encoding.Length = MaximumMoves;
422        }
423
424        private void StackAreaDimensions_Changed(object sender, EventArgs e)
425        {
426            StartStackArea = new StackingArea(StackAreaWidth, StackAreaHeight);
427            FinalStackArea = new StackingArea(StackAreaWidth, StackAreaHeight);
428            RandomizeStackingAreas();
429            Encoding.Bounds[0, 0] = 0;
430            Encoding.Bounds[0, 1] = StackAreaWidth;
431            MaximumMoves = StackAreaWidth * StackAreaHeight * 4;
432            Encoding.Length = MaximumMoves;
433        }
434        #endregion
435    }
436}
Note: See TracBrowser for help on using the repository browser.