Improving the design of sequences for DNA computing: A multiobjective evolutionary approach

Designing oligonucleotide strands that selectively hybridize to reduce undesired reactions is a critical step for successful DNA computing. To accomplish this, DNA molecules must be restricted to a wide window of thermodynamical and logical conditions, which in turn facilitate and control the algorithmic processes implemented by chemical reactions. In this paper, we propose a multiobjective evolutionary algorithm for DNA sequence design that, unlike preceding evolutionary approaches, uses a matrix-based chromosome as encoding strategy. Computational results show that a matrix-based GA along with its specific genetic operators may improve the performance for DNA sequence optimization compared to previous methods.     

An evolutionary simulation-based optimization approach for dispatching scheduling

An effective scheduling decision is one of the key factors towards improving the efficiency of a system’s performance, particularly in the instance of multiple products thus dispatching rules have been widely used for real-time scheduling because they can provide a very quick and pretty good solution. However, deciding how to select appropriate rules is very difficult. In this paper, we develop evolutionary simulation-based heuristics to construct near-optimal solutions for dispatching rule allocation. Our heuristic is easy to use and gives a manager a useful tool for testing a configuration that can minimize certain performance measures. The optimization heuristics are used to determine priority strategies to maximize the performance of a complex manufacturing system with a large number of different products, along with an overtime that changes with a mix of different process types, including assembly and disassembly operations and with different types of internal and external disturbances. Modeling is carried out using discrete-event simulation. Case study analysis is of a commercial offset printing production system.     

A spectral clustering algorithm for manufacturing cell formation

A graph clustering algorithm constructs groups of closely related parts and machines separately. After they are matched for the least intercell moves, a refining process runs on the initial cell formation to decrease the number of intercell moves. A simple modification of this main approach can deal with some practical constraints, such as the popular constraint of bounding the maximum number of machines in a cell. Our approach makes a big improvement in the computational time. More importantly, improvement is seen in the number of intercell moves when the computational results were compared with best known solutions from the literature.     

A new branch-&-bound-enhanced genetic algorithm for the manufacturing cell formation problem

This paper deals with the manufacturing cell formation (MCF) problem, which is based on group technology principles, using a graph partitioning formulation. An attempt has been made to take into account the natural constraints of real-life production systems, such as operation sequences, minimum and maximum numbers of cells, and maximum cell sizes. Cohabitation constraints were added to the proposed model in order to deal with the necessity of grouping certain machines in the same cell for technical reasons, and non-cohabitation constraints were included to prevent placing certain machines in close vicinity.     

A Kriging-assisted multiobjective evolutionary algorithm

A surrogate-assisted (SA) evolutionary algorithm for Multiobjective Optimization Problems (MOOPs) is presented as a contribution to Soft Computing (SC) in Artificial Intelligence (AI). Such algorithm is grounded on the cooperation between a “pure” evolutionary algorithm and a Kriging based algorithm featuring the Expected Hyper-Volume Improvement (EHVI) metric. Comparison with state-of-art pure and Kriging-assisted algorithms over two- and three-objective test functions have demonstrated that the proposed algorithm can achieve high performance in the approximation of the Pareto-optimal front mitigating the drawbacks of its parent algorithms.     

Comparison of experimental designs for simulation-based symbolic regression of manufacturing systems

In this article, an empirical analysis of experimental design approaches in simulation-based metamodelling of manufacturing systems with genetic programming (GP) is presented. An advantage of using GP is that prior assumptions on the structure of the metamodels are not required. On the other hand, having an unknown structure necessitates an analysis of the experimental design techniques used to sample the problem domain and capture its characteristics. Therefore, the study presents an empirical analysis of experimental design methods while developing GP metamodels to predict throughput rates in a common industrial system, serial production lines. The objective is to identify a robust sampling approach suitable for GP in simulation-based metamodelling. Experiments on different sizes of production lines are presented to demonstrate the effects of the experimental designs on the complexity and quality of approximations as well as their variance. The analysis showed that GP delivered system-wide metamodels with good predictive characteristics even with the limited sample data.     

Three-objective subgraph mining using multiobjective evolutionary programming

The existing methods for graph-based data mining (GBDM) follow the basic approach of applying a single-objective search with a user-defined threshold to discover interesting subgraphs. This obliges the user to deal with simple thresholds and impedes her/him from evaluating the mined subgraphs by defining different “goodness” (i.e., multiobjective) criteria regarding the characteristics of the subgraphs. In previous papers, we defined a multiobjective GBDM framework to perform bi-objective graph mining in terms of subgraph support and size maximization. Two different search methods were considered with this aim, a multiobjective beam search and a multiobjective evolutionary programming (MOEP). In this contribution, we extend the latter formulation to a three-objective framework by incorporating another classical graph mining objective, the subgraph diameter. The proposed MOEP method for multiobjective GBDM is tested on five synthetic and real-world datasets and its performance is compared against single and multiobjective subgraph mining approaches based on the classical Subdue technique in GBDM. The results highlight the application of multiobjective subgraph mining allows us to discover more diversified subgraphs in the objective space.     

