In the domain of computing, an everlasting requirement for developing new metaheuristics for particular problems, coming right from the well-known no free lunch theorem, may be observed. The need for new search and optimisation methods, hybrid ones in particular, paves the way for the development of different metaheuristics, going beyond classical methods (such as population-based ones). Evolutionary multiagent systems (EMAS), which brings together interesting features of agency (such as autonomy) and inspirations coming from population-based techniques, is a good example of such promising methods. However, constructing complex metaheuristics without a detailed description of their structure and behaviour may become pointless, and novel methods, though yielding promising results in particular cases, may be underestimated, because they have not been fully understood and analysed. This dissertation focuses on the issues concerning the justification of using agent-based metaheuristics (in particular EMAS and its variants), preparing of dedicated formal model, conducting an analysis aimed at proving so-called asymptotic guarantee of success and performing experimental analysis of the considered methods. These issues may be treated as the most important and novel aspects of this dissertation. In the beginning of the monograph, a systematic state-of-the-art review is given, then the concepts of EMAS and its modifications are discussed, later the formal model of structure and dynamics of the system using Markov-chains is described. Finally, the outcomes of a broad series of experiments on selected benchmark and real-world problems are discussed. The results presented in this dissertation are useful for practitioners who would to use agent-based metaheuristics and to obtain a deeper insight into the details of their design, experimental and formal features.
Wydawnictwa nie prowadzą sprzedaży książek z serii "Rozprawy Monografie". Zainteresowanych prosimy o kontakt z ich autorami.
- Spis treści
-
Abstract 7
Streszczenie 8
Preface 11
1. Contemporary search metaheuristics 17
1.1. Search problems and heuristic techniques 17
1.1.1. Difficult search problems 18
1.1.2. Metaheuristic and heuristic search methods 19
1.1.3. Selected single-solution metaheuristics 20
1.2. Evolutionary metaheuristic techniques 23
1.2.1. Avoiding the local extrema 24
1.2.2. Diversity in evolutionary algorithms 25
1.2.3. Stopping criteria for the evolutionary algorithms 27
1.3. Hybrid search methods 28
1.3.1. Classification of hybrid methods 28
1.3.2. Cultural and memetic computing 30
1.3.3. Immunological metaheuristic techniques 34
1.4. Agent-based computing 36
1.5. Vacant niches in theory and practice 41
2. Evolutionary multi-agent systems 44
2.1. Agent-based architectures of computing systems 45
2.2. Evolutionary multi-agent system 46
2.2.1. EMAS concept 47
2.2.2. Formal definition of EMAS 50
2.2.3. EMAS actions 57
2.2.4. EMAS management 66
2.3. Immunological evolutionary multi-agent system 70
2.3.1. iEMAS concept 70
2.3.2. Formal definition of iEMAS 72
2.3.3. iEMAS management 77
2.4. Towards verification of EMAS 81
3. Formal aspects of agent-based metaheuristics 82
3.1. Formal analysis of EMAS 82
3.1.1. EMAS dynamics 83
3.1.2. Ergodicity of EMAS 85
3.2. Formal analysis of iEMAS 89
3.2.1. iEMAS dynamics 89
3.2.2. Ergodicity of iEMAS 92
3.3. Goals attained in formal analysis 96
4. Experimental verification of EMAS 97
4.1. EMAS in solving benchmark problems 97
4.1.1. Definition of benchmark problems 98
4.1.2. Classical EMAS and PEA 100
4.1.3. Memetic EMAS and PEA 103
4.1.4. Classical and immunological EMAS 112
4.2. EMAS parameters tuning 113
4.2.1. Energy-related parameters 113
4.2.2. Probabilistic decision parameters 117
4.2.3. Immunological parameters 120
4.2.4. Parameters tuning recapitulation 124
4.3. EMAS in real-world problems 125
4.3.1. Step and flash imprint lithography inverse problem 126
4.3.2. Advisory strategy parameters optimisation 134
4.4. Goals attained in experimental verification 141
Summary 142
A. Experimental configuration details 145
B. Technical details of EMAS ergodicity proof 149
Bibliography 161