1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)


4  *


5  * This file is part of HeuristicLab.


6  *


7  * HeuristicLab is free software: you can redistribute it and/or modify


8  * it under the terms of the GNU General Public License as published by


9  * the Free Software Foundation, either version 3 of the License, or


10  * (at your option) any later version.


11  *


12  * HeuristicLab is distributed in the hope that it will be useful,


13  * but WITHOUT ANY WARRANTY; without even the implied warranty of


14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


15  * GNU General Public License for more details.


16  *


17  * You should have received a copy of the GNU General Public License


18  * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.


19  */


20  #endregion


21 


22  using System;


23  using System.Linq;


24  using HeuristicLab.Common;


25  using HeuristicLab.Core;


26  using HeuristicLab.Data;


27  using HeuristicLab.Encodings.PermutationEncoding;


28  using HeuristicLab.Optimization;


29  using HeuristicLab.Parameters;


30  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


31  using HeuristicLab.Problems.Instances;


32 


33  namespace HeuristicLab.Problems.PermutationProblems {


34  [Item("Linear Ordering Problem (LOP)", "Represents a Linear Ordering Problem")]


35  [Creatable(CreatableAttribute.Categories.CombinatorialProblems)]


36  [StorableClass]


37  public sealed class LinearOrderingProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IProblemInstanceConsumer<LOPData>, IProblemInstanceExporter<LOPData>, IStorableContent {


38  private static readonly LOPData DefaultInstance = new LOPData() {


39  Name = "Linaer Ordering Problem (LOP)",


40  Description = "The default instance of the LOP in HeuristicLab",


41  Dimension = 4,


42  Matrix = new double[,] {


43  {0 ,3, 6 ,6},


44  {2 ,0, 8 ,4},


45  {4 ,2, 0 ,4},


46  {5 ,3, 8 ,0}


47  }


48  };


49 


50  public OptionalValueParameter<Permutation> BestKnownSolutionParameter


51  {


52  get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }


53  }


54  public Permutation BestKnownSolution


55  {


56  get { return BestKnownSolutionParameter.Value; }


57  set


58  {


59  BestKnownSolutionParameter.Value = value;


60  }


61  }


62 


63  public ValueParameter<DoubleMatrix> MatrixParameter


64  {


65  get { return (ValueParameter<DoubleMatrix>)Parameters["Matrix"]; }


66  }


67  public DoubleMatrix Matrix


68  {


69  get { return MatrixParameter.Value; }


70  set { MatrixParameter.Value = value; }


71  }


72 


73  public override bool Maximization { get { return true; } }


74 


75  [StorableConstructor]


76  private LinearOrderingProblem(bool deserializing) : base(deserializing) { }


77  private LinearOrderingProblem(LinearOrderingProblem original, Cloner cloner) : base(original, cloner) { }


78  public LinearOrderingProblem() {


79  Parameters.Add(new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution of this LOP instance."));


80  Parameters.Add(new ValueParameter<DoubleMatrix>("Matrix", "The matrix which contains the corresponding LOPvalues"));


81 


82  Load(DefaultInstance);


83  EvaluatorParameter.GetsCollected = false;


84  EvaluatorParameter.Hidden = true;


85 


86  Evaluator.QualityParameter.ActualName = "Superdiagonal";


87  }


88 


89  public override IDeepCloneable Clone(Cloner cloner) {


90  return new LinearOrderingProblem(this, cloner);


91  }


92 


93  public void Load(LOPData data) {


94  if (data.Matrix.GetLength(0) != data.Matrix.GetLength(1)) {


95  throw new ArgumentException("Matrix must be square");


96  }


97  if (data.BestKnownQuality.HasValue) {


98  BestKnownQuality = data.BestKnownQuality.Value;


99  }


100  Name = data.Name;


101  Description = data.Description;


102  Matrix = new DoubleMatrix(data.Matrix);


103  Encoding.Length = Matrix.Columns;


104 


105  if (data.BestKnownPermutation != null) {


106  int[] permut = data.BestKnownPermutation;


107  //Clean up if the first index = 1


108  if (!permut.Contains(0)) { permut = permut.Select(v => v  1).ToArray(); }


109 


110  BestKnownSolution = new Permutation(PermutationTypes.Absolute, permut);


111  BestKnownQuality = Evaluate(new Permutation(PermutationTypes.Absolute, permut), Matrix);


112  }


113  }


114 


115  public LOPData Export() {


116  var result = new LOPData {


117  Name = Name,


118  Description = Description,


119  BestKnownQuality = BestKnownQuality,


120  BestKnownPermutation = BestKnownSolution.ToArray(),


121  Dimension = Matrix.Rows,


122  Matrix = Matrix.CloneAsMatrix()


123  };


124 


125  return result;


126  }


127 


128  public override double Evaluate(Individual individual, IRandom random) {


129  return Evaluate(individual.Permutation(), Matrix);


130  }


131  private double Evaluate(Permutation permutation, DoubleMatrix matrix) {


132  double sum = 0;


133  for (int i = 1; i < matrix.Columns; i++) {


134  for (int j = 0; j < i; j++) {


135  sum += matrix[permutation[j], permutation[i]];


136  }


137  }


138 


139  return sum;


140  }


141  }


142  }

