Over the years, the algorithms of evolutionary computation have emerged as popular tools for tackling complex real-world optimization problems. A common feature among these algorithms is that they focus on efficiently solving a single problem at a time. Despite the availability of a population of individuals navigating the search space, and the implicit parallelism of their collective behavior, seldom has an effort been made to multitask. Considering the power of implicit parallelism, we are drawn to the idea that population-based search strategies provide an idyllic setting for leveraging the underlying synergies between objective function landscapes of seemingly distinct optimization tasks, particularly when they are solved together with a single population of evolving individuals. As has been recently demonstrated, allowing the principles of evolution to autonomously exploit the available synergies can often lead to accelerated convergence for otherwise complex optimization tasks. With the aim of providing deeper insight into the processes of evolutionary multitasking, we present in this paper a conceptualization of what, in our opinion, is one possible interpretation of the complementarity between optimization tasks. In particular, we propose a synergy metric that captures the correlation between objective function landscapes of distinct tasks placed in synthetic multitasking environments. In the long run, it is contended that the metric will serve as an important guide toward better understanding of evolutionary multitasking, thereby facilitating the design of improved multitasking engines.

Consolidation lies at the heart of the last-mile logistics problem. Urban consolidation centers (UCCs) have been set up to facilitate such consolidation all over the world. To the best of our knowledge, most-if not all-of the UCCs operate on volume-based fixed-rate charges. To achieve environmental sustainability while ensuring economic sustainability in urban logistics, we propose, in this paper, a bicriteria auction mechanism for the automated assignment of last-mile delivery orders to transport resources. We formulate and solve the winner determination problem of the auction as a biobjective programming model. We then present a systematic way to generate the Pareto frontier to characterize the tradeoff between achieving economic and environmental sustainabilities in urban logistics. Finally, we demonstrate that our proposed bicriteria auction produces the solutions that significantly dominate those obtained from the fixed-rate mechanisms. Our sensitivity analysis on the willingness of carriers to participate in the UCC operation reveals that higher willingness is favorable toward achieving greater good for all, if UCC is designed to be nonprofit and self-sustaining.

The abundance of algorithms developed to solve different problems has given rise to an important research question: How do we choose the best algorithm for a given problem? Known as algorithm selection, this issue has been prevailing in many domains, as no single algorithm can perform best on all problem instances. Traditional algorithm selection and portfolio construction methods typically treat the problem as a classification or regression task. In this paper, we present a new approach that provides a more natural treatment of algorithm selection and portfolio construction as a ranking task. Accordingly, we develop a Ranking-Based Algorithm Selection (RAS) method, which employs a simple polynomial model to capture the ranking of different solvers for different problem instances. We devise an efficient iterative algorithm that can gracefully optimize the polynomial coefficients by minimizing a ranking loss function, which is derived from a sound probabilistic formulation of the ranking problem. Experiments on the SAT 2012 competition dataset show that our approach yields competitive performance to that of more sophisticated algorithm selection methods.

Profitable tour problem (PTP) belongs to the class of vehicle routing problem (VRP) with profits seeking to maximize the difference between the total collected profit and the total cost incurred. Traditionally, PTP involves single vehicle. In this paper, we consider PTP with multiple vehicles. Unlike the classical VRP that seeks to serve all customers, PTP involves the strategic-level customer selection so as to maximize the total collected profit and the operational-level route optimization to minimize the total cost incurred. Therefore, PTP is essentially the knapsack problem at the strategic level with VRP at the operational level. That means the evolutionary bi-level programming would be a suitable choice of methodology for solving the NP-hard PTP. Employing some evolutionary method to solve the bi-level program naively would undoubtedly be prohibitively expensive. We thus present in this paper the notion of knowledge adoption to approximate the initial solution to the lower-level optimization problem for a given trial solution of the upper-level decision variables. One may consider the knowledge adoption as a special case of knowledge transfer in which the transfer takes place within the same problem domain. Refining the approximate initial solution with local search forces it to quickly converge to some locally optimal solution. The better the estimation of the initial solution, the closer the local optimum will be to the global one. PTP finds its important application in the fields of transportation and logistics. In addressing last-mile problem using auction at the urban consolidation center (UCC), PTP plays a significant role in the winner determination problem (WDP) that follows. Empirical study demonstrates the efficacy of the proposed approach in solving the PTP-based WDP, yielding significantly higher profit, utilization, and service level compared to when the UCC adopts the conventional WDP based on multiple knapsack problem (i.e. the MKP-based WDP).

