pyggi.algorithms module

This module contains meta-heuristic search algorithms.

class pyggi.algorithms.LocalSearch(program)

Bases: object

Local Search (Abstact Class)

All children classes need to override

• get_neighbour()
• get_fitness()

Hint

Example of LocalSearch class.

from pyggi import Program, Patch, GranularityLevel
from pyggi.algorithms import LocalSearch
from pyggi.atomic_operator import LineReplacement, LineInsertion
from pyggi.custom_operator import LineDeletion

program = Program("<PROGRAM_ROOT_PATH>", GranularityLevel.LINE)

class MyLocalSearch(LocalSearch):
    def get_neighbour(self, patch):
        import random
        if len(patch) > 0 and random.random() < 0.5:
            patch.remove(random.randrange(0, len(patch)))
        else:
            edit_operator = random.choice([LineDeletion, LineInsertion, LineReplacement])
            patch.add(edit_operator.random(program))
        return patch

    def get_fitness(self, patch):
        return float(patch.test_result.custom['runtime'])

    def is_valid_patch(self, patch):
        return patch.test_result.compiled and patch.test_result.custom['pass_all'] == 'true'

    def stopping_criterion(self, iter, patch):
        return float(patch.test_result.custom['runtime']) < 100

local_search = MyLocalSearch(program)
results = local_search.run(warmup_reps=5, epoch=3, max_iter=100, timeout=15)

Parameters:program (Program) – The Program instance to optimize.

get_fitness(patch)

Define the fitness value of the patch

If you want to use original one(elapsed_time), simply call super().

Parameters:patch (Patch) – The patch instacne Returns:The fitness value

get_neighbour(patch)

Parameters:patch (Patch) – The patch that the search is visiting now Returns:The next(neighbour) patch Return type:Patch

Hint

An example:

return patch.add(LineDeletion.random(program))

is_better_than_the_best(fitness, best_fitness)

Parameters:

• fitness – The fitness value of the current patch
• best_fitness – The best fitness value ever in the current epoch

Returns:

If the current fitness are better than the best one, return True. False otherwise.

Return type:

bool

is_valid_patch(patch)

Parameters:patch (Patch) – The Patch instance whose validity should be checked. Returns:The validity of the patch Return type:bool

run(warmup_reps=1, epoch=5, max_iter=100, timeout=15, result_parser=<bound method TestResult.pyggi_result_parser of <class 'pyggi.test_result.TestResult'>>)

It starts from a randomly generated candidate solution and iteratively moves to its neighbouring solution with a better fitness value by making small local changes to the candidate solution.

Parameters:

• warmup_reps (int) – The number of warming-up test runs to get the base fitness value. For some properties, non-functional properties in particular, fitness value cannot be fixed. In that case, the base fitness value should be acquired by averaging the fitness values of original program.
• epoch (int) – The total epoch
• max_iter (int) – The maximum iterations per epoch
• timeout (float) – The time limit of test run (unit: seconds)
• result_parser (None or callable((str, str), TestResult)) – The parser of test output (default: TestResult.pyggi_result_parser())

Returns:

The result of searching(Time, Success, FitnessEval, CompileFailed, BestPatch)

Return type:

dict(int, dict(str, ))

stopping_criterion(iter, patch)

Parameters:

• iter (int) – The current iteration number in the epoch
• patch (Patch) – The patch visited in the current iteration

Returns:

If the satisfying patch is found or the budget is out of run, return True to stop the current epoch. False otherwise.

Return type:

bool