In this chapter we discuss problems to be solved, as encountered frequently by engineers, computer scientists, etc. We argue that problems and problem solvers can, and should, be distinguished, and observe that the field of evolutionary computing is primarily concerned with problem solvers. However, to characterise any problem solver it is useful to identify the kind of problems to which it can be applied. Therefore we start this book by discussing various classes of problems, and, in fact, even different ways of classifying problems.

In the following informal discussion, we introduce the concepts and the terminology needed for our purposes by examples, only using a formal treatment when it is necessary for a good understanding of the details. To avoid controversy, we are not concerned with social or political problems. The problems we have in mind are the typical ones with which artificial intelligence is associated: more akin to puzzles (e.g., the famous zebra puzzle), numerical problems (e.g., what is the shortest route from a northern city to a southern city), or pattern discovery (e.g., what will a new customer buy in our online book store, given their gender, age, address, etc).

Contents:

1.1 Optimisation, Modelling, and Simulation Problems . . . . . . . . . . 1

1.1.1 Optimisation ………………………………. 2

1.1.2 Modelling …………………………………. 3

1.1.3 Simulation…………………………………. 5

1.2 Search Problems …………………………………. 5

1.3 Optimisation Versus Constraint Satisfaction ……………. 6

1.4 The Famous NP Problems………………………….. 9