More Web Proxy on the site http://driver.im/

article

Assisting in search heuristics selection through multidimensional supervised classification: A case study on software testing

Authors:

Ramón Sagarna,

Alexander Mendiburu,

Jose A. LozanoAuthors Info & Claims

Information Sciences—Informatics and Computer Science, Intelligent Systems, Applications: An International Journal, Volume 258

Pages 122 - 139

https://doi.org/10.1016/j.ins.2013.09.050

Published: 01 February 2014 Publication History

Abstract

A fundamental question in the field of approximation algorithms, for a given problem instance, is the selection of the best (or a suitable) algorithm with regard to some performance criteria. A practical strategy for facing this problem is the application of machine learning techniques. However, limited support has been given in the literature to the case of more than one performance criteria, which is the natural scenario for approximation algorithms. We propose multidimensional Bayesian network (mBN) classifiers as a relatively simple, yet well-principled, approach for helping to solve this problem. Precisely, we relax the algorithm selection decision problem into the elucidation of the nondominated subset of algorithms, which contains the best. This formulation can be used in different ways to elucidate the main problem, each of which can be tackled with an mBN classifier. Namely, we deal with two of them: the prediction of the whole nondominated set and whether an algorithm is nondominated or not. We illustrate the feasibility of the approach for real-life scenarios with a case study in the context of Search Based Software Test Data Generation (SBSTDG). A set of five SBSTDG generators is considered and the aim is to assist a hypothetical test engineer in elucidating good generators to fulfil the branch testing of a given programme.

References

[1]

Achlioptas, D., Naor, A. and Peres, Y., Rigorous location of phase transitions in hard optimization problems. Nature. v435. 759-764.

[2]

Alba, E. and Chicano, F., Observations in using parallel and sequential evolutionary algorithms for automatic software testing. Computers & Operations Research. v35. 3161-3183.

Digital Library

[3]

ANSI/IEEE 1008-2002, IEEE Standard for Software Unit Testing: An American National Standard, IEEE Standards Board, American National Standards Institute, 2002.

[4]

Arcuri, A. and Fraser, G., On parameter tuning in search based software engineering. In: Cohen, M.B., Cinnéide, M.í. (Eds.), Proceedings of the Third International Conference on Search Based Software Engineering, Springer-Verlag. pp. 33-47.

[5]

