This paper proposes a machine learning (ML) based unified innovized progress (UIP) operator to simultaneously enhance the convergence and diversity capabilities of reference vector based evolutionary multi-and many-objective optimization algorithms, namely, RV-EMâOAs. Recent studies have demonstrated that ML intervention could help enhance convergence of RV-EMâOAs by capturing efficient search directions, through mapping of inter-generational solutions along the different reference vectors (RVs). This paper first demonstrates that ML intervention can also help enhance the diversity capability of RV-EMâOAs through mapping of intra-generational solutions across the RVs. Subsequently, the UIP operator integrates the convergence and diversity enhancement capabilities in a manner that is generic -applicable to different RV-EMâOAs, and practicable -not requiring any extra solution evaluations over the base RV-EMâOAs. Based on 24,056 experimental runs on multi-and many-objective problems, the UIP operator, when integrated with different RV-EMâOAs, has provided statistically better performance in about 36% instances, and better or equivalent in about 92% instances, compared to the respective base RV-EMâOAs.

The practicality of Pareto-dominance in solving many-objective optimization problems becomes questionable due to its inability to factor the critical human decision-making (HDM) elements, including the number of better objectives, the degree of betterment in objectives, and objectives’ relative preference. Relevant dominance principles are recently proposed to incorporate the first two HDM elements, often with the need for new tunable parameters. This article proposes a high-fidelity-dominance principle that factors all the three HDM elements, explicitly and simultaneously, and without requiring tuning of any parameter. This principle has been implemented in a reference-vector-based framework, leading to a computationally efficient many-objective evolutionary algorithm (MaOEA), namely, localized high-fidelity-dominance-based EA (LHFiD). Critically, LHFiD also has an inbuilt mechanism for on-the-fly determination of the timing for: 1) intermittent Nadir point estimation that enables faster convergence and 2) its self-termination that bears practically utility. This article is based on an extensive study involving 41 912 experiments, in which the proposed LHFiD approach is compared with the existing competitive MaOEAs. This article reports statistically better performance in about 60% instances, making it practical and worthy of further investigation and application.

Innovization is a task of learning common relationships among some or all of the Pareto-optimal (PO) solutions in multi- and many-objective optimization problems. A recent study has shown that a chronological sequence of nondominated solutions obtained along the successive generations of an optimizer possesses salient patterns that can be learnt using a Machine Learning (ML) model, and can help the offspring solutions progress in useful directions. This article enhances each constitutive module of the above approach, including novel interventions on management of the convergence-diversity tradeoff while mapping the solutions from the previous and current generation; use of a computationally more efficient ML method, namely, Random Forest (RF); and changing the manner and extent to which the learnt ML model is utilized toward advancement of the offspring. The proposed modules constitute what is called the enhanced innovized progress (IP2) operator. To investigate the search efficacy provided by the IP2 operator, it is integrated with multi-and many-objective optimization algorithms, such as NSGA-II, NSGA-III, MOEA/D, and MaOEA-IGD, and tested on a range of two- to ten-objective test problems, and five real-world problems. Since the IP2 operator utilizes the history of gradual and progressive improvements in solutions over generations, without requiring any additional solution evaluations, it opens up a new direction for ML-assisted evolutionary optimization.

Learning effective problem information from already explored search space in an optimization run, and utilizing it to improve the convergence of subsequent solutions, have represented important directions in Evolutionary Multi-objective Optimization (EMO) research. In this article, a machine learning (ML)-assisted approach is proposed that: (a) maps the solutions from earlier generations of an EMO run to the current non-dominated solutions in the decision space ; (b) learns the salient patterns in the mapping using an ML method, here an artificial neural network (ANN); and (c) uses the learned ML model to advance some of the subsequent offspring solutions in an adaptive manner. Such a multi-pronged approach, quite different from the popular surrogate-modeling methods, leads to what is here referred to as the Innovized Progress (IP) operator. On several test and engineering problems involving two and three objectives, with and without constraints, it is shown that an EMO algorithm assisted by the IP operator offers faster convergence behavior, compared to its base version independent of the IP operator. The results are encouraging, pave a new path for the performance improvement of EMO algorithms, and set the motivation for further exploration on more challenging problems.

