1057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long# Copyright (c) 2013 The Chromium OS Authors. All rights reserved. 2057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long# Use of this source code is governed by a BSD-style license that can be 3057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long# found in the LICENSE file. 4057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long"""The hill genetic algorithm. 5057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 6057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng LongPart of the Chrome build flags optimization. 7057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long""" 8057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 9057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long__author__ = 'yuhenglong@google.com (Yuheng Long)' 10057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 11057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Longimport random 12057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 13057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Longimport flags 14057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Longfrom flags import Flag 15057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Longfrom flags import FlagSet 16057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Longfrom generation import Generation 17057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Longfrom task import Task 18057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 19057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 20057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Longdef CrossoverWith(first_flag, second_flag): 21057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long """Get a crossed over gene. 22057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 23057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long At present, this just picks either/or of these values. However, it could be 24057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long implemented as an integer maskover effort, if required. 25057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 26057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long Args: 27057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long first_flag: The first gene (Flag) to cross over with. 28057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long second_flag: The second gene (Flag) to cross over with. 29057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 30057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long Returns: 31057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long A Flag that can be considered appropriately randomly blended between the 32057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long first and second input flag. 33057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long """ 34057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 35057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long return first_flag if random.randint(0, 1) else second_flag 36057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 37057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 38057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Longdef RandomMutate(specs, flag_set, mutation_rate): 39057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long """Randomly mutate the content of a task. 40057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 41057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long Args: 42057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long specs: A list of spec from which the flag set is created. 43057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long flag_set: The current flag set being mutated 44057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long mutation_rate: What fraction of genes to mutate. 45057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 46057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long Returns: 47057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long A Genetic Task constructed by randomly mutating the input flag set. 48057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long """ 49057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 50057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long results_flags = [] 51057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 52057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long for spec in specs: 53057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # Randomly choose whether this flag should be mutated. 54057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long if random.randint(0, int(1 / mutation_rate)): 55057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long continue 56057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 57057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # If the flag is not already in the flag set, it is added. 58057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long if spec not in flag_set: 59057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long results_flags.append(Flag(spec)) 60057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long continue 61057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 62057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # If the flag is already in the flag set, it is mutated. 63e896dfd76014af3c399d1b54be022fb1663a105bYuheng Long numeric_flag_match = flags.Search(spec) 64057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 65057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # The value of a numeric flag will be changed, and a boolean flag will be 66057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # dropped. 67e896dfd76014af3c399d1b54be022fb1663a105bYuheng Long if not numeric_flag_match: 68057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long continue 69057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 70057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long value = flag_set[spec].GetValue() 71057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 72057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # Randomly select a nearby value of the current value of the flag. 73057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long rand_arr = [value] 74e896dfd76014af3c399d1b54be022fb1663a105bYuheng Long if value + 1 < int(numeric_flag_match.group('end')): 75057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long rand_arr.append(value + 1) 76057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 77057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long rand_arr.append(value - 1) 78057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long value = random.sample(rand_arr, 1)[0] 79057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 80057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # If the value is smaller than the start of the spec, this flag will be 81057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # dropped. 82e896dfd76014af3c399d1b54be022fb1663a105bYuheng Long if value != int(numeric_flag_match.group('start')) - 1: 83057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long results_flags.append(Flag(spec, value)) 84057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 85057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long return GATask(FlagSet(results_flags)) 86057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 87057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 88057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Longclass GATask(Task): 89f2a3ef46f75d2196a93d3ed27f4d1fcf22b54fbeLuis Lozano 90057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long def __init__(self, flag_set): 91057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long Task.__init__(self, flag_set) 92057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 93057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long def ReproduceWith(self, other, specs, mutation_rate): 94057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long """Reproduce with other FlagSet. 95057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 96057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long Args: 97057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long other: A FlagSet to reproduce with. 98057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long specs: A list of spec from which the flag set is created. 99057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long mutation_rate: one in mutation_rate flags will be mutated (replaced by a 100057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long random version of the same flag, instead of one from either of the 101057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long parents). Set to 0 to disable mutation. 102057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 103057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long Returns: 104057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long A GA task made by mixing self with other. 105057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long """ 106057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 107057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # Get the flag dictionary. 108057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long father_flags = self.GetFlags().GetFlags() 109057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long mother_flags = other.GetFlags().GetFlags() 110057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 111057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # Flags that are common in both parents and flags that belong to only one 112057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # parent. 113057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long self_flags = [] 114057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long other_flags = [] 115057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long common_flags = [] 116057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 117057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # Find out flags that are common to both parent and flags that belong soly 118057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # to one parent. 119057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long for self_flag in father_flags: 120057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long if self_flag in mother_flags: 121057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long common_flags.append(self_flag) 122057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long else: 123057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long self_flags.append(self_flag) 124057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 125057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long for other_flag in mother_flags: 126057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long if other_flag not in father_flags: 127057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long other_flags.append(other_flag) 128057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 129057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # Randomly select flags that belong to only one parent. 130057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long output_flags = [father_flags[f] for f in self_flags if random.randint(0, 1)] 131057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long others = [mother_flags[f] for f in other_flags if random.randint(0, 1)] 132057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long output_flags.extend(others) 133057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # Turn on flags that belong to both parent. Randomly choose the value of the 134057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # flag from either parent. 135057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long for flag in common_flags: 136057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long output_flags.append(CrossoverWith(father_flags[flag], mother_flags[flag])) 137057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 138057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # Mutate flags 139057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long if mutation_rate: 140057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long return RandomMutate(specs, FlagSet(output_flags), mutation_rate) 141057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 142057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long return GATask(FlagSet(output_flags)) 143057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 144057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 145057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Longclass GAGeneration(Generation): 146057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long """The Genetic Algorithm.""" 147057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 148057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # The value checks whether the algorithm has converged and arrives at a fixed 149057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # point. If STOP_THRESHOLD of generations have not seen any performance 150057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # improvement, the Genetic Algorithm stops. 151057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long STOP_THRESHOLD = None 152057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 153057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # Number of tasks in each generation. 154057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long NUM_CHROMOSOMES = None 155057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 156057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # The value checks whether the algorithm has converged and arrives at a fixed 157057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # point. If NUM_TRIALS of trials have been attempted to generate a new task 158057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # without a success, the Genetic Algorithm stops. 159057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long NUM_TRIALS = None 160057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 161057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # The flags that can be used to generate new tasks. 162057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long SPECS = None 163057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 164057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # What fraction of genes to mutate. 165057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long MUTATION_RATE = 0 166057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 167057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long @staticmethod 168057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long def InitMetaData(stop_threshold, num_chromosomes, num_trials, specs, 169057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long mutation_rate): 170057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long """Set up the meta data for the Genetic Algorithm. 171057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 172057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long Args: 173057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long stop_threshold: The number of generations, upon which no performance has 174057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long seen, the Genetic Algorithm stops. 175057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long num_chromosomes: Number of tasks in each generation. 176057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long num_trials: The number of trials, upon which new task has been tried to 177057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long generated without success, the Genetic Algorithm stops. 178057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long specs: The flags that can be used to generate new tasks. 179057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long mutation_rate: What fraction of genes to mutate. 180057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long """ 181057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 182057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long GAGeneration.STOP_THRESHOLD = stop_threshold 183057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long GAGeneration.NUM_CHROMOSOMES = num_chromosomes 184057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long GAGeneration.NUM_TRIALS = num_trials 185057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long GAGeneration.SPECS = specs 186057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long GAGeneration.MUTATION_RATE = mutation_rate 187057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 188057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long def __init__(self, tasks, parents, total_stucks): 189057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long """Set up the meta data for the Genetic Algorithm. 190057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 191057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long Args: 192057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long tasks: A set of tasks to be run. 193057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long parents: A set of tasks from which this new generation is produced. This 194057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long set also contains the best tasks generated so far. 195057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long total_stucks: The number of generations that have not seen improvement. 196057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long The Genetic Algorithm will stop once the total_stucks equals to 197057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long NUM_TRIALS defined in the GAGeneration class. 198057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long """ 199057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 200057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long Generation.__init__(self, tasks, parents) 201057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long self._total_stucks = total_stucks 202057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 203c01232264caccaffe6302414b7e901a96d3b18bfYuheng Long def IsImproved(self): 204057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long """True if this generation has improvement upon its parent generation.""" 205057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 206057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long tasks = self.Pool() 207057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long parents = self.CandidatePool() 208057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 209057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # The first generate does not have parents. 210057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long if not parents: 211057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long return True 212057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 213057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # Found out whether a task has improvement upon the best task in the 214057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # parent generation. 215057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long best_parent = sorted(parents, key=lambda task: task.GetTestResult())[0] 216057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long best_current = sorted(tasks, key=lambda task: task.GetTestResult())[0] 217057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 218057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # At least one task has improvement. 219c01232264caccaffe6302414b7e901a96d3b18bfYuheng Long if best_current.IsImproved(best_parent): 220057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long self._total_stucks = 0 221057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long return True 222057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 223057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # If STOP_THRESHOLD of generations have no improvement, the algorithm stops. 224057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long if self._total_stucks >= GAGeneration.STOP_THRESHOLD: 225057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long return False 226057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 227057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long self._total_stucks += 1 228057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long return True 229057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 230057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long def Next(self, cache): 231057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long """Calculate the next generation. 232057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 233057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long Generate a new generation from the a set of tasks. This set contains the 234057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long best set seen so far and the tasks executed in the parent generation. 235057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 236057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long Args: 237057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long cache: A set of tasks that have been generated before. 238057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 239057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long Returns: 240057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long A set of new generations. 241057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long """ 242057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 243057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long target_len = GAGeneration.NUM_CHROMOSOMES 244057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long specs = GAGeneration.SPECS 245057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long mutation_rate = GAGeneration.MUTATION_RATE 246057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 247057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # Collect a set of size target_len of tasks. This set will be used to 248057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # produce a new generation of tasks. 249057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long gen_tasks = [task for task in self.Pool()] 250057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 251057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long parents = self.CandidatePool() 252057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long if parents: 253057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long gen_tasks.extend(parents) 254057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 255057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # A set of tasks that are the best. This set will be used as the parent 256057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # generation to produce the next generation. 257057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long sort_func = lambda task: task.GetTestResult() 258057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long retained_tasks = sorted(gen_tasks, key=sort_func)[:target_len] 259057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 260057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long child_pool = set() 261057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long for father in retained_tasks: 262057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long num_trials = 0 263057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # Try num_trials times to produce a new child. 264057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long while num_trials < GAGeneration.NUM_TRIALS: 265057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # Randomly select another parent. 266057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long mother = random.choice(retained_tasks) 267057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # Cross over. 268057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long child = mother.ReproduceWith(father, specs, mutation_rate) 269057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long if child not in child_pool and child not in cache: 270057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long child_pool.add(child) 271057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long break 272057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long else: 273057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long num_trials += 1 274057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 275057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long num_trials = 0 276057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 277057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long while len(child_pool) < target_len and num_trials < GAGeneration.NUM_TRIALS: 278057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long for keep_task in retained_tasks: 279057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # Mutation. 280057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long child = RandomMutate(specs, keep_task.GetFlags(), mutation_rate) 281057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long if child not in child_pool and child not in cache: 282057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long child_pool.add(child) 283057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long if len(child_pool) >= target_len: 284057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long break 285057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long else: 286057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long num_trials += 1 287057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 288057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # If NUM_TRIALS of tries have been attempted without generating a set of new 289057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long # tasks, the algorithm stops. 290057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long if num_trials >= GAGeneration.NUM_TRIALS: 291057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long return [] 292057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 293057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long assert len(child_pool) == target_len 294057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long 295057ad5c77ef0ea44ee260718eb6d30afef2f7f83Yuheng Long return [GAGeneration(child_pool, set(retained_tasks), self._total_stucks)] 296