source: branches/2605_StackingProblems/HeuristicLab.Problems.BlocksRelocationProblem/3.3/BlocksRelocationProblem.cs @ 16189

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;

namespace HeuristicLab.Problems.BlocksRelocationProblem
{

    [Item("Blocks Relocation Problem (BRP)", "Represents a Blocks Relocation Problem.")]
    [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 111)]
    [StorableClass]
    public class BlocksRelocationProblem : 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<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 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 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 BlocksRelocationProblem(bool deserializing) : base(deserializing) { }
        public BlocksRelocationProblem(BlocksRelocationProblem alg, Cloner cloner) : base(alg, cloner)
        {
            RegisterEventHandlers();
        }
        public override IDeepCloneable Clone(Cloner cloner)
        {
            return new BlocksRelocationProblem(this, cloner);
        }
        [StorableHook(HookType.AfterDeserialization)]
        private void AfterDeserialization()
        {
            RegisterEventHandlers();
        }
        #endregion

        public BlocksRelocationProblem() {
            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>("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);
        }

        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;
        }

        #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 MaxiumumMoves_Changed(object sender, EventArgs e)
        {
            Encoding.Length = MaximumMoves;
        }

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

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

        public static double Evaluate(MoveVector moveVector, ref StackingArea area, ref EvaluationResult result)
        {
            int height = area.MaxHeight;
            int width = area.Size;
            int score = 0, dislocated = 0;
            int realMoves = 0;
            int moves = StackingArea.ApplyMoves(ref area, moveVector, out realMoves);
            
            for (int stack = 0; stack < width; stack++)
            {
                int containerCount = height;
                
                for (int row = height - 1; row >= 0; row--)
                {
                    if (area[row, stack] == 0)
                    {
                        containerCount--;
                    } else
                    {
                        int diff = 0;
                        if (row != height - 1 && area[row + 1, stack] != 0)
                        {
                            diff = area[row, stack] - area[row + 1, stack] - 1;
                        }
                        int atop = containerCount - row;
                        int rowScore = 0;
                        if (diff < 0)
                        {
                            dislocated++;
                            rowScore = Convert.ToInt32(Math.Pow(diff, 2) + 20) * atop;
                        } else
                        {
                            rowScore = diff * atop;
                        }
                        score = score + rowScore;
                    }
                }
            }
            result.moves = realMoves;
            result.dislocated = dislocated;
            return score * dislocated + moves;
        }

        public override double Evaluate(Individual individual, IRandom random)
        {
            MoveVector moveVector = individual.MoveVector();
            StackingArea newStackingArea = (StackingArea)StartStackArea.Clone();
            EvaluationResult result = new EvaluationResult();
            double quality = Evaluate(moveVector, ref newStackingArea, ref result);
            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 = orderedIndividuals.First().Individual;

            MoveVector moveVector = best.MoveVector();
            StackingArea newStackingArea = (StackingArea)StartStackArea.Clone();
            EvaluationResult result = new EvaluationResult();
            double quality = Evaluate(moveVector, ref newStackingArea, ref result);
            if (!results.ContainsKey("BestKnownQuality"))
            {
                results.Add(new Result("BestKnownQuality", typeof(DoubleValue)));
            }
            if (!results.ContainsKey("BestKnownSolution"))
            {
                results.Add(new Result("BestKnownSolution", typeof(MoveVector)));
            }
            if (!results.ContainsKey("BestKnownMoves"))
            {
                results.Add(new Result("BestKnownMoves", typeof(IntValue)));
            }
            if (!results.ContainsKey("BestKnownDislocated"))
            {
                results.Add(new Result("BestKnownDislocated", typeof(IntValue)));
            }
            if (!results.ContainsKey("BestKnownStackingArea"))
            {
                results.Add(new Result("BestKnownStackingArea", typeof(StackingArea)));
            }

            if (results["BestKnownQuality"].Value == null || ((DoubleValue)results["BestKnownQuality"].Value).Value > BestKnownQuality)
            {
                results["BestKnownQuality"].Value = new DoubleValue(BestKnownQuality);
                results["BestKnownSolution"].Value = (IItem)BestKnownSolution.Clone();
                results["BestKnownMoves"].Value = new IntValue(BestKnownMoves.Value);
                results["BestKnownDislocated"].Value = new IntValue(BestKnownDislocated.Value);
                results["BestKnownStackingArea"].Value = (IItem)BestKnownStackArea.Clone();
            }*/

            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);
        }
    }
    public class EvaluationResult
    {
        public int moves;
        public int dislocated;
    }
}