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