research-article

Multi-objective optimization in rule-based design space exploration

Authors:

Dániel Varró,

Houari Sahraoui,

András Szabolcs Nagy,

Csaba Debreceni,

Ábel Hegedüs,

Ákos HorváthAuthors Info & Claims

ASE '14: Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering

Pages 289 - 300

https://doi.org/10.1145/2642937.2643005

Published: 15 September 2014 Publication History

Abstract

Design space exploration (DSE) aims to find optimal design candidates of a domain with respect to different objectives where design candidates are constrained by complex structural and numerical restrictions. Rule-based DSE aims to find such candidates that are reachable from an initial model by applying a sequence of exploration rules. Solving a rule-based DSE problem is a difficult challenge due to the inherently dynamic nature of the problem.

In the current paper, we propose to integrate multi-objective optimization techniques by using Non-dominated Sorting Genetic Algorithms (NSGA) to drive rule-based design space exploration. For this purpose, finite populations of the most promising design candidates are maintained wrt. different optimization criteria. In our context, individuals of a generation are defined as a sequence of rule applications leading from an initial model to a candidate model. Populations evolve by mutation and crossover operations which manipulate (change, extend or combine) rule execution sequences to yield new individuals.

Our multi-objective optimization approach for rule-based DSE is domain independent and it is automated by tooling built on the Eclipse framework. The main added value is to seamlessly lift multi-objective optimization techniques to the exploration process preserving both domain independence and a high-level of abstraction. Design candidates will still be represented as models and the evolution of these models as rule execution sequences. Constraints are captured by model queries while objectives can be derived both from models or rule applications.

References

[1]

P. Baldan and B. König. Approximating the behavior of graph transformation systems. In Proc. ICGT 2002, volume 2505 of LNCS, pages 14--29. Springer, 2002.

Digital Library

[2]

L. Baresi, V. Rafe, A. T. Rahmani, and P. Spoletini. An efficient solution for model checking graph transformation systems. ENTCS, 213, 2008.

Digital Library

[3]

L. Baresi and P. Spoletini. On the Use of Alloy to Analyze Graph Transformation Systems. In Graph Transformations, volume 4178 of LNCS, pages 306--320. 2006.

Digital Library

[4]

T. Basten, M. Hendriks, N. Trcka, L. Somers, M. Geilen, Y. Yang, G. Igna, S. de Smet, M. Voorhoeve, W. van der Aalst, et al. Model-driven design-space exploration for software-intensive embedded systems. In Model-Based Design of Adaptive Embedded Systems, pages 189--244. Springer, 2013.

[5]

T. Basten, E. van Benthum, et al. Model-driven design-space exploration for embedded systems: The Octopus toolset. In T. Margaria and B. Steffen, editors, Leveraging Applications of Formal Methods, Verification, and Validation, volume 6415 of LNCS, pages 90--105. Springer, 2010.

Digital Library

[6]

G. Bergmann, Z. Ujhelyi, I. Räth, and D. Varró. A graph query language for emf models. In Theory and Practice of Model Transformations, Fourth International Conference, ICMT 2011, Zurich, Switzerland, June 27-28, 2011. Proceedings, LNCS 6707, pages 167--182. Springer, 2011.

Digital Library

[7]

C. Bolchini, P. L. Lanzi, and A. Miele. A multi-objective genetic algorithm framework for design space exploration of reliable fpga-based systems. In IEEE Congress on Evolutionary Computation, pages 1--8, 2010.

[8]

H. Calborean, R. Jahr, T. Ungerer, and L. Vintan. A comparison of multi-objective algorithms for the automatic design space exploration of a superscalar system. In L. Dumitrache, editor, Advances in Intelligent Control Systems and Computer Science, volume 187 of Advances in Intelligent Systems and Computing, pages 489--502. Springer Berlin Heidelberg, 2013.

[9]

K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE Transactions Evolutionary Computation, 6(2):182--197, 2002.

Digital Library

[10]

J. Denil, M. Jukšs, C. Verbrugge, and H. Vangheluwe. Search-based model optimization using model transformations. Technical report, McGill University, Canada, 2014.

[11]

O. M. dos Santos, F. L. Dotti, and L. Ribeiro. Verifying object-based graph grammars. ENTCS, 109:125--136, 2004.