Baresel, A., Sthamer, H. and Schmidt, M., Fitness function design to improve evolutionary structural testing. In: Langdon, W.B., Cantú-Paz, E., Mathias, K., Roy, R., Davis, D., Poli, R., Balakrishnan, K., Honavar, V., Rudolph, G., Wegener, J., Bull, L., Potter, M.A., Schultz, A.C., Miller, J.F., Burke, E., Jonoska, N. (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference, Morgan Kaufman, San Mateo, CA. pp. 1329-1336.

[6]

Beizer, B., Software Testing Techniques. 1990. Van Nostrand Rheinhold, New York.

[7]

Bertolino, A., Software testing research: achievements, challenges, dreams. In: Briand, L.C., Wolf, A.L. (Eds.), Workshop on the Future of Software Engineering, IEEE CS Press, Washington, DC, USA. pp. 85-103.

[8]

Beyer, H.G., Schwefel, H.P. and Wegener, I., How to analyse evolutionary algorithms. Theoretical Computer Science. v287. 101-130.

Digital Library

[9]

Bielza, C., Li, G. and Larrañaga, P., Multi-dimensional classification with bayesian networks. International Journal of Approximate Reasoning. v52. 705-727.

Digital Library

[10]

Bishop, C.M., Pattern Recognition and Machine Learning. 2006. Springer.

[11]

Chankong, V. and Haimes, Y.Y., Multiobjective Decision Making: Theory and Methodology. 1983. North Holland.

[12]

Cheeseman, P., Kanefsky, B. and Taylor, W.M., Where the really hard problems are. In: Mylopoulos, J., Reiter, R. (Eds.), Proceedings of the 12th International Joint Conference on Artificial Intelligence, Morgan Kaufman, San Francisco, CA. pp. 331-337.

[13]

Chow, C. and Liu, C., Approximating discrete probability distributions with dependence trees. IEEE Transactions on Information Theory. v14. 462-467.

Digital Library

[14]

Demsar, J., Statistical comparisons of classifiers over multiple data sets. Journal of Machine Learning Research. v7. 1-30.

Digital Library

[15]

Duda, R.O., Hart, P.E. and Stork, D.G., Pattern Classification. 2001. Wiley.

[16]

Endres, A. and Rombach, D., A Handbook of Software and Systems Engineering. 2003. Pearson Education Limited, London.

[17]

Fenton, N.E., The structural complexity of flowgraphs. In: Alavy, Y., Chartrand, G., Lesniak, L., Lick, D.R., Wall, C.E. (Eds.), Graph Theory with Applications to Algorithms and Computer Science, John Wiley & Sons, New York. pp. 273-282.

[18]

Fernandes, J.A., Lozano, J.A., Inza, I., Irigoien, X., Pérez, A. and Rodríguez, J.D., Supervised pre-processing approaches in multiple class variables classification for fish recruitment forecasting. Environmental Modelling & Software. v40. 245-254.

[19]

Figueira, J., Greco, S. and Ehrgott, M., Multicriteria Decision Analysis: State of the Art Surveys. 2005. Springer, Boston.

[20]

Frankl, P. and Weyuker, E.J., A formal analysis of the fault-detecting ability of testing methods. IEEE Transactions on Software Engineering. v19. 202-213.

Digital Library

[21]

L. van der Gaag, P. de Waal, Multi-dimensional bayesian network classifiers, in: Proceedings of the Third European Workshop in Probabilistic Graphical Models, 2006, pp. 107-114.

[22]

García, S. and Herrera, F., An extension on 'Statistical comparisons of classifiers over multiple data sets' for all pairwise comparisons. Journal of Machine Learning Research. v9. 2677-2694.

[23]

Gendreau, M. and Potvin, J.Y., Handbook of Metaheuristics. 2010. Springer.

[24]

A. Guerri, M. Milano, Learning techniques for automatic algorithm portfolio selection, in: Proceedings of the 16th European Conference on Artificial Intelligence, 2004, pp. 475-479.

Digital Library

[25]

Guo, H. and Hsu, W.H., A machine learning approach to algorithm selection for np-hard optimization problems: a case study on the mpe problem. Annals of Operations Research. v156. 61-82.

[26]

Haim, S. and Walsh, T., Restart strategy selection using machine learning techniques. In: Proceedings of the 12th International Conference on Theory and Applications of Satisfiability Testing, Springer-Verlag. pp. 312-325.

[27]

Hall, M.A., Correlation-based feature selection for discrete and numeric class machine learning. In: Proceedings of the Seventeenth International Conference on Machine Learning, Morgan Kaufman Publishers. pp. 359-366.

[28]

M. Harman, A. Mansouri, Y. Zhang, Search Based Software Engineering: A Comprehensive Analysis and Review of Trends Techniques and Applications, Technical Report TR-09-03, King's College London, UK, 2009.

[29]

He, J., Reeves, C., Witt, C. and Yao, X., A note on problem difficulty measures in black-box optimization: classification, realizations and predictability. Evolutionary Computation. v15. 435-443.

Digital Library

[30]

Stochastic Local Search: Foundations & Applications. 2004. Morgan Kaufman, San Francisco, CA.

[31]

Hutter, F., Hamadi, Y., Hoos, H.H. and Leyton-Brown, K., Performance prediction and automated tuning of randomized and parametric algorithms. In: Benhamou, F. (Ed.), Proceedings of the 12th International Conference on Principles and Practice of Constraint Programming, Springer. pp. 213-228.

[32]

Kotthoff, L., Gent, I.P. and Miguel, I., An evaluation of machine learning in algorithm selection for search problems. AI Communications. v25. 257-270.

[33]

van Laarhoven, P.J.M. and Aarts, E.H.L., Simulated Annealing: Theory and Applications. 1987. Kluwer Academic Publishers, The Netherlands.

[34]

Larrañaga, P. and Lozano, J.A., . 2002. Kluwer Academic Publishers., Boston.

[35]

Leyton-Brown, K., Nudelman, E. and Shoham, Y., Empirical hardness models: methodology and a case study on combinatorial auctions. Journal of the ACM. v22. 1-52.

[36]

Lobo, F.G., Lima, C.F. and Michalewicz, Z., Parameter Setting in Evolutionary Algorithms. 2007. Springer-Verlag, Berlin, Heidelberg.

[37]

McCabe, T.J., A complexity measure. IEEE Transactions on Software Engineering. v12. 208-220.

[38]

McGraw, G., Michael, C. and Schatz, M., Generating software test data by evolution. IEEE Transactions on Software Engineering. v27. 1085-1110.

[39]

McMinn, P., Search-based software test data generation: a survey. Software Testing Verification and Reliability. v14. 105-156.

[40]

Mühlenbein, H. and Schlierkamp-Voosen, D., Predictive models for the breeder genetic algorithm. Evolutionary Computation. v1. 25-49.

Digital Library

[41]

Naudts, B. and Kallel, L., A comparison of predictive measures of problem difficulty in evolutionary algorithms. IEEE Transactions on Evolutionary Computation. v4. 1-15.

Digital Library

[42]

Oliveira, S. and Stewart, D.E., Writing Scientific Software: A Guide to Good Style. 2006. Cambridge University Press, New York.

[43]

Oliveto, P.S., He, J. and Yao, X., Time complexity of evolutionary algorithms for combinatorial optimization: a decade of results. International Journal of Automation and Computing. v4. 281-293.

[44]

Press, W.H., Flannery, B.P., Teukolsky, S.A. and Vetterling, W.T., . 1988. The Art of Scientific Computing, 1988.Cambridge University Press, New York.

[45]

Read, J., Pfahringer, B., Holmes, G. and Frank, E., Classifier chains for multi-label classification. Machine Learning. v85. 333-359.

Digital Library

[46]

Rice, J.R., The algorithm selection problem. Advances in Computers. v15. 65-118.

[47]

J.D. Rodríguez, J.A. Lozano, Learning Bayesian network classifiers for multi-dimensional supervised classification problems by means of a multi-objective approach, Technical Report EHU-KZAA-TR-3-2010, Department of Computer Science and Artificial Intelligence, University of the Basque Country, 2010.

[48]

RTCA/DO-178B, Software Considerations in Airborne Systems and Equipment Certification, Radio Technical Commission for Aeronautics, 1992.

[49]

Sagarna, R. and Lozano, J.A., Dynamic search space transformations for software test data generation. Computational Intelligence. v24. 23-61.

[50]

Cross-disciplinary perspectives on meta-learning for algorithm selection. ACM Computing Surveys. v41. 6:1-6:25.

[51]

Smith-Miles, K., Towards insightful algorithm selection for optimisation using meta-learning concepts. In: Proceedings of the International Joint Conference on Neural Networks, IEEE. pp. 4118-4124.

[52]

H. Sthamer, The Automatic Generation of Software Test Data Using Genetic Algorithms, Ph.D. thesis, University of Glamorgan, Pontyprid, Wales, Great Britain, 1996.

[53]

Tracey, N., Clark, J., Mander, K. and McDermid, J., An automated framework for structural test-data generation. In: Redmiles, D., Nuseibeh, B. (Eds.), Proceedings of the 13th IEEE Conference on Automated Software Engineering, IEEE CS Press. pp. 285-288.

[54]

Wegener, J., Baresel, A. and Sthamer, H., Evolutionary test environment for automatic structural testing. Information and Software Technology. v43. 841-854.

[55]

Xu, L., Hutter, F., Hoos, H.H. and Leyton-Brown, K., Satzilla: portfolio-based algorithm selection for sat. Journal of Articial Intelligence Research. v32. 565-606.

[56]

Zaragoza, J., Sucar, E., Morales, E., Larrañaga, P. and Bielza, C., Bayesian chain classifiers for multidimensional classification. In: Walsh, T. (Ed.), Proceedings of the Twentysecond International Joint Conference on Artificial Intelligence, AAAI Press. pp. 2192-2197.

Cited By

Jia BZhang M(2019)Multi-dimensional classification via kNN feature augmentationProceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v33i01.33013975(3975-3982)Online publication date: 27-Jan-2019
https://dl.acm.org/doi/10.1609/aaai.v33i01.33013975
Garciarena USantana RNeumann FSutton A(2016)Evolutionary Optimization of Compiler Flag Selection by Learning and Exploiting Flags InteractionsProceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion10.1145/2908961.2931696(1159-1166)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908961.2931696
Rodriguez DDolado JTuya JVos TEldh SPrasetya W(2015)Bayesian concepts in software testing: an initial reviewProceedings of the 6th International Workshop on Automating Test Case Design, Selection and Evaluation10.1145/2804322.2804329(41-46)Online publication date: 30-Aug-2015
https://dl.acm.org/doi/10.1145/2804322.2804329

Assisting in search heuristics selection through multidimensional supervised classification: A case study on software testing
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Supervised learning

Recommendations

A Switch-and-Restart Algorithm with Exponential Restart Strategy for Objective Selection and its Runtime Analysis
ICMLA '14: Proceedings of the 2014 13th International Conference on Machine Learning and Applications

There exist optimization problems with the target objective, which is to be optimized, and several extra objectives, which may or may not be helpful in the optimization process. This paper considers the case when it is possible to find an optimum of the ...
User preferences based software defect detection algorithms selection using MCDM

A variety of classification algorithms for software defect detection have been developed over the years. How to select an appropriate classifier for a given task is an important issue in Data mining and knowledge discovery (DMKD). Many studies have ...
Automatic selection of classification learning algorithms for data mining practitioners

Classification algorithm selection is an open research problem whose solution has tremendous value for practitioners. In recent years, metalearning has emerged as a viable approach. Unfortunately, the ratio of examples to classes is small at the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information Sciences: an International Journal

Information Sciences: an International Journal Volume 258, Issue

February, 2014

463 pages

ISSN:0020-0255

Issue’s Table of Contents

Copyright © Elsevier Inc. © 2013.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 01 February 2014

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jia BZhang M(2019)Multi-dimensional classification via kNN feature augmentationProceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v33i01.33013975(3975-3982)Online publication date: 27-Jan-2019
https://dl.acm.org/doi/10.1609/aaai.v33i01.33013975
Garciarena USantana RNeumann FSutton A(2016)Evolutionary Optimization of Compiler Flag Selection by Learning and Exploiting Flags InteractionsProceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion10.1145/2908961.2931696(1159-1166)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908961.2931696
Rodriguez DDolado JTuya JVos TEldh SPrasetya W(2015)Bayesian concepts in software testing: an initial reviewProceedings of the 6th International Workshop on Automating Test Case Design, Selection and Evaluation10.1145/2804322.2804329(41-46)Online publication date: 30-Aug-2015
https://dl.acm.org/doi/10.1145/2804322.2804329

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents