{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T05:52:44Z","timestamp":1744869164532,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,2,27]],"date-time":"2021-02-27T00:00:00Z","timestamp":1614384000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,2,27]],"date-time":"2021-02-27T00:00:00Z","timestamp":1614384000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Softw Syst Model"],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The problem of automatically discovering business process models from event logs has been intensely investigated in the past two decades, leading to a wide range of approaches that strike various trade-offs between accuracy, model complexity, and execution time. A few studies have suggested that the accuracy of automated process discovery approaches can be enhanced by means of metaheuristic optimization techniques. However, these studies have remained at the level of proposals without validation on real-life datasets or they have only considered one metaheuristic in isolation. This article presents a metaheuristic optimization framework for automated process discovery. The key idea of the framework is to construct a directly-follows graph (DFG) from the event log, to perturb this DFG so as to generate new candidate solutions, and to apply a DFG-based automated process discovery approach in order to derive a process model from each DFG. The framework can be instantiated by linking it to an automated process discovery approach, an optimization metaheuristic, and the quality measure to be optimized (e.g., fitness, precision, F-score). The article considers several instantiations of the framework corresponding to four optimization metaheuristics, three automated process discovery approaches (Inductive Miner\u2014directly-follows, Fodina, and Split Miner), and one accuracy measure (Markovian F-score). These framework instances are compared using a set of 20 real-life event logs. The evaluation shows that metaheuristic optimization consistently yields visible improvements in F-score for all the three automated process discovery approaches, at the cost of execution times in the order of minutes, versus seconds for the baseline approaches.<\/jats:p>","DOI":"10.1007\/s10270-020-00846-x","type":"journal-article","created":{"date-parts":[[2021,2,27]],"date-time":"2021-02-27T06:03:03Z","timestamp":1614405783000},"page":"1245-1270","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Optimization framework for DFG-based automated process discovery approaches"],"prefix":"10.1007","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7970-5246","authenticated-orcid":false,"given":"Adriano","family":"Augusto","sequence":"first","affiliation":[]},{"given":"Marlon","family":"Dumas","sequence":"additional","affiliation":[]},{"given":"Marcello","family":"La\u00a0Rosa","sequence":"additional","affiliation":[]},{"given":"Sander J. J.","family":"Leemans","sequence":"additional","affiliation":[]},{"given":"Seppe K. L. M.","family":"vanden\u00a0Broucke","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,2,27]]},"reference":[{"issue":"1","key":"846_CR1","first-page":"37","volume":"13","author":"A Adriansyah","year":"2015","unstructured":"Adriansyah, A., Munoz-Gama, J., Carmona, J., van Dongen, B., van der Aalst, W.: Measuring precision of modeled behavior. ISeB 13(1), 37\u201367 (2015)","journal-title":"Measuring precision of modeled behavior. ISeB"},{"key":"846_CR2","doi-asserted-by":"crossref","unstructured":"Adriansyah, A., van Dongen, B., van der Aalst, W.: Conformance checking using cost-based fitness analysis. In: EDOC. IEEE (2011)","DOI":"10.1109\/EDOC.2011.12"},{"issue":"11","key":"846_CR3","doi-asserted-by":"publisher","first-page":"4497","DOI":"10.1007\/s10489-018-1213-3","volume":"48","author":"S Alizadeh","year":"2018","unstructured":"Alizadeh, S., Norani, A.: ICMA: a new efficient algorithm for process model discovery. Appl. Intell. 48(11), 4497\u20134514 (2018)","journal-title":"Appl. Intell."},{"key":"846_CR4","doi-asserted-by":"crossref","unstructured":"Atashpaz-Gargari, E., Lucas, C.: Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition. In: Evolutionary computation, 2007. CEC 2007. IEEE Congress on, pp 4661\u20134667. IEEE (2007)","DOI":"10.1109\/CEC.2007.4425083"},{"key":"846_CR5","doi-asserted-by":"publisher","unstructured":"Augusto, A., Armas Cervantes, A., Conforti, R., Dumas, M., La Rosa, M.: Measuring fitness and precision of automatically discovered process models: a principled and scalable approach. IEEE Trans. Knowl. Data Eng. (2020). To appear https:\/\/doi.org\/10.1109\/TKDE.2020.3003258","DOI":"10.1109\/TKDE.2020.3003258"},{"key":"846_CR6","doi-asserted-by":"crossref","unstructured":"Augusto, A., Armas-Cervantes, A., Conforti, R., Dumas, M., La Rosa, M., Reissner, D.: Abstract-and-compare: a family of scalable precision measures for automated process discovery. In: BPM. Springer, Berlin (2018)","DOI":"10.1007\/978-3-319-98648-7_10"},{"key":"846_CR7","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1016\/j.datak.2018.04.007","volume":"117","author":"A Augusto","year":"2017","unstructured":"Augusto, A., Conforti, R., Dumas, M., La Rosa, M., Bruno, G.: Automated discovery of structured process models from event logs: the discover-and-structure approach. DKE 117, 373\u2013392 (2017)","journal-title":"DKE"},{"issue":"4","key":"846_CR8","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1109\/TKDE.2018.2841877","volume":"31","author":"A Augusto","year":"2019","unstructured":"Augusto, A., Conforti, R., Dumas, M., La Rosa, M., Maggi, F.M., Marrella, A., Mecella, M., Soo, A.: Automated discovery of process models from event logs: Review and benchmark. IEEE Trans. Knowl. Data Eng. 31(4), 686\u2013705 (2019)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"2","key":"846_CR9","first-page":"251","volume":"59","author":"A Augusto","year":"2018","unstructured":"Augusto, A., Conforti, R., Dumas, M., La Rosa, M., Polyvyanyy, A.: Split miner: automated discovery of accurate and simple business process models from event logs. KAIS 59(2), 251\u2013284 (2018)","journal-title":"KAIS"},{"key":"846_CR10","doi-asserted-by":"crossref","unstructured":"Augusto, A., Dumas, M., La Rosa, M.: Metaheuristic optimization for automated business process discovery. In: BPM. Springer, Berlin (2019)","DOI":"10.1007\/978-3-030-26619-6_18"},{"issue":"1","key":"846_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1162\/evco.1993.1.1.1","volume":"1","author":"Thomas B\u00e4ck","year":"1993","unstructured":"B\u00e4ck, Thomas, Schwefel, Hans-Paul: An overview of evolutionary algorithms for parameter optimization. Evol. Comput. 1(1), 1\u201323 (1993)","journal-title":"Evol. Comput."},{"key":"846_CR12","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/j.ins.2013.02.041","volume":"237","author":"I Boussa\u00efd","year":"2013","unstructured":"Boussa\u00efd, I., Lepagnot, J., Siarry, P.: A survey on optimization metaheuristics. Inf. Sci. 237, 82\u2013117 (2013)","journal-title":"Inf. Sci."},{"key":"846_CR13","doi-asserted-by":"crossref","unstructured":"Buijs, J., van Dongen, B., van der Aalst, W.: On the role of fitness, precision, generalization and simplicity in process discovery. In: CoopIS. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-33606-5_19"},{"key":"846_CR14","doi-asserted-by":"crossref","unstructured":"Burattin, A., Sperduti, A.: Automatic determination of parameters\u2019 values for heuristics miner++. In: IEEE Congress on Evolutionary Computation (2010)","DOI":"10.1109\/CEC.2010.5586208"},{"key":"846_CR15","doi-asserted-by":"crossref","unstructured":"Chifu, V.R., Pop, C.B., Salomie, I., Balla, I., Paven, R.: Hybrid particle swarm optimization method for process mining. In: ICCP. IEEE (2012)","DOI":"10.1109\/ICCP.2012.6356199"},{"key":"846_CR16","unstructured":"de\u00a0Medeiros, A.K.: Genetic process mining. PhD thesis, Eindhoven University of Technology (2006)"},{"key":"846_CR17","doi-asserted-by":"crossref","unstructured":"Effendi, Y.A., Sarno, R.: Discovering optimized process model using rule discovery hybrid particle swarm optimization. In: 2017 3rd International Conference on Science in Information Technology (ICSITech), pp. 97\u2013103. IEEE (2017)","DOI":"10.1109\/ICSITech.2017.8257092"},{"key":"846_CR18","unstructured":"Gao, D., Liu, Q.: An improved simulated annealing algorithm for process mining. In: CSCWD. IEEE (2009)"},{"issue":"5","key":"846_CR19","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/0305-0548(86)90048-1","volume":"13","author":"F Glover","year":"1986","unstructured":"Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput Oper. Res. 13(5), 533\u2013549 (1986)","journal-title":"Comput Oper. Res."},{"key":"846_CR20","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/1090.001.0001","volume-title":"Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence","author":"JH Holland","year":"1992","unstructured":"Holland, J.H.: Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press, Cambridge (1992)"},{"key":"846_CR21","doi-asserted-by":"crossref","unstructured":"Kennedy, J.: Particle swarm optimization. In: Encyclopedia of Machine Learning, pp. 760\u2013766. Springer, Berlin (2011)","DOI":"10.1007\/978-0-387-30164-8_630"},{"key":"846_CR22","doi-asserted-by":"publisher","first-page":"4598","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 4598 (1983)","journal-title":"Science"},{"issue":"1\u20132","key":"846_CR23","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn, H.W.: The Hungarian method for the assignment problem. NRL 2(1\u20132), 83\u201397 (1955)","journal-title":"NRL"},{"issue":"2","key":"846_CR24","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1007\/s10270-016-0545-x","volume":"17","author":"SJJ Leemans","year":"2018","unstructured":"Leemans, S.J.J., Fahland, D., van der Aalst, W.M.P.: Scalable process discovery and conformance checking. Softw. Syst. Model. 17(2), 599\u2013631 (2018)","journal-title":"Softw. Syst. Model."},{"key":"846_CR25","doi-asserted-by":"crossref","unstructured":"Nurlaili, A.L., Sarno, R.: A combination of the evolutionary tree miner and simulated annealing. In: 2017 4th International Conference on Electrical Engineering, Computer Science and Informatics (EECSI), pp. 1\u20135. IEEE (2017)","DOI":"10.1109\/EECSI.2017.8239134"},{"key":"846_CR26","unstructured":"Polyvyanyy, A., Solti, A., Weidlich, M., Ciccio, C.D., Mendling, J.: Monotone precision and recall measures for comparing executions and specifications of dynamic systems. CoRR (2018). arXiv:1812.07334"},{"key":"846_CR27","doi-asserted-by":"crossref","unstructured":"Ribeiro, J., Carmona Vargas, J.: A method for assessing parameter impact on control-flow discovery algorithms. In: Algorithms & Theories for the Analysis of Event Data (2015)","DOI":"10.1007\/978-3-662-53401-4_9"},{"key":"846_CR28","doi-asserted-by":"crossref","unstructured":"Smirnov, S., Weidlich, M., Mendling, J.: Business process model abstraction based on behavioral profiles. In: International Conference on Service-Oriented Computing, pp 1\u201316. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-17358-5_1"},{"key":"846_CR29","doi-asserted-by":"crossref","unstructured":"Song, W., Liu, S., Liu, Q.: Business process mining based on simulated annealing. In: ICYCS. IEEE (2008)","DOI":"10.1109\/ICYCS.2008.279"},{"key":"846_CR30","unstructured":"St\u00fctzle, T.: Local search algorithms for combinatorial problems. PhD thesis, Darmstadt University of Technology (1998)"},{"key":"846_CR31","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.is.2016.07.011","volume":"64","author":"S Suriadi","year":"2017","unstructured":"Suriadi, S., Andrews, R., ter Hofstede, A.H.M., Wynn, M.T.: Event log imperfection patterns for process mining: towards a systematic approach to cleaning event logs. Inf. Syst. 64, 132\u2013150 (2017)","journal-title":"Inf. Syst."},{"key":"846_CR32","doi-asserted-by":"crossref","unstructured":"Syring, A.F., Tax, N., van der Aalst, W.M.P.: Evaluating conformance measures in process mining using conformance propositions. In: Transactions on Petri Nets and Other Models of Concurrency XIV, pp. 192\u2013221. Springer, Berlin (2019)","DOI":"10.1007\/978-3-662-60651-3_8"},{"key":"846_CR33","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49851-4","volume-title":"Process Mining: Data Science in Action","author":"W van der Aalst","year":"2016","unstructured":"van der Aalst, W.: Process Mining: Data Science in Action. Springer, Berlin (2016)"},{"key":"846_CR34","doi-asserted-by":"crossref","unstructured":"vanden Broucke, S., De Weerdt, J.: Fodina: a robust and flexible heuristic process discovery technique. DSS 100, 109\u2013118 (2017)","DOI":"10.1016\/j.dss.2017.04.005"},{"key":"846_CR35","doi-asserted-by":"crossref","unstructured":"Weijters, A., Ribeiro, J.: Flexible heuristics miner (FHM). In: CIDM. IEEE (2011)","DOI":"10.1109\/CIDM.2011.5949453"},{"key":"846_CR36","doi-asserted-by":"crossref","unstructured":"Wen, L., Van Der Aalst, W.M.P., Wang, J., Sun, J.: Mining process models with non-free-choice constructs. Data Min. Knowl. Discov. 15(2), 145\u2013180 (2007)","DOI":"10.1007\/s10618-007-0065-y"}],"container-title":["Software and Systems Modeling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10270-020-00846-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10270-020-00846-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10270-020-00846-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,24]],"date-time":"2024-08-24T23:34:54Z","timestamp":1724542494000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10270-020-00846-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,27]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["846"],"URL":"https:\/\/doi.org\/10.1007\/s10270-020-00846-x","relation":{},"ISSN":["1619-1366","1619-1374"],"issn-type":[{"type":"print","value":"1619-1366"},{"type":"electronic","value":"1619-1374"}],"subject":[],"published":{"date-parts":[[2021,2,27]]},"assertion":[{"value":"24 February 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 September 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 November 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 February 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}