source: branches/2605_StackingProblems/HeuristicLab.Problems.Stacking/3.3/StackingProblem.cs @ 17366

using HeuristicLab.Analysis;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Data.MoveVectorData;
using HeuristicLab.Data.MoveVectorData.Interfaces;
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.Stacking
{
    [Item("Stacking Problem (SP)", "Represents a Stacking Problem.")]
    [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 111)]
    [StorableClass]
    public class StackingProblem : SingleObjectiveBasicProblem<MoveVectorEncoding>
    {
        private const int INITIAL_WIDTH = 6;
        private const int INITIAL_HEIGHT = 8;
        private const int INITIAL_INPUT_SIZE = INITIAL_WIDTH * INITIAL_HEIGHT;
        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> InputStackSizeParameter
        {
            get { return (IValueParameter<IntValue>)Parameters["InputStackSize"]; }
        }
        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<Stack> InputStackParameter
        {
            get { return (IValueParameter<Stack>)Parameters["InputStack"]; }
        }
        protected IValueParameter<StackingArea> StartStackAreaParameter
        {
            get { return (IValueParameter<StackingArea>)Parameters["StartStackArea"]; }
        }
        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.Length = value;
            }
        }
        public int InputStackSize
        {
            get { return InputStackSizeParameter.Value.Value; }
            set
            {
                InputStackSizeParameter.Value.Value = value;
            }
        }
        public int StackAreaHeight
        {
            get { return StackAreaHeightParameter.Value.Value; }
            set
            {
                StackAreaHeightParameter.Value.Value = value;
                Encoding.Bounds[0, 0] = 0;
                Encoding.Bounds[0, 1] = 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 Stack InputStack
        {
            get { return InputStackParameter.Value; }
            set { InputStackParameter.Value = value; }
        }
        public StackingArea StartStackArea
        {
            get { return StartStackAreaParameter.Value; }
            set { StartStackAreaParameter.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 StackingProblem(bool deserializing) : base(deserializing) { }
        public StackingProblem(StackingProblem alg, Cloner cloner) : base(alg, cloner)
        {
            RegisterEventHandlers();
        }
        public override IDeepCloneable Clone(Cloner cloner)
        {
            return new StackingProblem(this, cloner);
        }
        [StorableHook(HookType.AfterDeserialization)]
        private void AfterDeserialization()
        {
            RegisterEventHandlers();
        }
        #endregion

        public StackingProblem()
        {
            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>("InputStackSize", "Defines the maximum height of the input stack.", new IntValue(INITIAL_INPUT_SIZE)));
            Parameters.Add(new OptionalValueParameter<IntValue>("MaximumMoves", "Defines the maximum ammount of move actions.", new IntValue(INITIAL_WIDTH * INITIAL_HEIGHT + INITIAL_INPUT_SIZE * 2)));
            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<Stack>("InputStack", "Defines the status of the input stack at the start of the computation.", new Stack(0, INITIAL_INPUT_SIZE)));
            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>("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), typeof(IngoingMove), typeof(OutgoingMove) };
            RandomizeStackingAreas();
            RegisterEventHandlers();
        }

        private void RandomizeStackingAreas()
        {
            InputStack.Randomize(FillRate, InitSeed);
        }

        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 type
                foreach(Type t in Encoding.SolutionCreator.MoveTypes)
                {
                    var copy = individual.Copy();
                    IMove m = (IMove)Activator.CreateInstance(t);
                    m.Randomize(random, 0, StackAreaWidth - 1);
                    copy.MoveVector()[i] = m;
                    neighbours.Add(copy);
                }

                var move = currentSolution[i];
                //change moves
                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;
        }

        #region EventHandlers
        private void RegisterEventHandlers()
        {
            //this.Reset += StackingProblem_Reset;
            StackAreaWidthParameter.Value.ValueChanged += StackAreaDimensions_Changed;
            StackAreaHeightParameter.Value.ValueChanged += StackAreaDimensions_Changed;
            InputStackSizeParameter.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);
            InputStack = new Stack(0, InputStackSize);
            RandomizeStackingAreas();
            Encoding.Bounds[0, 0] = 0;
            Encoding.Bounds[0, 1] = StackAreaWidth;
            MaximumMoves = StackAreaWidth * StackAreaHeight + 2 * InputStackSize;
            Encoding.Length = MaximumMoves;
        }
        #endregion

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

        public static double Evaluate(MoveVector moveVector, ref StackingArea newStackingArea, ref Stack inputStack, ref EvaluationResult result, StackingArea startStackArea, int stackAreaWidth, int stackAreaHeight)
        {
            int realMoves = 0;
            int moves = StackingArea.ApplyMoves(ref newStackingArea, ref inputStack, moveVector, out realMoves);

            int stillInStackingArea = 0;
            int stillInInputStack = inputStack.CurrentHeight;
            int score = 0;
            for (int stack = 0; stack < stackAreaWidth; stack++)
            {
                int containerCount = stackAreaHeight;

                for (int row = stackAreaHeight - 1; row >= 0; row--)
                {
                    if (newStackingArea[row, stack] == 0)
                    {
                        containerCount--;
                    }
                    else
                    {
                        int diff = 0;
                        if (row != stackAreaHeight - 1 && newStackingArea[row + 1, stack] != 0)
                        {
                            diff = newStackingArea[row, stack] - newStackingArea[row + 1, stack] - 1;
                        }
                        int atop = containerCount - row;
                        int rowScore = 0;
                        if (diff < 0)
                        {
                            rowScore = Convert.ToInt32(Math.Pow(diff, 2) + 20) * atop;
                        }
                        else
                        {
                            rowScore = diff * atop;
                        }
                        score = score + rowScore;
                    }
                }
                stillInStackingArea = stillInStackingArea + containerCount;
            }

            result.moves = realMoves;
            result.dislocated = stillInStackingArea + stillInInputStack;
            return moves * 2 + stillInInputStack * 1000 + score;
        }

        public override double Evaluate(Individual individual, IRandom random)
        {
            MoveVector moveVector = individual.MoveVector();
            StackingArea newStackingArea = (StackingArea)StartStackArea.Clone();
            Stack newInputStack = (Stack)InputStack.Clone();
            EvaluationResult result = new EvaluationResult();
            double quality = Evaluate(moveVector, ref newStackingArea, ref newInputStack, ref result, StartStackArea, StackAreaWidth, StackAreaHeight);
            if (BestKnownQuality.Equals(double.NaN) || quality < BestKnownQuality)
            {
                BestKnownQuality = quality;
                BestKnownSolution = moveVector;
                BestKnownStackArea = newStackingArea;
                BestKnownDislocated = new IntValue(result.dislocated);
                BestKnownMoves = new IntValue(result.moves);
            }
            return quality;
        }

        public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random)
        {
            base.Analyze(individuals, qualities, results, random);
            var orderedIndividuals = individuals.Zip(qualities, (i, q) => new { Individual = i, Quality = q }).OrderBy(z => z.Quality);
            var best = Maximization ? orderedIndividuals.Last().Individual : orderedIndividuals.First().Individual;
            if (!results.ContainsKey("Best Solution"))
            {
                results.Add(new Result("Best Solution", typeof(MoveVector)));
            }
            results["Best Solution"].Value = (IItem)best.MoveVector().Clone();

            EvaluationResult result = new EvaluationResult();
            StackingArea newStackingArea = (StackingArea)StartStackArea.Clone();
            Stack newInputStack = (Stack)InputStack.Clone();
            double quality = Evaluate(best.MoveVector(), ref newStackingArea, ref newInputStack, ref result, StartStackArea, StackAreaWidth, StackAreaHeight);

            if (!results.ContainsKey("Best Solution Moves"))
            {
                results.Add(new Result("Best Solution Moves", typeof(IntValue)));
            }
            results["Best Solution Moves"].Value = new IntValue(result.moves);

            if (!results.ContainsKey("Best Solution Dislocated"))
            {
                results.Add(new Result("Best Solution Dislocated", typeof(IntValue)));
            }
            results["Best Solution Dislocated"].Value = new IntValue(result.dislocated);

            /*
            if (!results.ContainsKey("Best Stacking Area"))
            {
                results.Add(new Result("Best Stacking Area", typeof(StackingArea)));
            }
            results["Best Stacking Area"].Value = newStackingArea;*/

            Analysis.DataTable moveHistory;
            if (!results.ContainsKey("Move History"))
            {
                string description = "Shows move amount.";
                moveHistory = new Analysis.DataTable("Amount of Moves", description);
                moveHistory.VisualProperties.XAxisTitle = "Iteration";
                moveHistory.VisualProperties.YAxisTitle = "Moves";
                results.Add(new Result("Move History", description, moveHistory));
            }
            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(result.moves);



            Analysis.DataTable dislocatedHistory;
            if (!results.ContainsKey("Dislocated History"))
            {
                string description = "Shows move amount.";
                dislocatedHistory = new Analysis.DataTable("Dislocated Containers", description);
                dislocatedHistory.VisualProperties.XAxisTitle = "Iteration";
                dislocatedHistory.VisualProperties.YAxisTitle = "Dislocated Containers";
                results.Add(new Result("Dislocated History", description, dislocatedHistory));
            }
            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(result.dislocated);
        }
    }
    public class EvaluationResult
    {
        public int moves;
        public int dislocated;
    }
}