Journal of Computer Science and Technology ›› 2021, Vol. 36 ›› Issue (6): 1388-1406.doi: 10.1007/s11390-020-0293-9

Special Issue: Software Systems

• Regular Paper • Previous Articles     Next Articles

Activity Diagram Synthesis Using Labelled Graphs and the Genetic Algorithm

Chun-Hui Wang1,2,3, Member, CCF, Zhi Jin1,2,*, Fellow, CCF, Senior Member, IEEE, Wei Zhang1,2, Didar Zowghi4, Hai-Yan Zhao1,2, Senior Member, CCF, Member, ACM, IEEE, and Wen-Pin Jiao1,2        

  1. 1 Key Laboratory of High Confidence Software Technology(Ministry of Education), Peking University Beijing 100871, China;
    2 Institute of Software, School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China;
    3 School of Computer Science, Inner Mongolia Normal University, Hohhot 010022, China;
    4 Faculty of Engineering and Information Technology, University of Technology, Sydney 2007, Australia
  • Received:2020-01-17 Revised:2020-06-09 Online:2021-11-30 Published:2021-12-01
  • Contact: Zhi Jin E-mail:zhijin@pku.edu.cn
  • Supported by:
    This work was supported by the National Natural Science Foundation of China under Grant Nos. 61620106007, 61751210 and 61690200.

PDF (PC)

240

Supplement

1

Many applications need to meet diverse requirements of a large-scale distributed user group. That challenges the current requirements engineering techniques. Crowd-based requirements engineering was proposed as an umbrella term for dealing with the requirements development in the context of the large-scale user group. However, there are still many issues. Among others, a key issue is how to merge these requirements to produce the synthesized requirements description when a set of requirements descriptions from different participants are received. Appropriate techniques are needed for supporting the requirements synthesis. Diagrams are widely used in industry to represent requirements. This paper chooses the activity diagrams and proposes a novel approach for the activity diagram synthesis which adopts the genetic algorithm to repeatedly modify a population of individual solutions toward an optimal solution. As a result, it can automatically generate a resulting diagram which combines the commonalities as many as possible while leveraging the variabilities of a set of input diagrams. The approach is featured by: 1) the labelled graph proposed as the representation of the candidate solutions during the iterative evolution; 2) the generalized entropy proposed and defined as the measurement of the solutions; 3) the genetic algorithm designed for sorting out the high-quality solution. Four cases of different scales are used to evaluate the effectiveness of the approach. The experimental results show that not only the approach gets high precision and recall but also the resulting diagram satisfies the properties of minimization and information preservation and can support the requirements traceability.

Key words: crowd-based requirements engineering; requirements synthesis; activity diagram; genetic algorithm;