Increasing selective pressure towards the best compromise in evolutionary multiobjective optimization: The extended NOSGA method

Most current approaches in the evolutionary multiobjective optimization literature concentrate on adapting an evolutionary algorithm to generate an approximation of the Pareto frontier. However, finding this set does not solve the problem. The decision-maker still has to choose the best compromise solution out of that set. Here, we introduce a new characterization of the best compromise solution of a multiobjective optimization problem. By using a relational system of preferences based on a multicriteria decision aid way of thinking, and an outranked-based dominance generalization, we derive some necessary and sufficient conditions which describe satisfactory approximations to the best compromise. Such conditions define a lexicographic minimum of a bi-objective optimization problem, which is a map of the original one. The NOSGA-II method is a NSGA-II inspired efficient way of solving the resulting mapped problem.     

Integrated multiobjective optimization and a priori preferences using genetic algorithms

One of the tasks of decision-making support systems is to develop methods that help the designer select a solution among a set of actions, e.g. by constructing a function expressing his/her preferences over a set of potential solutions. In this paper, a new method to solve multiobjective optimization (MOO) problems is developed in which the user’s information about his/her preferences is taken into account within the search process. Preference functions are built that reflect the decision-maker’s (DM) interests and use meaningful parameters for each objective. The preference functions convert these objective preferences into numbers. Next, a single objective is automatically built and no weight selection is performed. Problems found due to the multimodality nature of a generated single cost index are managed with Genetic Algorithms (GAs). Three examples are given to illustrate the effectiveness of the method.     

A genetic algorithm approach for group formation in collaborative learning considering multiple student characteristics

Considering that group formation is one of the key processes in collaborative learning, the aim of this paper is to propose a method based on a genetic algorithm approach for achieving inter-homogeneous and intra-heterogeneous groups. The main feature of such a method is that it allows for the consideration of as many student characteristics as may be desired, translating the grouping problem into one of multi-objective optimization. In order to validate our approach, an experiment was designed with 135 college freshmen considering three characteristics: an estimate of student knowledge levels, an estimate of student communicative skills, and an estimate of student leadership skills. Results of such an experiment allowed for the validation, not only from the computational point of view by measuring the algorithmic performance, but also from the pedagogical point of view by measuring student outcomes, and comparing them with two traditional group formation strategies: random and self-organized.     

A parallel double-level multiobjective evolutionary algorithm for robust optimization

Robust optimization is a popular method to tackle uncertain optimization problems. However, traditional robust optimization can only find a single solution in one run which is not flexible enough for decision-makers to select a satisfying solution according to their preferences. Besides, traditional robust optimization often takes a large number of Monte Carlo simulations to get a numeric solution, which is quite time-consuming. To address these problems, this paper proposes a parallel double-level multiobjective evolutionary algorithm (PDL-MOEA). In PDL-MOEA, a single-objective uncertain optimization problem is translated into a bi-objective one by conserving the expectation and the variance as two objectives, so that the algorithm can provide decision-makers with a group of solutions with different stabilities. Further, a parallel evolutionary mechanism based on message passing interface (MPI) is proposed to parallel the algorithm. The parallel mechanism adopts a double-level design, i.e., global level and sub-problem level. The global level acts as a master, which maintains the global population information. At the sub-problem level, the optimization problem is decomposed into a set of sub-problems which can be solved in parallel, thus reducing the computation time. Experimental results show that PDL-MOEA generally outperforms several state-of-the-art serial/parallel MOEAs in terms of accuracy, efficiency, and scalability.     

A hybrid multi-objective approach based on the genetic algorithm and neural network to design an incremental cellular manufacturing system

One important issue related to the implementation of cellular manufacturing systems (CMSs) is to decide whether to convert an existing job shop into a CMS comprehensively in a single run, or in stages incrementally by forming cells one after the other, taking the advantage of the experiences of implementation. This paper presents a new multi-objective nonlinear programming model in a dynamic environment. Furthermore, a novel hybrid multi-objective approach based on the genetic algorithm and artificial neural network is proposed to solve the presented model. From the computational analyses, the proposed algorithm is found much more efficient than the fast non-dominated sorting genetic algorithm (NSGA-II) in generating Pareto optimal fronts.     

A mathematical programming model for manufacturing cell formation to develop multiple configurations

This paper presents and analyses a mathematical model for the design of manufacturing cells which considers two conflicting objectives such as the heterogeneity of cells and the intercell moves. A genetic algorithm (GA) based solution methodology is developed for the model which is also solved using an optimization package. The model is suitable for getting multiple potential solutions in a structured way for the cell formation problem by making a trade-off between the two objectives, instead of reaching at a single negotiating solution. This model provides the decision maker the flexibility of choosing a suitable cell design from different alternatives by considering the practical constraints. A part assignment heuristic is also developed by which part-families can be identified and is integrated with the GA based solution procedure. A comparison of the proposed method is made with other seven methods using 36 problems from the literature. Grouping efficacy is the basis for comparison and it is found to give reasonably good results.     