Abstract Many real-world phenomena can be represented as dynamic graphs, i.e., networks that change over time. The problem of dynamic graph summarization, i.e., to succinctly describe the evolution of a dynamic graph, has been widely studied. Existing methods typically use objective measures to find fixed structures such as cliques, stars, and cores. Most of the methods, however, do not consider the problem of online summarization, where the summary is incrementally conveyed to the analyst as the graph evolves, and (thus) do not take into account the knowledge of the analyst at a specific moment in time. We address this gap in the literature through a novel, generic framework for subjective interestingness for sequential data. Specifically, we iteratively identify atomic changes, called ‘actions’, that provide most information relative to the current knowledge of the analyst. For this, we introduce a novel information gain measure, which is motivated by the minimum description length (MDL) principle. With this measure, our approach discovers compact summaries without having to decide on the number of patterns. As such, we are the first to combine approaches for data mining based on subjective interestingness (using the maximum entropy principle) with pattern-based summarization (using the MDL principle). We instantiate this framework for dynamic graphs and dense subgraph patterns, and present DSSG, a heuristic algorithm for the online summarization of dynamic graphs by means of informative actions, each of which represents an interpretable change to the connectivity structure of the graph. The experiments on real-world data demonstrate that our approach effectively discovers informative summaries. We conclude with a case study on data from an airline network to show its potential for real-world applications.

Automated Innovization procedure aims to extract hidden, non-intuitive, closed-form relationships from a design task without human intervention. Existing procedures involve the application of an Evolutionary Multi-objective optimization (EMO) Algorithm in two phases. The first phase of EMO algorithm leads to a set of Pareto-optimal (PO) solutions, while the second phase helps identify the implicit relationships. The latter involves clustering which in turn enables the evaluation of innovization-driven objective function. The existing procedures for Automated Innovization differ in their clustering technique and objective formulation. Unlike any existing study, this paper proposes a Unified Automated Innovization (UAI) framework which can deal with both continuous and discrete variable problems, and identify the inherent single- or multiple-cluster rules, as the case may be. The scope and efficacy of the proposed UAI, demonstrated through some benchmark design problems, is rooted in the novel contributions made in the clustering technique, and innovization-driven objective function formulation(s).

Multiobjective evolutionary algorithms evolve a population of solutions through successive generations toward the Pareto-optimal front (POF). One of the most critical questions faced by the researchers and practitioners in this domain relates to the number of generations that may be sufficient for an algorithm to offer a good approximation of the POF for a given problem. Ironically, to date, this question largely remains unanswered and the number of generations are arbitrarily fixed a priori, with potentially punitive implications. If the a priori fixed generations are insufficient, then the algorithm reports suboptimal solutions. In contrast, if the a priori fixed generations are far too many, it implies waste of computational resources. This paper proposes a novel entropy-based dissimilarity measure that helps identify on the fly the number of generations beyond which an algorithm stabilizes, implying that either a good approximation has been obtained or that it cannot be obtained due to the stagnation of the algorithm in the search space. Given that in either case no further improvement in the approximation can be obtained, despite additional computational expense, the proposed dissimilarity measure provides a termination criterion and facilitates a termination detection algorithm. The generality, on-the-fly implementation, low-computational complexity, and the demonstrated efficacy of the proposed termination detection algorithm, on a wide range of multiobjective and many-objective test problems, define the novel contribution of this paper.

