diff options
author | Yuheng Long <yuhenglong@google.com> | 2013-08-11 12:24:32 -0700 |
---|---|---|
committer | ChromeBot <chrome-bot@google.com> | 2013-08-11 17:03:29 -0700 |
commit | c01232264caccaffe6302414b7e901a96d3b18bf (patch) | |
tree | 5adcfa6bb7cb5d32925dce3be372419ef9adcd58 | |
parent | 2b514c28dd26aa02c2ea0f9924be91fb2394c8a0 (diff) | |
download | toolchain-utils-c01232264caccaffe6302414b7e901a96d3b18bf.tar.gz |
Refine the module hill_climb_best_neighbor.
BUG=None
TEST=unit testings for the pipeline stage, pipeline workers, generation,
steering, task, flag and hill climbing.
Change-Id: I95fd82072f1474b73735a643f2da589eb930b838
Reviewed-on: https://gerrit-int.chromium.org/42663
Reviewed-by: Luis Lozano <llozano@chromium.org>
Tested-by: Yuheng Long <yuhenglong@google.com>
Commit-Queue: Yuheng Long <yuhenglong@google.com>
-rw-r--r-- | bestflags/generation.py | 22 | ||||
-rw-r--r-- | bestflags/genetic_algorithm.py | 4 | ||||
-rw-r--r-- | bestflags/hill_climb_best_neighbor.py | 20 | ||||
-rw-r--r-- | bestflags/steering.py | 2 | ||||
-rw-r--r-- | bestflags/steering_test.py | 2 | ||||
-rw-r--r-- | bestflags/task.py | 2 |
6 files changed, 28 insertions, 24 deletions
diff --git a/bestflags/generation.py b/bestflags/generation.py index 6fe851a8..331c8105 100644 --- a/bestflags/generation.py +++ b/bestflags/generation.py @@ -12,7 +12,7 @@ until all the tasks in this generation are done executing. It also contains a set of tasks that could potentially be used to generate the next generation, e.g., in the genetic algorithm, a set of good species will be kept to evolve to the successive generations. For the hill climbing algorithm example, the -candidate_pool will contain a current task t being evaluated and the exe_pool +candidate_pool will contain a current task t being evaluated and the exe_set will contains all the task t's neighbor. """ @@ -28,27 +28,27 @@ class Generation(object): """A generation of a framework run. The base class of generation. Concrete subclasses, e.g., GAGeneration should - override the Next and Improved method to implement algorithm specific + override the Next and IsImproved method to implement algorithm specific applications. """ - def __init__(self, exe_pool, candidate_pool): + def __init__(self, exe_set, candidate_pool): """Set up the tasks set of this generation. Args: - exe_pool: A set of tasks to be run. + exe_set: A set of tasks to be run. candidate_pool: A set of tasks to be considered to be used to generate the next generation. """ - self._exe_pool = exe_pool + self._exe_set = exe_set self._candidate_pool = candidate_pool # Keeping the record of how many tasks are pending. Pending tasks are the # ones that have been sent out to the next stage for execution but have not # finished. A generation is not ready for the reproduction of the new # generations until all its pending tasks have been executed. - self._pending = len(exe_pool) + self._pending = len(exe_set) def CandidatePool(self): """Return the candidate tasks of this generation.""" @@ -58,7 +58,7 @@ class Generation(object): def Pool(self): """Return the task set of this generation.""" - return self._exe_pool + return self._exe_set def Done(self): """All the tasks in this generation are done. @@ -96,13 +96,13 @@ class Generation(object): """ # If there is a match, the input task belongs to this generation. - if task not in self._exe_pool: + if task not in self._exe_set: return False # Remove the place holder task in this generation and store the new input # task and its result. - self._exe_pool.remove(task) - self._exe_pool.add(task) + self._exe_set.remove(task) + self._exe_set.add(task) # The current generation will have one less task to wait on. self._pending -= 1 @@ -111,7 +111,7 @@ class Generation(object): return True - def Improved(self): + def IsImproved(self): """True if this generation has improvement upon its parent generation. Raises: diff --git a/bestflags/genetic_algorithm.py b/bestflags/genetic_algorithm.py index 0e7de07f..be9e8970 100644 --- a/bestflags/genetic_algorithm.py +++ b/bestflags/genetic_algorithm.py @@ -200,7 +200,7 @@ class GAGeneration(Generation): Generation.__init__(self, tasks, parents) self._total_stucks = total_stucks - def Improved(self): + def IsImproved(self): """True if this generation has improvement upon its parent generation.""" tasks = self.Pool() @@ -216,7 +216,7 @@ class GAGeneration(Generation): best_current = sorted(tasks, key=lambda task: task.GetTestResult())[0] # At least one task has improvement. - if best_current.Improved(best_parent): + if best_current.IsImproved(best_parent): self._total_stucks = 0 return True diff --git a/bestflags/hill_climb_best_neighbor.py b/bestflags/hill_climb_best_neighbor.py index aec420f9..409b42c9 100644 --- a/bestflags/hill_climb_best_neighbor.py +++ b/bestflags/hill_climb_best_neighbor.py @@ -23,35 +23,39 @@ from task import Task class HillClimbingBestBranch(Generation): """A variation of the hill climbing algorithm. - Given a task, it explores all its neighbors. Pick if best neighbor for the + Given a task, it explores all its neighbors. Pick the best neighbor for the next iteration. """ - def __init__(self, exe_pool, parents, specs): + def __init__(self, exe_set, parents, specs): """Set up the tasks set of this generation. Args: - exe_pool: A set of tasks to be run. + exe_set: A set of tasks to be run. parents: A set of tasks to be used to check whether their neighbors have improved upon them. specs: A list of specs to explore. The spec specifies the flags that can be changed to find neighbors of a task. """ - Generation.__init__(self, exe_pool, parents) + Generation.__init__(self, exe_set, parents) self._specs = specs - def Improved(self): + def IsImproved(self): """True if this generation has improvement over its parent generation. + If this generation improves upon the previous generation, this method finds + out the best task in this generation and sets it to _next_task for the + method Next to use. + Returns: True if the best neighbor improves upon the parent task. """ # Find the best neighbor. best_task = None - for task in self._exe_pool: - if not best_task or task.Improved(best_task): + for task in self._exe_set: + if not best_task or task.IsImproved(best_task): best_task = task if not best_task: @@ -63,7 +67,7 @@ class HillClimbingBestBranch(Generation): assert len(parents) == 1 self._next_task = best_task # If the best neighbor improves upon the parent task. - return best_task.Improved(parents[0]) + return best_task.IsImproved(parents[0]) self._next_task = best_task return True diff --git a/bestflags/steering.py b/bestflags/steering.py index 5cdf8aed..a7a559e2 100644 --- a/bestflags/steering.py +++ b/bestflags/steering.py @@ -99,7 +99,7 @@ def Steering(cache, generations, input_queue, result_queue): # A generation may not generate the next generation, e.g., because a # fixpoint has been reached, there has not been any improvement for a few # generations or a local maxima is reached. - if not generation.Improved(): + if not generation.IsImproved(): continue for new_generation in generation.Next(cache): diff --git a/bestflags/steering_test.py b/bestflags/steering_test.py index 5063079c..2000dc45 100644 --- a/bestflags/steering_test.py +++ b/bestflags/steering_test.py @@ -53,7 +53,7 @@ class MockGeneration(Generation): def Next(self, _): return self._next_generations - def Improved(self): + def IsImproved(self): if self._next_generations: return True return False diff --git a/bestflags/task.py b/bestflags/task.py index b20493fd..f1ac417f 100644 --- a/bestflags/task.py +++ b/bestflags/task.py @@ -391,7 +391,7 @@ class Task(object): # Write out the result in the comma-separated format (CSV). out_file.write('%s,%s,%s\n' % test_result) - def Improved(self, other): + def IsImproved(self, other): """Compare the current task with another task. Args: |