Free cookie consent management tool by TermsFeed Policy Generator

Changeset 15533 for branches


Ignore:
Timestamp:
12/18/17 14:38:18 (7 years ago)
Author:
ddorfmei
Message:

#2747: Improved hard-coded genetic algorithm

  • implemented restart strategy
  • implemented 1-Opt algorithm
  • added parameters to control restart strategy and optimal assignment strategy
  • additional results: best solution found after number of generations, jobs/nests (for evaluation only)
Location:
branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3
Files:
4 edited
1 copied
1 moved

Legend:

Unmodified
Added
Removed

  • branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/CFSAP.cs

    r15493 r15533  
    112112
    113113    public int Evaluate(Permutation order, BinaryVector assignment) {
    114       return EvaluateAssignement(order, assignment, ProcessingTimes, SetupTimes);
     114      return EvaluateAssignment(order, assignment, ProcessingTimes, SetupTimes);
    115115    }
    116116
    … …  
    147147
    148148    //Function to evaluate individual with the specified assignment
    149     public static int EvaluateAssignement(Permutation order, BinaryVector assignment, IntMatrix processingTimes, ItemList<IntMatrix> setupTimes) {
     149    public static int EvaluateAssignment(Permutation order, BinaryVector assignment, IntMatrix processingTimes, ItemList<IntMatrix> setupTimes) {
    150150      if (processingTimes.Rows != 2) throw new ArgumentException("Method can only be used when there are two machines.", "assignment");
    151151      var N = order.Length;

  • branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/GeneticAlgorithm.cs

    r15493 r15533  
    3535
    3636namespace HeuristicLab.Problems.Scheduling.CFSAP {
     37  public enum OptimalAssignmentType { None, Polynomial, OneOpt, Both };
     38
    3739  [Item("Genetic Algorithm (CFSAP)", "")]
    3840  [StorableClass]
    … …  
    7981      get { return pauseAfterGenerationParameter; }
    8082    }
     83    [Storable]
     84    private IFixedValueParameter<EnumValue<OptimalAssignmentType>> optimalAssignmentParameter;
     85    public IFixedValueParameter<EnumValue<OptimalAssignmentType>> OptimalAssignmentParameter {
     86      get { return optimalAssignmentParameter; }
     87    }
    8188
    8289    public int PopulationSize {
    … …  
    103110      get { return pauseAfterGenerationParameter.Value.Value; }
    104111      set { pauseAfterGenerationParameter.Value.Value = value; }
     112    }
     113    public OptimalAssignmentType OptimalAssignment {
     114      get { return optimalAssignmentParameter.Value.Value; }
     115      set { optimalAssignmentParameter.Value.Value = value; }
    105116    }
    106117
    … …  
    115126      maximumEvaluatedSolutionsParameter = cloner.Clone(original.maximumEvaluatedSolutionsParameter);
    116127      pauseAfterGenerationParameter = cloner.Clone(original.pauseAfterGenerationParameter);
     128      optimalAssignmentParameter = cloner.Clone(original.optimalAssignmentParameter);
     129
    117130      generation = original.generation;
    118131      evaluatedSolutions = original.evaluatedSolutions;
    119132      bestQuality = original.bestQuality;
     133
    120134      if (original.population != null)
    121135        population = original.population.Select(cloner.Clone).ToArray();
    … …  
    126140    }
    127141    public GeneticAlgorithm() {
    128       Parameters.Add(populationSizeParameter = new FixedValueParameter<IntValue>("PopulationSize", "The size of the population, each individual of the population is a solution with a permutation and a binary vector.", new IntValue(100)));
     142      Parameters.Add(populationSizeParameter = new FixedValueParameter<IntValue>("PopulationSize", "The size of the population, each individual of the population is a solution with a permutation and a binary vector.", new IntValue(500)));
    129143      Parameters.Add(elitesParameter = new FixedValueParameter<IntValue>("Elites", "The number of best individuals from the previous population that will continue to the next generation.", new IntValue(1)));
    130144      Parameters.Add(mutationProbabilityParameter = new FixedValueParameter<PercentValue>("MutationProbability", "The probability that an individual should be mutated after it has been created through crossover.", new PercentValue(0.05)));
    … …  
    132146      Parameters.Add(maximumEvaluatedSolutionsParameter = new FixedValueParameter<IntValue>("MaximumEvaluatedSolutions", "The number of evaluated solutions before the algorithm terminates.", new IntValue(100000000)));
    133147      Parameters.Add(pauseAfterGenerationParameter = new FixedValueParameter<BoolValue>("PauseAfterGeneration", "Whether the algorithm should pause after each generation.", new BoolValue(true)));
     148      Parameters.Add(optimalAssignmentParameter = new FixedValueParameter<EnumValue<OptimalAssignmentType>>("OptimalAssignment", "Which optimal assignment strategy should be used.", new EnumValue<OptimalAssignmentType>(OptimalAssignmentType.Polynomial)));
    134149    }
    135150
    … …  
    194209            Assignment = CrossAssignment(parent1.Assignment, parent2.Assignment)
    195210          };
     211
    196212          var mutProb = random.NextDouble();
    197213          if (mutProb < MutationProbability) {
    … …  
    199215            MutateAssignment(nextGeneration[p].Assignment);
    200216          }
     217
    201218          nextGeneration[p].Quality = Problem.Evaluate(nextGeneration[p].Sequence, nextGeneration[p].Assignment);
    202219          evaluatedSolutions++;
    203220
    204221          if (nextGeneration[p].Quality <= bestQuality) {
    205             if (!optimalSequences.Contains(nextGeneration[p].Sequence)) {
    206               int cycleTime;
    207               var assignment = OptimalAssignment.MakeAssignment(nextGeneration[p].Sequence, Problem.ProcessingTimes, Problem.SetupTimes, out cycleTime);
    208               evaluatedSolutions++;
    209               nextGeneration[p].Assignment = new BinaryVector(assignment.Select(x => x == 1).ToArray());
    210               nextGeneration[p].Quality = cycleTime;
    211               optimalSequences.Add(nextGeneration[p].Sequence);
     222            switch (OptimalAssignment) {
     223              case OptimalAssignmentType.None:
     224                break;
     225              case OptimalAssignmentType.Polynomial:
     226                OptimalPolynomialAssignment(nextGeneration[p]);
     227                break;
     228              case OptimalAssignmentType.OneOpt:
     229                OneOptAssignment(nextGeneration[p]);
     230                break;
     231              case OptimalAssignmentType.Both:
     232                HybridAssignment(nextGeneration[p]);
     233                break;
     234              default:
     235                throw new InvalidOperationException("Optimal assignment strategy not defined.");
    212236            }
    213             if (nextGeneration[p].Quality < bestQuality) {
     237
     238          if (nextGeneration[p].Quality < bestQuality) {
    214239              bestQuality = nextGeneration[p].Quality;
    215240              ((DoubleValue)Results["BestQuality"].Value).Value = bestQuality;
    … …  
    232257          break;
    233258        }
     259      }
     260    }
     261
     262    private void OptimalPolynomialAssignment(EncodedSolution generation) {
     263      if (!optimalSequences.Contains(generation.Sequence)) {
     264        var assignment = Scheduling.CFSAP.OptimalPolynomialAssignment.MakeAssignment(generation.Sequence, Problem.ProcessingTimes, Problem.SetupTimes, out var cycleTime);
     265        evaluatedSolutions++;
     266        generation.Assignment = new BinaryVector(assignment.Select(x => x == 1).ToArray());
     267        generation.Quality = cycleTime;
     268        optimalSequences.Add(generation.Sequence);
     269      }
     270    }
     271
     272    private void OneOptAssignment(EncodedSolution generation) {
     273      var assignment = Scheduling.CFSAP.OneOptAssignment.MakeAssignment(generation.Sequence, generation.Assignment, Problem.ProcessingTimes, Problem.SetupTimes, out var cycleTime);
     274      evaluatedSolutions++;
     275      generation.Assignment = assignment;
     276      generation.Quality = cycleTime;
     277    }
     278
     279    private void HybridAssignment(EncodedSolution generation) {
     280      var a = random.Next(2);
     281      switch (a) {
     282        case 0: OptimalPolynomialAssignment(generation); break;
     283        case 1: OneOptAssignment(generation); break;
     284        default: throw new InvalidOperationException("Assignment not defined.");
    234285      }
    235286    }
    … …  
    257308
    258309    private void MutateSequence(Permutation sequence) {
    259       var cx = random.Next(7);
    260       switch (cx) {
     310      var m = random.Next(7);
     311      switch (m) {
    261312        case 0: InversionManipulator.Apply(random, sequence); break;
    262313        case 1: InsertionManipulator.Apply(random, sequence); break;
    … …  
    266317        case 5: TranslocationInversionManipulator.Apply(random, sequence); break;
    267318        case 6: ScrambleManipulator.Apply(random, sequence); break;
    268         default: throw new InvalidOperationException("Crossover not defined.");
     319        default: throw new InvalidOperationException("Manipulator not defined.");
    269320      }
    270321    }
    … …  
    284335    }
    285336
    286     private class EncodedSolution : IDeepCloneable, IComparable<EncodedSolution> {
     337    [StorableClass]
     338    private class EncodedSolution : DeepCloneable, IComparable<EncodedSolution> {
     339      [Storable]
    287340      public Permutation Sequence { get; set; }
     341      [Storable]
    288342      public BinaryVector Assignment { get; set; }
     343      [Storable]
    289344      public double Quality { get; set; }
    290345
    291       public IDeepCloneable Clone(Cloner cloner) {
    292         return new EncodedSolution() {
    293           Sequence = cloner.Clone(this.Sequence),
    294           Assignment = cloner.Clone(this.Assignment),
    295           Quality = this.Quality
    296         };
    297       }
    298 
    299       public object Clone() {
    300         return Clone(new Cloner());
     346      [StorableConstructor]
     347      private EncodedSolution(bool deserializing) { }
     348
     349      private EncodedSolution(EncodedSolution original, Cloner cloner) : base(original, cloner) {
     350        Sequence = cloner.Clone(original.Sequence);
     351        Assignment = cloner.Clone(original.Assignment);
     352        Quality = original.Quality;
     353      }
     354
     355      public EncodedSolution() { }
     356
     357      public override IDeepCloneable Clone(Cloner cloner) {
     358        return new EncodedSolution(this, cloner);
    301359      }
    302360

  • branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/HeuristicLab.Problems.Scheduling.CFSAP-3.3.csproj

    r15493 r15533  
    130130    <Compile Include="MultiNestCFSAP.cs" />
    131131    <Compile Include="MultiNestCFSAPSolvingStrategy.cs" />
    132     <Compile Include="OptimalAssignment.cs" />
     132    <Compile Include="OneOptAssignment.cs" />
     133    <Compile Include="OptimalPolynomialAssignment.cs" />
    133134    <Compile Include="Plugin.cs" />
    134135    <None Include="Properties\AssemblyInfo.cs.frame" />

  • branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/MultiNestCFSAPSolvingStrategy.cs

    r15472 r15533  
    1212
    1313namespace HeuristicLab.Problems.Scheduling.CFSAP {
    14   [Item("MultiNest CFSAP Solver", "Solving strategy that applies an algorithm instace to the worst nest.")]
     14  [Item("MultiNest CFSAP Solver", "Solving strategy that applies an algorithm instance to the worst nest.")]
    1515  [StorableClass]
    1616  [Creatable(CreatableAttribute.Categories.Algorithms)]
    … …  
    3333    }
    3434
    35 
    3635    public IFixedValueParameter<StringValue> EvaluatedSolutionsNameParameter {
    3736      get { return (IFixedValueParameter<StringValue>)Parameters["EvaluatedSolutionsName"]; }
     37    }
     38
     39    public IValueParameter<BoolValue> RestartParameter {
     40      get { return (IValueParameter<BoolValue>)Parameters["Restart"]; }
     41    }
     42
     43    public IValueParameter<IntValue> MinTriesParameter {
     44      get { return (IValueParameter<IntValue>)Parameters["Restart.MinTries"]; }
     45    }
     46
     47    public IValueParameter<DoubleValue> LastSuccessPercentageParameter {
     48      get { return (IValueParameter<DoubleValue>)Parameters["Restart.LastSuccessPercentage"]; }
    3849    }
    3950
    … …  
    5364    }
    5465
     66    public bool Restart {
     67      get => RestartParameter.Value.Value;
     68      set => RestartParameter.Value.Value = value;
     69    }
     70
     71    public int MinTries {
     72      get => MinTriesParameter.Value.Value;
     73      set => MinTriesParameter.Value.Value = value;
     74    }
     75
     76    public double LastSuccessPercentage {
     77      get => LastSuccessPercentageParameter.Value.Value;
     78      set => LastSuccessPercentageParameter.Value.Value = value;
     79    }
     80
    5581    [StorableConstructor]
    5682    protected MultiNestCFSAPSolvingStrategy(bool deserializing) : base(deserializing) { }
     83
    5784    protected MultiNestCFSAPSolvingStrategy(MultiNestCFSAPSolvingStrategy original, Cloner cloner)
    5885      : base(original, cloner) {
    … …  
    6794      if (original.qualityPerEvaluations != null)
    6895        qualityPerEvaluations = cloner.Clone(original.qualityPerEvaluations);
    69     }
     96
     97      restart = original.restart;
     98      minTries = original.minTries;
     99      lastSuccessPercentage = original.lastSuccessPercentage;
     100    }
     101
    70102    public MultiNestCFSAPSolvingStrategy() {
    71103      Parameters.Add(new ValueParameter<IAlgorithm>("Solver", "The actual solver template.") { GetsCollected = false });
    72104      Parameters.Add(new FixedValueParameter<TimeSpanValue>("MaximumRuntime", "The maximum time that the strategy should run.", new TimeSpanValue(TimeSpan.FromSeconds(60))));
    73105      Parameters.Add(new FixedValueParameter<StringValue>("EvaluatedSolutionsName", "The name of the result that shows the number of evaluated solutions by the actual solver.", new StringValue("EvaluatedSolutions")));
    74     }
    75    
     106      Parameters.Add(new ValueParameter<BoolValue>("Restart", "Whether the worst algorithm should be restarted, if it doesn't find any better solutions.", new BoolValue(restart)));
     107      Parameters.Add(new ValueParameter<IntValue>("Restart.MinTries", "The minimum number of tries before the worst algorithm is restarted.", new IntValue(minTries)));
     108      Parameters.Add(new ValueParameter<DoubleValue>("Restart.LastSuccessPercentage", "Only if the last found best solution is older than x percent of the total number of tries, the worst algorithm is restarted.", new DoubleValue(lastSuccessPercentage)));
     109    }
     110
    76111    public override IDeepCloneable Clone(Cloner cloner) {
    77112      return new MultiNestCFSAPSolvingStrategy(this, cloner);
    78113    }
    79 
    80114
    81115    [StorableHook(HookType.AfterDeserialization)]
    … …  
    83117      if (!Parameters.ContainsKey("EvaluatedSolutionsName"))
    84118        Parameters.Add(new FixedValueParameter<StringValue>("EvaluatedSolutionsName", "The name of the result that shows the number of evaluated solutions by the actual solver.", new StringValue("EvaluatedSolutions")));
     119      if (!Parameters.ContainsKey("Restart"))
     120        Parameters.Add(new ValueParameter<BoolValue>(nameof(Restart), "Whether the worst algorithm should be restarted, if it doesn't find any better solutions.", new BoolValue(restart)));
     121      if (!Parameters.ContainsKey("Restart.MinTries"))
     122        Parameters.Add(new ValueParameter<IntValue>("Restart.MinTries", "The minimum number of tries before the worst algorithm is restarted.", new IntValue(minTries)));
     123      if (!Parameters.ContainsKey("Restart.LastSuccessPercentage"))
     124        Parameters.Add(new ValueParameter<DoubleValue>("Restart.LastSuccessPercentage", "Only if the last found best solution is older than x percent of the total number of tries, the worst algorithm is restarted.", new DoubleValue(lastSuccessPercentage)));
    85125    }
    86126
    … …  
    95135    [Storable]
    96136    private IndexedDataTable<double> qualityPerEvaluations;
     137    [Storable]
     138    private bool restart = true;
     139    [Storable]
     140    private int minTries = 10000;
     141    [Storable]
     142    private double lastSuccessPercentage = 0.1;
    97143
    98144    protected override void OnPrepared() {
    … …  
    117163        cfsap.UpdateEncoding();
    118164        algorithms.Add(clone);
    119         algorithmsResults.Add(new Result("Nest " + (n + 1), clone.Results));
     165        algorithmsResults.Add(new Result($"Nest {n + 1}", clone.Results));
    120166        clone.Start();
    121167      }
    … …  
    133179      qualityPerEvaluations.Rows.Add(qpeRow);
    134180      double evaluations = GetEvaluatedSolutions();
    135       qpeRow.Values.Add(Tuple.Create((double)evaluations, (double)min));
    136       qpeRow.Values.Add(Tuple.Create((double)evaluations, (double)min));
     181      qpeRow.Values.Add(Tuple.Create(evaluations, (double)min));
     182      qpeRow.Values.Add(Tuple.Create(evaluations, (double)min));
    137183
    138184      Results.Add(new Result("Nest with maximum T", new IntValue(worst.Index + 1)));
    139185      Results.Add(new Result("Maximum T", new IntValue(min)));
    140186      Results.Add(new Result("BestQuality", new DoubleValue(min)));
     187      Results.Add(new Result("Best Solution Found After Evaluated Solutions", new DoubleValue(evaluations)));
    141188      Results.Add(new Result("Best Solution Found At", new TimeSpanValue(ExecutionTime)));
    142189      Results.Add(new Result("Delta T", new PercentValue((min - Problem.BestKnownQuality) / Problem.BestKnownQuality)));
    … …  
    144191      Results.Add(new Result("QualityPerClock", qualityPerClock));
    145192      Results.Add(new Result("QualityPerEvaluations", qualityPerEvaluations));
     193      Results.Add(new Result("Tries", new IntValue(nests)));
     194      Results.Add(new Result("Nests", new IntValue(nests)));
     195      Results.Add(new Result("Jobs", new IntValue(Problem.ProcessingTimes.First().Count() / Problem.SetupTimes.First().Count())));
    146196
    147197      base.Initialize(cancellationToken);
    … …  
    149199
    150200    private double GetEvaluatedSolutions() {
    151       if (algorithmsResults == null) throw new InvalidOperationException("Strategy has not been started yet.");
     201      if (algorithmsResults == null)
     202        throw new InvalidOperationException("Strategy has not been started yet.");
    152203      return algorithmsResults.Select(x => {
    153         IResult res;
    154         if (((ResultCollection)x.Value).TryGetValue(EvaluatedSolutionsName, out res)) {
     204        if (((ResultCollection)x.Value).TryGetValue(EvaluatedSolutionsName, out var res)) {
    155205          var itm = res.Value;
    156           if (itm is IntValue) return ((IntValue)itm).Value;
    157           else if (itm is DoubleValue) return ((DoubleValue)itm).Value;
     206          if (itm is IntValue)
     207            return ((IntValue)itm).Value;
     208          else if (itm is DoubleValue)
     209            return ((DoubleValue)itm).Value;
    158210        }
    159         throw new InvalidOperationException("No result " + EvaluatedSolutionsName + " in the collection of " + x.Name);
     211        throw new InvalidOperationException($"No result {EvaluatedSolutionsName} in the collection of {x.Name}");
    160212      }).Sum();
    161213    }
    162214
    163215    protected override void Run(CancellationToken cancellationToken) {
     216      var evaluationsPrevTries = 0.0;
    164217      var worst = qualities.Select((v, i) => new { Index = i, Quality = v }).MaxItems(x => x.Quality).First();
    165218      var min = worst.Quality;
    166219
    167       while (ExecutionTime < MaximumRuntime) {
    168         algorithms[worst.Index].Start(cancellationToken);
    169         qualities[worst.Index] = (int)((DoubleValue)algorithms[worst.Index].Results["BestQuality"].Value).Value;
    170         worst = qualities.Select((v, i) => new { Index = i, Quality = v }).MaxItems(x => x.Quality).First();
    171 
    172         var evaluations = GetEvaluatedSolutions();
    173         var time = ExecutionTime.TotalSeconds;
    174         var qpcRow = qualityPerClock.Rows.First();
    175         var qpeRow = qualityPerEvaluations.Rows.First();
    176         qpcRow.Values[qpcRow.Values.Count - 1] = Tuple.Create(time, (double)min);
    177         qpeRow.Values[qpeRow.Values.Count - 1] = Tuple.Create(evaluations, (double)min);
    178 
    179         if (worst.Quality < min) {
    180           min = worst.Quality;
    181           ((IntValue)Results["Nest with maximum T"].Value).Value = worst.Index + 1;
    182           ((IntValue)Results["Maximum T"].Value).Value = min;
    183           ((DoubleValue)Results["BestQuality"].Value).Value = min;
    184           ((TimeSpanValue)Results["Best Solution Found At"].Value).Value = TimeSpan.FromSeconds(time);
    185           ((PercentValue)Results["Delta T"].Value).Value = (min - Problem.BestKnownQuality) / Problem.BestKnownQuality;
    186           qpcRow.Values.Add(Tuple.Create(time, (double)min));
    187           qpeRow.Values.Add(Tuple.Create(evaluations, (double)min));
     220      var overallBestQualities = algorithms.Select(a => ((DoubleValue)a.Results["BestQuality"].Value).Value).ToArray();
     221
     222      do {
     223        var tries = 0;
     224        var lastSuccess = 0;
     225
     226        while (ExecutionTime < MaximumRuntime && !cancellationToken.IsCancellationRequested &&
     227            (!Restart || (tries < MinTries || (tries - lastSuccess) < tries * LastSuccessPercentage))) {
     228          ++tries;
     229          ++((IntValue)Results["Tries"].Value).Value;
     230
     231          algorithms[worst.Index].Start(cancellationToken);
     232          qualities[worst.Index] = (int)((DoubleValue)algorithms[worst.Index].Results["BestQuality"].Value).Value;
     233          worst = qualities.Select((v, i) => new { Index = i, Quality = v }).MaxItems(x => x.Quality).First();
     234
     235          var evaluations = evaluationsPrevTries + GetEvaluatedSolutions();
     236          var time = ExecutionTime.TotalSeconds;
     237          var qpcRow = qualityPerClock.Rows.First();
     238          var qpeRow = qualityPerEvaluations.Rows.First();
     239          qpcRow.Values[qpcRow.Values.Count - 1] = Tuple.Create(time, (double)Math.Min(worst.Quality, min));
     240          qpeRow.Values[qpeRow.Values.Count - 1] = Tuple.Create(evaluations, (double)Math.Min(worst.Quality, min));
     241
     242          if (worst.Quality < min) {
     243            min = worst.Quality;
     244            overallBestQualities[worst.Index] = min;
     245            ((IntValue)Results["Nest with maximum T"].Value).Value = worst.Index + 1;
     246            ((IntValue)Results["Maximum T"].Value).Value = min;
     247            ((DoubleValue)Results["BestQuality"].Value).Value = min;
     248            ((DoubleValue)Results["Best Solution Found After Evaluated Solutions"].Value).Value = evaluations;
     249            ((TimeSpanValue)Results["Best Solution Found At"].Value).Value = TimeSpan.FromSeconds(time);
     250            ((PercentValue)Results["Delta T"].Value).Value = (min - Problem.BestKnownQuality) / Problem.BestKnownQuality;
     251            qpcRow.Values.Add(Tuple.Create(time, (double)min));
     252            qpeRow.Values.Add(Tuple.Create(evaluations, (double)min));
     253            lastSuccess = tries;
     254          }
    188255        }
    189256
    190         if (cancellationToken.IsCancellationRequested) return;
     257        if (cancellationToken.IsCancellationRequested || ExecutionTime >= MaximumRuntime || !Restart)
     258          break;
     259
     260        evaluationsPrevTries += GetEvaluatedSolutions();
     261
     262        // restart worst algorithm
     263        var worstAlgorithm = algorithms[worst.Index];
     264        var prevGenerations = ((IntValue)worstAlgorithm.Results["Generation"].Value).Value;
     265        var prevEvaluatedSolutions = ((IntValue)worstAlgorithm.Results["EvaluatedSolutions"].Value).Value;
     266
     267        worstAlgorithm.Prepare();
     268        worstAlgorithm.Start(cancellationToken);
     269        ++((IntValue)Results["Tries"].Value).Value;
     270
     271        ((IntValue)worstAlgorithm.Results["Generation"].Value).Value += prevGenerations;
     272        ((IntValue)worstAlgorithm.Results["EvaluatedSolutions"].Value).Value += prevEvaluatedSolutions;
     273      } while (Restart);
     274
     275      for (var i = 0; i < algorithms.Count(); ++i) {
     276        if (overallBestQualities[i] < ((DoubleValue)algorithms[i].Results["BestQuality"].Value).Value) {
     277          ((DoubleValue)algorithms[i].Results["BestQuality"].Value).Value = overallBestQualities[i];
     278        }
    191279      }
    192280    }

  • branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/OneOptAssignment.cs

    r15493 r15533  
    2323using HeuristicLab.Core;
    2424using HeuristicLab.Data;
     25using HeuristicLab.Encodings.BinaryVectorEncoding;
    2526using HeuristicLab.Encodings.PermutationEncoding;
    2627
    2728namespace HeuristicLab.Problems.Scheduling.CFSAP {
    28   public static class OptimalAssignment {
     29  public static class OneOptAssignment {
    2930
    30     public static int[] MakeAssignment(Permutation order, IntMatrix processingTimes, ItemList<IntMatrix> setupTimes, out int T) {
    31       var N = order.Length;
     31    public static BinaryVector MakeAssignment(Permutation order, BinaryVector assignment, IntMatrix processingTimes, ItemList<IntMatrix> setupTimes, out int T) {
     32      var oneOptAssignment = (BinaryVector)assignment.Clone();
     33      T = CFSAP.EvaluateAssignment(order, assignment, processingTimes, setupTimes);
    3234
    33       int[,,] weights = new int[2, 2 * N, 2 * N];
    34       int[,] graph = new int[2, N];
    35       int[,] prevPath = new int[2, N + 1];                     //Only for optimal assignment evaluation
    36       int[] optimalAssignment = new int[N];                //Only for optimal assignment evaluation
     35      while (true) {
     36        var foundBetterSolution = false;
    3737
    38       //Calculate weights in the graph
    39       for (int S = 0; S < N; S++) { //Starting point of the arc
    40         for (int sM = 0; sM < 2; sM++) {    //Starting point machine
    41           int eM = sM == 0 ? 1 : 0;
    42           weights[sM, S, S + 1] = 0;
    43 
    44           for (int E = S + 2; E < S + N; E++)
    45             weights[sM, S, E] =
    46               weights[sM, S, E - 1] +
    47               processingTimes[eM, order[(E - 1) % N]] +
    48               setupTimes[eM][order[(E - 1) % N], order[E % N]];
    49 
    50           for (int E = S + 1; E < S + N; E++)
    51             weights[sM, S, E] += (
    52               processingTimes[sM, order[S % N]] +
    53               setupTimes[sM][order[S % N], order[(E + 1) % N]]
    54             );
    55         }
    56       }
    57 
    58       //Determine the shortest path in the graph
    59       T = int.MaxValue / 2;
    60       for (int S = 0; S < N - 1; S++)      //Start node in graph          O(N)
    61         for (int SM = 0; SM < 2; SM++) {   //Start node machine in graph  O(1)
    62           graph[SM, S] = 0;
    63           graph[SM == 0 ? 1 : 0, S] = int.MaxValue / 2;
    64           prevPath[SM, 0] = -1;
    65           for (int E = S + 1; E < N; E++)      //Currently calculated node          O(N)
    66             for (int EM = 0; EM < 2; EM++) {   //Currently calculated node machine  O(1)
    67               graph[EM, E] = int.MaxValue / 2;
    68               for (int EC = S; EC < E; EC++) { //Nodes connected to node E          O(N)
    69                 int newWeight = graph[EM == 0 ? 1 : 0, EC] + weights[EM == 0 ? 1 : 0, EC, E];
    70                 if (newWeight < graph[EM, E]) {
    71                   graph[EM, E] = newWeight;
    72                   prevPath[EM, E] = EC;
    73                 }
    74               }
    75             }
    76 
    77           int EP = S + N; //End point.
    78           int newT = int.MaxValue / 2;
    79           for (int EC = S + 1; EC < N; EC++) { //Nodes connected to EP O(N)
    80             int newWeight = graph[SM == 0 ? 1 : 0, EC] + weights[SM == 0 ? 1 : 0, EC, EP];
    81             if (newWeight < newT) {
    82               newT = newWeight;
    83               prevPath[SM, S] = EC;
    84             }
    85           }
    86 
    87           if (newT < T) {
     38        for (var i = 0; i < oneOptAssignment.Length; ++i) {
     39          var newAssignment = (BinaryVector)oneOptAssignment.Clone();
     40          newAssignment[i] = !newAssignment[i];
     41          int newT = CFSAP.EvaluateAssignment(order, newAssignment, processingTimes, setupTimes);
     42          if (newT < T) { // new best solution has been found
     43            oneOptAssignment = newAssignment;
    8844            T = newT;
    89             optimalAssignment = MakeAssignement(S, SM, prevPath, order);
     45            foundBetterSolution = true;
     46            break;
    9047          }
    9148        }
    9249
    93       //Omitted solutions
    94       for (int machine = 0; machine < 2; machine++) {
    95         int[] assignment = Enumerable.Repeat(machine, N).ToArray();
    96         int newT = CFSAP.EvaluateAssignement(order, assignment, processingTimes, setupTimes);
    97         if (newT < T) { //New best solution has been found
    98           T = newT;
    99           optimalAssignment = assignment;
    100         }
     50        if (!foundBetterSolution)
     51          return oneOptAssignment;
    10152      }
    102 
    103       return optimalAssignment;
    104     }
    105 
    106     private static int[] MakeAssignement(int start, int startMach, int[,] prevPath, Permutation order) {
    107       var N = order.Length;
    108       int[] assignment = Enumerable.Repeat(-1, N).ToArray();
    109       var inverseOrder = new int[N];
    110 
    111       for (int i = 0; i < N; i++)
    112         inverseOrder[order[i]] = i;
    113 
    114       int end = start + N;
    115 
    116       int currMach = startMach;
    117       int currNode = start;
    118       while (true) {
    119         assignment[inverseOrder[currNode]] = currMach;
    120         currNode = prevPath[currMach, currNode];
    121         currMach = currMach == 0 ? 1 : 0;
    122         if (currNode == start)
    123           break;
    124       }
    125 
    126       currMach = startMach;
    127       for (int i = 0; i < N; i++) {
    128         if (assignment[inverseOrder[i]] != -1)
    129           currMach = currMach == 0 ? 1 : 0;
    130         else
    131           assignment[inverseOrder[i]] = currMach;
    132       }
    133 
    134       return assignment;
    13553    }
    13654  }

  • branches/CFSAP/HeuristicLab.Problems.Scheduling.CFSAP/3.3/OptimalPolynomialAssignment.cs

    r15532 r15533  
    2626
    2727namespace HeuristicLab.Problems.Scheduling.CFSAP {
    28   public static class OptimalAssignment {
     28  public static class OptimalPolynomialAssignment {
    2929
    3030    public static int[] MakeAssignment(Permutation order, IntMatrix processingTimes, ItemList<IntMatrix> setupTimes, out int T) {
    … …  
    3333      int[,,] weights = new int[2, 2 * N, 2 * N];
    3434      int[,] graph = new int[2, N];
    35       int[,] prevPath = new int[2, N + 1];                     //Only for optimal assignment evaluation
    36       int[] optimalAssignment = new int[N];                //Only for optimal assignment evaluation
     35      int[,] prevPath = new int[2, N + 1];    //Only for optimal assignment evaluation
     36      int[] optimalAssignment = new int[N];   //Only for optimal assignment evaluation
    3737
    3838      //Calculate weights in the graph
    39       for (int S = 0; S < N; S++) { //Starting point of the arc
    40         for (int sM = 0; sM < 2; sM++) {    //Starting point machine
     39      for (int S = 0; S < N; S++) {        //Starting point of the arc
     40        for (int sM = 0; sM < 2; sM++) {   //Starting point machine
    4141          int eM = sM == 0 ? 1 : 0;
    4242          weights[sM, S, S + 1] = 0;
    … …  
    8787          if (newT < T) {
    8888            T = newT;
    89             optimalAssignment = MakeAssignement(S, SM, prevPath, order);
     89            optimalAssignment = MakeAssignment(S, SM, prevPath, order);
    9090          }
    9191        }
    … …  
    104104    }
    105105
    106     private static int[] MakeAssignement(int start, int startMach, int[,] prevPath, Permutation order) {
     106    private static int[] MakeAssignment(int start, int startMach, int[,] prevPath, Permutation order) {
    107107      var N = order.Length;
    108108      int[] assignment = Enumerable.Repeat(-1, N).ToArray();
Note: See TracChangeset for help on using the changeset viewer.