Approximated set-valued mapping approach for handling multiobjective bilevel problems

A significant amount of research has been done on bilevel optimization problems both in the realm of classical and evolutionary optimization. However, the multiobjective extensions of bilevel programming have received relatively little attention from researchers in both the domains. The existing algorithms are mostly brute-force nested strategies, and therefore computationally demanding. In this paper, we develop insights into multiobjective bilevel optimization through theoretical progress made in the direction of parametric multiobjective programming. We introduce an approximated set-valued mapping procedure that would be helpful in the development of efficient evolutionary approaches for solving these problems. The utility of the procedure has been emphasized by incorporating it in a hierarchical evolutionary framework and assessing the improvements. Test problems with varying levels of complexity have been used in the experiments.     

A double-multiplicative dynamic penalty approach for constrained evolutionary optimization

The present paper proposes a double-multiplicative penalty strategy for constrained optimization by means of genetic algorithms (GAs). The aim of this research is to provide a simple and efficient way of handling constrained optimization problems in the GA framework without the need for tuning the values of penalty factors for any given optimization problem. After a short review on the most popular and effective exterior penalty formulations, the proposed penalty strategy is presented and tested on five different benchmark problems. The obtained results are compared with the best solutions provided in the literature, showing the effectiveness of the proposed approach.     

An evolutionary approach to generalized biobjective traveling salesperson problem

We consider the generalized biobjective traveling salesperson problem, where there are a number of nodes to be visited and each node pair is connected by a set of edges. The final route requires finding the order in which the nodes are visited (tours) and finding edges to follow between the consecutive nodes of the tour. We exploit the characteristics of the problem to develop an evolutionary algorithm for generating an approximation of nondominated points. For this, we approximate the efficient tours using approximate representations of the efficient edges between node pairs in the objective function space. We test the algorithm on several randomly-generated problem instances and our experiments show that the evolutionary algorithm approximates the nondominated set well.     

Genetic algorithms to solve the cover printing problem

Inspired by successful application of evolutionary algorithms to solving difficult optimization problems, we explore in this paper, the applicability of genetic algorithms (GAs) to the cover printing problem, which consists in the grouping of book covers on offset plates in order to minimize the total production cost. We combine GAs with a linear programming solver and we propose some innovative features such as the “unfixed two-point crossover operator” and the “binary stochastic sampling with replacement” for selection. Two approaches are proposed: an adapted genetic algorithm and a multiobjective genetic algorithm using the Pareto fitness genetic algorithm. The resulting solutions are compared. Some computational experiments have also been done to analyze the effects of different genetic operators on both algorithms.     

The two-stage recombination operator and its application to the multiobjective 0/1 knapsack problem: A comparative study

In this paper, we first propose a new recombination operator called the two-stage recombination and then we test its performance in the context of the multiobjective 0/1 knapsack problem (MOKP). The proposed recombination operator generates only one offspring solution from a selected pair of parents according to the following two stages. In the first stage, called genetic shared-information stage or similarity-preserving stage, the generated offspring inherits all parent similar genes (i.e., genes or decision variables having the same positions and the same values in both parents). In the second stage, called problem fitness-information stage, the parent non-similar genes (i.e., genes or decision variables having the same positions but different values regarding the two parents) are selected from one of the two parents using some fitness information. Initially, we propose two different approaches for the second stage: the general version and the restricted version. However, the application of the restricted version to the MOKP leads to an improved version which is more specific to this problem. The general and the MOKP-specific versions of the two-stage recombination are compared against three traditional crossovers using two well-known multiobjective evolutionary algorithms. Promising results are obtained. We also provide a comparison between the general version and the MOKP-specific version.     

A solution process for simulation-based multiobjective design optimization with an application in the paper industry

In this paper, we address some computational challenges arising in complex simulation-based design optimization problems. High computational cost, black-box formulation and stochasticity are some of the challenges related to optimization of design problems involving the simulation of complex mathematical models. Solving becomes even more challenging in case of multiple conflicting objectives that must be optimized simultaneously. In such cases, application of multiobjective optimization methods is necessary in order to gain an understanding of which design offers the best possible trade-off. We apply a three-stage solution process to meet the challenges mentioned above. As our case study, we consider the integrated design and control problem in paper mill design where the aim is to decrease the investment cost and enhance the quality of paper on the design level and, at the same time, guarantee the smooth performance of the production system on the operational level. In the first stage of the three-stage solution process, a set of solutions involving different trade-offs is generated with a method suited for computationally expensive multiobjective optimization problems using parallel computing. Then, based on the generated solutions an approximation method is applied to create a computationally inexpensive surrogate problem for the design problem and the surrogate problem is solved in the second stage with an interactive multiobjective optimization method. This stage involves a decision maker and her/his preferences to find the most preferred solution to the surrogate problem. In the third stage, the solution best corresponding that of stage two is found for the original problem.