The difficulties faced by existing multiobjective evolutionary algorithms (MOEAs) in handling many-objective problems relate to the inefficiency of selection operators, high computational cost, and difficulty in visualization of objective space. While many approaches aim to counter these difficulties by increasing the fidelity of the standard selection operators, the objective reduction approach attempts to eliminate objectives that are not essential to describe the Pareto-optimal front (POF). If the number of essential objectives is found to be two or three, the problem could be solved by the existing MOEAs. It implies that objective reduction could make an otherwise unsolvable (many-objective) problem solvable. Even when the essential objectives are four or more, the reduced representation of the problem will have favorable impact on the search efficiency, computational cost, and decision-making. Hence, development of generic and robust objective reduction approaches becomes important. This paper presents a principal component analysis and maximum variance unfolding based framework for linear and nonlinear objective reduction algorithms, respectively. The major contribution of this paper includes: 1) the enhancements in the core components of the framework for higher robustness in terms of applicability to a range of problems with disparate degree of redundancy; mechanisms to handle input data that poorly approximates the true POF; and dependence on fewer parameters to minimize the variability in performance; 2) proposition of an error measure to assess the quality of results; 3) sensitivity analysis of the proposed algorithms for the critical parameter involved, and the characteristics of the input data; and 4) study of the performance of the proposed algorithms vis-à-vis dominance relation preservation based algorithms, on a wide range of test problems (scaled up to 50 objectives) and two real-world problems.

Many objective optimization is a natural extension to multi-objective optimization where the number of objectives are significantly more than five. The performance of current state of the art algorithms (e.g. NSGA-II, SPEA2) is known to deteriorate significantly with increasing number of objectives due to the lack of adequate convergence pressure. It is of no surprise that the performance of NSGA-II on some constrained many-objective optimization problems (Deb and Saxena, 2006) (e.g., DTLZ5-(5,M), M = 10, 20) in an earlier study (Saxena, 2008) was far from satisfactory. Till date, research in many-objective optimization has focussed on two major areas (a) dimensionality reduction in the objective space and (b) preference ordering based approaches. This paper introduces a novel evolutionary algorithm powered by epsilon dominance (implemented within the framework of NSGA-II) and controlled infeasibility for improved convergence while the critical set of objectives is identified through a nonlinear dimensionality reduction scheme. Since approaching the Pareto-optimal front from within the feasible search space will need to overcome the problems associated with low selection pressure, the mechanism to approach the front from within the infeasible search space is promising as illustrated in this paper. The performance of the proposed algorithm is compared with NSGA-II (original, with crowding distance measure) and NSGA-II (epsilon dominance) on the above set of constrained multiobjective problems to highlight the benefits.

The notion ofoptimalsystemdesignholds thatinordertodasiatrulypsilamaximize/minimizeanobjectivefunction,thefeasiblesetneedstobeoptimized. Inspired by it, the attempt in our recent work was to incorporateconstraint-reductionin our earlier proposed procedures on dimensionality reduction of objectives. In that, while targetting constrained single-objective optimization problems (SOPs), we could arrive at a critical set of constraints and also their importance based rank-ordering. This information was used to study the shift from the constrained to the unconstrained optima. The methodology above was based on treating the a priori stated constraints as objectives besides the original-objective, and on applying (K. Deb et al., 2006), (D.K. Saxena et al., 2007) to this combined objective set-but-without constraints. In this work, the endeavor is to extend the above notion to the realm of multi-objective optimization problems (MOPs). Towards it, while we hire much from the above methodology, we make a fundamental shift, in that, we retain the a priori stated constraints, while evaluating the combined objective set. The motivation for this shift lies, in that, it allows more effective realization of the notion of system design than the approach in (D.K. Saxen et al., 2007). Reasonable effort has been spent on establishing this argument. Incorporating this change, a procedure for simultaneous reduction in objectives and constraints (for both SOPs, MOPs) is proposed, which also defines a realizable path towards optimal system design. Finally, the procedure is demonstrated on two test problems and one real world problem.

Preferences are ubiquitous in real life - many problems are over-constrained and would not be solvable if we insist that all our requirements are strictly met. This paper portrays ‘constraints’ in an unconventional perspective, based on the realization that in order to truly maximize/minimize objective function(s), one has to optimize the feasible set. On a broader level, this paper acknowledges the need to move from ‘optimizing the given’, towards ‘designing the optimal’. Here, the constraints are treated as objectives over and above the stated objective(s) and no other restrictions are used to ‘constrain’ the search space. We then evaluate this enhanced set of objectives, in terms of their criticality or redundancy. To this effect, we utilize our earlier proposed dimensionality reduction procedures [3], [7], to obtain a minimal set of objectives, which would characterize the original system with reasonable accuracy (from dimensionality reduction perspective) but with enhanced effectiveness (from a ‘system design’ perspective).