BinarySearch

class decida.BinarySearch.BinarySearch(low, high, min_value, max_value, min_delta=None, bracket_step=None, bracket_mult=None, find_max=True)

Bases: future.types.newobject.newobject

synopsis:

Binary Search iterator class.

BinarySearch organizes a binary search for a parameter value based on some external evaluation which gives a success or failure using trial parameter values presented by the BinarySearch instance.

The binary search proceeds as follows:

  • Set the parameter to the low configuration value.
  • Bracket1 mode: stay or move the parameter value lower until the external evaluation produces success (if find_max is False, look for failure).
  • Set the parameter value to the high configuration value.
  • Bracket2 mode: stay or move the parameter value higher until the external evaluation producess failure (if find_max is False, look for success).
  • With the upper and lower brackets determined, search within their interval for the maximum value of the parameter which produces success (if find_max is False, look for the minimum value of the parameter which produces success).
  • Bracket trial values are changed according to the configuration options bracket_step (increase or decrease by a specific step), or bracket_mult (increase or decrease by multiplying or dividing by a specific factor). Also the initial brackets are limited by min and max configuration options.
  • Convergence is reported when the absolute change in trial parameter values is less than the min_delta configuration option.

constructor arguments:

low (float)

first parameter value to try in binary-search bracket lower-bound (bracket1) mode. If the evaluation produces a success, the mode proceeds to bracket upper-bound (bracket2) mode. Otherwise, the parameter is decremented by bracket_step, if specified, or divided by bracket_mult if specified.

high (float)

first parameter value to try in binary-search bracket upper-bound (bracket2) mode. If the evaluation produces a success, the mode proceeds to binary search (bisection) mode. Otherwise, the parameter is incremented by bracket_step, if specified, or multiplied by bracket_mult if specified.

min_value (float)

minimum value of the parameter. If searching in bracket1 mode goes below min, the binary search stops.

max_value (float)

maximum value of the parameter. If searching in bracket2 mode goes above max, the binary search stops.

min_delta (float, default=None)

Convergence is achieved if the absolute change between parameter steps is less than min_delta.

bracket_step (float, default=None)

If specified, the parameter is revised by one bracket_step in bracket1 or bracket2 modes.

bracket_mult (float, default=None)

If specified, the parameter is revised by scaling by bracket_mult in bracket1 or bracket2 modes.

find_max (bool, default=True)

If True, maximum value of the parameter is found which gives a successful result. If False, bracket modes and searching goes in the opposite sense.

example (from test_BinarySearch_2):

def funct(x) :
    a, b, c = 1.0, -4.0, 2.0
    y = a*x*x + b*x + c
    return y

bin = BinarySearch(
     low=1.0, high=2.0, min=-10, max=3,
     min_delta=1e-6, bracket_step=0.1
)

bin.start()
while not bin.is_done() :
    x=bin.value()
    f=funct(x)
    success = (f >= 0)
    print("%-10s: x=%-18s y=%-18s %-5s" % (bin.mode(), x, f, success))
    bin.update(success)

print
print("x = ", bin.last_success())

public methods:

is_done()

return True if convergence is achieved.

results:

  • Return True if bisection has converged.
last_success()

return the last successful parameter value.

results:

  • Returns the parameter value which last achieved success.
mode()

return the binary search mode.

results:

  • The binary search mode is returned. The modes are:

    • start : initial mode.
    • bracket1 : search for the lowest value of the parameter that produces a successful result.
    • bracket2 : search for the highest value of the parameter that produces an unsuccessful result.
    • bisection : binary search mode.
    • done : convergence.
start()

reset parameter value, brackets and binary search mode.

results:

  • Resets the binary search object to its starting state.
  • The parameter is set to the first trial value.
  • Initial bracket values are reset.
  • The bisection mode is set to “start”
update(success)

update the trial parameter value.

results:

  • Revise the parameter value based on the two last bracketed binary search values and success or failure of the current parameter value.
  • Binary search brackets are revised.
value()

return the updated parameter value.

results:

  • Returns the updated parameter value which is to be tried for success.