[1] Tuunanen T, Rossi M. Engineering a method for wide audience requirements elicitation and integrating it to software development. In Proc. the 37th Hawaii International Conference on System Sciences, January 2014. DOI: 10.1109/HICSS.2004.1265420.
[2] Snijders R, Atilla Ö, Dalpiaz F, Brinkkemper S. Crowd-centric requirements engineering: A method based on crowdsourcing and gamification. Technical Report, Utrecht University, 2015. http://www.cs.uu.nl/research/techreps/repo/CS-2015/2015-004.pdf, June 2020.
[3] Groen E C, Seyff N, Ali R et al. The crowd in requirements engineering: The landscape and challenges. IEEE Software, 2017, 34(2): 42-52. DOI: 10.1109/MS.2017.33.
[4] Adepetu A, Ahmed K A, Abd Y A, Zabbi A A, Svetinovic D. CrowdREquire: A requirements engineering crowdsourcing platform. In Proc. the 2012 AAAI Spring Symposium on Wisdom of the Crowd, March 2012, Article No. 1.
[5] Hosseini M, Shahri A, Phalp K, Taylor J, Ali R, Dalpiaz F. Configuring crowdsourcing for requirements elicitation. In Proc. the 9th IEEE International Conference on Research Challenges in Information Science, May 2015, pp.133-138. DOI: 10.1109/RCIS.2015.7128873.
[6] Pratyoush K S, Richa S. Crowdsourcing to elicit requirements for MyERP application. In Proc. the 1st IEEE International Workshop on Crowd-Based Requirements Engineering, August 2015, pp.31-35. DOI: 10.1109/CrowdRE.2015.7367586.
[7] Murukannaiah P K, Ajmeri N, Singh M P. Acquiring creative requirements from the crowd: Understanding the influences of personality and creative potential in crowd RE. In Proc. the 24th IEEE International Requirements Engineering Conference, September 2016, pp.176-185. DOI: 10.1109/RE.2016.68.
[8] Groen E, Dörr J, Adam S. Towards crowd-based requirements engineering: A research preview. In Proc. the 21st International Working Conference on Requirements Engineering: Foundation for Software Quality, March 2015, pp.247-253. DOI: 10.1007/978-3-319-16101-316.
[9] Murukannaiah P K, Ajmeri N, Singh M P. Toward automating crowd RE. In Proc. the 25th International Requirements Engineering Conference, September 2017, pp.512-515. DOI: 10.1109/RE.2017.74.
[10] Rosa L M, Dumas M, Uba R, Dijkman R. Business process model merging: An approach to business process consolidation. ACM Transactions on Software Engineering and Methodology, 2013, 22(2): Article No. 11. DOI: 10.1145/2430545.2430547.
[11] Dalpiaz F, Brinkkemper S. Agile requirements engineering with user stories. In Proc. the 26th International Requirements Engineering Conference, August 2018, pp.506-507. DOI: 10.1109/RE.2018.00075.
[12] Sutcliffe A, Maiden N, Minocha S, Manuel D. Supporting scenario-based requirements engineering. IEEE Transactions on Software Engineering, 1998, 24(12): 1072-1088. DOI: 10.1109/32.738340.
[13] Song X P, Hwong B, Matos G, Rudorfer A, Nelson C, Han M, Girenkov A. Understanding requirements for computer aided healthcare workflows: Experiences and challenges. In Proc. the 28th International Conference on Software Engineering, May 2006, pp.930-934. DOI: 10.1145/1134285.1134455.
[14] Ahmad T, Iqbal J, Ashraf A, Truscan D, Porres I. Modelbased testing using UML activity diagrams: A systematic mapping study. Computer Science Review, 2019, 33: 98-112. DOI: 10.1016/j.cosrev.2019.07.001.
[15] Nejati S, Sabetzadeh M, Chechik M, Easterbrook S M, Zave P. Matching and merging of statecharts specifications. In Proc. the 29th International Conference on Software Engineering, May 2007, pp.54-64. DOI: 10.1109/ICSE.2007.50.
[16] Sabetzadeh M. Merging and consistency checking of distributed models [Ph.D. Thesis]. Department of Computer Science, The University of Toronto, 2008.
[17] Rubin J, Chechik M. N-way model merging. In Proc. the 9th Joint Meeting on Foundations of Software Engineering, August 2013, pp.301-311. DOI: 10.1145/2491411.2491446.
[18] Harman M, Mansouri S A, Zhang Y Y. Search-based software engineering: Trends, techniques and applications. ACM Computing Surveys, 2012, 45(1): Article No. 11. DOI: 10.1145/2379776.2379787.
[19] Alshahwan N, Harman M. Automated web application testing using search based software engineering. In Proc. the 26th IEEE/ACM International Conference on Automated Software Engineering, November 2011, pp.3-12. DOI: 10.1109/ASE.2011.6100082.
[20] Dai Y S, Xie M, Poh K, Yang B. Optimal testing-resource allocation with genetic algorithm for modular software systems. Journal of Systems and Software, 2003, 66(1): 47-55. DOI: 10.1016/S0164-1212(02)00062-6.
[21] Wang C H, Zhang W, Zhao H Y, Jin Z. Eliciting activity requirements from crowd using genetic algorithm. In Proc. the 4th Asia Pacific Requirements Engineering Conference, November 2017, pp.99-113. DOI: 10.1007/978-981-10-7796-88.
[22] Shannon C E. A mathematical theory of communication. Bell System Technical Journal, 1948, 27(3): 379-423. DOI: 10.1002/j.1538-7305.1948.tb01338.x.
[23] Fernando S, Stevenson M. A semantic similarity approach to paraphrase detection. In Proc. the 11th Annual Research Colloquium of the UK Special Interest Group for Computational Linguistics, December 2008, pp.45-52.
[24] Kondrak G. N-gram similarity and distance. In Proc. the 12th International Conference on String Processing and Information Retrieval, November 2005, pp.115-126. DOI: 10.1007/11575832_13.
[25] Niwattanakul S, Singthongchai J, Naenudorn E, Wanapu S. Using of Jaccard Coefficient for keywords similarity. In Proc. the 2013 International MultiConference of Engineers and Computer Scientists, March 2013.
[26] Simon D. Evolutionary Optimization Algorithms. John Wiley & Sons., 2013.
[27] Saraph V, Milenkovic T. MAGNA: Maximizing accuracy in global network alignment. Bioinformatics, 2014, 30(20): 2931-2940. DOI: 10.1093/bioinformatics/btu409.
[28] Arora C, Sabetzadeh M, Briand L C, Zimmer F. Automated extraction and clustering of requirements glossary terms. IEEE Transactions on Software Engineering, 2017, 43(10): 918-945. DOI: 10.1109/TSE.2016.2635134.
[29] Lim S L, Finkelstein A. StakeRare: Using social networks and collaborative filtering for large-scale requirements elicitation. IEEE Transactions on Software Engineering, 2012, 38(3): 707-735. DOI: 10.1109/TSE.2011.36.
[30] Breaux T, Schaub F. Scaling requirements extraction to the crowd: Experiments with privacy policies. In Proc. the 22nd International Requirements Engineering Conference, August 2014, pp.163-172. DOI: 10.1109/RE.2014.6912258.
[31] Maalej W, Happel H, Rashid A. When users become collaborators: Towards continuous and context-aware user input. In Proc. the 24th Annual ACM SIGPLAN Conference Companion on Object-Oriented Programming, Systems, Languages, and Applications, October 2009, pp.981-990. DOI: 10.1145/1639950.1640068.
[32] Kessentini M, Werda W, Langer P, Wimmer M. Searchbased model merging. In Proc. the 15th Annual Conference on Genetic and Evolutionary Computation, July 2013, pp.1453-1460. DOI: 10.1145/2463372.2463553.
[33] Assunção W K G, Vergilio S R, Lopez-Herrejon R E. Discovering software architectures with search-based merge of UML model variants. In Proc. the 16th International Conference on Software Reuse, May 2017, pp.95-111. DOI: 10.1007/978-3-319-56856-0_7.
[34] Debreceni C, Ráth I, Varró D, De Carlos X, Mendialdua X, Trujillo S. Automated model merge by design space exploration. In Proc. the 19th International Conference on Fundamental Approaches to Software Engineering, April 2016, pp.104-121. DOI: 10.1007/978-3-662-49665-7_7.
[1] Jian-Fu Zhu, Zhong-Kai Hao, Qi Liu, Yu Yin, Cheng-Qiang Lu, Zhen-Ya Huang, and En-Hong Chen. Towards Exploring Large Molecular Space: An Efficient Chemical Genetic Algorithm [J]. Journal of Computer Science and Technology, 2022, 37(6): 1464-1477.
[2] Xiao-Bing Chen, Hao Qi, Shao-Hui Peng, Yi-Min Zhuang, Tian Zhi, and Yun-Ji Chen. Tetris: A Heuristic Static Memory Management Framework for Uniform Memory Multicore Neural Network Accelerators [J]. Journal of Computer Science and Technology, 2022, 37(6): 1255-1270.
[3] Yong-Hao Long, Yan-Cheng Chen, Xiang-Ping Chen, Xiao-Hong Shi, and Fan Zhou. Test-Driven Feature Extraction of Web Components [J]. Journal of Computer Science and Technology, 2022, 37(2): 389-404.
[4] Jie Xiao, Zhan-Hui Shi, Jian-Hui Jiang, Xu-Hua Yang, Yu-Jiao Huang, Hai-Gen Hu. A Locating Method for Reliability-Critical Gates with a Parallel-Structured Genetic Algorithm [J]. Journal of Computer Science and Technology, 2019, 34(5): 1136-1151.
[5] Rong-Zhi Qi, Zhi-Jian Wang, Shui-Yan Li. A Parallel Genetic Algorithm Based on Spark for Pairwise Test Suite Generation [J]. , 2016, 31(2): 417-427.
[6] Concha Bielza, Juan A. Fernández del Pozo, and Pedro Larrañaga. Parameter Control of Genetic Algorithms by Learning and Simulation of Bayesian Networks —— A Case Study for the Optimal Ordering of Tables [J]. , 2013, 28(4): 720-731.
[7] Antonio M. Mora, Antonio Fernández-Ares, Juan J. Merelo, Pablo García-Sánchez, and Carlos M. Fernandes. Effect of Noisy Fitness in Real-Time Strategy Games Player Behaviour Optimisation Using Evolutionary Algorithms [J]. , 2012, 27(5): 1007-1023.
[8] Zhu-Fei Chu (储著飞), Student Member, IEEE, Yin-Shui Xia (夏银水), and Lun-Yao Wang (王伦耀). Cell Mapping for Nanohybrid Circuit Architecture Using Genetic Algorithm [J]. , 2012, 27(1): 113-120.
[9] Feng Zeng, Student Member, CCF, and Zhi-Gang Chen, Member, CCF. Cost-Sensitive and Load-Balancing Gateway Placement in Wireless Mesh Networks with QoS Constraints [J]. , 2009, 24(4): 775-785.
[10] Sriparna Saha, Student Member, IEEE, and Sanghamitra Bandyopadhyay, Senior Member, IEEE. A New Line Symmetry Distance and Its Application to Data Clustering [J]. , 2009, 24(3): 544-556.
[11] Ji-Bao Lai , Hui-Qiang Wang, Xiao-Wu Liu, Ying Liang, Rui-Juan Zheng, and Guo-Sheng Zhao. WNN-Based Network Security Situation Quantitative Prediction Method and Its Optimization [J]. , 2008, 23(2): 222-230 .
[12] Ehab Z. Elfeky, Ruhul A. Sarker, and Daryl L. Essam. Analyzing the Simple Ranking and Selection Process for Constrained Evolutionary Optimization [J]. , 2008, 23(1): 19-34 .
[13] Sheng-Zhi Du, Zeng-Qiang Chen, and Zhu-Zhi Yuan. Evolutionary Pseudo-Relaxation Learning Algorithm for Bidirectional Associative Memory [J]. , 2005, 20(4): 559-566 .
[14] Tian-Ming Bu, Song-Nian Yu, and Hui-Wei Guan. Binary-Coding-Based Ant Colony Optimization and Its Convergence [J]. , 2004, 19(4): 0-0.
[15] Zhao-Xia Wang, Zeng-Qiang Chen, and Zhu-Zhi Yuan. QoS Routing Optimization Strategy Using Genetic Algorithm in Optical Fiber Communication Networks [J]. , 2004, 19(2): 0-0.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] Zhou Di;. A Recovery Technique for Distributed Communicating Process Systems[J]. , 1986, 1(2): 34 -43 .
[2] Li Wei;. A Structural Operational Semantics for an Edison Like Language(2)[J]. , 1986, 1(2): 42 -53 .
[3] Chen Shihua;. On the Structure of Finite Automata of Which M Is an(Weak)Inverse with Delay τ[J]. , 1986, 1(2): 54 -59 .
[4] Li Wanxue;. Almost Optimal Dynamic 2-3 Trees[J]. , 1986, 1(2): 60 -71 .
[5] Feng Yulin;. Recursive Implementation of VLSI Circuits[J]. , 1986, 1(2): 72 -82 .
[6] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[7] Wang Xuan; Lü Zhimin; Tang Yuhai; Xiang Yang;. A High Resolution Chinese Character Generator[J]. , 1986, 1(2): 1 -14 .
[8] C.Y.Chung; H.R.Hwa;. A Chinese Information Processing System[J]. , 1986, 1(2): 15 -24 .
[9] Sun Zhongxiu; Shang Lujun;. DMODULA:A Distributed Programming Language[J]. , 1986, 1(2): 25 -31 .
[10] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved