Multi-objective optimal control of dynamic bioprocesses using ACADO Toolkit

The optimal design and operation of dynamic bioprocesses gives in practice often rise to optimisation problems with multiple and conflicting objectives. As a result typically not a single optimal solution but a set of Pareto optimal solutions exist. From this set of Pareto optimal solutions, one has to be chosen by the decision maker. Hence, efficient approaches are required for a fast and accurate generation of the Pareto set such that the decision maker can easily and systematically evaluate optimal alternatives. In the current paper the multi-objective optimisation of several dynamic bioprocess examples is performed using the freely available ACADO Multi-Objective Toolkit (http://www.acadotoolkit.org). This toolkit integrates efficient multiple objective scalarisation strategies (e.g., Normal Boundary Intersection and (Enhanced) Normalised Normal Constraint) with fast deterministic approaches for dynamic optimisation (e.g., single and multiple shooting). It has been found that the toolkit is able to efficiently and accurately produce the Pareto sets for all bioprocess examples. The resulting Pareto sets are added as supplementary material to this paper.     

Flower pollination algorithm with runway balance strategy for the aircraft landing scheduling problem

Aircraft landing scheduling is a challenging problem in the field of air traffic, whose objective is to determine the best combination of assigning the sequence and corresponding landing time for a given set of aircraft to a runway, and then minimize the sum of the deviations of the actual and target landing times under the condition of safe landing. In this paper, a flower pollination algorithm embedded with runway balance is proposed to solve it. Context cognitive learning and runway balance strategy are devised here to enhance its searching ability. 36 scheduling instances are selected from OR-Library to validate its performance. The experimental results show that the proposed algorithm can get the optimal solutions for instances up to 100 aircrafts, and is also capable of obtaining better solutions compared with SS, BA and FCFS for instances up to 500 aircrafts in a shorter time.     

Enhancing distributed EAs by a proactive strategy

In this work we propose a new distributed evolutionary algorithm that uses a proactive strategy to adapt its migration policy and the mutation rate. The proactive decision is carried out locally in each subpopulation based on the entropy of that subpopulation. In that way, each subpopulation can change their own incoming flow of individuals by asking their neighbors for more frequent or less frequent migrations in order to maintain the genetic diversity at a desired level. Moreover, this proactive strategy is reinforced by adapting the mutation rate while the algorithm is searching for the problem solution. All these strategies avoid the subpopulations to get trapped into local minima. We conduct computational experiments on large instances of the NK landscape problem which have shown that our proactive approach outperforms traditional dEAs, particularly for not highly rugged landscapes, in which it does not only reaches the most accurate solutions, but it does the fastest.     

On the inference of parsimonious indel evolutionary scenarios

Given a multiple alignment of orthologous DNA sequences and a phylogenetic tree for these sequences, we investigate the problem of reconstructing a most parsimonious scenario of insertions and deletions capable of explaining the gaps observed in the alignment. This problem, called the Indel Parsimony Problem, is a crucial component of the problem of ancestral genome reconstruction, and its solution provides valuable information to many genome functional annotation approaches. We first show that the problem is NP-complete. Second, we provide an algorithm, based on the fractional relaxation of an integer linear programming formulation. The algorithm is fast in practice, and the solutions it produces are, in most cases, provably optimal. We describe a divide-and-conquer approach that makes it possible to solve very large instances on a simple desktop machine, while retaining guaranteed optimality. Our algorithms are tested and shown efficient and accurate on a set of 1.8 Mb mammalian orthologous sequences in the CFTR region.     

Who should Decide for the Unrepresented?

Unrepresented patients lack the capacity to make medical decisions for themselves, have no clear documentation of preferences for medical treatment, and have no surrogate decision maker or obvious candidate for that role. There is no consensus about who should serve as the decision maker for these patients, particularly regarding whether to continue or to limit life‐sustaining treatment. Several authors have argued that ethics committees should play this role rather than the patient's treating physician, a common current default. We argue that concerns about the adequacy of physicians as surrogates are either empirically unfounded or apply equally to ethics committees. We suggest that physicians should be the primary decision maker for the unrepresented because of their fiduciary duties toward their patients. As part of the process of fulfilling these duties, they should seek the advice of third parties such as ethic committees; but final end‐of‐life decision‐making for the unrepresented should rest with the treating physician.     

Metaheuristics for the bi-objective orienteering problem

In this paper, heuristic solution techniques for the multi-objective orienteering problem are developed. The motivation stems from the problem of planning individual tourist routes in a city. Each point of interest in a city provides different benefits for different categories (e.g., culture, shopping). Each tourist has different preferences for the different categories when selecting and visiting the points of interests (e.g., museums, churches). Hence, a multi-objective decision situation arises. To determine all the Pareto optimal solutions, two metaheuristic search techniques are developed and applied. We use the Pareto ant colony optimization algorithm and extend the design of the variable neighborhood search method to the multi-objective case. Both methods are hybridized with path relinking procedures. The performances of the two algorithms are tested on several benchmark instances as well as on real world instances from different Austrian regions and the cities of Vienna and Padua. The computational results show that both implemented methods are well performing algorithms to solve the multi-objective orienteering problem.     

Exploiting symmetry properties of the discretizable molecular distance geometry problem

The Discretizable Molecular Distance Geometry Problem (DMDGP) involves a subset of instances of the distance geometry problem for which some assumptions allowing for discretization are satisfied. The search domain for the DMDGP is a binary tree that can be efficiently explored by employing a Branch & Prune (BP) algorithm. We showed in recent works that this binary tree may contain several symmetries, which are directly related to the total number of solutions of DMDGP instances. In this paper, we study the possibility of exploiting these symmetries for speeding up the solution of DMDGPs, and propose an extension of the BP algorithm that we named symmetry-driven BP (symBP). Computational experiments on artificial and protein instances are presented.     

Memetic algorithms for the unconstrained binary quadratic programming problem

This paper presents a memetic algorithm, a highly effective evolutionary algorithm incorporating local search for solving the unconstrained binary quadratic programming problem (BQP). To justify the approach, a fitness landscape analysis is conducted experimentally for several instances of the BQP. The results of the analysis show that recombination-based variation operators are well suited for the evolutionary algorithms with local search. Therefore, the proposed approach includes--besides a highly effective randomized k-opt local search--a new variation operator that has been tailored specially for the application in the hybrid evolutionary framework. The operator is called innovative variation and is fundamentally different from traditional crossover operators, since new genetic material is included in the offspring which is not contained in one of the parents. The evolutionary heuristic is tested on 35 publicly available BQP instances, and it is shown experimentally that the algorithm is capable of finding best-known solutions to large BQPs in a short time and with a high frequency. In comparison to other approaches for the BQP, the approach appears to be much more effective, particularly for large instances of 1000 or 2500 binary variables.     

The Value of the Value of Information

An important application of decision analysis is determining the value that information has to a decision maker. The expected value of information (EVOI) is the expected increase in the value (or decrease in the loss) associated with obtaining more information about quantities relevant to the decision process. The EVOI can be thought of as a measure of the importance of the uncertainty about a quantity in terms of the expected improvement in the decision that might be obtained from having additional information about it. Examples of EVOI quantities useful in risk management situations include the expected value of including uncertainty (EVIU), the expected value of perfect information (EVPI), and the expected value of sample information (EVSI). Value of information (VOI) analysis is useful because it makes the losses associated with decision errors explicit, balances competing probabilities and costs, helps identify the decision alternative that minimizes the expected loss, prioritizes spending on research, quantifies the value of the research to the decision maker, and provides an upper bound on what should be spent on getting information.     

Studies on generalized kinetic model and Pareto optimization of a product-driven self-cycling bioprocess

The aim of this study is the optimization of a product-driven self-cycling bioprocess and presentation of a way to determine the best possible decision variables out of a set of alternatives based on the designed model. Initially, a product-driven generalized kinetic model, which allows a flexible choice of the most appropriate kinetics is designed and analysed. The optimization problem is given as the bi-objective one, where maximization of biomass productivity and minimization of unproductive loss of substrate are the objective functions. Then, the Pareto fronts are calculated for exemplary kinetics. It is found that in the designed bioprocess, a decrease of emptying/refilling fraction and an increase of substrate feeding concentration cause an increase of the biomass productivity. An increase of emptying/refilling fraction and a decrease of substrate feeding concentration cause a decrease of unproductive loss of substrate. The preferred solutions are calculated using the minimum distance from an ideal solution method, while giving proposals of their modifications derived from a decision maker’s reactions to the generated solutions.     

A Multilevel Probabilistic Beam Search Algorithm for the Shortest Common Supersequence Problem

The shortest common supersequence problem is a classical problem with many applications in different fields such as planning, Artificial Intelligence and especially in Bioinformatics. Due to its NP-hardness, we can not expect to efficiently solve this problem using conventional exact techniques. This paper presents a heuristic to tackle this problem based on the use at different levels of a probabilistic variant of a classical heuristic known as Beam Search. The proposed algorithm is empirically analysed and compared to current approaches in the literature. Experiments show that it provides better quality solutions in a reasonable time for medium and large instances of the problem. For very large instances, our heuristic also provides better solutions, but required execution times may increase considerably.     

A Genetic Algorithm for the Bi-Level Topological Design of Local Area Networks

Local access networks (LAN) are commonly used as communication infrastructures which meet the demand of a set of users in the local environment. Usually these networks consist of several LAN segments connected by bridges. The topological LAN design bi-level problem consists on assigning users to clusters and the union of clusters by bridges in order to obtain a minimum response time network with minimum connection cost. Therefore, the decision of optimally assigning users to clusters will be made by the leader and the follower will make the decision of connecting all the clusters while forming a spanning tree. In this paper, we propose a genetic algorithm for solving the bi-level topological design of a Local Access Network. Our solution method considers the Stackelberg equilibrium to solve the bi-level problem. The Stackelberg-Genetic algorithm procedure deals with the fact that the follower’s problem cannot be optimally solved in a straightforward manner. The computational results obtained from two different sets of instances show that the performance of the developed algorithm is efficient and that it is more suitable for solving the bi-level problem than a previous Nash-Genetic approach.     

Resource-aware taxon selection for maximizing phylogenetic diversity

Phylogenetic diversity (PD) is a useful metric for selecting taxa in a range of biological applications, for example, bioconservation and genomics, where the selection is usually constrained by the limited availability of resources. We formalize taxon selection as a conceptually simple optimization problem, aiming to maximize PD subject to resource constraints. This allows us to take into account the different amounts of resources required by the different taxa. Although this is a computationally difficult problem, we present a dynamic programming algorithm that solves it in pseudo-polynomial time. Our algorithm can also solve many instances of the Noah's Ark Problem, a more realistic formulation of taxon selection for biodiversity conservation that allows for taxon-specific extinction risks. These instances extend the set of problems for which solutions are available beyond previously known greedy-tractable cases. Finally, we discuss the relevance of our results to real-life scenarios.     

Cultural assessment in bioethical advocacy--toward cultural competency in bioethical practice

The continued diversification of the U.S. population poses increasing challenges for bioethical advocates (e.g., ethicists, physicians, nurses, social workers, psychologists, surrogates, researchers, and lawyers), especially those serving rapidly expanding and culturally varied populations. The issue from the bioethics perspective is that the members of ethnically diverse groups often bring different normative expectations and their own preferred decision-making formats to the bioethics table. For example, some advocates will encounter a "collectivity," or the family-as-a-whole rather than the individual, as a decision maker. In other instances, they may encounter cultural groups whose members (or some of whose members) will value the principle of beneficence more than personal autonomy. Moreover, such value-based challenges are likely to continue since forecasters predict that diversification will actually quicken in the United States throughout the next five decades. In the face of these changes in the bioethical climate, advocates must be prepared to strengthen their cultural assessment skills. Taking a multidimensional approach to the problem yields a four-point cultural assessment model to help advocates handle the great diversity of outlook and orientation among their culturally diverse clientele.     

Exact methods for the robotic cell problem

This paper investigates an exact method for the Robotic Cell Problem. We present a branch-and-bound algorithm which is the first exact procedure specifically designed with regard to this complex flow shop scheduling variant. Also, we propose a new mathematical programming model as well as new lower bounds. Furthermore, we describe an effective genetic algorithm that includes, as a mutation operator, a local search procedure. We report the results of a computational study that provides evidence that medium-sized instances, with up to 176 operations, can be optimally solved. Also, we found that the new proposed lower bounds outperform lower bounds from the literature. Finally, we show, that the genetic algorithm delivers good solutions while requiring short CPU times.     

Surveillance for threatened and invasive species when uncertainty is severe

Aim This study develops methods for efficient surveillance and monitoring systems to address a wide range of problems in biosecurity, ecology and conservation biology. It focuses especially on surveillance systems relevant for management that aims to reduce trade in threatened species and curb the spread of potential pests and diseases. Location Melbourne, Australia. Methods This paper develops different approaches to make decisions about the allocation of resources that aim to avoid unacceptable outcomes. The analysis solves for the optimal allocation of surveillance effort in each of two facilities as a function of the arrival rates of invasive species in two facilities (that is, when the arrival rates are known). However, when arrival rates are unknown, it is not possible to solve for this optimum. The analysis also provides a satisficing approach for situations in which arrival rates are unknown, in which a degree of tolerance for deviating from the optimal solution is specified. Results The study provides simple analytical solutions to these two problems, analogous to results developed earlier in operations research. The analysis is illustrated with an example of the inspection of quarantine facilities for pests and diseases associated with trade. Main conclusions The best surveillance strategy depends on the choice of an objective function and the attitude of the decision‐maker to the robustness of the decision. The example application could be adapted to many other environmental surveillance scenarios.     

Coevolving solutions to the shortest common superstring problem

The shortest common superstring (SCS) problem, known to be NP-Complete, seeks the shortest string that contains all strings from a given set. In this paper we compare four approaches for finding solutions to the SCS problem: a standard genetic algorithm, a novel cooperative-coevolutionary algorithm, a benchmark greedy algorithm, and a parallel coevolutionary-greedy approach. We show the coevolutionary approach produces the best results, and discuss directions for future research.     

Organ Donation: Who Should Decide?—A Canadian Perspective

This paper examines an under-explored issue in organ donation: whose decision making authority should be privileged posthumously in the context of known, explicit consent for donation? Current practices in Canada support the family as the ultimate decision maker, despite the existence of legislative support in many Canadian provinces for the potential donor as legitimate decision maker. Arguments for and against privileging the family and the potential donor are identified. Informing the question of “who should decide” are considerations of individual and relational autonomy, distributive and social justice, personhood, and arguments “from distress”. Tensions and competing obligations emerge from an exploration of these considerations that call for further, inclusive dialogue and deliberation on this important organ donation issue.     

A DNA-based in vitroGenetic Program

In PNA-mediated Whiplash PCR (PWPCR), autonomous molecular computation is implemented by the recursive polymerase extension of a mixture of DNA hairpins. Like other methods based on exhaustive search, however, application to problem instances of realistic size is prevented by the exponential scaling of thesolution space. The tendency of evolving populations to minimize the sampling of large, low fitness basins suggests that a DNA-based evolutionary approach might be an effective alternative to exhaustive search. In this work, PWPCR is modified to support the evolution of a population of finite state machines. A practical, in vitroalgorithm for applying this architecture to evolve approximate solutions to instances of the NP-complete problem, Hamiltonian Pathis described in detail.     

Fast Generation of Sparse Random Kernel Graphs

The development of kernel-based inhomogeneous random graphs has provided models that are flexible enough to capture many observed characteristics of real networks, and that are also mathematically tractable. We specify a class of inhomogeneous random graph models, called random kernel graphs, that produces sparse graphs with tunable graph properties, and we develop an efficient generation algorithm to sample random instances from this model. As real-world networks are usually large, it is essential that the run-time of generation algorithms scales better than quadratically in the number of vertices n. We show that for many practical kernels our algorithm runs in time at most 𝒪(n(logn)²). As a practical example we show how to generate samples of power-law degree distribution graphs with tunable assortativity.