Knowledge discovery can be regarded as exploration of high-dimensional and multi-modal search spaces. However, finding the global optimum of an objective function with many degrees of freedom and numerous local optima is computationally demanding. Systems capable of learning and adaptivity therefore fundamentally rely on search techniques. These should sample the search space in such a way that there is a high probability of finding near-optimal solutions. Many search techniques have been developed and most of them are specialized to solve specific types of problems. An important class of search techniques are stochastic algorithms where certain steps are based on random choice. Most stochastic search algorithms were shown effective and efficient in finding near-optimal solutions to complex problems, but with no guarantee of finding true global optima. The presentation covers stochastic search techniques inspired by phenomena found in nature: simulated annealing and evolutionary algorithms.

Simulated annealing is a popular stochastic algorithm designed in analogy with the physical process of cooling a molten substance where condensing of matter into a crystalline solid takes place. In this context, searching for an optimal solution is like finding a configuration of the cooled system with minimum free energy. Because of its ability of escaping from local optima, simulated annealing is a powerful algorithm for numerical and combinatorial optimization.

Evolutionary algorithms are simplified models of the search processes of natural evolution. They simulate collective learning within an population of individuals that represent potential solutions to the considered problem. The population evolves towards better regions of the search space by means of stochastic transformations of individuals and feedback on their performance from the environment.

Three variants of evolutionary algorithms are discussed: evolution strategies, genetic algorithms and genetic programming. Evolution strategies were proposed as a technique of evolutionary experimentation in engineering design and are nowadays used as numerical optimization algorithms. Genetic algorithms are general-purpose search and optimization algorithms based on string representation of candidate solutions and variation operators mimicking genetic processes in nature. Genetic programming is an extension of genetic algorithms designed to evolve not simple solutions to given problems, but computer programs to solve the problems. It is an important step towards automatic programming of computers and has already reached the stage of producing human-competitive solutions in a wide range of application domains.