Pareto optimization in algebraic dynamic programming
- PDF / 2,270,127 Bytes
- 20 Pages / 595.276 x 793.701 pts Page_size
- 53 Downloads / 220 Views
Open Access
RESEARCH
Pareto optimization in algebraic dynamic programming Cédric Saule* and Robert Giegerich
Abstract Pareto optimization combines independent objectives by computing the Pareto front of its search space, defined as the set of all solutions for which no other candidate solution scores better under all objectives. This gives, in a precise sense, better information than an artificial amalgamation of different scores into a single objective, but is more costly to compute. Pareto optimization naturally occurs with genetic algorithms, albeit in a heuristic fashion. Non-heuristic Pareto optimization so far has been used only with a few applications in bioinformatics. We study exact Pareto optimization for two objectives in a dynamic programming framework. We define a binary Pareto product operator ∗Par on arbitrary scoring schemes. Independent of a particular algorithm, we prove that for two scoring schemes A and B used in dynamic programming, the scoring scheme A∗Par B correctly performs Pareto optimization over the same search space. We study different implementations of the Pareto operator with respect to their asymptotic and empirical efficiency. Without artificial amalgamation of objectives, and with no heuristics involved, Pareto optimization is faster than computing the same number of answers separately for each objective. For RNA structure prediction under the minimum free energy versus the maximum expected accuracy model, we show that the empirical size of the Pareto front remains within reasonable bounds. Pareto optimization lends itself to the comparative investigation of the behavior of two alternative scoring schemes for the same purpose. For the above scoring schemes, we observe that the Pareto front can be seen as a composition of a few macrostates, each consisting of several microstates that differ in the same limited way. We also study the relationship between abstract shape analysis and the Pareto front, and find that they extract information of a different nature from the folding space and can be meaningfully combined. Keywords: Pareto optimization, Dynamic programming, Algebraic dynamic programming, RNA structure, Sankoff algorithm Background In combinatorial optimization, we evaluate a search space X of solution candidates by means of an objective function ψ. Generated from some input data of size n, the search space X is typically discrete and has size O(α n ) for some α. Conceptually, as well as in practice, it is convenient to formulate the objective function as the composition of a choice function ϕ and a scoring function σ, ψ = ϕ ◦ σ , computing their composition as (ϕ ◦ σ )(X) = ϕ({σ (x)|x ∈ X}) for the overall solution. The most common form of the objective function ψ is *Correspondence: cedric.saule@uni‑bielefeld.de Faculty of Technology and the Center for Biotechnology, Bielefeld University, Bielefeld, Germany
that σ evaluates each candidate to a score (or cost) value, and ϕ chooses the candidate which maximizes (or minimizes) this value. One or all optimal solutions can
Data Loading...
