|
|
Grammatical evolution
Nohejl, Adam ; Mráz, František (advisor) ; Iša, Jiří (referee)
Grammatical evolution (GE) is a recent grammar-based approach to genetic programming that allows development of solutions in an arbitrary programming language. Its existing implementations lack documentation and do not provide reproducible results suitable for further analysis. This thesis summarises the methods of GE and the standard methods used in evolutionary algorithms, and reviews the existing implementations, foremost the only actively developed one, GEVA. A new comprehensive software framework for GE is designed and implemented based on this review. It is modular, well-documented, portable, and gives reproducible results. It has been tested in two benchmark applications, in which it showed competitive results and outperformed GEVA 10 to 29 times in computational time. It is also shown how to further improve the performance and results by using techniques unsupported by GEVA, including new modications to the previously published methods of bit-level mutation and "sensible" initialisation. The thesis and the software together form a solid foundation for further experiments and research.
|
|
|
Grammar-based genetic programming
Nohejl, Adam ; Mráz, František (advisor) ; Iša, Jiří (referee)
Tree-based genetic programming (GP) has several known shortcomings: difficult adaptability to specific programming languages and environments, the problem of closure and multiple types, and the problem of declarative representation of knowledge. Most of the methods that try to solve these problems are based on formal grammars. The precise effect of their distinctive features is often difficult to analyse and a good comparison of performance in specific problems is missing. This thesis reviews three grammar-based methods: context-free grammar genetic programming (CFG-GP), including its variant GPHH recently applied to exam timetabling, grammatical evolution (GE), and LOGENPRO, it discusses how they solve the problems encountered by GP, and compares them in a series of experiments in six applications using success rates and derivation tree characteristics. The thesis demonstrates that neither GE nor LOGENPRO provide a substantial advantage over CFG-GP in any of the experiments, and analyses the differences between the effects of operators used in CFG-GP and GE. It also presents results from a highly efficient implementation of CFG-GP and GE.
|
|
|
Polysemy of Japanese V-V compound verbs- a corpus analysis
Nohejl, Adam ; Kanasugi, Petra (advisor) ; Rosen, Alexandr (referee)
The thesis analyses Japanese verb-verb compound verbs using a corpus in order to build a pedagogical word list of these verbs accounting for their polysemy. First, the typology and characteristics of Japanese compound verbs are discussed. The following review of pedagogical resources identifies the need for a list of compound verbs and their senses based on frequency criteria. A methodology for creating the word list and assessing its utility to learners is discussed with attention to the characteristics of the Japanese language. The resulting word list based on a corpus analysis (included in the appendix) consists of 37 compound verbs, out of which 32 are lexical, includes 45 senses of lexical compound verbs. It covers 17.95 % of the lexical compound verb occurrences, which is proportional to covering 85 % verbs overall. Finally, the quantitative characteristics of Japanese compound verbs and English phrasal verbs are compared. The comparison shows that the Japanese compound verbs are more frequent and diverse and therefore also likely to be an major stumbling block for language learners.
|
|
|
Grammar-based genetic programming
Nohejl, Adam ; Mráz, František (advisor) ; Iša, Jiří (referee)
Tree-based genetic programming (GP) has several known shortcomings: difficult adaptability to specific programming languages and environments, the problem of closure and multiple types, and the problem of declarative representation of knowledge. Most of the methods that try to solve these problems are based on formal grammars. The precise effect of their distinctive features is often difficult to analyse and a good comparison of performance in specific problems is missing. This thesis reviews three grammar-based methods: context-free grammar genetic programming (CFG-GP), including its variant GPHH recently applied to exam timetabling, grammatical evolution (GE), and LOGENPRO, it discusses how they solve the problems encountered by GP, and compares them in a series of experiments in six applications using success rates and derivation tree characteristics. The thesis demonstrates that neither GE nor LOGENPRO provide a substantial advantage over CFG-GP in any of the experiments, and analyses the differences between the effects of operators used in CFG-GP and GE. It also presents results from a highly efficient implementation of CFG-GP and GE.
|
|
|
Grammatical evolution
Nohejl, Adam ; Iša, Jiří (referee) ; Mráz, František (advisor)
Grammatical evolution (GE) is a recent grammar-based approach to genetic programming that allows development of solutions in an arbitrary programming language. Its existing implementations lack documentation and do not provide reproducible results suitable for further analysis. This thesis summarises the methods of GE and the standard methods used in evolutionary algorithms, and reviews the existing implementations, foremost the only actively developed one, GEVA. A new comprehensive software framework for GE is designed and implemented based on this review. It is modular, well-documented, portable, and gives reproducible results. It has been tested in two benchmark applications, in which it showed competitive results and outperformed GEVA 10 to 29 times in computational time. It is also shown how to further improve the performance and results by using techniques unsupported by GEVA, including new modications to the previously published methods of bit-level mutation and "sensible" initialisation. The thesis and the software together form a solid foundation for further experiments and research.
|
guest ::
RSS feed.