heuristics

Module summary

Implements several heuristics to be used with a separate script to generate .csv logs.

Heuristics for the original problem generally have orig_ prefix in the name, for the simplified problem – simpl_ prefix.

The module also contains some code related to possible further research and testing.

(In the implementation details below, click on class/function names for additional documentation and links to the source code.)

❖❖❖

Implements functions (outside the classes above):

fast_greedy_2sifts(A, B)	finds a good alignment target with greedy pairs of sifts
fast_greedy_sifts(A, B)	Finds a good alignment target with greedy sifts.
fastslide(X, a, p)	An experimental function implementing faster 'sift' operation.
minAB(A, B)	Best of A and B heuristic (simplified problem).
orig_5random(A, B, simpl)	Five random orders (original problem).
orig_bestAB(A, B, simpl)	Best of A and B (original problem).
orig_gsifts1p(A, B, simpl)	Greedy sifts heuristic for the original problem.
orig_interleave_when_diverge(A, B, simpl)	Another experimental heuristic (further research).
orig_interleaved(A, B, simpl)	Experimental heuristic (further research).
orig_meta(A, B, simpl)	Another experimental heuristic (further research).
orig_rnd_starts(A, B, simpl)	Another experimental heuristic (further research).
orig_simpl(A, B, simpl)	A heuristic for the original problem involving simplified problem.
simpl_5random(A, B)	Implements 'Best of 5 random orders' heuristic.
simpl_g2sifts_1p(A, B)	Experimental: greedy pairs of sifts (simplified problem), one pass.
simpl_g2sifts_2p(A, B)	Experimental: greedy pairs of sifts (simplified problem), two passes.
simpl_greedy_2sifts(A, B[, passes])	Finds a good alignment target with greedy pairs of sifts.
simpl_greedy_sifts(A, B[, passes])	Finds a good alignment target with greedy sifts
simpl_greedy_swaps(A, B)	finds a good alignment target with greedy swaps
simpl_gsifts_1p(A, B)	Greedy sifts: one pass.
simpl_gsifts_2p(A, B)	Greedy sifts: two passes.
simpl_gsifts_3p(A, B)	Greedy sifts: three passes.
simpl_gsifts_inf(A, B)	Greedy sifts: all passes.
toA(A, B)	Helper: align to A heuristic.
toB(A, B)	Helper: align to B heuristic.

Attributes defined in the module:

heuristics.SIMPL_HEU = [['simpl_minAB', <function minAB>, 'Best of A and B'], ['simpl_gswaps', <function simpl_greedy_swaps>, 'Greedy swaps'], ['simpl_5random', <function simpl_5random>, 'Best/five random orders'], ['simpl_gsifts_1p', <function simpl_gsifts_1p>, 'Greedy sifts (one pass)'], ['simpl_gsifts_2p', <function simpl_gsifts_2p>, 'Greedy sifts (two passes)'], ['simpl_gsifts_inf', <function simpl_gsifts_inf>, 'Greedy sifts (all)']]

List of heuristics for the simplified problem.

heuristics.ORIG_HEU = [['orig_simpl', <function orig_simpl>, 'Simplified problem'], ['orig_gsifts1p', <function orig_gsifts1p>, 'Greedy BDD sifts (one pass)'], ['orig_bestAB', <function orig_bestAB>, 'Best of A and B'], ['orig_5random', <function orig_5random>, 'Best of five random orders']]

List of heuristics for the original problem.

❖❖❖

Implementation details

❖❖❖

Functions

heuristics.fast_greedy_2sifts(A, B)

finds a good alignment target with greedy pairs of sifts

Makes sifts while it can improve the objective (picking the best improvement at each step)

heuristics.fast_greedy_sifts(A, B)

Finds a good alignment target with greedy sifts.

Makes sifts while it can improve the objective (picking the best improvement at each step)

heuristics.fastslide(X, a, p)

An experimental function implementing faster ‘sift’ operation.

heuristics.minAB(A, B)

Best of A and B heuristic (simplified problem).

heuristics.orig_5random(A, B, simpl)

Five random orders (original problem).

heuristics.orig_bestAB(A, B, simpl)

Best of A and B (original problem).

heuristics.orig_gsifts1p(A, B, simpl)

Greedy sifts heuristic for the original problem.

heuristics.orig_interleave_when_diverge(A, B, simpl)

Another experimental heuristic (further research).

heuristics.orig_interleaved(A, B, simpl)

Experimental heuristic (further research).

heuristics.orig_meta(A, B, simpl)

Another experimental heuristic (further research).

heuristics.orig_rnd_starts(A, B, simpl)

Another experimental heuristic (further research).

heuristics.orig_simpl(A, B, simpl)

A heuristic for the original problem involving simplified problem.

heuristics.simpl_5random(A, B)

Implements ‘Best of 5 random orders’ heuristic.

heuristics.simpl_g2sifts_1p(A, B)

Experimental: greedy pairs of sifts (simplified problem), one pass.

heuristics.simpl_g2sifts_2p(A, B)

Experimental: greedy pairs of sifts (simplified problem), two passes.

heuristics.simpl_greedy_2sifts(A, B, passes=-1)

Finds a good alignment target with greedy pairs of sifts.

Makes sifts while it can improve the objective, or for a given number of passes, picking the best improvement at each step. (one pass = examining all the variables.)

heuristics.simpl_greedy_sifts(A, B, passes=-1)

Finds a good alignment target with greedy sifts

Makes sifts while it can improve the objective or for a given number of passes, picking the best improvement at each step. (one pass = examining all the variables)

heuristics.simpl_greedy_swaps(A, B)

finds a good alignment target with greedy swaps

Makes swaps while it can improve the objective (picking the best improvement at each step)

heuristics.simpl_gsifts_1p(A, B)

Greedy sifts: one pass.

heuristics.simpl_gsifts_2p(A, B)

Greedy sifts: two passes.

heuristics.simpl_gsifts_3p(A, B)

Greedy sifts: three passes.

heuristics.simpl_gsifts_inf(A, B)

Greedy sifts: all passes.

heuristics.toA(A, B)

Helper: align to A heuristic.

heuristics.toB(A, B)

Helper: align to B heuristic.