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