MOTIVATION: The need for efficient molecular docking tools for high-throughput screening is growing alongside the rapid growth of drug-fragment databases. AutoDock Vina ('Vina') is a widely used docking tool with parallelization for speed. QuickVina ('QVina 1') then further enhanced the speed via a heuristics, requiring high exhaustiveness. With low exhaustiveness, its accuracy was compromised. We present in this article the latest version of QuickVina ('QVina 2') that inherits both the speed of QVina 1 and the reliability of the original Vina. RESULTS: We tested the efficacy of QVina 2 on the core set of PDBbind 2014. With the default exhaustiveness level of Vina (i.e. 8), a maximum of 20.49-fold and an average of 2.30-fold acceleration with a correlation coefficient of 0.967 for the first mode and 0.911 for the sum of all modes were attained over the original Vina. A tendency for higher acceleration with increased number of rotatable bonds as the design variables was observed. On the accuracy, Vina wins over QVina 2 on 30% of the data with average energy difference of only 0.58 kcal/mol. On the same dataset, GOLD produced RMSD smaller than 2 Å on 56.9% of the data while QVina 2 attained 63.1%. AVAILABILITY AND IMPLEMENTATION: The C++ source code of QVina 2 is available at (www.qvina.org). CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Predicting binding between macromolecule and small molecule is a crucial phase in the field of rational drug design. AutoDock Vina, one of the most widely used docking software released in 2009, uses an empirical scoring function to evaluate the binding affinity between the molecules and employs the iterated local search global optimizer for global optimization, achieving a significantly improved speed and better accuracy of the binding mode prediction compared its predecessor, AutoDock 4. In this paper, we propose further improvement in the local search algorithm of Vina by heuristically preventing some intermediate points from undergoing local search. Our improved version of Vina-dubbed QVina-achieved a maximum acceleration of about 25 times with the average speed-up of 8.34 times compared to the original Vina when tested on a set of 231 protein-ligand complexes while maintaining the optimal scores mostly identical. Using our heuristics, larger number of different ligands can be quickly screened against a given receptor within the same time frame.

The success of Memetic Algorithms (MAs) has driven many researchers to be more focused on the efficiency aspect of the algorithms such that it would be possible to effectively employ MAs to solve computationally expensive optimization problems where single evaluation of the objective and constraint functions may require minutes to hours of CPU time. One of the important design issues in MAs is the choice of the individuals upon which local search procedure should be applied. Selecting only some potential individuals lessens the demand for functional evaluations hence accelerates convergence to the global optimum. In recent years, advances have been made targeting optimization problems with single equality constraint h(x) = 0. The presence of previously evaluated candidate solutions with different signs of constraint values within some localities thus allows the estimation of the constraint boundary. An individual will undergo local search only if it is sufficiently close to the approximated boundary. Elegant as it may seem, the approach had unfortunately assumed that every constraint function maps the design variables to optimize into unbounded real values. This, however, may not always be the case in practice. In this paper, we present a strategy to efficiently solve constrained problems with a single equality constraint; the function of which maps the design variables into restricted (either strictly non-negative or strictly non-positive) real values only.

The H1N1 influenza A 2009 pandemic caused a global concern as it has killed more than 18,000 people worldwide so far. Studies that have found cross-neutralizing antibodies between the 1918 and 2009 pandemic flu elicit a basis of pre-existing immunity against the 2009 H1N1 virus in old population. The cross-reactivity occurs due to conserved antigenic epitopes shared between the two pandemic viruses. However, evolutionary mutation can enable the virus to elude human immunity system, making these antibodies probably no longer effective. In our study, we found that a possible mutation in B-cell epitope (the sequence PNHDSNKG) could be the chance for the virus to escape the 1918 antibody recognition. Hence, this finding can be helpful for further vaccine designs against the H1N1 2009 influenza A virus.

An important issue in designing memetic algorithms (MAs) is the choice of solutions in the population for local refinements, which becomes particularly crucial when solving computationally expensive problems. With single evaluation of the objective/constraint functions necessitating tremendous computational power and time, it is highly desirable to be able to focus search efforts on the regions where the global optimum is potentially located so as not to waste too many function evaluations. For constrained optimization, the global optimum must either be located at the trough of some feasible basin or some particular point along the feasibility boundary. Presented in this paper is an instance of optinformatics where a new concept of modeling the feasibility structure of inequality-constrained optimization problems-dubbed the feasibility structure modeling-is proposed to perform geometrical predictions of the locations of candidate solutions in the solution space: deep inside any infeasible region, nearby any feasibility boundary, or deep inside any feasible region. This knowledge may be unknown prior to executing an MA but it can be mined as the search for the global optimum progresses. As more solutions are generated and subsequently stored in the database, the feasibility structure can thus be approximated more accurately. As an integral part, a new paradigm of incorporating the classification-rather than the regression-into the framework of MAs is introduced, allowing the MAs to estimate the feasibility boundary such that effective assessments of whether or not the candidate solutions should experience local refinements can be made. This eventually helps preventing the unnecessary refinements and consequently reducing the number of function evaluations required to reach the global optimum.

Many deterministic algorithms in the context of constrained optimization require the first-order derivatives, or the gradient vectors, of the objective and constraint functions to determine the next feasible direction along which the search should progress. Although the second-order derivatives, or the Hessian matrices, are also required by some methods such as the sequential quadratic programming (SQP), their values can be approximated based on the first-order information, making the gradients central to the deterministic algorithms for solving constrained optimization problems. In this paper, two ways of obtaining the gradients are compared under the framework of the simple memetic algorithm (MA) employing genetic algorithm (GA) and SQP. Despite the simplicity and straightforwardness of the finite-difference gradients, faster convergence rate can be achieved when the analytical gradients can be made available. The savings on the number of function evaluations as well as the amount of time taken to solve some benchmark problems are presented along with some discussions.

Regression has been successfully combined with the memetic algorithm (MA) for constructing surrogate models. It is essentially an attempt to approximate the objective or constraint landscape of a constrained optimization problem. Classification, on the other hand, has probably never been thought of being of any assistance to the MA. In fact, it can be used to approximate the feasibility boundary by means of some decision functions. The search effort can thus be focussed on the nearby region, recalling that many constrained optimization problems have their optimal solutions situated on the boundaries. This simply means that only potential individuals will undergo local refinements, reducing the number of function evaluations and accelerating the identification of the global optimum. Presented in this paper is a new approach that combines the support vector machine (SVM) with the MA to achieve this purpose.