Improved Genetic Operators for the Multiobjective Generalized Assignment Problem

• Robert F. Subtil CEFET-MG
• Eduardo G. Carrano CEFET-MG
• Ricardo H. C. Takahashi UFMG
• Marcone J. F. Souza UFOP
• Sérgio R. de Souza CEFET-MG

Resumo

The original formulation of the Generalized Assignment Problem (GAP) consists in, given a set of n different tasks and m different agents, assigning each task to an agent in such a way that a cost function is minimized. A previous work introduced the Equilibrium Function as a new objective function in the problem formulation. The purpose of this second objective function is to minimize the maximum difference between the amount of work assigned to the agents. This allows better distributions of the tasks between the agents than the results found from the original problem, with a small increase in the cost. This paper proposes new crossover and mutation operators that produce improvements in the algorithm presented in [Subtil et al. 2010], leading to considerably better Pareto approximations than the ones obtained in the previous work, within the same number of function evaluations. The proposed operators exploit problem-specific information in a probabilistic way, performing operations that lead to objective function enhancement or feasibility enhancement with greater probability than operations that do not cause such enhancements. A statistical comparison procedure is employed for supporting such conclusions.

Referências

Balachandran, V. (1976). An integer generalized transportation model for optimal job assignment in computer networks. Operations Research, 24:742–759.

Beasley, J. E. Or-library. [link].

Carrano, E. G., Takahashi, R. H. C., and Wanner, E. F. (2008). An enhanced statistical approach for evolutionary algorithm comparison. In Proceedings of the Genetic and Evolutionary Computation Conference - GECCO’08, Atlanta, USA.

Carrano, E. G., Wanner, E. F., and Takahashi, R. H. C. (2011). A multi-criteria statistical based comparison methodology for evaluating evolutionary algorithms. IEEE Transactions on Evolutionary Computation. to appear.

Chu, P. C. and Beasley, J. E. (1997). A genetic algorithm for the generalised assignment problem. Computers and Operations Research, 24:17–23.

Coello, C. A. C. (2000). An updated survey of GA-based multiobjective optimization techniques. ACM Computing Surveys, 32(2):109–143.

Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA II. IEEE Transactions on Evolutionary Computation, 6(2):182–197.

Efron, B. (1979). Bootstrap methods: Another look at the jackknife. The Annals of Statistics, 7:1–26.

Fisher, M. L. and Jaikumar, R. (2006). A generalized assignment heuristic for vehicle routing. Networks, 11:109–124.

Fonseca, C. M. and Fleming, P. (1995). An overview of evolutionary algorithms in multiobjective optimization. Evolutionary Computation, 3(1):1–16.

Lenstra, J. K., Shmoys, D. B., and Tardos, E. (1990). Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming: Series A and B, 46:259–271.

Lindman, H. R. (1974). Analysis of Variance in Complex Experimental Designs. W. H. Freeman & Co., San Francisco, USA.

Ross, G. T. and Soland, R. M. (1977). Modeling facility location problems as generalized assignment problems. Management Science, 24:345–357.

Sahni, S. and Gonzalez, T. (1976). P-complete approximation problems. Journal of the ACM, 23:555–565.

Subtil, R. F., Carrano, E. G., Souza, M. J. F., and Takahashi, R. H. C. (2010). Using an enhanced integer NSGA-II for solving the Multiobjective Generalized Assignment Problem. In Proc. IEEE World Congress on Computational Intelligence, Barcelona.

Turek, J., Wolf, J. L., and Yu, P. S. (1992). Approximate algorithms scheduling parallelizable tasks. In Proc. ACM Symposium on Parallel Algorithms and Architectures, San Diego, USA.

Yagiura, M., Glover, F., and Ibaraki, T. (2006). A path relinking approach with ejection chains for the generalized assignment problem. European Journal of Operational Research, 169:548–569.

Zitzler, E. (1999). Evolutionary algorithms for multiobjective optimization: Methods and applications. PhD thesis, Computer Engineering and Networks Laboratory - Swiss Federal Institute of Technology Zurich.