José F. Fontanari

Sandro M. Reia, Larissa F. Aquino, José F. Fontanari

Biological and cultural inspired optimization algorithms are nowadays part of the basic toolkit of a great many research domains. By mimicking processes in nature and animal societies, these general-purpose search algorithms promise to deliver optimal or near-optimal solutions using hardly any information on the optimization problems they are set to tackle. Here we study the performances of a cultural-inspired algorithm -- the imitative learning search -- as well as of asexual and sexual variants of evolutionary algorithms in finding the global maxima of NK-fitness landscapes. The main performance measure is the total number of agent updates required by the algorithms to find those global maxima and the baseline performance, which establishes the effectiveness of the cooperative algorithms, is set by the blind search in which the agents explore the problem space (binary strings) by flipping bits at random. We find that even for smooth landscapes that exhibit a single maximum, the evolutionary algorithms do not perform much better than the blind search due to the stochastic effects of the genetic roulette. The imitative learning is immune to this effect thanks to the deterministic choice of the fittest string in the population, which is used as a model for imitation. The tradeoff is that for rugged landscapes the imitative learning search is more prone to be trapped in local maxima than the evolutionary algorithms. In fact, in the case of rugged landscapes with a mild density of local maxima, the blind search either beats or matches the cooperative algorithms regardless of whether the task is to find the global maximum or to find the fittest state within a given runtime.

José F. Fontanari

The brain's self-monitoring of activities, including internal activities -- a functionality that we refer to as awareness -- has been suggested as a key element of consciousness. Here we investigate whether the presence of an inner-eye-like process (monitor) that supervises the activities of a number of subsystems (operative agents) engaged in the solution of a problem can improve the problem-solving efficiency of the system. The problem is to find the global maximum of a NK fitness landscape and the performance is measured by the time required to find that maximum. The operative agents explore blindly the fitness landscape and the monitor provides them with feedback on the quality (fitness) of the proposed solutions. This feedback is then used by the operative agents to bias their searches towards the fittest regions of the landscape. We find that a weak feedback between the monitor and the operative agents improves the performance of the system, regardless of the difficulty of the problem, which is gauged by the number of local maxima in the landscape. For easy problems (i.e., landscapes without local maxima), the performance improves monotonically as the feedback strength increases, but for difficult problems, there is an optimal value of the feedback strength beyond which the system performance degrades very rapidly.