research-article

A Formal Design Model for Genetic Algorithms Operators and its Encoding in PVS

Authors:

M. Saqib Nawaz,

Meng SunAuthors Info & Claims

BDIOT '18: Proceedings of the 2018 2nd International Conference on Big Data and Internet of Things

Pages 186 - 190

https://doi.org/10.1145/3289430.3289449

Published: 24 October 2018 Publication History

Abstract

Genetic Algorithms (GA) are bio-inspired algorithms that are now used in safety critical systems, robotics, artificial intelligence and bioinformatics, etc. A formal semantic model for GA is needed that can provide a framework for the modeling, reasoning and verification of GA based systems. On the other hand, Unifying Theories of Programming (UTP) offers formal semantic foundations for programming as well as specification languages. UTP is used in this paper to formalize a family of crossover and mutation operators of GA, where operators are defined as design models. UTP design models also allow the establishment of refinement and equivalence relations between GA operators by introducing implication between predicates. As an example, the equivalence relation between operators is proved with the PVS proof assistant.

References

[1]

F. Aguado, J. L. Doncel, J. M. Molinelli, G. Pérez, and C. Vidal. 2008. Genetic algorithms in Coq: Generalization and formalization of the crossover operator. Journal of Formalized Reasoning 1 (2008), 25--37.

[2]

F. Aguado, J. L. Doncel, J. M. Molinelli, G. Pérez, C. Vidal, and A. Vieites. 2007. Certified genetic algorithms: Crossover operators for permutations. In Proceedings of EUROCAST, 2007. Springer, 282--289.

Digital Library

[3]

M. Dorigo and T. Stútzle. 2004. Ant Colony Optimization. MIT Press, Cambridge, MA, USA.

Digital Library

[4]

A. George, B. R. Rajakumar, and D. Bino. 2012. Genetic algorithm based airlines booking terminal open/close decision systems. In Proceedings of ICACCI, 2012. ACM, 174--179.

Digital Library

[5]

C. Gondro and B. P. Kinghom. 2007. A simple genetic algorithm for multiple sequence alignment. Genetics and Molecular Research 6 (2007), 964--982.

[6]

C. A. R. Hoare and J. He. 1998. Unifying Theories of Programming. Prentice Hall International.

[7]

J. H. Holland. 1975. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI, USA.

Digital Library

[8]

J Kennedy and R. C. Eberhart. 1995. Particle swarm optimization. In Proceedings of International Conference on Neural Neworks. IEEE, 1942--1948.

[9]

M. S. Nawaz, M. I. Lali, and M. A. Pasha. 2013. Formal verification of crossover operator in genetic algorithms using prototype verification system (PVS). In Proceedings of ICET, 2013. IEEE, 1--6.

[10]

M. S. Nawaz, M. I. U. Lali, and S. Meng. 2017. Formal modeling, analysis and verification of black white bakery algorithm. In Proceedings of IHMSC, 2017. IEEE, 407--410.

[11]

S. Noor, M. I. Lali, and M. S. Nawaz. 2015. Solving job shop scheduling problem with genetic algroithm. Science International 27 (2015), 3367--3371.

[12]

F. A. Omara and M. M. Arafa. 2010. Genetic algorithms for task scheduling problem. Journal of Parallel and Distributed Computing 70 (2010), 13--22.

Digital Library

[13]

S. Owre, N. Shankar, J. M. Rushby, and D. W. J. Stringer-Calvert. 2001. PVS system guide, PVS prover guide, PVS language reference. Technical Report. SRI International, USA.

[14]

M. Patrascu. 2014. Genetically enhanced modal controller design for seismic vibration in nonlinear multi-damper configuration. Journal of Systems and Control Engineering 229 (2014), 158--168.

[15]

PVS dump file. {n. d.}. https://github.com/saqibdola/UTPGA/blob/master/utpga.

[16]

F. Siefert, F. Nafz, H. Seebach, and W. Reif. 2011. A genetic algorithm for self-optimization in safety-critical resource-flow systems. In Proceedings of EAIS, 2011. IEEE, 77--84.

[17]

S.N. Sivanandam and S.N. Deepa. 2008. Introduction to Genetic Algorithms. Springer.

Digital Library

[18]

M. Sun, F. Arbab, B. K. Aichernig, L. Astefanoaei, F. S. de Boer, and J. Rutten. 2012. Connectors as designs: Modeling, refinement and test case generation. Science of Computer Programming 77, 7-8 (2012), 799--822.

Digital Library

[19]

