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

research-article

Open access

Explaining a Staff Rostering Genetic Algorithm using Sensitivity Analysis and Trajectory Analysis.

Authors:

Alexander BrownleeAuthors Info & Claims

GECCO '23 Companion: Proceedings of the Companion Conference on Genetic and Evolutionary Computation

Pages 1648 - 1656

https://doi.org/10.1145/3583133.3596353

Published: 24 July 2023 Publication History

Abstract

In the field of Explainable AI, population-based search metaheuristics are of growing interest as they become more widely used in critical applications. The ability to relate key information regarding algorithm behaviour and drivers of solution quality to an end-user is vital. This paper investigates a novel method of explanatory feature extraction based on analysis of the search trajectory and compares the results to those of sensitivity analysis using "Weighted Ranked Biased Overlap". We apply these techniques to search trajectories generated by a genetic algorithm as it solves a staff rostering problem. We show that there is a significant overlap between these two explainability methods when identifying subsets of rostered workers whose allocations are responsible for large portions of fitness change in an optimization run. Both methods identify similar patterns in sensitivity, but our method also draws out additional information. As the search progresses, the techniques reveal how individual workers increase or decrease in the influence on the overall rostering solution's quality. Our method also helps identify workers with a lower impact on overall solution fitness and at what stage in the search these individuals can be considered highly flexible in their roster assignment.

References

[1]

Alejandro Barredo Arrieta, Natalia Díaz-Rodríguez, Javier Del Ser, Adrien Bennetot, Siham Tabik, Alberto Barbado, Salvador Garcia, Sergio Gil-Lopez, Daniel Molina, Richard Benjamins, Raja Chatila, and Francisco Herrera. Explainable Artificial Intelligence (XAI): Concepts, taxonomies, opportunities and challenges toward responsible AI. Information Fusion, 58:82--115, 2020.

Digital Library

[2]

Shubham Sharma, Jette Henderson, and Joydeep Ghosh. Certifai: Counterfactual explanations for robustness, transparency, interpretability, and fairness of artificial intelligence models. Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, Feb 2020.

[3]

A. Duygu Arbatli and H. Levent Akin. Rule extraction from trained neural networks using genetic algorithms. Nonlinear Analysis: Theory, Methods & Applications, 30(3):1639--1648, 1997.

[4]

Brownlee A.E.I. Cagnoni S. Iacca G. McCall J.A.W. Walker D. Bacardit, J. "Evolutionary Computation and Explainable AI: a year in review". Late-breaking Abstracts, EvoStar Conference 2023, Brno, Czech Republic.

[5]

Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In International conference on machine learning, pages 3145--3153. PMLR, 2017.

[6]

Sebastian Bach, Alexander Binder, Grégoire Montavon, Frederick Klauschen, Klaus-Robert Müller, and Wojciech Samek. On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation. PloS one, 10(7):e0130140, 2015.

[7]

Piotr Dabkowski and Yarin Gal. Real time image saliency for black box classifiers. Advances in neural information processing systems, 30, 2017.

[8]

Yaochu Jin. Surrogate-assisted evolutionary computation: Recent advances and future challenges. Swarm and Evolutionary Computation, 1(2):61--70, 2011.

[9]

Aidan Wallace, Alexander E. I. Brownlee, and David Cairns. Towards explaining metaheuristic solution quality by data mining surrogate fitness models for importance of variables. In Max Bramer and Richard Ellis, editors, Artificial Intelligence XXXVIII, pages 58--72, Cham, 2021. Springer International Publishing.

Digital Library

[10]

Manjinder Singh, Alexander E. I. Brownlee, and David Cairns. Towards explainable metaheuristic: Mining surrogate fitness models for importance of variables. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO '22, page 1785--1793, New York, NY, USA, 2022. Association for Computing Machinery.

Digital Library

[11]

Gabriela Ochoa, Katherine Malan, and Christian Blum. Search trajectories illuminated. ACM SIGEVOlution, 14:1--5, 07 2021.

Digital Library

[12]

Gabriela Ochoa, Katherine Malan, and Christian Blum. Search trajectory networks: A tool for analysing and visualising the behaviour of metaheuristics. Applied Soft Computing, 109:107492, 05 2021.

[13]

Jonathan Wright, Mengchao Wang, Alexander Brownlee, and R.A. Buswell. Variable convergence in evolutionary optimization and its relationship to sensitivity analysis. 01 2012.

[14]

Paulo Cortez and Mark J Embrechts. Opening black box data mining models using sensitivity analysis. In 2011 IEEE Symposium on Computational Intelligence and Data Mining (CIDM), pages 341--348. IEEE, 2011.

[15]

Paulo Cortez and Mark J Embrechts. Using sensitivity analysis and visualization techniques to open black box data mining models. Information Sciences, 225:1--17, 2013.

Digital Library

[16]

Martin Fyvie, John AW McCall, and Lee A Christie. Towards explainable metaheuristics: PCA for trajectory mining in evolutionary algorithms. In International Conference on Innovative Techniques and Applications of Artificial Intelligence, pages 89--102. Springer, 2021.

Digital Library

[17]

Andrea Saltelli, Marco Ratto, Terry Andres, Francesca Campolongo, Jessica Cariboni, Debora Gatelli, Michaela Saisana, and Stefano Tarantola. Global sensitivity analysis: the primer. John Wiley & Sons, 2008.

[18]

Samprit Chatterjee, AS Hadi, and B Price. Regression analysis by example john wiley & sons. Inc., New York, 2000.

[19]

