Computational Optimization and Innovation

Kalyanmoy Deb | |

*Affiliated and Supported by NSF-funded BEACON Center Study of Evolution in Action


The Computational Optimization and Innovation (COIN) Laboratory engages in research, development and application of single and multi-criterion optimization, and machine learning methodologies in handling various practicalities such as non-linear constraints, mixed-integer programming, large-dimensional problems, uncertainties in design variables and parameters, computationally expensive evaluation functions, bi-level problems, dynamic optimization problems, feature extraction, classification, search and big data handling problems. Creation of Innovative knowledge by analyzing optimized solutions is a unique expertise and focus of COIN Laboratory.

Research Scope and Achievements:

  • Modeling: Modeling objective and constraint functions for optimization from various scientific, engineering, technical, economic, and societal points of views from available data or by analyzing the problem.
  • Development of Customized Optimization Algorithms for Large-scale problems: It is well established that one optimization algorithm is not efficient for solving different problems. Thus, the choice of a suitable optimization algorithm for a particular problem is as important as solving the problem itself and requires a thorough knowledge and expertise in solving different problems. Prof. Deb has been working with industries since 1995 and engaged in optimization research since 1987. Figure 1 shows results from a recent application in casting sequence design for which a sub-quadratic complexity algorithm was developed (one Billion variable problem solved in a polynomial computational time complexity).
  • Hybrid Classical and Evolutionary Optimization Methods: Evolutionary optimization (EO) methods are ideal for a global overall search in handling non-smooth, multi-modal problems. Classical methods are ideal for performing a local search in handling smooth and convex problems. One of the focuses of COIN is to hybridize classical and EO methods in a manner that makes the switch adaptively depending on the status of search and without requiring any input from the user.
  • Non-linear constraints: Non-linear constraints make any search process difficult and stagnated. EO methods, due to their use of a population of points and broad search operators, are relatively less vulnerable to different complexities including non-linear nature of constraints. Prof. Deb developed parameter-less constraint handling approach ([1] with 2,397 citations) that is now used as default by EC researchers.
  • Mixed-integer problems: Many problems in practice involve discrete, integer, and continuous variables. Some problems also involve a schedule or a connectivity that is often represented as a permutation of a number of objects. Prof. Deb’s GeneAS [2] uses binary, real-parameter, and order-based genetic algorithms (GAs) for handling such problems. Simulated Binary Crossover (SBX) ([3] with 1,674 citations) and polynomial mutation operators [8] made significant impact in solving real-parameter optimization problems using GAs.
  • Computationally Expensive Problems: Many engineering design and process optimization problems involve expensive evaluation methods – use of FEM, CFD, flow-solvers are common. Some such problems are stochastic and require multiple evaluation schemes. COIN has developed computationally efficient meta-modeling methods based on Kriging, SVM, and response surface techniques that work with constraints and multiple objectives. COIN has also developed efficient integration schemes of combining meta-modeling with EO algorithms for a faster overall application.
  • Optimization with a Budget: Many practical problems pre-specify a limit on the use of overall number of solution evaluations based on the availability of expected time. COIN has developed computationally efficient algorithms for allocating solution evaluations optimally among meta-modeling method, available parallel computing hardware, and hybrid classical-EO methods for single and multi-objective problems.
  • Multiple Optimal Solutions: Many practical problems has multiple global and many local optimal solutions worth a consideration. Practitioners are often interested in finding not one, but a few global and local optimal solutions. Prof. Deb is a pioneer in multi-modal EOs for finding multiple optimal solutions in a single simulation and developed efficient “niched GAs” [4], [5]. Knowledge of multiple optimal solutions provide an opportunity to practitioners to first have a look at different alternate optimal solutions before choosing a single preferred solution.
  • Multiple conflicting objectives: No optimization problem in practice involves a single objective function. Cost and quality are two usual conflicting objectives of a design. Such multi-objective optimization problems give rise to multiple Pareto-optimal solutions. Prof. Deb has championed in developing efficient evolutionary multi-objective optimization (EMO) methods since 1994 and remains world’s leading expert in the field. His NSGA ([6] with 5,408 citations) and NSGA-II ([7] with 20,620 citations) are most popular methods in all areas of EC. COIN Lab continues to develop innovative methods in EMO and extend them to address various practicalities encountered in practical problems. 
  • Multi-criterion Optimization and Decision-making: In multi-objective optimization task, there is a need to choose a single preferred solution for its implementation. Prof. Deb has worked with Multiple Criteria Decision Making (MCDM) researchers to integrate efficient MCDM methods with EMO so that a decision making aid can be used a-priori, a-posteriori, or in an interactive manner [8],[9]. COIN Lab leads in this area of providing a complete solution to multi-objective optimization task, rather than finding just a set of trade-off solutions.
  • Optimization with Uncertainty: When design variables or associated problem parameters (including environmental conditions) are uncertain, what good is an optimal solution that is often isolated and overly sensitive to uncertainties? COIN Lab has developed “robust” single and multi-objective optimization methods that are capable of finding robust (instead of optimal) solutions that are relatively insensitive to uncertainties [10]. Optimal solutions are also risky for violating constraints in presence of uncertainties. COIN Lab’s research in developing reliability based, evidence based, and Bayesian based optimization methods are significant steps in making evolutionary optimization closer to practice.  
  • Many Conflicting Objectives: There exist many problems (involving societal and large-scale “wicked” problems) that involve five or more objectives. These so-called many-objective optimization problems require special dimension-handling optimization methods. COIN Lab’s latest research (development of NSGA-III) and its applications are significant contributions to optimization. NSGA-III is shown to solve up to 15-objective problems efficiently.
  • “Innovization” Innovative Knowledge Creation: Multiple high-performing trade-off solutions found from an EMO can be utilized to reveal vital properties common to the solutions. They provide “signature” properties of optimal solutions. Naturally, once found, they would provide new and innovative solution principles that dictate “how to create an optimal solution?” [11]. COIN Lab has recently developed machine learning procedures for finding “innovized” principles as rules and decision trees hidden in trade-off multi-objective data. COIN Lab’s research in this direction rejuvenates the importance of using optimization task in practice and provides a new meaning to the use of optimization in practice. 
  • Multiobjectivization: The principle of using at least two conflicting objectives and finding multiple trade-off solutions before choosing a single preferred solution can be extended to solve different problem-solving tasks including data mining and many single-objective optimization problems. COIN has developed efficient multi-modal optimization and constraint handling methods and continues to apply the concept to other problem areas.
  • Parallel and Distributed Optimization Methods: EO methods are highly parallelizable. COIN Lab uses latest GPU based hardware and parallel computers to develop computationally faster algorithms (making 500-1000 times faster than a single-processor application) for both single and multi-objective optimization problems.
  • Bi-level optimization problems: Many practical problems involve two nested optimization tasks -- an upper level optimization makes a solution feasible if it corresponds to an optimal solution of a lower-level optimization problem. Control problems, transportation problems, and structural design problems are some examples. Prof. Deb has pioneered in developing efficient methods for single and multi-objective bi-level problems.
  • Dynamic optimization problems: Most problems in practice are dynamic in nature -- the problem changes as the optimization task is ongoing. Prof. Deb has proposed efficient algorithms for handling dynamic problems in two different ways – off-line rule generation and “frozen-time” methods.
  • Practical Optimization: A major hallmark feature of COIN Lab is to solve practical problems. Prof. Deb helped develop “evORElution” software (for an Australian company “Orelogy”) for finding optimized mine schedules having multi-million variables. A recent collaborative work with NSF Beacon Center’s Director Prof. Erik Goodman and New Zealand’s Forest Research Lab scientist Dr. Oliver Chikumbo has resulted into an award-winning many-criterion application.  Prof. Deb and COIN Lab plan to continue to do award-winning work with industries and academics in solving challenging problems.