Digital Library

[12]

S. Edelkamp, S. Jabbar, and A. Lluch-Lafuente. Heuristic search for the analysis of graph transition systems. In Proceedings of the Third international conference on Graph Transformations, volume 4178 of LNCS, pages 414--429. Springer-Verlag, 2006.

Digital Library

[13]

R. Etemaadi and M. R. Chaudron. A model-based tool for automated quality-driven design of system architectures. In Proceedings of the 8th European Conference on Modelling Foundations and Applications (ECMFA'12), pages 2--5, 2012.

[14]

I. Galvao Lourenco da Silva, E. Zambon, A. Rensink, L. Wevers, and M. Aksit. Knowledge-based graph exploration analysis. In Fourth International Symposium on Applications of Graph Transformation with Industrial Relevance, AGTIVE 2011, Budapest, Hungary, LNCS 7233, pages 105--120. Springer, October 2011.

Digital Library

[15]

A. Gamatié, S. Le Beux, É. Piel, R. Ben Atitallah, A. Etien, P. Marquet, and J.-L. Dekeyser. A model-driven design framework for massively parallel embedded systems. ACM Transactions on Embedded Computing Systems (TECS), 10(4):39, 2011.

Digital Library

[16]

M. Harman, S. A. Mansouri, and Y. Zhang. Search-based software engineering: Trends, techniques and applications. ACM Comput. Surv., 45(1):11:1--11:61, Dec. 2012.

Digital Library

[17]

Á. Hegedüs, Á. Horváth, I. Ráth, M. C. Branco, and D. Varró. Quick fix generation for DSMLs. In IEEE Symposium on Visual Languages and Human-Centric Computing, VL/HCC 2011. IEEE Computer Society, 09/2011 2011.

[18]

Á. Hegedüs, Á. Horváth, I. Ráth, and D. Varró. A model-driven framework for guided design space exploration. In 26th IEEE/ACM International Conference on Automated Software Engineering (ASE 2011), Lawrence, Kansas, USA, 11/2011 2011. IEEE Computer Society, IEEE Computer Society.

Digital Library

[19]

Á. Hegedüs, Á. Horváth, and D. Varró. Towards guided trajectory exploration of graph transformation systems. Electronic Communications of the EASST, Petri Nets and Graph Transformations 2010, 40, 08/2011 2011.

[20]

Á. Horvüth and D. Varró. Dynamic constraint satisfaction problems over models. Software and Systems Modeling, 11:385--408, 2012 2012.

Digital Library

[21]

R. Jahr, H. Calborean, L. Vintan, and T. Ungerer. Boosting design space explorations with existing or automatically learned knowledge. In J. Schmitt, editor, Measurement, Modelling, and Evaluation of Computing Systems and Dependability and Fault Tolerance, volume 7201 of Lecture Notes in Computer Science, pages 221--235. Springer Berlin Heidelberg, 2012.

Digital Library

[22]

H. Jain and K. Deb. An evolutionary many-objective optimization algorithm using reference-point based non-dominated sorting approach, part ii: Handling constraints and extending to an adaptive approach. Evolutionary Computation, IEEE Transactions on, 2013.

[23]

E. Kang, E. K. Jackson, and W. Schulte. An approach for effective design space exploration. In Monterey Workshop, pages 33--54, 2010.

Digital Library

[24]

M. Kessentini, P. Langer, and M. Wimmer. Searching models, modeling search: On the synergies of sbse and mde. In CMSBSE@ICSE, pages 51--54, 2013.

Digital Library

[25]

M. Kessentini, H. Sahraoui, M. Boukadoum, and O. Omar. Search-based model transformation by example. Software and Systems Modeling, 11(2):209--226, 2012.

Digital Library

[26]

B. König and V. Kozioura. Counterexample-guided abstraction refinement for the analysis of graph transformation systems. In TACAS, pages 197--211, 2006.

Digital Library

[27]

I. Meedeniya, A. Aleti, and L. Grunske. Architecture-driven reliability optimization with uncertain model parameters. Journal of Systems and Software, 85(10):2340--2355, 2012.

Digital Library

[28]

I. Meedeniya, B. Buhnova, A. Aleti, and L. Grunske. Reliability-driven deployment optimization for embedded systems. Journal of Systems and Software, 84(5):835--846, 2011.

Digital Library

[29]

S. Neema, J. Sztipanovits, G. Karsai, and K. Butts. Constraint-based design-space exploration and model synthesis. In R. Alur and I. Lee, editors, Embedded Software, volume 2855 of LNCS, pages 290--305. Springer, 2003.

[30]

A. Rensink. The GROOVE simulator: A tool for state space generation. In Applications of Graph Transformations with Industrial Relevance (AGTIVE), volume 3062 of LNCS, pages 479--485. Springer, 2004. 10.1007/978-3-540-25959-6 40.

[31]

H. Saada, M. Huchard, C. Nebut, and H. A. Sahraoui. Recovering model transformation traces using multi-objective optimization. In ASE, pages 688--693, 2013.

Digital Library

[32]

T. Saxena and G. Karsai. MDE-based approach for generalizing design space exploration. In D. Petriu, N. Rouquette, and Ø. Haugen, editors, Model Driven Engineering Languages and Systems, volume 6394 of LNCS, pages 46--60. Springer, 2010.

Digital Library

[33]

B. Schatz, F. Holzl, and T. Lundkvist. Design-space exploration through constraint-based model-transformation. In Engineering of Computer Based Systems (ECBS), pages 173--182, March 2010.

Digital Library

[34]

Á. Schmidt and D. Varró. CheckVML: A tool for model checking visual modeling languages. In P. Stevens, J. Whittle, and G. Booch, editors, Proc. UML 2003: 6th International Conference on the Unified Modeling Language, volume 2863 of LNCS, pages 92--95, San Francisco, CA, USA, October 20-24 2003. Springer.

[35]

M. Shousha, L. C. Briand, and Y. Labiche. A uml/spt model analysis methodology for concurrent systems based on genetic algorithms. In MoDELS, pages 475--489, 2008.

Digital Library

[36]

Z. Ujhelyi, G. Bergmann, A. Hegedüs, A. Horváth, B. Izsó, I. Ráth, Z. Szatmári, and D. Varró. EMF-IncQuery: An Integrated development environment for live model queries. Science of Computer Programming, (0):--, 2014.

[37]

Y. Zhang. Multi-Objective Search-based Requirements Selection and Optimisation. Phd. thesis, King's College London, UK, 2010.

Cited By

Eisenberg MWimmer M(2024)From single-objective to multi-objective reinforcement learning-based model transformationSoftware and Systems Modeling10.1007/s10270-024-01233-6Online publication date: 19-Nov-2024
https://doi.org/10.1007/s10270-024-01233-6
Fritsche LLauer ASchürr ATaentzer G(2024)Using Application Conditions to Rank Graph Transformations for Graph RepairGraph Transformation10.1007/978-3-031-64285-2_8(138-157)Online publication date: 2-Jul-2024
https://doi.org/10.1007/978-3-031-64285-2_8
Taentzer GKosiol JLambers L(2024)On the Application of Model-Driven Optimization to Business ProcessesApplication and Theory of Petri Nets and Concurrency10.1007/978-3-031-61433-0_2(24-35)Online publication date: 26-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-61433-0_2
Show More Cited By

Index Terms

Multi-objective optimization in rule-based design space exploration
1. Software and its engineering
  1. Software creation and management

Recommendations

Multi-objective optimization using teaching-learning-based optimization algorithm

Two major goals in multi-objective optimization are to obtain a set of nondominated solutions as closely as possible to the true Pareto front (PF) and maintain a well-distributed solution set along the Pareto front. In this paper, we propose a teaching-...
MOEA/D for Multiple Multi-objective Optimization
Evolutionary Multi-Criterion Optimization
Abstract
This paper defines a new multi-objective optimization problem, called multiple multi-objective optimization problem (MMOP). An MMOP is composed of several multi-objective optimization problems (MOPs) with different decision spaces and the same ...
A comparative study of a teaching-learning-based optimization algorithm on multi-objective unconstrained and constrained functions

Multi-objective optimization is the process of simultaneously optimizing two or more conflicting objectives subject to certain constraints. Real-life engineering designs often contain more than one conflicting objective function, which requires a multi-...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ASE '14: Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering

September 2014

934 pages

ISBN:9781450330138

DOI:10.1145/2642937

General Chair:
Ivica Crnkovic
Mälardalen University, Sweden
,
Program Chairs:
Marsha Chechik
University of Toronto, Canada
,
Paul Grünbacher
Johannes Kepler Universität Linz, Austria

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAI: ACM Special Interest Group on Artificial Intelligence
SIGSOFT: ACM Special Interest Group on Software Engineering
Mälardalen University: Mälardalen University
IEEE CS

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 September 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

ASE '14

Sponsor:

SIGAI
SIGSOFT
Mälardalen University

ASE '14: ACM/IEEE International Conference on Automated Software Engineering

September 15 - 19, 2014

Vasteras, Sweden

Acceptance Rates

ASE '14 Paper Acceptance Rate 82 of 337 submissions, 24%;

Overall Acceptance Rate 82 of 337 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

54
Total Citations
View Citations
518
Total Downloads

Downloads (Last 12 months)55
Downloads (Last 6 weeks)5

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Eisenberg MWimmer M(2024)From single-objective to multi-objective reinforcement learning-based model transformationSoftware and Systems Modeling10.1007/s10270-024-01233-6Online publication date: 19-Nov-2024
https://doi.org/10.1007/s10270-024-01233-6
Fritsche LLauer ASchürr ATaentzer G(2024)Using Application Conditions to Rank Graph Transformations for Graph RepairGraph Transformation10.1007/978-3-031-64285-2_8(138-157)Online publication date: 2-Jul-2024
https://doi.org/10.1007/978-3-031-64285-2_8
Taentzer GKosiol JLambers L(2024)On the Application of Model-Driven Optimization to Business ProcessesApplication and Theory of Petri Nets and Concurrency10.1007/978-3-031-61433-0_2(24-35)Online publication date: 26-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-61433-0_2
Morais BZhang JSchirner G(2023)TSAR-ILP: Tile-Based, Synchronization-AwaRe ILP Allocating Heterogeneous Platforms for Streaming ApplicationsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.327405042:11(3693-3706)Online publication date: Dec-2023
https://doi.org/10.1109/TCAD.2023.3274050
David IArchambault PWolak QVu CLalonde TRiaz KSyriani ESahraoui H(2023)Digital Twins for Cyber-Biophysical Systems: Challenges and Lessons Learned2023 ACM/IEEE 26th International Conference on Model Driven Engineering Languages and Systems (MODELS)10.1109/MODELS58315.2023.00014(1-12)Online publication date: 1-Oct-2023
https://doi.org/10.1109/MODELS58315.2023.00014
Gemeinhardt FEisenberg MKlikovits SWimmer M(2023)Model-Driven Optimization for Quantum Program Synthesis with MOMoT2023 ACM/IEEE International Conference on Model Driven Engineering Languages and Systems Companion (MODELS-C)10.1109/MODELS-C59198.2023.00100(614-621)Online publication date: 1-Oct-2023
https://doi.org/10.1109/MODELS-C59198.2023.00100
Van Arragon LDamasceno CStrüber D(2023)Model-Driven Optimization: Towards Performance-Enhancing Low-Level Encodings2023 ACM/IEEE International Conference on Model Driven Engineering Languages and Systems Companion (MODELS-C)10.1109/MODELS-C59198.2023.00095(571-579)Online publication date: 1-Oct-2023
https://doi.org/10.1109/MODELS-C59198.2023.00095
Kosiol JJohn STaentzer G(2023)A generic construction for crossovers of graph-like structures and its realization in the eclipse modeling frameworkJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2023.100909(100909)Online publication date: Oct-2023
https://doi.org/10.1016/j.jlamp.2023.100909
Siabdelhadi AChadli ACherroun HOuared ASahraoui H(2023)MoTrans-BDI: Leveraging the Beliefs-Desires-Intentions agent architecture for collaborative model transformation by exampleJournal of Computer Languages10.1016/j.cola.2022.10117474(101174)Online publication date: Jan-2023
https://doi.org/10.1016/j.cola.2022.101174
John SKosiol JLambers LTaentzer G(2023)A graph-based framework for model-driven optimization facilitating impact analysis of mutation operator propertiesSoftware and Systems Modeling10.1007/s10270-022-01078-x22:4(1281-1318)Online publication date: 17-Jan-2023
https://doi.org/10.1007/s10270-022-01078-x
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten