Adding Learning to CMSA

CMSA is undeniably an algorithm whose efficacy can, to some extent, be attributed to its inherent simplicity. As demonstrated in previous chapters of this book, unsophisticated variants of CMSA are capable of yielding highly satisfactory results. Nevertheless, such basic CMSA variants can, of course, undergo enhancement through the incorporation of supplementary algorithmic components. One avenue for refining barebone CMSA variants involves introducing a learning component into the solution construction mechanism. This addition enables the solution construction mechanism to generate solutions of improving quality over time. In this chapter, we will show how this can be done in the context of two combinatorial optimization problems that were already used for the illustration of other CMSA variants in previous chapters. In particular, applications to the Minimum Dominating Set (MDS) problem and the Far From Most String (FFMS) problem are presented.