William Webber, Alistair Moffat, and Justin Zobel. A similarity measure for indefinite rankings. ACM Transactions on Information Systems (TOIS), 28(4):1--38, 2010.

[20]

Krupesh Raikar. How to objectively compare two ranked lists in python, 01 2023.

[21]

Alessia Sarica, Andrea Quattrone, and Aldo Quattrone. Introducing the rank-biased overlap as similarity measure for feature importance in explainable machine learning: A case study on parkinson's disease. In Mufti Mahmud, Jing He, Stefano Vassanelli, André van Zundert, and Ning Zhong, editors, Brain Informatics, pages 129--139, Cham, 2022. Springer International Publishing.

Digital Library

[22]

Mary Dimitropoulaki, Mathias Kern, Gilbert Owusu, and Alistair McCormick. Workforce rostering via metaheuristics. In Artificial Intelligence XXXV: 38th SGAI International Conference on Artificial Intelligence, AI 2018, Cambridge, UK, December 11--13, 2018, Proceedings 38, pages 277--290. Springer, 2018.

[23]

K. N. Reid, J. Li, A. E. I. Brownlee, M. Kern, N. Veerapen, J. Swan, and G. Owusu. A hybrid metaheuristic approach to a real world employee scheduling problem. In Proc. of the Genetic and Evolutionary Computation COnference. Prague, Czech Republic, 2019. Accepted, to appear.

Digital Library

[24]

J. Blank and K. Deb. pymoo: Multi-Objective Optimization in Python. IEEE Access, 8:89497--89509, 2020.

[25]

Kalyanmoy Deb, Karthik Sindhya, and Tatsuya Okabe. Self-adaptive simulated binary crossover for real-parameter optimization. In Proceedings of the 9th annual conference on genetic and evolutionary computation, pages 1187--1194, 2007.

Digital Library

Cited By

Lipinski PBalcer KLi XHandl J(2024)Explaining Session-based Recommendations using Grammatical EvolutionProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3664156(1590-1597)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3664156
Catalano GBrownlee ACairns DMcCall JFyvie MAinslie R(2024)Explaining a Staff Rostering Problem Using Partial SolutionsArtificial Intelligence XLI10.1007/978-3-031-77918-3_13(179-193)Online publication date: 29-Nov-2024
https://doi.org/10.1007/978-3-031-77918-3_13
Collins JZăvoianu AMcCall J(2023)Comparison of Simulated Annealing and Evolution Strategies for Optimising Cyclical Rosters with Uneven Demand and Flexible Trainee PlacementArtificial Intelligence XL10.1007/978-3-031-47994-6_39(451-464)Online publication date: 8-Nov-2023
https://doi.org/10.1007/978-3-031-47994-6_39
Show More Cited By

Index Terms

Explaining a Staff Rostering Genetic Algorithm using Sensitivity Analysis and Trajectory Analysis.
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
  2. Machine learning
    1. Machine learning approaches
      1. Bio-inspired approaches
        Genetic algorithms
2. Theory of computation
  1. Models of computation

Recommendations

Explaining a Staff Rostering Problem by Mining Trajectory Variance Structures
Artificial Intelligence XL
Abstract
The use of Artificial Intelligence-driven solutions in domains involving end-user interaction and cooperation has been continually growing. This has also lead to an increasing need to communicate crucial information to end-users about algorithm ...
Variations of biogeography-based optimization and Markov analysis

Biogeography-based optimization (BBO) is a new evolutionary algorithm that is inspired by biogeography. Previous work has shown that BBO is a competitive optimization algorithm, and it demonstrates good performance on various benchmark functions and ...
Smart Staff Recruiting

"The genius of President Obama is his ability to make smart people work harder." Surely every manager wants to aspire to this ability, but first he must find "smart" staff. The objective of this article is to help readers better prepare to recruit smart ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '23 Companion: Proceedings of the Companion Conference on Genetic and Evolutionary Computation

July 2023

2519 pages

ISBN:9798400701207

DOI:10.1145/3583133

Chair:
Sara Silva,
Program Chair:
Luís Paquete

Copyright © 2023 Owner/Author(s).

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 July 2023

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '23 Companion

Sponsor:

SIGEVO

GECCO '23 Companion: Companion Conference on Genetic and Evolutionary Computation

July 15 - 19, 2023

Lisbon, Portugal

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
247
Total Downloads

Downloads (Last 12 months)182
Downloads (Last 6 weeks)17

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lipinski PBalcer KLi XHandl J(2024)Explaining Session-based Recommendations using Grammatical EvolutionProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3664156(1590-1597)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3664156
Catalano GBrownlee ACairns DMcCall JFyvie MAinslie R(2024)Explaining a Staff Rostering Problem Using Partial SolutionsArtificial Intelligence XLI10.1007/978-3-031-77918-3_13(179-193)Online publication date: 29-Nov-2024
https://doi.org/10.1007/978-3-031-77918-3_13
Collins JZăvoianu AMcCall J(2023)Comparison of Simulated Annealing and Evolution Strategies for Optimising Cyclical Rosters with Uneven Demand and Flexible Trainee PlacementArtificial Intelligence XL10.1007/978-3-031-47994-6_39(451-464)Online publication date: 8-Nov-2023
https://doi.org/10.1007/978-3-031-47994-6_39
Fyvie MMcCall JChristie LZăvoianu ABrownlee AAinslie R(2023)Explaining a Staff Rostering Problem by Mining Trajectory Variance StructuresArtificial Intelligence XL10.1007/978-3-031-47994-6_27(275-290)Online publication date: 12-Dec-2023
https://dl.acm.org/doi/10.1007/978-3-031-47994-6_27

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents