#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 System.Threading; using HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Encodings.IntegerVectorEncoding; using HeuristicLab.Parameters; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; using HeuristicLab.Random; namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment { [Item("RandomButFeasibleSolutionCreator", "Creates a random, but feasible solution to the Generalized Quadratic Assignment Problem.")] [StorableClass] public class RandomFeasibleSolutionCreator : GQAPStochasticSolutionCreator { public IValueLookupParameter MaximumTriesParameter { get { return (IValueLookupParameter)Parameters["MaximumTries"]; } } public IValueLookupParameter CreateMostFeasibleSolutionParameter { get { return (IValueLookupParameter)Parameters["CreateMostFeasibleSolution"]; } } [StorableConstructor] protected RandomFeasibleSolutionCreator(bool deserializing) : base(deserializing) { } protected RandomFeasibleSolutionCreator(RandomFeasibleSolutionCreator original, Cloner cloner) : base(original, cloner) { } public RandomFeasibleSolutionCreator() : base() { Parameters.Add(new ValueLookupParameter("MaximumTries", "The maximum number of tries to create a feasible solution after which an exception is thrown. If it is set to 0 or a negative value there will be an infinite number of attempts.", new IntValue(100000))); Parameters.Add(new ValueLookupParameter("CreateMostFeasibleSolution", "If this is set to true the operator will always succeed, and outputs the solution with the least violation instead of throwing an exception.", new BoolValue(false))); } public override IDeepCloneable Clone(Cloner cloner) { return new RandomFeasibleSolutionCreator(this, cloner); } public static IntegerVector CreateSolution(IRandom random, GQAPInstance problemInstance, int maximumTries, bool createMostFeasibleSolution, CancellationToken cancel) { var capacities = problemInstance.Capacities; var demands = problemInstance.Demands; IntegerVector result = null; bool isFeasible = false; int counter = 0; double minViolation = double.MaxValue; var slack = new double[capacities.Length]; var assignment = new int[demands.Length]; while (!isFeasible) { cancel.ThrowIfCancellationRequested(); if (maximumTries > 0) { counter++; if (counter > maximumTries) { if (createMostFeasibleSolution) break; else throw new InvalidOperationException("A feasible solution could not be obtained after " + maximumTries + " attempts."); } } for (int i = 0; i < capacities.Length; i++) slack[i] = capacities[i]; foreach (var equipment in Enumerable.Range(0, demands.Length).Shuffle(random)) { var freeLocations = GetFreeLocations(equipment, demands, slack); assignment[equipment] = freeLocations.SampleRandom(random); slack[assignment[equipment]] -= demands[equipment]; } double violation = slack.Select(x => x < 0 ? -x : 0).Sum(); isFeasible = violation == 0; if (isFeasible || violation < minViolation) { result = new IntegerVector(assignment); minViolation = violation; } } return result; } protected override IntegerVector CreateRandomSolution(IRandom random, GQAPInstance problemInstance) { return CreateSolution(random, problemInstance, MaximumTriesParameter.ActualValue.Value, CreateMostFeasibleSolutionParameter.ActualValue.Value, CancellationToken); } private static IEnumerable GetFreeLocations(int equipment, DoubleArray demands, double[] freeCapacities) { var freeLocations = freeCapacities .Select((v, idx) => new KeyValuePair(idx, v)) .Where(x => x.Value >= demands[equipment]); if (!freeLocations.Any()) { freeLocations = freeCapacities .Select((v, idx) => new KeyValuePair(idx, v)) .OrderByDescending(x => x.Value) .Take(3); // if there are none, take the three where the free capacity is largest } return freeLocations.Select(x => x.Key); } } }