Decision Support
A hybrid genetic algorithm for multiobjective problems with activity analysis-based local search

https://doi.org/10.1016/j.ejor.2007.10.050Get rights and content

Abstract

The objective of this research was the development of a method that integrated an activity analysis model of profits from production with a biophysical model, and included the capacity for optimization over multiple objectives. We specified a hybrid genetic algorithm using activity analysis as a local search method, and NSGA-II for calculation of the multiple objective Pareto optimal set. We describe a parallel computing approach to computation of the genetic algorithm, and apply the algorithm to evaluation of an input tax to regulate pollution from agricultural production.

Introduction

The Conservation Effects Assessment Project (CEAP) at the Agriculture Research Service, United States Department of Agriculture, has the objective of producing a national assessment of environmental benefits of conservation programs to support policy decision and program implementation.1 As part of the CEAP economics team, we were charged with the development of a method that integrated an economic model of agricultural production with a biophysical model. Further, the method had requirements to optimize over multiple objectives to show the trade-offs among alternative conservation practices. We chose a model derived from an activity analysis model proposed by Shephard (1970). In this study, we differentiate activity analysis and data envelopment analysis (DEA). Data envelopment analysis (Charnes et al., 1978, Cooper et al., 2004) is generally considered to be an approach to for evaluation of the performance of a set of decision-making units (DMU) by the calculation of efficiency and related measures. Färe and Grosskopf (2002) point out that the DEA approach of Charnes et al. (1978) coincides with Shephard’s (1970) activity analysis output price model. Much of literature that we reference concerns DEA, but is identically applicable to activity analysis. We note that where an activity analysis model is used to specify an objective in this study, a DEA model could be used in exactly the same way if the objective concerned the classic DEA results, such as efficiency. Our interest here is to calculate the maximum profit possible for each DMU. We use an activity analysis model that establishes the production possibility frontier by constraining input/output combinations to lie within a production possibility set defined by experimental observation. Variations of the activity analysis model have been usefully applied to agricultural production in several studies, and have also been integrated with the biophysical model, soil and water assessment tool (SWAT) (Whittaker et al., 2003).

Fig. 1 illustrates the requirements of the CEAP project. First, consider the calculation of the trade-offs between two objectives, maximization of farm profit and minimization of surface water pollution resulting from farm production, where a “green” tax is imposed on fertilizer (Fig. 1a). The first objective is specified by an activity analysis model that calculates maximum farm profit, constrained by fertilizer taxation. The second objective is specified by using the optimal inputs and outputs chosen by the profit maximizing activity analysis model to drive a physical model that calculates the chemical pollution from farm production.

The CEAP objectives also require the use of multiple activity analysis models to calculate the trade-offs among objectives. In Fig. 1b, two different activity analysis models are used to specify the objectives of profit maximization and policy efficiency, where policy efficiency is defined in the context of CEAP as the expenditure on conservation programs per unit increase in environmental quality. Activity Analysismodel 1 calculates inputs and outputs to maximize farm level profit and Activity Analysismodel 2 optimizes industry wide (see for example, Brännlund et al. (1998). The Pareto frontiers represented in Fig. 1 can be easily calculated a single point at a time by applying a series of weights to the objectives. However, the CEAP program requires the calculation of the Pareto frontier for all objectives at once; a surface in four dimensional space (farm level profit, environmental quality, program efficiency, and location within the watershed). Calculation of a Pareto optimal surface in four dimensional space, one point at time, is not practical without an algorithm to direct the search. A more formal statement of the problem described above follows.

A multi-objective optimization problem (MOOP) is generally understood to contain a number of objective functions that are to be minimized. Following Deb (2001), the general form of a MOOP isMinimize/Maximizefm(x),m=1,2,,M,subject togj(x)0,j=1,2,,J,hk(x)=0,k=1,2,,K,xiLxixjUi=1,2,,n.The MOOP consists of M objective functions, with J inequality constraints and K equality constraints. A solution x is a vector of n decision variables that are constrained by lower xiL and upper xiU boundaries. This formulation of a MOOP strongly resembles both activity analysis and data envelopment model specifications. Some researchers have pointed out that DEA itself is a multiple criteria decision analysis (MCDA) method, where multiple inputs and outputs function as multiple criteria (Jahanshahloo and Foroughi, 2005, Korhonen and Syrjänen, 2004, Li and Reeves, 1999). Others have noted common elements in DEA and multiple criteria analysis methods, and have combined the two approaches in identifying the most efficient firms (Belton, 1992, Belton and Stewart, 1999, Belton and Vickers, 1993, Joro et al., 1998).The application that motivates the research presented here requires a more general interpretation of (1). The CEAP project plan requires that several objective functions fm(x) can be specified by a separate activity analysis model for each m, e.g. profit maximization at the firm level for m = 1 and permit trading at the watershed level for m = 2. It is additionally required that other objective functions fm(x) are defined by an altogether different specification that can include hydrologic and agronomic models.

The simplest way to calculate a MOOP with activity analysis specification of multiple objectives is to convert the problem into a single objective by using a weighting vector (Soloveitchik et al., 2002). The concept of value efficiency has been used to incorporate preferences (and by extension, multiple objectives) into DEA (Färe et al., 2004, Halme et al., 1999) for the calculation of optimal solutions, but is limited to calculation of one result for each set of parameters supplied by the user. DEA has been used in a genetic algorithm as a method for selection, but has not been included in the objective function (Yun et al., 2004). This study extends research in this area with the introduction of a method where a genetic algorithm is used for optimization, and activity analysis and an integrated activity analysis/biophysical model are incorporated in a hybrid genetic algorithm that is able to calculate the Pareto optimal set for multiple objectives in a single run. The next section describes the algorithm and places it in context in the literature. The third section of this paper describes the way activity analysis works within the evaluation module of a genetic algorithm. We end by demonstrating the proposed algorithm with an application to the analysis of an environmental policy with multiple objectives concerning agricultural production and emissions. The application section also describes the computational scheme and a way to parallelize the problem for execution on a computer cluster.

Section snippets

Structure of the hybrid genetic algorithm

A simple genetic algorithm (GA) is an iterative algorithm based on retention of the best or “fittest” members of a population of answers until a stopping condition is satisfied (Goldberg, 1989). In an optimization application, the GA consists of an initial randomly generated population that is evaluated for fitness using an objective function, a test for convergence, and application of the GA operations of selection, crossover and mutation. These elements are followed iteratively until an

Activity analysis as a local search method

Activity analysis, introduced by Von Neumann (1937) and extended by Shephard, among others (Koopmans, 1951, Shephard, 1953, Shephard, 1970), is especially effective for analyzing multiple inputs and multiple outputs. The usual computational specification is a linear program that finds the optimum combination of inputs and outputs by a comparison of the observed combinations. Our motivation lies in profit maximization of the firm, so we will discuss a profit maximization specification of an

Application of the activity analysis hybrid GA

To demonstrate the algorithm, we applied it to the calculation of the Pareto optimal set for two conflicting objectives using an input tax as an environmental policy instrument. The example incorporates the features required by the Conservation Effects Assessment Project; multiple objectives, a biophysical model, and multiple activity analysis models. The use of only two objectives allows the structure of the algorithm, data flow and results to be easily visualized.

The first objective is

Conclusion

The strategy of using activity analysis as a local search method in a genetic algorithm provides a fast method for calculation of the Pareto optimal set for multiple objectives. The hybrid activity analysis genetic algorithm can be modified to execute on a parallel computer. This approach also facilitates integration of a biophysical model with an economic model in the optimization. The approach has immediate application in evaluation of agricultural and environmental policy.

References (32)

  • R. Brännlund et al.

    Emissions trading and profitability: The Swedish pulp and paper industry

    Environmental and Resource Economics

    (1998)
  • R.B. Confesor et al.

    Automatic calibration of hydrologic models with multi-objective evolutionary algorithm and Pareto optimization

    Journal of the American Water Resources Association

    (2007)
  • W.W. Cooper et al.

    Handbook on Data Envelopment Analysis

    (2004)
  • K. Deb

    Multi-objective Optimization Using Evolutionary Algorithms

    (2001)
  • K. Deb et al.

    A fast and elitist multiobjective genetic algorithm: NSGA-II

    IEEE Transactions on Evolutionary Computation

    (2002)
  • R. Färe et al.

    Two perspectives on DEA: Unveiling the link between CCR and Shephard

    Journal of Productivity Analysis

    (2002)
  • Cited by (66)

    • A multi-objective approach for supply chain design considering disruptions impacting supply availability and quality

      2018, Computers and Industrial Engineering
      Citation Excerpt :

      For example, Ding, Benyoucef, and Xie (2009) proposed an NSGA II-based genetic algorithm to optimize the design of a production-distribution network. While NSGA II offers a general ranking approach to measure the distance of a solution to the empirical Pareto-optimal front with respect to a population of solutions, a data envelopment analysis (DEA) based approach may be more appropriate when there is a clear economic interpretation of the relationship between multiple conflicting objectives (Ankaiah & Ravi, 2015; Li, Liao, & Coit, 2009; Lin, Sir, & Pasupathy, 2013; Wang, Ochoa, & Harrison, 2011; Whittaker et al., 2009). DEA is a powerful non-parametric linear programming-based technique to measure the relative efficiency of a decision-making unit (DMU) relative to a set of decision-making units (Bian, 2008; Fare & Grosskopf, 2004; Hadi-Vencheh, Kazemi-Matin, & Tavassoli-Kajani, 2005; Seiford & Zhu, 2002).

    • Matheuristic approaches for parallel machine scheduling problem with time-dependent deterioration and multiple rate-modifying activities

      2018, Computers and Operations Research
      Citation Excerpt :

      The general pseudo-code of SA_EM is as follows: Local search heuristics are widely used in metaheuristic algorithms to improve solutions (Asadzadeh, 2015; Vallada and Ruiz, 2011; Whittaker et al., 2009). Although buckets are effectively constructed by the bucket construction heuristic, it is still necessary for a tight bucket construction to enhance solution quality.

    • Spatial targeting of agri-environmental policy using bilevel evolutionary optimization

      2017, Omega (United Kingdom)
      Citation Excerpt :

      One of the early approaches to bilevel optimization [37] uses a linear program (LP) for lower level optimization and a genetic algorithm for upper level optimization. Our approach is related to this work, where we use a hybrid genetic algorithm that uses linear programming to solve DEA (or activity analysis) problems at the lower level and NSGA-II for upper level multiple objective optimization [56]. Genetic algorithms (GAs) are an approach to optimization loosely based on the Darwinian evolutionary process [23].

    View all citing articles on Scopus

    The use of trade, firm, or corporation names in this publication (or page) is for the information and convenience of the reader. Such use does not constitute an official endorsement or approval by the United States Department of Agriculture or the Agricultural Research Service of any product or service to the exclusion of others that may be suitable.

    View full text