Correo Electrónico
DNINFOA - SIA
Bibliotecas
Convocatorias
Identidad U.N.
Published
A Multi-Agent Proposal for the Resolution of BIBD instances
Una propuesta multi-agente en la resolución de instancias del BIBD
DOI:
https://doi.org/10.15446/rce.v39n2.52838Keywords:
Balanced Incomplete Block Design, Hill Climbing, Tabu Search, Multi-Agents, vector space (en)Diseño de bloques incompletos equilibrados, Proceso vectorial, Búsqueda por computador, Diseño de experimentos. (es)
The problem with designing balanced incomplete blocks (BIBD) is enclosed within the combinatorial optimization approach that has been extensively used in experimental design. The present proposal addresses thi problem by using local search techniques known as Hill Climbing, Tabu Search, and an approach based considerable sized the use of Multi-Agents, which allows the exploration of diverse areas of search spaces. Furthermore, the use of a vector vision for the consideration associated with vicinity is presented. The experimental results prove the advantage of this technique compared to other proposals that are reported in the current literature.
El problema del diseño de bloques incompletos equilibrados (BIBD) se enmarca dentro del enfoque de optimización combinatoria que ha sido utilizado ampliamente en el diseño de experimentos. La presente propuesta aborda este problema utilizando técnicas de búsqueda local conocidas como Ascenso a la Colina (Hill Climbing), Búsqueda Tabú (Tabu Search) y un enfoque basado en el uso de Multi-Agentes que permiten la exploración de diversas áreas de espacios de búsqueda de tamaño considerable, además se presenta el uso de una visión vectorial para la consideración asociada a la vecindad. Los resultados experimentales evidencian la ventaja de esta técnica frente a otras propuestas mostradas en la literatura actual.
https://doi.org/10.15446/rce.v39n2.52838
1Universidad Nacional Experimental del Táchira, Departamento de Ing. Informática, San Cristóbal, Venezuela. Associate Professor. Email: drodri@unet.edu.ve
2Universidad Nacional de Colombia, Facultad de Ciencias Agrarias, Departamento de Agronomía, Bogotá, Colombia. Assistant Professor. Email: aqedarghanco@unal.edu.co
3Universidad de Pamplona, Facultad de Ciencias Básicas, Departamento de Matemáticas, Pamplona, Colombia. Associate Professor. Email: julio.monroy@unipamplona.edu.co
The problem with designing balanced incomplete blocks (BIBD) is enclosed within the combinatorial optimization approach that has been extensively used in experimental design. The present proposal addresses this problem by using local search techniques known as Hill Climbing, Tabu Search, and an approach based considerable sized the use of Multi-Agents, which allows the exploration of diverse areas of search spaces. Furthermore, the use of a vector vision for the consideration associated with vicinity is presented. The experimental results prove the advantage of this technique compared to other proposals that are reported in the current literature.
Key words: Balanced incomplete block design, Vector process, Computer search, Experimental design.
El problema del diseño de bloques incompletos equilibrados (BIBD) se enmarca dentro del enfoque de optimización combinatoria que ha sido utilizado ampliamente en el diseño de experimentos. La presente propuesta aborda este problema utilizando técnicas de búsqueda local conocidas como Ascenso a la Colina (Hill Climbing), Búsqueda Tabú (Tabu Search) y un enfoque basado en el uso de Multi-Agentes que permiten la exploración de diversas áreas de espacios de búsqueda de tamaño considerable, además se presenta el uso de una visión vectorial para la consideración asociada a la vecindad. Los resultados experimentales evidencian la ventaja de esta técnica frente a otras propuestas mostradas en la literatura actual.
Palabras clave: diseño de bloques incompletos equilibrados, proceso vectorial, búsqueda por computador, diseño de experimentos.
Texto completo disponible en PDF
References
1. Anderson, I. (1997), Combinatorial designs and tournaments, Clarendon Press, Oxford University Press.
2. Bofill, P., Guimerà, R. & Torras, C. (2003), 'Comparison of simulated annealing and mean field annealing as applied to the generation of block designs', Neural Networks 16(10), 1421-1428.
3. Buratti, M. (1999), 'Some (17q, 17, 2) and (25q, 25, 3)BIBD constructions', Designs, Codes and Cryptography 16(2), 117-120.
4. Colbourn, C. & Dinitz, J., eds (1996), The CRC handbook of combinatorial designs, CRC Press, Boca Raton.
5. Corneil, D. G. & Mathon, R. (1978), 'Algorithmic techniques for the generation and analysis of strongly regular graphs and other combinatorial configurations', Annals of Discrete Mathematics 2, 1-32.
6. Daisuke Yokoya, T. Y. (2009), 'A mathematical programming approach to the construction of bibds', International Journal of Computer Mathematics, 1-16.
7. Fisher, R. A. (1926), 'The arrangement of field experiments', Journal of the Ministry of Agriculture Great Britain 33.
8. Fisher, R. A. (1940), 'An examination of the different possible solutions of a problem in incomplete blocks', Annals of Eugenics 10, 52-75.
9. Flener, P., Frisch, A. M., Hnich, B., Kzltan, Z., Miguel, I. & Walsh, T. (2001), Matrix modelling, 'CP-01 Workshop on Modelling and Problem Formulation. International Conference on the Principles and Practice of Constraint Programming'.
10. Gibbons, P. B. & Ostergard, P. R. J. (2007), Computational methods in design theory, 'Handbook of Combinatorial Designs', Chapman & Hall/CRC Press, Boca Raton, p. 755-783.
11. Hall, M. J. (1998), Combinatorial Theory, 2 edn, John Wiley & Sons, Inc., New York, USA.
12. Hinkelman, K. & Kempthorne, O. (1994), Design and analysis of experiments, Vol. 1, John Wiley and Sons, Inc., New York.
13. John, J. A., Whitaker, D. & Triggs, C. M. (1993), 'Construction of cyclic designs using integer programming', Journal of statistical planning and inference 36(2), 357-366.
14. Lan, L., Tai, Y. Y., Lin, S., Memari, B. & Honary, B. (2008), 'New constructions of quasi-cyclic LDPC codes based on special classes of BIDBs for the AWGN and binary erasure channels', IEEE Transactions on Communications 56(1), 39-48.
15. Mead, R. (1993), Design of Experiments: Statistical Principles for Practical Applications, Cambridge University Press.
16. Meseguer, P. & Torras, C. (2001), 'Exploiting symmetries within constraint satisfaction search', Artificial Intelligence 129(1-2), 133-163.
17. Prestwich, S. (2003a), A local search algorithm for balanced incomplete block designs, '9th International Conference on Principles and Practices of Constraint Programming (CP2003)', LNCS, Springer, p. 53-64.
18. Prestwich, S. (2003b), 'Negative effects of modeling techniques on search performance', Annals of Operations Research 18, 137-150.
19. Puget, Jean-Francois (2002), Symmetry breaking revisited, '8th International Conference on Principles and Practice of Constraint Programming (CP 2002)', Vol. 2470 of LNCS, Springer, Ithaca, NY, USA, p. 446-461.
20. Raghavarao, D. (1988), Constructions and Combinatorial Problems in Design of Experiments (Paperback), Dover Publications.
21. Rodriguez, D., Cotta,. & Leiva, A. José Fernandez (2011), 'A memetic algorithm for designing balanced incomplete blocks', IJCOPI 2(1), 14-22.
22. Rodriguez, D., Cotta, C. & Fernandez, A. (2009), Finding balanced incomplete block designs with metaheuristics, 'Evolutionary Computation in Combinatorial Optimization 2009', Vol. 5482 of Lecture Notes in Computer Science, Springer, p. 156-167.
23. Whitaker, D., Triggs, C. M. & John, J. A. (1990), 'Construction of block designs using mathematical programming', Journal of the Royal Statistical Society, Series B 52(3), 497-503.
24. Yates, F. (1936), 'Incomplete randomized blocks', Annals of Eugenics 7, 121-140.
25. van Lint, J. & Wilson, R. (1992), A Course in Combinatorics, Cambridge University Press.
Este artículo se puede citar en LaTeX utilizando la siguiente referencia bibliográfica de BibTeX:
@ARTICLE{RCEv39n2a07,
AUTHOR = {Rodríguez, David and Darghan, Enrique and Monroy, Julio},
TITLE = {{A Multi-Agent Proposal for the Resolution of BIBD Instances}},
JOURNAL = {Revista Colombiana de Estadística},
YEAR = {2016},
volume = {39},
number = {2},
pages = {267-280}
}
References
Anderson, I. (1997), Combinatorial designs and tournaments, Clarendon Press, Oxford University Press.
Bofill, P., Guimerà, R. & Torras, C. (2003), ‘Comparison of simulated annealing and mean field annealing as applied to the generation of block designs’, Neural Networks 16(10), 1421–1428.
Buratti, M. (1999), ‘Some (17q, 17, 2) and (25q, 25, 3)BIBD constructions’, Designs, Codes and Cryptography 16(2), 117–120.
Colbourn, C. & Dinitz, J., eds (1996), The CRC handbook of combinatorial designs, CRC Press, Boca Raton.
Corneil, D. G. & Mathon, R. (1978), ‘Algorithmic techniques for the generation and analysis of strongly regular graphs and other combinatorial configurations’, Annals of Discrete Mathematics 2, 1–32.
Daisuke Yokoya, T. Y. (2009), ‘A mathematical programming approach to the construction of bibds’, International Journal of Computer Mathematics pp. 1–16.
Fisher, R. A. (1926), ‘The arrangement of field experiments’, Journal of the Ministry of Agriculture Great Britain 33.
Fisher, R. A. (1940), ‘An examination of the different possible solutions of a problema in incomplete blocks’, Annals of Eugenics 10, 52–75.
Flener, P., Frisch, A. M., Hnich, B., Kzltan, Z., Miguel, I. & Walsh, T. (2001), Matrix modelling, in ‘CP-01 Workshop on Modelling and Problem Formulation. International Conference on the Principles and Practice of Constraint Programming’.
Gibbons, P. B. & Ostergard, P. R. J. (2007), Computational methods in design theory, in C. J. Colbourn & J. H. Dinitz, eds, ‘Handbook of Combinatorial Designs’, Chapman & Hall/CRC Press, Boca Raton, pp. 755–783.
Hall, M. J. (1998), Combinatorial Theory, 2 edn, John Wiley & Sons, Inc., New York, USA.
Hinkelman, K. & Kempthorne, O. (1994), Design and analysis of experiments, Vol. 1, John Wiley and Sons, Inc., New York.
John, J. A., Whitaker, D. & Triggs, C. M. (1993), ‘Construction of cyclic designs using integer programming’, Journal of statistical planning and inference 36(2), 357–366.
Lan, L., Tai, Y. Y., Lin, S., Memari, B. & Honary, B. (2008), ‘New constructions of quasi-cyclic LDPC codes based on special classes of BIDBs for the AWGN and binary erasure channels’, IEEE Transactions on Communications 56(1), 39–48.
Mead, R. (1993), Design of Experiments: Statistical Principles for Practical Applications, Cambridge University Press.
Meseguer, P. & Torras, C. (2001), ‘Exploiting symmetries within constraint satisfaction search’, Artificial Intelligence 129(1-2), 133–163.
Prestwich, S. (2003a), A local search algorithm for balanced incomplete block designs, in F. Rossi, ed., ‘9th International Conference on Principles and Practices of Constraint Programming (CP2003)’, LNCS, Springer, pp. 53–64.
Prestwich, S. (2003b), ‘Negative effects of modeling techniques on search performance’, Annals of Operations Research 18, 137–150.
Puget, J.-F. (2002), Symmetry breaking revisited, in P. V. Hentenryck, ed., ‘8th International Conference on Principles and Practice of Constraint Programming (CP 2002)’, Vol. 2470 of LNCS, Springer, Ithaca, NY, USA, pp. 446–461.
Raghavarao, D. (1988), Constructions and Combinatorial Problems in Design of Experiments (Paperback), Dover Publications.
Rodriguez, D., Cotta, C. & Fernandez, A. (2009), Finding balanced incomplete block designs with metaheuristics, in C. Cotta & P. Cowling, eds, ‘Evolutionary Computation in Combinatorial Optimization 2009’, Vol. 5482 of Lecture Notes in Computer Science, Springer, pp. 156–167.
Rodriguez, D., Cotta, C. & Leiva, A. J. F. (2011), ‘A memetic algorithm for designing balanced incomplete blocks’, IJCOPI 2(1), 14–22.
van Lint, J. & Wilson, R. (1992), A Course in Combinatorics, Cambridge University Press.
Whitaker, D., Triggs, C. M. & John, J. A. (1990), ‘Construction of block designs using mathematical programming’, Journal of the Royal Statistical Society, Series B 52(3), 497–503.
Yates, F. (1936), ‘Incomplete randomized blocks’, Annals of Eugenics 7, 121–140.
How to Cite
APA
ACM
ACS
ABNT
Chicago
Harvard
IEEE
MLA
Turabian
Vancouver
Download Citation
CrossRef Cited-by
1. David Rodríguez Rueda, Carlos Cotta, Antonio J. Fernández-Leiva. (2020). Memetic collaborative approaches for finding balanced incomplete block designs. Computers & Operations Research, 114, p.104804. https://doi.org/10.1016/j.cor.2019.104804.
Dimensions
PlumX
Article abstract page views
Downloads
License
Copyright (c) 2016 Revista Colombiana de Estadística
This work is licensed under a Creative Commons Attribution 4.0 International License.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
