بکارگیری الگوریتم ژنتیک GA برای ماکزیمم کردن کارایی فنی در تحلیل پوششی داده ها DEA

ABSTRACT Using Genetic Algorithms for Maximizing Technical Efficiency in Data Envelopment Analysis

Over the past 50 years technologies have been estimated using many different approaches [9]. The two principal methods are stochastic frontiers, which use econometric techniques, and Data Envelopment Analysis (DEA), which is a non-parametric technique based on mathematical programming for the evaluation of technical efficiency of a set of decision making units (DMUs) that consume inputs to produce outputs [10]. Unlike other efficiency methodologies, DEA simultaneously provides both an efficiency score and benchmarking information through efficient targets. In DEA, the efficiency score is obtained from the distance between the assessed DMU and a point at the frontier of the technology, which serves as an efficient target for the assessed DMU.

efficient targets that maximize the final level of technical efficiency (see [2, 3, 5] to name but a few). This contrasts with the usual approaches followed from the origins of DEA, where only the furthest efficient targets are calculated for computational reasons. Indeed, maximizing technical efficiency is computationally difficult while minimizing technical efficiency is easier, since this is usually associated with the resolution of a standard linear program.

Regarding papers that have studied the computational aspects of DEA models associated with the determination of the least distance to the frontier and, therefore, related to the maximization of the technical efficiency, we cite Aparicio et al. [4] and Jahanshahloo et al. [11, 12, 13]. Some approaches are based on Mixed Integer Linear Programming or Bilevel Linear Programming, while others are derived from algorithms that allow the determination of all the facets of a polyhedron. As we will argue in Section 2, all these approaches have their strong and weak points and, consequently, there is currently no approach accepted as the best solution to the problem.

The approach in [4], based on Mixed Integer Linear Programming, is used and we use metaheuristics to try to solve the model these authors introduced. The complexity of the model makes it difficult to generate solutions satisfying all the restrictions. In [7, 14] heuristics were used to generate valid solutions for a subset of restrictions of the problem of maximizing technical efficiency in DEA. In this paper, all the constraints have been incorporated (in the previous papers only 9 of 14 constraints were considered), the heuristics are improved, and new ones are developed, so initial populations of solutions satisfying all the constraints are generated. Additionally, the solutions generated by our approach for a battery of simulated databases are compared with the solutions obtained through the determination of all the facets of the frontier in DEA (see [1]). In this case, the optimizer CPLEX was used to measure technical efficiency.

The remainder of the paper is organized as follows. In Section 2, a brief introduction of the main notions associated with Data Envelopment Analysis is presented, and the existing approaches for maximizing efficiency are outlined. Then, heuristic methods to generate initial populations with valid solutions are studied in Section 3. After that, a Genetic Algorithm to improve the solutions is discussed in Section 4. In Section 5, the results of some experiments are summarized. Section 6 concludes the paper and outlines some possible research directions.