A. Uchibori and N. Endou. 1999. Basic properties of genetic algorithms. Journal of Formalized Mathematics 8 (1999), 151--160.

[20]

M. P. Vicmudo, E. P. Dadios, and R. R. Vicerra. 2014. Path planning of underwater swarm robots using genetic algorithm. In Proceedings of HNICEM, 2014. 1--5.

[21]

H. Wu, W. Hsiao, C. Lin, and T. Cheng. 2011. Application of genetic algorithm to the development of artificial intelligence module system. In Proceedings of ICICIP, 2011. IEEE, 290--294.

[22]

J. Zhang, M. Kang, X. Li, and G. Liu. 2017. Bio-Inspired genetic algorithms with formalized crossover operators for robotic applications. Frontiers in Neurorobotics 11 (2017), 1--12.

Cited By

Nawaz MNoor SFournier-Viger P(2022)Reasoning About Order Crossover in Genetic AlgorithmsAdvances in Swarm Intelligence10.1007/978-3-031-09677-8_22(261-271)Online publication date: 26-Jun-2022
https://doi.org/10.1007/978-3-031-09677-8_22
Nawaz MFournier-Viger PSong WLin JNoack B(2021)Investigating Crossover Operators in Genetic Algorithms for High-Utility Itemset MiningIntelligent Information and Database Systems10.1007/978-3-030-73280-6_2(16-28)Online publication date: 7-Apr-2021
https://dl.acm.org/doi/10.1007/978-3-030-73280-6_2
Nawaz MSun MShahzad BLali MUmer TWan S(2019)Quality of service in IoT protocol as designs and its verification in PVSTransactions on Emerging Telecommunications Technologies10.1002/ett.374233:8Online publication date: 9-Oct-2019
https://doi.org/10.1002/ett.3742

Index Terms

A Formal Design Model for Genetic Algorithms Operators and its Encoding in PVS
1. Computing methodologies
  1. Machine learning
    1. Machine learning approaches
      1. Bio-inspired approaches
        Genetic algorithms
2. Software and its engineering
  1. Software organization and properties
    1. Software functional properties
      1. Formal methods

Recommendations

Evolution of Appropriate Crossover and Mutation Operators in a Genetic Process

Traditional genetic algorithms use only one crossover and one mutation operator to generate the next generation. The chosen crossover and mutation operators are critical to the success of genetic algorithms. Different crossover or mutation operators, ...
On the applicability of diploid genetic algorithms in dynamic environments

Diploid genetic algorithms (DGAs) promise robustness as against simple genetic algorithms which only work towards optimization. Moreover, these algorithms outperform others in dynamic environments. The work examines the theoretical aspect of the concept ...
Reasoning About Order Crossover in Genetic Algorithms
Advances in Swarm Intelligence
Abstract
The formal modeling and verification of algorithms is a challenging task, but it is a necessary requirement for the proof of correctness. Evolutionary computation and theorem proving approach of formal methods are two different domains in ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

BDIOT '18: Proceedings of the 2018 2nd International Conference on Big Data and Internet of Things

October 2018

217 pages

ISBN:9781450365192

DOI:10.1145/3289430

Copyright © 2018 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]

In-Cooperation

Deakin University

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 October 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

National Natural Science Foundation of China

Conference

BDIOT 2018

BDIOT 2018: 2018 2nd International Conference on Big Data and Internet of Things

October 24 - 26, 2018

Beijing, China

Acceptance Rates

Overall Acceptance Rate 75 of 136 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
66
Total Downloads

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

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Nawaz MNoor SFournier-Viger P(2022)Reasoning About Order Crossover in Genetic AlgorithmsAdvances in Swarm Intelligence10.1007/978-3-031-09677-8_22(261-271)Online publication date: 26-Jun-2022
https://doi.org/10.1007/978-3-031-09677-8_22
Nawaz MFournier-Viger PSong WLin JNoack B(2021)Investigating Crossover Operators in Genetic Algorithms for High-Utility Itemset MiningIntelligent Information and Database Systems10.1007/978-3-030-73280-6_2(16-28)Online publication date: 7-Apr-2021
https://dl.acm.org/doi/10.1007/978-3-030-73280-6_2
Nawaz MSun MShahzad BLali MUmer TWan S(2019)Quality of service in IoT protocol as designs and its verification in PVSTransactions on Emerging Telecommunications Technologies10.1002/ett.374233:8Online publication date: 9-Oct-2019
https://doi.org/10.1002/ett.3742

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.

Media

Figures

Other

Tables

View Table of Contents