source: branches/2605_StackingProblems/HeuristicLab.Problems.BlocksWorldProblem/3.3/BlocksWorldProblem.cs @ 17800

using HeuristicLab.Analysis;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Data.MoveVectorData;
using HeuristicLab.Data.MoveVectorData.Moves;
using HeuristicLab.Encodings.MoveVectorEncoding;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using System;
using System.Collections.Generic;
using System.Linq;

namespace HeuristicLab.Problems.BlocksWorldProblem
{

    [Item("Blocks World Problem (BWP)", "Represents a Blocks World Problem.")]
    [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 111)]
    [StorableClass]
    public class BlocksWorldProblem : SingleObjectiveBasicProblem<MoveVectorEncoding>
    {
        private const int INITIAL_WIDTH = 6;
        private const int INITIAL_HEIGHT = 7;
        private const double INITIAL_FILL_RATE = 0.5;

        #region Parameter Properties
        protected IValueParameter<IntValue> StackAreaWidthParameter
        {
            get { return (IValueParameter<IntValue>)Parameters["StackAreaWidth"]; }
        }
        protected IValueParameter<IntValue> StackAreaHeightParameter
        {
            get { return (IValueParameter<IntValue>)Parameters["StackAreaHeight"]; }
        }
        protected IValueParameter<IntValue> MaximumMovesParameter
        {
            get { return (IValueParameter<IntValue>)Parameters["MaximumMoves"]; }
        }
        protected IValueParameter<IntValue> InitSeedParameter
        {
            get { return (IValueParameter<IntValue>)Parameters["InitSeed"]; }
        }
        protected IValueParameter<DoubleValue> FillRateParameter
        {
            get { return (IValueParameter<DoubleValue>)Parameters["FillRate"]; }
        }
        protected IValueParameter<StackingArea> StartStackAreaParameter
        {
            get { return (IValueParameter<StackingArea>)Parameters["StartStackArea"]; }
        }
        protected IValueParameter<StackingArea> FinalStackAreaParameter
        {
            get { return (IValueParameter<StackingArea>)Parameters["FinalStackArea"]; }
        }
        protected IValueParameter<MoveVector> BestKnownSolutionParameter
        {
            get { return (IValueParameter<MoveVector>)Parameters["BestKnownSolution"]; }
        }
        protected IValueParameter<StackingArea> BestKnownStackAreaParameter
        {
            get { return (IValueParameter<StackingArea>)Parameters["BestKnownStackArea"]; }
        }
        protected IValueParameter<IntValue> BestKnownDislocatedParameter
        {
            get { return (IValueParameter<IntValue>)Parameters["BestKnownDislocated"]; }
        }
        protected IValueParameter<IntValue> BestKnownMovesParameter
        {
            get { return (IValueParameter<IntValue>)Parameters["BestKnownMoves"]; }
        }
        #endregion

        #region Properties
        public int StackAreaWidth
        {
            get { return StackAreaWidthParameter.Value.Value; }
            set
            {
                StackAreaWidthParameter.Value.Value = value;
                Encoding.Bounds[0, 0] = 0;
                Encoding.Bounds[0, 1] = value;
            }
        }
        public int StackAreaHeight
        {
            get { return StackAreaHeightParameter.Value.Value; }
            set {
                StackAreaHeightParameter.Value.Value = value;
            }
        }
        public int MaximumMoves
        {
            get { return MaximumMovesParameter.Value.Value; }
            set
            {
                MaximumMovesParameter.Value.Value = value;
                Encoding.Length = value;
            }
        }
        public int InitSeed
        {
            get { return InitSeedParameter.Value.Value; }
            set { InitSeedParameter.Value.Value = value; }
        }
        public double FillRate
        {
            get { return FillRateParameter.Value.Value; }
            set { FillRateParameter.Value.Value = value; }
        }
        public StackingArea StartStackArea
        {
            get { return StartStackAreaParameter.Value; }
            set { StartStackAreaParameter.Value = value; }
        }
        public StackingArea FinalStackArea
        {
            get { return FinalStackAreaParameter.Value; }
            set { FinalStackAreaParameter.Value = value; }
        }
        public MoveVector BestKnownSolution
        {
            get { return BestKnownSolutionParameter.Value; }
            set { BestKnownSolutionParameter.Value = value; }
        }
        public StackingArea BestKnownStackArea
        {
            get { return BestKnownStackAreaParameter.Value; }
            set { BestKnownStackAreaParameter.Value = value; }
        }
        public IntValue BestKnownDislocated
        {
            get { return BestKnownDislocatedParameter.Value; }
            set { BestKnownDislocatedParameter.Value = value; }
        }
        public IntValue BestKnownMoves
        {
            get { return BestKnownMovesParameter.Value; }
            set { BestKnownMovesParameter.Value = value; }
        }
        #endregion

        #region Cloning
        [StorableConstructor]
        protected BlocksWorldProblem(bool deserializing) : base(deserializing) { }
        public BlocksWorldProblem(BlocksWorldProblem alg, Cloner cloner) : base(alg, cloner)
        {
            RegisterEventHandlers();
        }
        public override IDeepCloneable Clone(Cloner cloner)
        {
            return new BlocksWorldProblem(this, cloner);
        }
        [StorableHook(HookType.AfterDeserialization)]
        private void AfterDeserialization()
        {
            RegisterEventHandlers();
        }
        #endregion

        private Dictionary<int, Tuple<int, int>> targetPositions;

        public BlocksWorldProblem() {
            Parameters.Add(new OptionalValueParameter<IntValue>("StackAreaWidth", "Defines the width of the stacking arew.", new IntValue(INITIAL_WIDTH)));
            Parameters.Add(new OptionalValueParameter<IntValue>("StackAreaHeight", "Defines the maximum height of the stacking area.", new IntValue(INITIAL_HEIGHT)));
            Parameters.Add(new OptionalValueParameter<IntValue>("MaximumMoves", "Defines the maximum ammount of move actions.", new IntValue(2 * INITIAL_WIDTH * INITIAL_HEIGHT)));
            Parameters.Add(new OptionalValueParameter<IntValue>("InitSeed", "Seed for the random stacking area number generator.", new IntValue(Convert.ToInt32(DateTime.Now.Ticks % 10000))));
            Parameters.Add(new OptionalValueParameter<DoubleValue>("FillRate", "How much containers are randomly generated in the stacking area.", new DoubleValue(INITIAL_FILL_RATE)));
            Parameters.Add(new OptionalValueParameter<StackingArea>("StartStackArea", "Defines the status of the stacking area at the start of the computation.", new StackingArea(StackAreaWidth, StackAreaHeight)));
            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)));
            Parameters.Add(new OptionalValueParameter<StackingArea>("BestKnownStackArea", "Best known StackArea solution."));
            Parameters.Add(new OptionalValueParameter<MoveVector>("BestKnownSolution", "Best Solution found."));
            Parameters.Add(new OptionalValueParameter<IntValue>("BestKnownDislocated", "Best amount of dislocated containers found."));
            Parameters.Add(new OptionalValueParameter<IntValue>("BestKnownMoves", "Best amount of moves found."));
            Encoding = new MoveVectorEncoding(MaximumMoves, 0, StackAreaWidth);
            Encoding.SolutionCreator.MoveTypes = new List<Type>() { typeof(TwoPointMove) };
            RandomizeStackingAreas();
            RegisterEventHandlers();
        }

        private void RandomizeStackingAreas()
        {
            StartStackArea.Randomize(FillRate, InitSeed);
            FinalStackArea.Randomize(FillRate, InitSeed * 2);
        }

        public override bool Maximization { get { return false; } }

        public override double Evaluate(Individual individual, IRandom random)
        {
            MoveVector moveVector = individual.MoveVector();
            StackingArea copy = (StackingArea)StartStackArea.Clone();
            int realMoves = 0;
            int dislocated = 0;
            int moves = StackingArea.ApplyMoves(ref copy, moveVector, out realMoves);

            if(targetPositions == null)
            {
                targetPositions = new Dictionary<int, Tuple<int, int>>(StackAreaWidth * StackAreaHeight);
                for (int i = 0; i < StackAreaWidth; i++)
                {
                    for (int j = 0; j < StackAreaHeight; j++)
                    {
                        if (FinalStackArea[j, i] != 0)
                        {
                            targetPositions.Add(FinalStackArea[j, i], new Tuple<int, int>(j, i));
                        }
                    }
                }
            }

            int distances = 0;
            for (int stack = 0; stack < StackAreaWidth; stack++)
            {
                int currentStackContainerCount = StackAreaHeight;

                for (int row = StackAreaHeight - 1; row >= 0; row--)
                {
                    int currentValue = copy[row, stack];
                    if (currentValue == 0)
                    {
                        currentStackContainerCount--;
                    }
                    else
                    {
                        if (FinalStackArea[row, stack] - currentValue != 0)
                        {
                            dislocated++;
                            var targetPos = new Tuple<int, int>(row, stack);
                            if (targetPositions.TryGetValue(currentValue, out targetPos))
                            {
                                int distanceBetweenStacks = Math.Abs(targetPos.Item2 - stack);
                                int distanceAtopSource = currentStackContainerCount - row - 1; // -1 because current container doesn't count
                                int distanceAtopTarget = Math.Abs(copy[targetPos.Item2].CurrentHeight - targetPos.Item1);
                                int distance = 0;
                                if (distanceBetweenStacks == 0)
                                {
                                    distance = distanceAtopSource + 1; // +1 because dislocated
                                }
                                else {
                                    distance = distanceAtopSource + distanceAtopTarget + distanceBetweenStacks + 1;
                                }
                                distances = distances + distance;
                            } else
                            {
                                throw new AccessViolationException("TryGetValue failed.");
                            }
                        }
                    }
                }

                /*
                for (int j = 0; j < StackAreaHeight; j++)
                {
                    if (FinalStackArea[j, i] - copy[j, i] != 0)
                    {
                        dislocated++;
                        var near = new Tuple<int, int>(j, i);
                        if(positions.TryGetValue(copy[j, i], out near))
                        {
                            int distanceAtopSource = StackAreaHeight - j;
                            int distanceAtopTarget = StackAreaHeight - near.Item1;
                            int distanceBetweenStacks = Math.Abs(near.Item2 - i);
                            int distance = distanceAtopSource + distanceAtopTarget + distanceBetweenStacks + 1;
                            distances = distances + distance;
                        }
                    }
                }
                */
            }

            double quality = moves + 10 * distances; //distances are 10 times more important than the ammount of moves

            if (BestKnownQuality.Equals(double.NaN) || quality < BestKnownQuality)
            {
                BestKnownQuality = quality;
                BestKnownSolution = moveVector;
                BestKnownStackArea = copy;
                BestKnownDislocated = new IntValue(dislocated);
                BestKnownMoves = new IntValue(realMoves);
            }
            return quality;
        }

        public override IEnumerable<Individual> GetNeighbors(Individual individual, IRandom random)
        {
            var neighbours = new List<Individual>();
            var currentSolution = individual.MoveVector();

            for (int i = 0; i < currentSolution.Length; i++)
            {
                //change moves
                var move = currentSolution[i];
                foreach (var newMove in move.GenerateNeighbours(random, 0, StackAreaWidth - 1))
                {
                    var copy1 = individual.Copy();
                    copy1.MoveVector()[i] = newMove;
                    neighbours.Add(copy1);
                }

                //change position
                if (currentSolution.Length > 1)
                {
                    var len = currentSolution.Length - 1;
                    var right = individual.Copy();
                    var r = right.MoveVector();
                    var left = individual.Copy();
                    var l = left.MoveVector();
                    if (i == 0)
                    {
                        r[i].Enabled = true;
                        Swap(r, i, i + 1);
                        l[i].Enabled = true;
                        Swap(l, i, len);
                    }
                    else if (i == len)
                    {
                        r[i].Enabled = true;
                        Swap(r, i, 0);
                        l[i].Enabled = true;
                        Swap(l, i, i - 1);
                    }
                    else
                    {
                        r[i].Enabled = true;
                        Swap(r, i, i + 1);
                        l[i].Enabled = true;
                        Swap(l, i, i - 1);
                    }
                    neighbours.Add(right);
                    neighbours.Add(left);
                }
            }

            neighbours.AddRange(base.GetNeighbors(individual, random));
            return neighbours;
        }

        private static void Swap(MoveVector c, int index1, int index2)
        {
            var save = c[index1];
            c[index1] = c[index2];
            c[index2] = save;
        }

        public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random)
        {
            base.Analyze(individuals, qualities, results, random);

            if (!results.ContainsKey("Move History"))
            {
                string description = "Shows move amount.";
                Analysis.DataTable add;
                add = new Analysis.DataTable("Amount of Moves", description);
                add.VisualProperties.XAxisTitle = "Iteration";
                add.VisualProperties.YAxisTitle = "Moves";
                results.Add(new Result("Move History", description, add));
            }

            if (!results.ContainsKey("Dislocated History"))
            {
                string description = "Shows move amount.";
                Analysis.DataTable add;
                add = new Analysis.DataTable("Dislocated Containers", description);
                add.VisualProperties.XAxisTitle = "Iteration";
                add.VisualProperties.YAxisTitle = "Dislocated Containers";
                results.Add(new Result("Dislocated History", description, add));
            }

            Analysis.DataTable moveHistory = (Analysis.DataTable)results["Move History"].Value;
            Analysis.DataRow row;
            if (!moveHistory.Rows.TryGetValue("MoveDistribution", out row))
            {
                row = new Analysis.DataRow("MoveDistribution");
                row.VisualProperties.ChartType = DataRowVisualProperties.DataRowChartType.Line;
                moveHistory.Rows.Add(row);
            }
            row.Values.Add(BestKnownMoves.Value);

            Analysis.DataTable dislocatedHistory = (Analysis.DataTable)results["Dislocated History"].Value;
            if (!dislocatedHistory.Rows.TryGetValue("DislocatedDistribution", out row))
            {
                row = new Analysis.DataRow("DislocatedDistribution");
                row.VisualProperties.ChartType = DataRowVisualProperties.DataRowChartType.Line;
                dislocatedHistory.Rows.Add(row);
            }
            row.Values.Add(BestKnownDislocated.Value);
        }

        #region EventHandlers
        private void RegisterEventHandlers()
        {
            //this.Reset += StackingProblem_Reset;
            StackAreaWidthParameter.Value.ValueChanged += StackAreaDimensions_Changed;
            StackAreaHeightParameter.Value.ValueChanged += StackAreaDimensions_Changed;
            MaximumMovesParameter.Value.ValueChanged += MaxiumumMoves_Changed;
            InitSeedParameter.Value.ValueChanged += InitSeed_Changed;
            FillRateParameter.Value.ValueChanged += FillRate_Changed;
        }

        private void FillRate_Changed(object sender, EventArgs e)
        {
            RandomizeStackingAreas();
        }

        private void InitSeed_Changed(object sender, EventArgs e)
        {
            RandomizeStackingAreas();
        }

        /*private void StackingProblem_Reset(object sender, EventArgs e)
        {
            positions = null;
            BestKnownQualityParameter.Value = null;
            BestKnownSolutionParameter.Value = null;
            BestKnownStackAreaParameter.Value = null;
        }*/

        private void MaxiumumMoves_Changed(object sender, EventArgs e)
        {
            Encoding.Length = MaximumMoves;
        }

        private void StackAreaDimensions_Changed(object sender, EventArgs e)
        {
            StartStackArea = new StackingArea(StackAreaWidth, StackAreaHeight);
            FinalStackArea = new StackingArea(StackAreaWidth, StackAreaHeight);
            RandomizeStackingAreas();
            Encoding.Bounds[0, 0] = 0;
            Encoding.Bounds[0, 1] = StackAreaWidth;
            MaximumMoves = StackAreaWidth * StackAreaHeight * 4;
            Encoding.Length = MaximumMoves;
        }
        #endregion
    }
}