source: branches/2520_PersistenceReintegration/HeuristicLab.Encodings.ScheduleEncoding/3.3/ScheduleEncoding/Crossovers/DirectScheduleGTCrossover.cs @ 16453

Last change on this file since 16453 was 16453, checked in by jkarder, 10 months ago

#2520: updated year of copyrights

File size: 4.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2019 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
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
22using HeuristicLab.Common;
23using HeuristicLab.Core;
24using HeuristicLab.Data;
25using HeuristicLab.Parameters;
26using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
27
28namespace HeuristicLab.Encodings.ScheduleEncoding.ScheduleEncoding {
29  [Item("DirectScheduleGTCrossover", "Represents a crossover using the GT-Algorithm to cross two direct schedule representations.")]
30  [StorableClass]
31  public class DirectScheduleGTCrossover : DirectScheduleCrossover {
32
33    public IValueLookupParameter<DoubleValue> MutationProbabilityParameter {
34      get { return (IValueLookupParameter<DoubleValue>)Parameters["MutationProbability"]; }
35    }
36
37    [StorableConstructor]
38    protected DirectScheduleGTCrossover(bool deserializing) : base(deserializing) { }
39    protected DirectScheduleGTCrossover(DirectScheduleGTCrossover original, Cloner cloner) : base(original, cloner) { }
40    public DirectScheduleGTCrossover()
41      : base() {
42      Parameters.Add(new ValueLookupParameter<DoubleValue>("MutationProbability", "The probability that a task from the conflict set is chosen randomly instead of from one of the parents."));
43    }
44
45    public override IDeepCloneable Clone(Cloner cloner) {
46      return new DirectScheduleGTCrossover(this, cloner);
47    }
48
49    public static Schedule Apply(IRandom random, Schedule parent1, Schedule parent2, ItemList<Job> jobData, double mutProp) {
50      var child = new Schedule(parent1.Resources.Count);
51
52      //Reset scheduled tasks in result
53      foreach (Job j in jobData) {
54        foreach (Task t in j.Tasks) {
55          t.IsScheduled = false;
56        }
57      }
58
59      //GT-Algorithm
60      //STEP 0 - Compute a list of "earliest operations"
61      ItemList<Task> earliestTasksList = GTAlgorithmUtils.GetEarliestNotScheduledTasks(jobData);
62      while (earliestTasksList.Count > 0) {
63        //STEP 1 - Get earliest not scheduled operation with minimal earliest completing time
64        Task minimal = GTAlgorithmUtils.GetTaskWithMinimalEC(earliestTasksList, child);
65        int conflictedResourceNr = minimal.ResourceNr;
66        Resource conflictedResource = child.Resources[conflictedResourceNr];
67
68        //STEP 2 - Compute a conflict set of all operations that can be scheduled on the conflicted resource
69        ItemList<Task> conflictSet = GTAlgorithmUtils.GetConflictSetForTask(minimal, earliestTasksList, jobData, child);
70
71        //STEP 3 - Select a task from the conflict set
72        int progressOnResource = conflictedResource.Tasks.Count;
73        Task selectedTask = null;
74        if (random.NextDouble() < mutProp) {
75          //Mutation
76          selectedTask = conflictSet[random.Next(conflictSet.Count)];
77        } else {
78          //Crossover
79          selectedTask = SelectTaskFromConflictSet(conflictSet, ((random.Next(2) == 0) ? parent1 : parent2), conflictedResourceNr, progressOnResource);
80        }
81
82        //STEP 4 - Add the selected task to the current schedule
83        selectedTask.IsScheduled = true;
84        double startTime = GTAlgorithmUtils.ComputeEarliestStartTime(selectedTask, child);
85        child.ScheduleTask(selectedTask.ResourceNr, startTime, selectedTask.Duration, selectedTask.JobNr);
86
87        //STEP 5 - Back to STEP 1
88        earliestTasksList = GTAlgorithmUtils.GetEarliestNotScheduledTasks(jobData);
89      }
90
91      return child;
92    }
93
94    private static Task SelectTaskFromConflictSet(ItemList<Task> conflictSet, Schedule usedParent, int conflictedResourceNr, int progressOnResource) {
95      //Apply Crossover
96      foreach (ScheduledTask st in usedParent.Resources[conflictedResourceNr].Tasks) {
97        foreach (Task t in conflictSet) {
98          if (st.JobNr == t.JobNr)
99            return t;
100        }
101      }
102      return conflictSet[0];
103    }
104
105
106    public override Schedule Cross(IRandom random, Schedule parent1, Schedule parent2) {
107      var jobData = (ItemList<Job>)JobDataParameter.ActualValue.Clone();
108      var mutProp = MutationProbabilityParameter.ActualValue;
109      return Apply(random, parent1, parent2, jobData, mutProp.Value);
110    }
111  }
112}
Note: See TracBrowser for help on using the repository browser.