[6956] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
[16728] | 3 | * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
[6956] | 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 |
|
---|
[7311] | 22 | using System;
|
---|
[15504] | 23 | using System.Collections.Generic;
|
---|
[6956] | 24 | using System.Linq;
|
---|
[16728] | 25 | using HEAL.Attic;
|
---|
[15504] | 26 | using HeuristicLab.Analysis;
|
---|
[6956] | 27 | using HeuristicLab.Common;
|
---|
| 28 | using HeuristicLab.Core;
|
---|
| 29 | using HeuristicLab.Data;
|
---|
| 30 | using HeuristicLab.Encodings.IntegerVectorEncoding;
|
---|
| 31 | using HeuristicLab.Optimization;
|
---|
[15504] | 32 | using HeuristicLab.Optimization.Operators;
|
---|
[6956] | 33 | using HeuristicLab.Parameters;
|
---|
| 34 | using HeuristicLab.PluginInfrastructure;
|
---|
[7443] | 35 | using HeuristicLab.Problems.Instances;
|
---|
[6956] | 36 |
|
---|
| 37 | namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
|
---|
[15490] | 38 | [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.")]
|
---|
[16728] | 39 | [Creatable(CreatableAttribute.Categories.CombinatorialProblems)]
|
---|
| 40 | [StorableType("20DC9B2F-F667-425E-A235-B0192CCB1BF4")]
|
---|
[15504] | 41 | public sealed class GQAP : SingleObjectiveBasicProblem<IntegerVectorEncoding>,
|
---|
[7548] | 42 | IProblemInstanceConsumer<QAPData>,
|
---|
| 43 | IProblemInstanceConsumer<CTAPData>,
|
---|
| 44 | IProblemInstanceConsumer<TSPData>,
|
---|
| 45 | IProblemInstanceConsumer<ATSPData>,
|
---|
| 46 | IProblemInstanceConsumer<GQAPData> {
|
---|
[7419] | 47 |
|
---|
[15504] | 48 | public override bool Maximization { get { return false; } }
|
---|
[6956] | 49 |
|
---|
[15506] | 50 | [Storable]
|
---|
| 51 | private bool initialized; // ABE: helper variable that defines if the constructor has completed
|
---|
| 52 |
|
---|
[7419] | 53 | #region Parameter Descriptions
|
---|
[7423] | 54 | public static readonly string BestKnownQualityDescription = "The best known quality (if available).";
|
---|
| 55 | public static readonly string BestKnownSolutionDescription = "The best known solution (if available).";
|
---|
[7438] | 56 | public static readonly string BestKnownSolutionsDescription = "Contains an archive of best-known solutions regarding flow-distance quality and installation quality.";
|
---|
[15504] | 57 | public static readonly string ProblemInstanceDescription = "The problem instance that is to be solved.";
|
---|
| 58 | public static readonly string EvaluationDescription = "The evaluation result of a solution to the GQAP.";
|
---|
[7419] | 59 | #endregion
|
---|
| 60 |
|
---|
[6956] | 61 | #region Parameter Properties
|
---|
[7470] | 62 | public OptionalValueParameter<GQAPAssignment> BestKnownSolutionParameter {
|
---|
| 63 | get { return (OptionalValueParameter<GQAPAssignment>)Parameters["BestKnownSolution"]; }
|
---|
[6956] | 64 | }
|
---|
[7438] | 65 | public OptionalValueParameter<GQAPAssignmentArchive> BestKnownSolutionsParameter {
|
---|
| 66 | get { return (OptionalValueParameter<GQAPAssignmentArchive>)Parameters["BestKnownSolutions"]; }
|
---|
| 67 | }
|
---|
[15504] | 68 | public IValueParameter<GQAPInstance> ProblemInstanceParameter {
|
---|
| 69 | get { return (IValueParameter<GQAPInstance>)Parameters["ProblemInstance"]; }
|
---|
[7415] | 70 | }
|
---|
[6956] | 71 | #endregion
|
---|
| 72 |
|
---|
| 73 | #region Properties
|
---|
[7470] | 74 | public GQAPAssignment BestKnownSolution {
|
---|
[7443] | 75 | get { return BestKnownSolutionParameter.Value; }
|
---|
| 76 | set { BestKnownSolutionParameter.Value = value; }
|
---|
| 77 | }
|
---|
[7448] | 78 | public GQAPAssignmentArchive BestKnownSolutions {
|
---|
| 79 | get { return BestKnownSolutionsParameter.Value; }
|
---|
| 80 | set { BestKnownSolutionsParameter.Value = value; }
|
---|
| 81 | }
|
---|
[15504] | 82 | public GQAPInstance ProblemInstance {
|
---|
| 83 | get { return ProblemInstanceParameter.Value; }
|
---|
| 84 | set { ProblemInstanceParameter.Value = value; }
|
---|
| 85 | }
|
---|
[6956] | 86 | #endregion
|
---|
| 87 |
|
---|
| 88 | [StorableConstructor]
|
---|
[16728] | 89 | private GQAP(StorableConstructorFlag _) : base(_) { }
|
---|
[15504] | 90 | private GQAP(GQAP original, Cloner cloner)
|
---|
[6956] | 91 | : base(original, cloner) {
|
---|
[7432] | 92 | RegisterEventHandlers();
|
---|
[15506] | 93 | initialized = original.initialized;
|
---|
[6956] | 94 | }
|
---|
[15504] | 95 | public GQAP() : base() {
|
---|
| 96 | Encoding = new IntegerVectorEncoding("Assignment");
|
---|
[16961] | 97 | Parameters.Add(new OptionalValueParameter<GQAPAssignment>("BestKnownSolution", BestKnownSolutionDescription, null) { GetsCollected = false });
|
---|
| 98 | Parameters.Add(new OptionalValueParameter<GQAPAssignmentArchive>("BestKnownSolutions", BestKnownSolutionsDescription, null) { GetsCollected = false });
|
---|
| 99 | Parameters.Add(new ValueParameter<GQAPInstance>("ProblemInstance", "The problem instance that is to be solved.", new GQAPInstance()) { GetsCollected = false });
|
---|
[6956] | 100 |
|
---|
[15504] | 101 | InitializeOperators();
|
---|
| 102 | RegisterEventHandlers();
|
---|
[15506] | 103 | initialized = true;
|
---|
| 104 | Parameterize();
|
---|
[15504] | 105 | }
|
---|
[6956] | 106 |
|
---|
[15504] | 107 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
| 108 | return new GQAP(this, cloner);
|
---|
| 109 | }
|
---|
[6956] | 110 |
|
---|
[15504] | 111 | public override double Evaluate(Individual individual, IRandom random = null) {
|
---|
| 112 | var assignment = individual.IntegerVector();
|
---|
| 113 | var evaluation = ProblemInstance.Evaluate(assignment);
|
---|
| 114 | individual["Evaluation"] = evaluation;
|
---|
| 115 | return ProblemInstance.ToSingleObjective(evaluation);
|
---|
| 116 | }
|
---|
[6956] | 117 |
|
---|
[15504] | 118 | public double Evaluate(IntegerVector assignment) {
|
---|
| 119 | var evaluation = ProblemInstance.Evaluate(assignment);
|
---|
| 120 | return ProblemInstance.ToSingleObjective(evaluation);
|
---|
| 121 | }
|
---|
[6956] | 122 |
|
---|
[15504] | 123 | public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random) {
|
---|
| 124 | AnalyzeBestSolution(results, GetBestIndividual(individuals, qualities));
|
---|
| 125 | AnalyzeParetoArchive(results,
|
---|
| 126 | individuals.Select(i => Tuple.Create((IntegerVector)i.IntegerVector().Clone(),
|
---|
| 127 | (Evaluation)i["Evaluation"])));
|
---|
| 128 | }
|
---|
[6956] | 129 |
|
---|
[15504] | 130 | private void AnalyzeBestSolution(ResultCollection results, Tuple<Individual, double> best) {
|
---|
| 131 | var bestVector = best.Item1.IntegerVector();
|
---|
| 132 | var bestEvaluation = (Evaluation)best.Item1["Evaluation"];
|
---|
[6956] | 133 |
|
---|
[15504] | 134 | IResult bestResult;
|
---|
| 135 | if (!results.TryGetValue("Best Solution", out bestResult)) {
|
---|
| 136 | bestResult = new Result("Best Solution", typeof(GQAPAssignment));
|
---|
| 137 | results.Add(bestResult);
|
---|
| 138 | }
|
---|
| 139 | var item = bestResult.Value as GQAPAssignment;
|
---|
| 140 | if (item == null) bestResult.Value = new GQAPAssignment((IntegerVector)bestVector.Clone(), ProblemInstance, bestEvaluation);
|
---|
| 141 | else if (ProblemInstance.ToSingleObjective(bestEvaluation)
|
---|
[16728] | 142 | < ProblemInstance.ToSingleObjective(item.Solution.Evaluation)) {
|
---|
[15504] | 143 | item.ProblemInstance = ProblemInstance;
|
---|
[16728] | 144 | item.Solution = new GQAPSolution((IntegerVector)bestVector.Clone(), bestEvaluation);
|
---|
[15504] | 145 | }
|
---|
[6956] | 146 | }
|
---|
| 147 |
|
---|
[15504] | 148 | private void AnalyzeParetoArchive(ResultCollection results, IEnumerable<Tuple<IntegerVector, Evaluation>> solutions) {
|
---|
| 149 | IResult archiveResult;
|
---|
| 150 | if (!results.TryGetValue("Solution Archive", out archiveResult)) {
|
---|
| 151 | archiveResult = new Result("Solution Archive", typeof(GQAPAssignmentArchive));
|
---|
| 152 | results.Add(archiveResult);
|
---|
| 153 | }
|
---|
| 154 | var archive = archiveResult.Value as GQAPAssignmentArchive;
|
---|
[15510] | 155 | if (archive == null) {
|
---|
| 156 | archive = new GQAPAssignmentArchive(ProblemInstance);
|
---|
| 157 | archiveResult.Value = archive;
|
---|
| 158 | } else archive.ProblemInstance = ProblemInstance;
|
---|
[15504] | 159 |
|
---|
| 160 | var combinedArchive = solutions
|
---|
| 161 | .Select(x => new GQAPSolution(x.Item1, x.Item2))
|
---|
| 162 | .Concat(archive.Solutions);
|
---|
| 163 | archive.Solutions = GetFeasibleParetoFront(combinedArchive);
|
---|
| 164 |
|
---|
| 165 | if (BestKnownSolutions == null) {
|
---|
| 166 | BestKnownSolutions = archive;
|
---|
| 167 | } else {
|
---|
| 168 | var combinedArchive2 = solutions
|
---|
| 169 | .Select(x => new GQAPSolution(x.Item1, x.Item2))
|
---|
| 170 | .Concat(BestKnownSolutions.Solutions);
|
---|
| 171 | BestKnownSolutions.Solutions = GetFeasibleParetoFront(combinedArchive2);
|
---|
| 172 | }
|
---|
[6956] | 173 | }
|
---|
| 174 |
|
---|
[7548] | 175 | #region Problem Instance Loading
|
---|
| 176 | public void Load(QAPData data) {
|
---|
| 177 | Name = data.Name;
|
---|
| 178 | Description = data.Description;
|
---|
[7448] | 179 |
|
---|
[7548] | 180 | var weights = new DoubleMatrix(data.Weights);
|
---|
| 181 | var distances = new DoubleMatrix(data.Distances);
|
---|
| 182 | var installationCosts = new DoubleMatrix(weights.Rows, distances.Columns); // all zero
|
---|
| 183 | var capacities = new DoubleArray(Enumerable.Range(0, distances.Rows).Select(x => 1.0).ToArray());
|
---|
| 184 | var demands = new DoubleArray(Enumerable.Range(0, weights.Rows).Select(x => 1.0).ToArray());
|
---|
[7443] | 185 |
|
---|
[7548] | 186 | Load(demands, capacities, weights, distances, installationCosts, new DoubleValue(1));
|
---|
| 187 | EvaluateAndLoadAssignment(data.BestKnownAssignment);
|
---|
| 188 | }
|
---|
[7445] | 189 |
|
---|
[7548] | 190 | public void Load(CTAPData data) {
|
---|
| 191 | Name = data.Name;
|
---|
| 192 | Description = data.Description;
|
---|
| 193 |
|
---|
| 194 | var capacities = new DoubleArray(data.MemoryCapacities);
|
---|
| 195 | var demands = new DoubleArray(data.MemoryRequirements);
|
---|
| 196 | var weights = new DoubleMatrix(data.CommunicationCosts);
|
---|
| 197 | var installationCosts = new DoubleMatrix(data.ExecutionCosts.Transpose());
|
---|
| 198 | var distances = new DoubleMatrix(capacities.Length, capacities.Length);
|
---|
| 199 | for (int i = 0; i < capacities.Length - 1; i++)
|
---|
| 200 | for (int j = i + 1; j < capacities.Length; j++) {
|
---|
| 201 | distances[i, j] = 1;
|
---|
[7466] | 202 | }
|
---|
[7548] | 203 |
|
---|
| 204 | Load(demands, capacities, weights, distances, installationCosts, new DoubleValue(1));
|
---|
| 205 | EvaluateAndLoadAssignment(data.BestKnownAssignment);
|
---|
[7443] | 206 | }
|
---|
| 207 |
|
---|
[7548] | 208 | public void Load(TSPData data) {
|
---|
| 209 | if (data.Dimension > 1000)
|
---|
| 210 | throw new System.IO.InvalidDataException("Instances with more than 1000 cities are not supported.");
|
---|
[7448] | 211 |
|
---|
[7548] | 212 | Name = data.Name;
|
---|
| 213 | Description = data.Description;
|
---|
[7466] | 214 |
|
---|
[7548] | 215 | var capacities = new DoubleArray(data.Dimension);
|
---|
| 216 | var demands = new DoubleArray(data.Dimension);
|
---|
| 217 | for (int i = 0; i < data.Dimension; i++) {
|
---|
| 218 | capacities[i] = 1;
|
---|
| 219 | demands[i] = 1;
|
---|
| 220 | }
|
---|
| 221 | var installationCosts = new DoubleMatrix(data.Dimension, data.Dimension);
|
---|
| 222 | var weights = new DoubleMatrix(data.Dimension, data.Dimension);
|
---|
| 223 | for (int i = 0; i < data.Dimension; i++)
|
---|
| 224 | weights[i, (i + 1) % data.Dimension] = 1;
|
---|
| 225 | var distances = new DoubleMatrix(data.GetDistanceMatrix());
|
---|
[7466] | 226 |
|
---|
[7548] | 227 | Load(demands, capacities, weights, distances, installationCosts, new DoubleValue(1));
|
---|
| 228 | EvaluateAndLoadAssignment(data.BestKnownTour);
|
---|
| 229 | }
|
---|
| 230 |
|
---|
| 231 | public void Load(ATSPData data) {
|
---|
| 232 | Name = data.Name;
|
---|
| 233 | Description = data.Description;
|
---|
| 234 |
|
---|
| 235 | var capacities = new DoubleArray(data.Dimension);
|
---|
| 236 | var demands = new DoubleArray(data.Dimension);
|
---|
| 237 | for (int i = 0; i < data.Dimension; i++) {
|
---|
| 238 | capacities[i] = 1;
|
---|
| 239 | demands[i] = 1;
|
---|
[7466] | 240 | }
|
---|
[7548] | 241 | var installationCosts = new DoubleMatrix(data.Dimension, data.Dimension);
|
---|
| 242 | var weights = new DoubleMatrix(data.Dimension, data.Dimension);
|
---|
| 243 | for (int i = 0; i < data.Dimension; i++)
|
---|
| 244 | weights[i, (i + 1) % data.Dimension] = 1;
|
---|
| 245 | var distances = new DoubleMatrix(data.Distances);
|
---|
| 246 |
|
---|
| 247 | Load(demands, capacities, weights, distances, installationCosts, new DoubleValue(1));
|
---|
| 248 | EvaluateAndLoadAssignment(data.BestKnownTour);
|
---|
[7466] | 249 | }
|
---|
[7445] | 250 |
|
---|
[7548] | 251 | public void Load(GQAPData data) {
|
---|
| 252 | Name = data.Name;
|
---|
| 253 | Description = data.Description;
|
---|
[7470] | 254 |
|
---|
[7548] | 255 | var capacities = new DoubleArray(data.Capacities);
|
---|
| 256 | var demands = new DoubleArray(data.Demands);
|
---|
| 257 | var installationCosts = new DoubleMatrix(data.InstallationCosts);
|
---|
| 258 | var weights = new DoubleMatrix(data.Weights);
|
---|
| 259 | var distances = new DoubleMatrix(data.Distances);
|
---|
| 260 | var transportationCosts = new DoubleValue(data.TransportationCosts);
|
---|
[7445] | 261 |
|
---|
[7548] | 262 | Load(demands, capacities, weights, distances, installationCosts, transportationCosts);
|
---|
| 263 | EvaluateAndLoadAssignment(data.BestKnownAssignment);
|
---|
[7466] | 264 |
|
---|
[7548] | 265 | if (data.BestKnownAssignment == null && data.BestKnownQuality.HasValue) {
|
---|
[15504] | 266 | BestKnownQuality = data.BestKnownQuality.Value;
|
---|
[7445] | 267 | }
|
---|
| 268 | }
|
---|
| 269 |
|
---|
[7548] | 270 | public void Load(DoubleArray demands, DoubleArray capacities,
|
---|
| 271 | DoubleMatrix weights, DoubleMatrix distances, DoubleMatrix installationCosts,
|
---|
[7970] | 272 | DoubleValue transportationCosts) {
|
---|
[7548] | 273 | if (weights == null || weights.Rows == 0)
|
---|
| 274 | throw new System.IO.InvalidDataException(
|
---|
| 275 | @"The given instance does not contain weights!");
|
---|
| 276 | if (weights.Rows != weights.Columns)
|
---|
| 277 | throw new System.IO.InvalidDataException(
|
---|
[7970] | 278 | @"The weights matrix of the given instance contains
|
---|
| 279 | an unequal number of rows and columns.");
|
---|
[7548] | 280 | if (distances == null || distances.Rows == 0)
|
---|
| 281 | throw new System.IO.InvalidDataException(
|
---|
| 282 | @"The given instance does not contain distances!");
|
---|
| 283 | if (distances.Rows != distances.Columns)
|
---|
| 284 | throw new System.IO.InvalidDataException(
|
---|
[7970] | 285 | @"The distances matrix of the given instance contains
|
---|
| 286 | an unequal number of rows and columns.");
|
---|
[7548] | 287 | if (installationCosts == null || installationCosts.Rows == 0)
|
---|
| 288 | throw new System.IO.InvalidDataException(
|
---|
| 289 | @"The given instance does not contain installation costs!");
|
---|
| 290 | if (installationCosts.Rows != weights.Rows
|
---|
| 291 | || installationCosts.Columns != distances.Columns)
|
---|
| 292 | throw new System.IO.InvalidDataException(
|
---|
[7970] | 293 | @"The installation costs matrix of the given instance
|
---|
| 294 | contains different number of rows than given in the
|
---|
| 295 | weights matrix and a different number of columns than
|
---|
[7548] | 296 | given in the distances matrix.");
|
---|
| 297 | if (capacities == null || capacities.Length == 0)
|
---|
| 298 | throw new System.IO.InvalidDataException(
|
---|
| 299 | @"The given instance does not contain capacities!");
|
---|
| 300 | if (capacities.Length != distances.Rows)
|
---|
| 301 | throw new System.IO.InvalidDataException(
|
---|
[7970] | 302 | @"The given instance contains a different number of
|
---|
| 303 | capacities than rows given in the distances matrix.");
|
---|
[7548] | 304 | if (demands == null || demands.Length == 0)
|
---|
| 305 | throw new System.IO.InvalidDataException(
|
---|
| 306 | @"The given instance does not contain demands!");
|
---|
| 307 | if (demands.Length != weights.Rows)
|
---|
| 308 | throw new System.IO.InvalidDataException(
|
---|
[7970] | 309 | @"The given instance contains a different number of
|
---|
| 310 | demands than rows given in the weights matrix.");
|
---|
[7548] | 311 | if (transportationCosts == null)
|
---|
| 312 | throw new System.IO.InvalidDataException(
|
---|
| 313 | @"The given instance does not contain transportation costs.");
|
---|
[7523] | 314 |
|
---|
[15504] | 315 | ProblemInstance = new GQAPInstance() {
|
---|
| 316 | Weights = weights,
|
---|
| 317 | Distances = distances,
|
---|
| 318 | InstallationCosts = installationCosts,
|
---|
| 319 | Capacities = capacities,
|
---|
| 320 | Demands = demands,
|
---|
| 321 | TransportationCosts = transportationCosts.Value
|
---|
| 322 | };
|
---|
| 323 | BestKnownQualityParameter.Value = null;
|
---|
[7548] | 324 | BestKnownSolution = null;
|
---|
| 325 | BestKnownSolutions = null;
|
---|
[15504] | 326 | ProblemInstance.CalculatePenaltyLevel();
|
---|
[7523] | 327 | }
|
---|
[7445] | 328 | private void EvaluateAndLoadAssignment(int[] vector) {
|
---|
[7548] | 329 | if (vector == null || vector.Length == 0) return;
|
---|
[7471] | 330 | EvaluateAndLoadAssignment(new IntegerVector(vector));
|
---|
| 331 | }
|
---|
[7548] | 332 | public void EvaluateAndLoadAssignment(IntegerVector assignment) {
|
---|
[15504] | 333 | if (!ProblemInstance.IsValid()) {
|
---|
| 334 | BestKnownQualityParameter.Value = null;
|
---|
[7523] | 335 | BestKnownSolution = null;
|
---|
| 336 | BestKnownSolutions = null;
|
---|
[15504] | 337 | return;
|
---|
[7523] | 338 | }
|
---|
[15504] | 339 | var evaluation = ProblemInstance.Evaluate(assignment);
|
---|
| 340 | var quality = ProblemInstance.ToSingleObjective(evaluation);
|
---|
| 341 |
|
---|
| 342 | BestKnownSolution = new GQAPAssignment((IntegerVector)assignment.Clone(), ProblemInstance, evaluation);
|
---|
| 343 | BestKnownQuality = quality;
|
---|
| 344 | BestKnownSolutions = new GQAPAssignmentArchive(ProblemInstance);
|
---|
| 345 | BestKnownSolutions.Solutions.Add(new GQAPSolution((IntegerVector)assignment.Clone(), evaluation));
|
---|
[7445] | 346 | }
|
---|
[7548] | 347 | #endregion
|
---|
[7445] | 348 |
|
---|
[6956] | 349 | #region Events
|
---|
[7311] | 350 | protected override void OnOperatorsChanged() {
|
---|
| 351 | base.OnOperatorsChanged();
|
---|
[15506] | 352 | if (!initialized) return;
|
---|
[7311] | 353 | Parameterize();
|
---|
| 354 | }
|
---|
[15504] | 355 | protected override void OnEncodingChanged() {
|
---|
| 356 | base.OnEncodingChanged();
|
---|
[15506] | 357 | if (!initialized) return;
|
---|
[7311] | 358 | Parameterize();
|
---|
| 359 | }
|
---|
[6956] | 360 | #endregion
|
---|
| 361 |
|
---|
| 362 | #region Helpers
|
---|
| 363 | [StorableHook(HookType.AfterDeserialization)]
|
---|
[7412] | 364 | private void AfterDeserialization() {
|
---|
[7432] | 365 | RegisterEventHandlers();
|
---|
[6956] | 366 | }
|
---|
| 367 |
|
---|
[7432] | 368 | private void RegisterEventHandlers() {
|
---|
[15504] | 369 | ProblemInstanceParameter.ValueChanged += ProblemInstanceParameterOnValueChanged;
|
---|
| 370 | ProblemInstance.CapacitiesParameter.ValueChanged += ProblemInstanceCapacitiesParameterOnValueChanged;
|
---|
| 371 | ProblemInstance.DemandsParameter.ValueChanged += ProblemInstanceDemandsParameterOnValueChanged;
|
---|
| 372 | ProblemInstance.Capacities.Reset += ProblemInstanceCapacitiesOnReset;
|
---|
| 373 | ProblemInstance.Demands.Reset += ProblemInstanceDemandsOnReset;
|
---|
[6956] | 374 | }
|
---|
| 375 |
|
---|
[15504] | 376 | private void ProblemInstanceParameterOnValueChanged(object sender, EventArgs e) {
|
---|
| 377 | ProblemInstance.CapacitiesParameter.ValueChanged += ProblemInstanceCapacitiesParameterOnValueChanged;
|
---|
| 378 | ProblemInstance.Capacities.Reset += ProblemInstanceCapacitiesOnReset;
|
---|
| 379 | ProblemInstance.DemandsParameter.ValueChanged += ProblemInstanceDemandsParameterOnValueChanged;
|
---|
| 380 | ProblemInstance.Demands.Reset += ProblemInstanceDemandsOnReset;
|
---|
| 381 | UpdateEncoding();
|
---|
| 382 | }
|
---|
| 383 | private void ProblemInstanceCapacitiesParameterOnValueChanged(object sender, EventArgs e) {
|
---|
| 384 | ProblemInstance.Capacities.Reset += ProblemInstanceCapacitiesOnReset;
|
---|
| 385 | UpdateEncoding();
|
---|
| 386 | }
|
---|
| 387 | private void ProblemInstanceDemandsParameterOnValueChanged(object sender, EventArgs e) {
|
---|
| 388 | ProblemInstance.Demands.Reset += ProblemInstanceDemandsOnReset;
|
---|
| 389 | UpdateEncoding();
|
---|
| 390 | }
|
---|
| 391 | private void ProblemInstanceDemandsOnReset(object sender, EventArgs e) {
|
---|
| 392 | UpdateEncoding();
|
---|
| 393 | }
|
---|
| 394 | private void ProblemInstanceCapacitiesOnReset(object sender, EventArgs e) {
|
---|
| 395 | UpdateEncoding();
|
---|
| 396 | }
|
---|
| 397 |
|
---|
| 398 | private void UpdateEncoding() {
|
---|
| 399 | Encoding.Length = ProblemInstance.Demands.Length;
|
---|
| 400 | Encoding.Bounds = new IntMatrix(new int[,] { { 0, ProblemInstance.Capacities.Length } });
|
---|
| 401 | }
|
---|
| 402 |
|
---|
[6956] | 403 | private void InitializeOperators() {
|
---|
[15510] | 404 | Operators.RemoveAll(x => x is ISingleObjectiveMoveOperator);
|
---|
| 405 | Operators.RemoveAll(x => x is SingleObjectiveImprover);
|
---|
[7415] | 406 | Operators.AddRange(ApplicationManager.Manager.GetInstances<IGQAPOperator>());
|
---|
[7413] | 407 | Operators.AddRange(ApplicationManager.Manager.GetInstances<IGQAPMoveEvaluator>());
|
---|
[15506] | 408 | Operators.Add(new HammingSimilarityCalculator() { SolutionVariableName = Encoding.Name, QualityVariableName = Evaluator.QualityParameter.ActualName });
|
---|
| 409 | Operators.Add(new QualitySimilarityCalculator() { SolutionVariableName = Encoding.Name, QualityVariableName = Evaluator.QualityParameter.ActualName });
|
---|
[15504] | 410 |
|
---|
| 411 | Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
|
---|
[6956] | 412 | }
|
---|
[7311] | 413 |
|
---|
| 414 | private void Parameterize() {
|
---|
[7419] | 415 | var operators = Operators.Union(new IOperator[] { SolutionCreator, Evaluator }).ToArray();
|
---|
[15506] | 416 | Encoding.ConfigureOperators(operators.OfType<IOperator>());
|
---|
| 417 | foreach (var op in operators.OfType<IAssignmentAwareGQAPOperator>()) {
|
---|
| 418 | op.AssignmentParameter.ActualName = Encoding.Name;
|
---|
| 419 | op.AssignmentParameter.Hidden = true;
|
---|
| 420 | }
|
---|
[7419] | 421 | foreach (var op in operators.OfType<IBestKnownQualityAwareGQAPOperator>()) {
|
---|
| 422 | op.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
|
---|
[7970] | 423 | op.BestKnownQualityParameter.Hidden = true;
|
---|
[7419] | 424 | }
|
---|
| 425 | foreach (var op in operators.OfType<IBestKnownSolutionAwareGQAPOperator>()) {
|
---|
| 426 | op.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
|
---|
[7970] | 427 | op.BestKnownSolutionParameter.Hidden = true;
|
---|
[7419] | 428 | }
|
---|
[7438] | 429 | foreach (var op in operators.OfType<IBestKnownSolutionsAwareGQAPOperator>()) {
|
---|
| 430 | op.BestKnownSolutionsParameter.ActualName = BestKnownSolutionsParameter.Name;
|
---|
[7970] | 431 | op.BestKnownSolutionsParameter.Hidden = true;
|
---|
[7438] | 432 | }
|
---|
[7419] | 433 | foreach (var op in operators.OfType<IGQAPCrossover>()) {
|
---|
[15504] | 434 | op.ParentsParameter.ActualName = Encoding.Name;
|
---|
[7970] | 435 | op.ParentsParameter.Hidden = true;
|
---|
[15504] | 436 | op.ChildParameter.ActualName = Encoding.Name;
|
---|
[7970] | 437 | op.ChildParameter.Hidden = true;
|
---|
[7319] | 438 | }
|
---|
[7419] | 439 | var moveEvaluator = operators.OfType<IGQAPMoveEvaluator>().FirstOrDefault();
|
---|
| 440 | foreach (var op in operators.OfType<IGQAPMoveEvaluator>()) { // synchronize all move evaluators
|
---|
| 441 | if (moveEvaluator != null) {
|
---|
| 442 | op.MoveQualityParameter.ActualName = moveEvaluator.MoveQualityParameter.ActualName;
|
---|
[7970] | 443 | op.MoveQualityParameter.Hidden = true;
|
---|
[15504] | 444 | op.MoveEvaluationParameter.ActualName = "MoveEvaluation";
|
---|
| 445 | op.MoveEvaluationParameter.Hidden = true;
|
---|
[7419] | 446 | }
|
---|
| 447 | }
|
---|
| 448 | foreach (var op in operators.OfType<IMoveQualityAwareGQAPOperator>()) {
|
---|
| 449 | if (moveEvaluator != null) {
|
---|
| 450 | op.MoveQualityParameter.ActualName = moveEvaluator.MoveQualityParameter.ActualName;
|
---|
[7970] | 451 | op.MoveQualityParameter.Hidden = true;
|
---|
[15504] | 452 | op.MoveEvaluationParameter.ActualName = "MoveEvaluation";
|
---|
| 453 | op.MoveEvaluationParameter.Hidden = true;
|
---|
[7419] | 454 | }
|
---|
| 455 | }
|
---|
[15504] | 456 | foreach (var op in operators.OfType<IProblemInstanceAwareGQAPOperator>()) {
|
---|
| 457 | op.ProblemInstanceParameter.ActualName = ProblemInstanceParameter.Name;
|
---|
| 458 | op.ProblemInstanceParameter.Hidden = true;
|
---|
[7419] | 459 | }
|
---|
| 460 | foreach (var op in operators.OfType<IQualitiesAwareGQAPOperator>()) {
|
---|
[7412] | 461 | op.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
|
---|
[7970] | 462 | op.QualityParameter.Hidden = true;
|
---|
[15504] | 463 | op.EvaluationParameter.ActualName = "Evaluation";
|
---|
| 464 | op.EvaluationParameter.Hidden = true;
|
---|
[7407] | 465 | }
|
---|
[7419] | 466 | foreach (var op in operators.OfType<IQualityAwareGQAPOperator>()) {
|
---|
[7412] | 467 | op.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
|
---|
[7970] | 468 | op.QualityParameter.Hidden = true;
|
---|
[15504] | 469 | op.EvaluationParameter.ActualName = "Evaluation";
|
---|
| 470 | op.EvaluationParameter.Hidden = true;
|
---|
[7412] | 471 | }
|
---|
[15504] | 472 | }
|
---|
| 473 | #endregion
|
---|
[7407] | 474 |
|
---|
[15504] | 475 | public static ItemList<GQAPSolution> GetFeasibleParetoFront(IEnumerable<GQAPSolution> solutions) {
|
---|
| 476 | var front = new ItemList<GQAPSolution>(solutions.Where(x => x.Evaluation.IsFeasible));
|
---|
[7970] | 477 |
|
---|
[15504] | 478 | for (int i = 0; i < front.Count - 1; i++) {
|
---|
| 479 | for (int j = i + 1; j < front.Count; j++) {
|
---|
| 480 | if (front[i].Evaluation.FlowCosts <= front[j].Evaluation.FlowCosts
|
---|
| 481 | && front[i].Evaluation.InstallationCosts <= front[j].Evaluation.InstallationCosts) {
|
---|
| 482 | front.RemoveAt(j);
|
---|
| 483 | j--;
|
---|
| 484 | } else if (front[i].Evaluation.FlowCosts >= front[j].Evaluation.FlowCosts
|
---|
| 485 | && front[i].Evaluation.InstallationCosts >= front[j].Evaluation.InstallationCosts) {
|
---|
| 486 | front.RemoveAt(i);
|
---|
| 487 | j = i;
|
---|
| 488 | }
|
---|
| 489 | }
|
---|
[7970] | 490 | }
|
---|
[15504] | 491 | return front;
|
---|
[6956] | 492 | }
|
---|
| 493 | }
|
---|
| 494 | }
|
---|