Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2521_ProblemRefactoring/HeuristicLab.Encodings.ScheduleEncoding/3.3/ScheduleEncoding/Crossovers/DirectScheduleGTCrossover.cs @ 17226

Last change on this file since 17226 was 17226, checked in by mkommend, 5 years ago

#2521: Merged trunk changes into problem refactoring branch.

File size: 4.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 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 HEAL.Attic;
27
28namespace HeuristicLab.Encodings.ScheduleEncoding {
29  [Item("DirectScheduleGTCrossover", "Represents a crossover using the GT-Algorithm to cross two direct schedule representations.")]
30  [StorableType("07921864-BC23-431D-BA28-B302691F7FF8")]
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(StorableConstructorFlag _) : base(_) { }
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
67        //STEP 2 - Compute a conflict set of all operations that can be scheduled on the conflicted resource
68        ItemList<Task> conflictSet = GTAlgorithmUtils.GetConflictSetForTask(minimal, earliestTasksList, child);
69
70        //STEP 3 - Select a task from the conflict set
71        Task selectedTask = null;
72        if (random.NextDouble() < mutProp) {
73          //Mutation
74          selectedTask = conflictSet[random.Next(conflictSet.Count)];
75        } else {
76          //Crossover
77          selectedTask = SelectTaskFromConflictSet(conflictSet, ((random.Next(2) == 0) ? parent1 : parent2), conflictedResourceNr);
78        }
79
80        //STEP 4 - Add the selected task to the current schedule
81        selectedTask.IsScheduled = true;
82        double startTime = GTAlgorithmUtils.ComputeEarliestStartTime(selectedTask, child);
83        child.ScheduleTask(selectedTask.ResourceNr, startTime, selectedTask.Duration, selectedTask.JobNr);
84
85        //STEP 5 - Back to STEP 1
86        earliestTasksList = GTAlgorithmUtils.GetEarliestNotScheduledTasks(jobData);
87      }
88
89      return child;
90    }
91
92    private static Task SelectTaskFromConflictSet(ItemList<Task> conflictSet, Schedule usedParent, int conflictedResourceNr) {
93      //Apply Crossover
94      foreach (ScheduledTask st in usedParent.Resources[conflictedResourceNr].Tasks) {
95        foreach (Task t in conflictSet) {
96          if (st.JobNr == t.JobNr)
97            return t;
98        }
99      }
100      return conflictSet[0];
101    }
102
103
104    public override Schedule Cross(IRandom random, Schedule parent1, Schedule parent2) {
105      var jobData = (ItemList<Job>)JobDataParameter.ActualValue.Clone();
106      var mutProp = MutationProbabilityParameter.ActualValue;
107      return Apply(random, parent1, parent2, jobData, mutProp.Value);
108    }
109  }
110}
Note: See TracBrowser for help on using the repository browser.