#region License Information /* HeuristicLab * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. * * HeuristicLab is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * HeuristicLab is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with HeuristicLab. If not, see . */ #endregion using System; using System.Collections.Generic; using System.Linq; using HEAL.Attic; using HeuristicLab.Analysis; using HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Encodings.IntegerVectorEncoding; using HeuristicLab.Optimization; using HeuristicLab.Optimization.Operators; using HeuristicLab.Parameters; using HeuristicLab.PluginInfrastructure; using HeuristicLab.Problems.Instances; using HEAL.Attic; namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment { [Item("Generalized Quadratic Assignment Problem (GQAP)", "The Generalized Quadratic Assignment Problem (GQAP) is a generalization of the QAP in that it allows to assign multiple facilities (here called equipment) to a single location. The problem is described in Lee, C.G., and Ma, Z. 2003. The Generalized Quadratic Assignment Problem. Technical Report M5S 3G8, University of Toronto, Canada.")] [Creatable(CreatableAttribute.Categories.CombinatorialProblems)] [StorableType("20DC9B2F-F667-425E-A235-B0192CCB1BF4")] public sealed class GQAP : SingleObjectiveBasicProblem, IProblemInstanceConsumer, IProblemInstanceConsumer, IProblemInstanceConsumer, IProblemInstanceConsumer, IProblemInstanceConsumer { public override bool Maximization { get { return false; } } [Storable] private bool initialized; // ABE: helper variable that defines if the constructor has completed #region Parameter Descriptions public static readonly string BestKnownQualityDescription = "The best known quality (if available)."; public static readonly string BestKnownSolutionDescription = "The best known solution (if available)."; public static readonly string BestKnownSolutionsDescription = "Contains an archive of best-known solutions regarding flow-distance quality and installation quality."; public static readonly string ProblemInstanceDescription = "The problem instance that is to be solved."; public static readonly string EvaluationDescription = "The evaluation result of a solution to the GQAP."; #endregion #region Parameter Properties public OptionalValueParameter BestKnownSolutionParameter { get { return (OptionalValueParameter)Parameters["BestKnownSolution"]; } } public OptionalValueParameter BestKnownSolutionsParameter { get { return (OptionalValueParameter)Parameters["BestKnownSolutions"]; } } public IValueParameter ProblemInstanceParameter { get { return (IValueParameter)Parameters["ProblemInstance"]; } } #endregion #region Properties public GQAPAssignment BestKnownSolution { get { return BestKnownSolutionParameter.Value; } set { BestKnownSolutionParameter.Value = value; } } public GQAPAssignmentArchive BestKnownSolutions { get { return BestKnownSolutionsParameter.Value; } set { BestKnownSolutionsParameter.Value = value; } } public GQAPInstance ProblemInstance { get { return ProblemInstanceParameter.Value; } set { ProblemInstanceParameter.Value = value; } } #endregion [StorableConstructor] private GQAP(StorableConstructorFlag _) : base(_) { } private GQAP(GQAP original, Cloner cloner) : base(original, cloner) { RegisterEventHandlers(); initialized = original.initialized; } public GQAP() : base() { Encoding = new IntegerVectorEncoding("Assignment"); Parameters.Add(new OptionalValueParameter("BestKnownSolution", BestKnownSolutionDescription, null, false)); Parameters.Add(new OptionalValueParameter("BestKnownSolutions", BestKnownSolutionsDescription, null, false)); Parameters.Add(new ValueParameter("ProblemInstance", "The problem instance that is to be solved.", new GQAPInstance(), false)); InitializeOperators(); RegisterEventHandlers(); initialized = true; Parameterize(); } public override IDeepCloneable Clone(Cloner cloner) { return new GQAP(this, cloner); } public override double Evaluate(Individual individual, IRandom random = null) { var assignment = individual.IntegerVector(); var evaluation = ProblemInstance.Evaluate(assignment); individual["Evaluation"] = evaluation; return ProblemInstance.ToSingleObjective(evaluation); } public double Evaluate(IntegerVector assignment) { var evaluation = ProblemInstance.Evaluate(assignment); return ProblemInstance.ToSingleObjective(evaluation); } public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random) { AnalyzeBestSolution(results, GetBestIndividual(individuals, qualities)); AnalyzeParetoArchive(results, individuals.Select(i => Tuple.Create((IntegerVector)i.IntegerVector().Clone(), (Evaluation)i["Evaluation"]))); } private void AnalyzeBestSolution(ResultCollection results, Tuple best) { var bestVector = best.Item1.IntegerVector(); var bestEvaluation = (Evaluation)best.Item1["Evaluation"]; IResult bestResult; if (!results.TryGetValue("Best Solution", out bestResult)) { bestResult = new Result("Best Solution", typeof(GQAPAssignment)); results.Add(bestResult); } var item = bestResult.Value as GQAPAssignment; if (item == null) bestResult.Value = new GQAPAssignment((IntegerVector)bestVector.Clone(), ProblemInstance, bestEvaluation); else if (ProblemInstance.ToSingleObjective(bestEvaluation) < ProblemInstance.ToSingleObjective(item.Solution.Evaluation)) { item.ProblemInstance = ProblemInstance; item.Solution = new GQAPSolution((IntegerVector)bestVector.Clone(), bestEvaluation); } } private void AnalyzeParetoArchive(ResultCollection results, IEnumerable> solutions) { IResult archiveResult; if (!results.TryGetValue("Solution Archive", out archiveResult)) { archiveResult = new Result("Solution Archive", typeof(GQAPAssignmentArchive)); results.Add(archiveResult); } var archive = archiveResult.Value as GQAPAssignmentArchive; if (archive == null) { archive = new GQAPAssignmentArchive(ProblemInstance); archiveResult.Value = archive; } else archive.ProblemInstance = ProblemInstance; var combinedArchive = solutions .Select(x => new GQAPSolution(x.Item1, x.Item2)) .Concat(archive.Solutions); archive.Solutions = GetFeasibleParetoFront(combinedArchive); if (BestKnownSolutions == null) { BestKnownSolutions = archive; } else { var combinedArchive2 = solutions .Select(x => new GQAPSolution(x.Item1, x.Item2)) .Concat(BestKnownSolutions.Solutions); BestKnownSolutions.Solutions = GetFeasibleParetoFront(combinedArchive2); } } #region Problem Instance Loading public void Load(QAPData data) { Name = data.Name; Description = data.Description; var weights = new DoubleMatrix(data.Weights); var distances = new DoubleMatrix(data.Distances); var installationCosts = new DoubleMatrix(weights.Rows, distances.Columns); // all zero var capacities = new DoubleArray(Enumerable.Range(0, distances.Rows).Select(x => 1.0).ToArray()); var demands = new DoubleArray(Enumerable.Range(0, weights.Rows).Select(x => 1.0).ToArray()); Load(demands, capacities, weights, distances, installationCosts, new DoubleValue(1)); EvaluateAndLoadAssignment(data.BestKnownAssignment); } public void Load(CTAPData data) { Name = data.Name; Description = data.Description; var capacities = new DoubleArray(data.MemoryCapacities); var demands = new DoubleArray(data.MemoryRequirements); var weights = new DoubleMatrix(data.CommunicationCosts); var installationCosts = new DoubleMatrix(data.ExecutionCosts.Transpose()); var distances = new DoubleMatrix(capacities.Length, capacities.Length); for (int i = 0; i < capacities.Length - 1; i++) for (int j = i + 1; j < capacities.Length; j++) { distances[i, j] = 1; } Load(demands, capacities, weights, distances, installationCosts, new DoubleValue(1)); EvaluateAndLoadAssignment(data.BestKnownAssignment); } public void Load(TSPData data) { if (data.Dimension > 1000) throw new System.IO.InvalidDataException("Instances with more than 1000 cities are not supported."); Name = data.Name; Description = data.Description; var capacities = new DoubleArray(data.Dimension); var demands = new DoubleArray(data.Dimension); for (int i = 0; i < data.Dimension; i++) { capacities[i] = 1; demands[i] = 1; } var installationCosts = new DoubleMatrix(data.Dimension, data.Dimension); var weights = new DoubleMatrix(data.Dimension, data.Dimension); for (int i = 0; i < data.Dimension; i++) weights[i, (i + 1) % data.Dimension] = 1; var distances = new DoubleMatrix(data.GetDistanceMatrix()); Load(demands, capacities, weights, distances, installationCosts, new DoubleValue(1)); EvaluateAndLoadAssignment(data.BestKnownTour); } public void Load(ATSPData data) { Name = data.Name; Description = data.Description; var capacities = new DoubleArray(data.Dimension); var demands = new DoubleArray(data.Dimension); for (int i = 0; i < data.Dimension; i++) { capacities[i] = 1; demands[i] = 1; } var installationCosts = new DoubleMatrix(data.Dimension, data.Dimension); var weights = new DoubleMatrix(data.Dimension, data.Dimension); for (int i = 0; i < data.Dimension; i++) weights[i, (i + 1) % data.Dimension] = 1; var distances = new DoubleMatrix(data.Distances); Load(demands, capacities, weights, distances, installationCosts, new DoubleValue(1)); EvaluateAndLoadAssignment(data.BestKnownTour); } public void Load(GQAPData data) { Name = data.Name; Description = data.Description; var capacities = new DoubleArray(data.Capacities); var demands = new DoubleArray(data.Demands); var installationCosts = new DoubleMatrix(data.InstallationCosts); var weights = new DoubleMatrix(data.Weights); var distances = new DoubleMatrix(data.Distances); var transportationCosts = new DoubleValue(data.TransportationCosts); Load(demands, capacities, weights, distances, installationCosts, transportationCosts); EvaluateAndLoadAssignment(data.BestKnownAssignment); if (data.BestKnownAssignment == null && data.BestKnownQuality.HasValue) { BestKnownQuality = data.BestKnownQuality.Value; } } public void Load(DoubleArray demands, DoubleArray capacities, DoubleMatrix weights, DoubleMatrix distances, DoubleMatrix installationCosts, DoubleValue transportationCosts) { if (weights == null || weights.Rows == 0) throw new System.IO.InvalidDataException( @"The given instance does not contain weights!"); if (weights.Rows != weights.Columns) throw new System.IO.InvalidDataException( @"The weights matrix of the given instance contains an unequal number of rows and columns."); if (distances == null || distances.Rows == 0) throw new System.IO.InvalidDataException( @"The given instance does not contain distances!"); if (distances.Rows != distances.Columns) throw new System.IO.InvalidDataException( @"The distances matrix of the given instance contains an unequal number of rows and columns."); if (installationCosts == null || installationCosts.Rows == 0) throw new System.IO.InvalidDataException( @"The given instance does not contain installation costs!"); if (installationCosts.Rows != weights.Rows || installationCosts.Columns != distances.Columns) throw new System.IO.InvalidDataException( @"The installation costs matrix of the given instance contains different number of rows than given in the weights matrix and a different number of columns than given in the distances matrix."); if (capacities == null || capacities.Length == 0) throw new System.IO.InvalidDataException( @"The given instance does not contain capacities!"); if (capacities.Length != distances.Rows) throw new System.IO.InvalidDataException( @"The given instance contains a different number of capacities than rows given in the distances matrix."); if (demands == null || demands.Length == 0) throw new System.IO.InvalidDataException( @"The given instance does not contain demands!"); if (demands.Length != weights.Rows) throw new System.IO.InvalidDataException( @"The given instance contains a different number of demands than rows given in the weights matrix."); if (transportationCosts == null) throw new System.IO.InvalidDataException( @"The given instance does not contain transportation costs."); ProblemInstance = new GQAPInstance() { Weights = weights, Distances = distances, InstallationCosts = installationCosts, Capacities = capacities, Demands = demands, TransportationCosts = transportationCosts.Value }; BestKnownQualityParameter.Value = null; BestKnownSolution = null; BestKnownSolutions = null; ProblemInstance.CalculatePenaltyLevel(); } private void EvaluateAndLoadAssignment(int[] vector) { if (vector == null || vector.Length == 0) return; EvaluateAndLoadAssignment(new IntegerVector(vector)); } public void EvaluateAndLoadAssignment(IntegerVector assignment) { if (!ProblemInstance.IsValid()) { BestKnownQualityParameter.Value = null; BestKnownSolution = null; BestKnownSolutions = null; return; } var evaluation = ProblemInstance.Evaluate(assignment); var quality = ProblemInstance.ToSingleObjective(evaluation); BestKnownSolution = new GQAPAssignment((IntegerVector)assignment.Clone(), ProblemInstance, evaluation); BestKnownQuality = quality; BestKnownSolutions = new GQAPAssignmentArchive(ProblemInstance); BestKnownSolutions.Solutions.Add(new GQAPSolution((IntegerVector)assignment.Clone(), evaluation)); } #endregion #region Events protected override void OnOperatorsChanged() { base.OnOperatorsChanged(); if (!initialized) return; Parameterize(); } protected override void OnEncodingChanged() { base.OnEncodingChanged(); if (!initialized) return; Parameterize(); } #endregion #region Helpers [StorableHook(HookType.AfterDeserialization)] private void AfterDeserialization() { RegisterEventHandlers(); } private void RegisterEventHandlers() { ProblemInstanceParameter.ValueChanged += ProblemInstanceParameterOnValueChanged; ProblemInstance.CapacitiesParameter.ValueChanged += ProblemInstanceCapacitiesParameterOnValueChanged; ProblemInstance.DemandsParameter.ValueChanged += ProblemInstanceDemandsParameterOnValueChanged; ProblemInstance.Capacities.Reset += ProblemInstanceCapacitiesOnReset; ProblemInstance.Demands.Reset += ProblemInstanceDemandsOnReset; } private void ProblemInstanceParameterOnValueChanged(object sender, EventArgs e) { ProblemInstance.CapacitiesParameter.ValueChanged += ProblemInstanceCapacitiesParameterOnValueChanged; ProblemInstance.Capacities.Reset += ProblemInstanceCapacitiesOnReset; ProblemInstance.DemandsParameter.ValueChanged += ProblemInstanceDemandsParameterOnValueChanged; ProblemInstance.Demands.Reset += ProblemInstanceDemandsOnReset; UpdateEncoding(); } private void ProblemInstanceCapacitiesParameterOnValueChanged(object sender, EventArgs e) { ProblemInstance.Capacities.Reset += ProblemInstanceCapacitiesOnReset; UpdateEncoding(); } private void ProblemInstanceDemandsParameterOnValueChanged(object sender, EventArgs e) { ProblemInstance.Demands.Reset += ProblemInstanceDemandsOnReset; UpdateEncoding(); } private void ProblemInstanceDemandsOnReset(object sender, EventArgs e) { UpdateEncoding(); } private void ProblemInstanceCapacitiesOnReset(object sender, EventArgs e) { UpdateEncoding(); } private void UpdateEncoding() { Encoding.Length = ProblemInstance.Demands.Length; Encoding.Bounds = new IntMatrix(new int[,] { { 0, ProblemInstance.Capacities.Length } }); } private void InitializeOperators() { Operators.RemoveAll(x => x is ISingleObjectiveMoveOperator); Operators.RemoveAll(x => x is SingleObjectiveImprover); Operators.AddRange(ApplicationManager.Manager.GetInstances()); Operators.AddRange(ApplicationManager.Manager.GetInstances()); Operators.Add(new HammingSimilarityCalculator() { SolutionVariableName = Encoding.Name, QualityVariableName = Evaluator.QualityParameter.ActualName }); Operators.Add(new QualitySimilarityCalculator() { SolutionVariableName = Encoding.Name, QualityVariableName = Evaluator.QualityParameter.ActualName }); Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType())); } private void Parameterize() { var operators = Operators.Union(new IOperator[] { SolutionCreator, Evaluator }).ToArray(); Encoding.ConfigureOperators(operators.OfType()); foreach (var op in operators.OfType()) { op.AssignmentParameter.ActualName = Encoding.Name; op.AssignmentParameter.Hidden = true; } foreach (var op in operators.OfType()) { op.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name; op.BestKnownQualityParameter.Hidden = true; } foreach (var op in operators.OfType()) { op.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name; op.BestKnownSolutionParameter.Hidden = true; } foreach (var op in operators.OfType()) { op.BestKnownSolutionsParameter.ActualName = BestKnownSolutionsParameter.Name; op.BestKnownSolutionsParameter.Hidden = true; } foreach (var op in operators.OfType()) { op.ParentsParameter.ActualName = Encoding.Name; op.ParentsParameter.Hidden = true; op.ChildParameter.ActualName = Encoding.Name; op.ChildParameter.Hidden = true; } var moveEvaluator = operators.OfType().FirstOrDefault(); foreach (var op in operators.OfType()) { // synchronize all move evaluators if (moveEvaluator != null) { op.MoveQualityParameter.ActualName = moveEvaluator.MoveQualityParameter.ActualName; op.MoveQualityParameter.Hidden = true; op.MoveEvaluationParameter.ActualName = "MoveEvaluation"; op.MoveEvaluationParameter.Hidden = true; } } foreach (var op in operators.OfType()) { if (moveEvaluator != null) { op.MoveQualityParameter.ActualName = moveEvaluator.MoveQualityParameter.ActualName; op.MoveQualityParameter.Hidden = true; op.MoveEvaluationParameter.ActualName = "MoveEvaluation"; op.MoveEvaluationParameter.Hidden = true; } } foreach (var op in operators.OfType()) { op.ProblemInstanceParameter.ActualName = ProblemInstanceParameter.Name; op.ProblemInstanceParameter.Hidden = true; } foreach (var op in operators.OfType()) { op.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName; op.QualityParameter.Hidden = true; op.EvaluationParameter.ActualName = "Evaluation"; op.EvaluationParameter.Hidden = true; } foreach (var op in operators.OfType()) { op.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName; op.QualityParameter.Hidden = true; op.EvaluationParameter.ActualName = "Evaluation"; op.EvaluationParameter.Hidden = true; } } #endregion public static ItemList GetFeasibleParetoFront(IEnumerable solutions) { var front = new ItemList(solutions.Where(x => x.Evaluation.IsFeasible)); for (int i = 0; i < front.Count - 1; i++) { for (int j = i + 1; j < front.Count; j++) { if (front[i].Evaluation.FlowCosts <= front[j].Evaluation.FlowCosts && front[i].Evaluation.InstallationCosts <= front[j].Evaluation.InstallationCosts) { front.RemoveAt(j); j--; } else if (front[i].Evaluation.FlowCosts >= front[j].Evaluation.FlowCosts && front[i].Evaluation.InstallationCosts >= front[j].Evaluation.InstallationCosts) { front.RemoveAt(i); j = i; } } } return front; } } }