Computational Methods for Two-Level 0-1 Programming Problems through Distributed Genetic Algorithms

• Autorzy: Niwa K. , Hayashida T. , Sakawa M.
• Języki publikacji: EN

Abstrakty

EN

In this paper, we consider a two-level 0-1 programming problem in which there is not coordination between the decision maker (DM) at the upper level and the decision maker at the lower level. We propose a revised computational method that solves problems related to computational methods for obtaining the Stackelberg solution. Specifically, in order to improve the computational accuracy of approximate Stakelberg solutions and shorten the computational time of a computational method implementing a genetic algorithm (GA) proposed by the authors, a distributed genetic algorithm is introduced with respect to the upper level GA, which handles decision variables for the upper level DM. Parallelization of the lower level GA is also performed along with parallelization of the upper level GA. The proposed algorithm is also improved in order to eliminate unnecessary computation during operation of the lower level GA, which handles decision variables for the lower level DM. In order to verify the effectiveness of the proposed method, we propose comparisons with existing methods by performing numerical experiments to verify both the accuracy of the solution and the time required for the computation.

Słowa kluczowe

EN

distributed genetic algorithm; Stackelberg solution; two-level 0-1 programming problem

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2010
• Tom: nr 2
• Strony: 78--87
• Opis fizyczny: Bibliogr. 17 poz., rys., tab.

Twórcy

autor

Niwa K.

autor

Hayashida T.

autor

Sakawa M.

• Department for Information Systems in Business, Faculty of Economics, Hiroshima University of Economics, Hiroshima, 731-0192, Japan,

Bibliografia

• [1] K. Shimizu, Y. Ishizuka, and J. F. Bard, Nondifferentiable and Two-Level Mathematical Programming. Norwell: Kluwer, 1997.
• [2] J. Bard and J.Moore, “An algorithm for the discrete bilevel program- ming problem”, Nav. Res. Log., vol. 39, pp. 419–435, 1992.
• [3] J. Bard and J. Moore, “The mixed integer linear bilevel programming problem”, Oper. Res., vol. 38, pp. 911–921, 1990.
• [4] W. P. Wen and Y. H. Yang, “Algorithms for solving the mixed integer two-level linear programming problem”, Comput. Oper. Res., vol. 17, pp. 133–142, 1990.
• [5] D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Norwell: Addison Wesley, 1989.
• [6] M. Sakawa and M. Tanaka, Genetic Algorithms. Tokyo: Asakura Publishing, 1995.
• [7] G. Anandalingam, R. Mathieu, C. L. Pittard, and N. Sinha, “Artificial intelligence based approaches for solving hierarchical optimization problems,” in Impacts of Recent Computer Advances on Operations Research, R. Sharda, B. L. Golden, E. Wasil, O. Balci and W. Stewart, Eds. New York: Elsevier Science Publishing, 1989, pp. 289–301.
• [8] I. Nishizaki and M. Sakawa, “Computational methods through genetic algorithms for obtaining Stackelberg solutions to two-level integer programming problems”, Cybernet. Syst. Int. J., vol. 36, pp. 565–579, 2005.
• [9] I. Nishizaki and M. Sakawa, “Computational methods through genetic algorithms for obtaining Stackelberg solutions to two-level mixed zero-one programming problems”, Cybernet. Syst. Int. J., vol. 31, pp. 203–221, 2000.
• [10] K. Niwa, I. Nishizaki, and M. Sakawa, “Decentralized two-level 0-1 programming through genetic algorithms with double strings”, in Proc. 2nd Int. Conf. Knowl. Int. Electron. Syst., 1998, vol. 2, pp. 278–284.
• [11] K. Niwa, “Revised computational methods for using genetic algorithms for obtaining Stackelberg solutions to two-level 0-1 programming problems”, in Essays and Studies in Commemoration of the 40th Anniversary of the Founding of Hiroshima University of Economics, Hiroshima University Economics, 2007, pp. 771–794 (in Japanese).
• [12] K. Niwa, I. Nishizaki, and M. Sakawa, “Two-Level 0-1 Programming Using Genetic Algorithms and a Sharing Scheme Based on Cluster Analysis”, in Proc. Int. MultiConf. Eng. Comput. Sci., Hong Kong, China, 2008, pp. 1931–1936.
• [13] K. Niwa, I. Nishizaki, and M. Sakawa, “Two-level 0-1 programming through parallel genetic algorithms”, in Proc. Int. MultiConf. Eng. Comput. Sci., Hong Kong, China, 2009, vol. 2, pp. 2000–2005.
• [14] D. E. Goldberg and R. Lingle, “Alleles, loci, and the traveling salesman problem”, in Proc. First Int. Conf. Genet. Algorithms Appl., Hillsdale, USA, 1985, pp. 154—159.
• [15] D. Abramson and J. Abela, “A parallel genetic algorithm for solving the school timetabling problem”, in Proc. 15th Austr. Comput. Sci. Conf., Hobart, Australia, 1992, vol. 14, pp. 1–11.
• [16] E. Cant ´u-Paz, Efficient and Accurate Parallel Genetic Algorithms. Norwell, Massachusetts: Kluwer, 2000.
• [17] T. C. Fogarty and R. Huang, “Implementing the genetic algorithm on transputer based parallel processing systems”, in Proc. First Int. Conf. Parallel Prob. Solv. Nat., Dortmund, Germany, 1990, pp. 145–149.