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.