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