In order to demonstrate the optimization power of the alife environments, we have modified the nagual experiment in order to obtain a continuos substained evolution. In this new environment we have limited the individual extension to a single cell considering only the head of the nagual filaments which became points moving in a two-dimensional lattice.

Furthermore, in the genoma of each individual we incorporate a new block of information that represents the parameters of the specific problem to optimize (configuration or solution). On the base of this information a fitness function is computed which represent the quality connected with the configuration recorded in the genoma. The optimization problem consists in the maximization of this function. In the reproduction, we apply the mutations only in this block of information.

Upon the meeting of two individuals, a mechanism of competition is activated. The competition is based on the value of fitness of the two individuals: an individual which has a higher fitness survives. After a while, individuals which have higher fitness are able to survive and continue the evolution. In this way the best solution, that corresponds to the individual with the highest fitness increases continuously its presence in the population reaching the optimal values.

The benchmark: Travelling Salesman Problem

In order to compare the optimization power of the artificial societies we have tested the algorithm on several benchmark problems comparing the results with other approaches which are not problem-dependent. In this section we report the results obtained on the Travelling Salesman Problem.

The Travelling Salesman Problem (TSP [20,21]) is one of the most famous and well-studied optimization problems. Its formulation is the following, "Given n towns find the minimal path such that each town, except the first, is visited exactly once". It is known to be a NP hard problem and researchers [23,25,26,27] use this problem as a benchmark for optimization algorithms. In order to test the capabilities of the artificial life optimization strategy, we customized the algorithm to solve TSP and compared the results with those obtained with the most successful algorithms based on the genetic approach. The numerical experiments have been carried out on two classical problems [23,24]: Oliver30 (30 towns) and Eil51 (50 towns).

The path, or the ordered list of towns, is the part of the genoma which defines the solution of the problem. The fitness corresponds to the inverse of the global path. In the reproduction, a son has a very similar genoma in respect to its father but a mutation can occurs in the list of the town: in particular, two towns can exchange their reciprocal position in the ordered list.

In order to improve the performances of the artificial society we have included a modification in the algorithm that allowed the possibility to develop cycles of development of the biodiversity in the sense of different genoma and cycles of selection. This effect was achieved by including modification in the reproduction. In most of the cases, the son can survive after the birth only if his fitness is higher than the father's. But in very few cases the son can also survive with a lower fitness.

The effect of this assumption is that the population select the best individuals by decreasing the probability of new births and consequently decreasing the number of living individuals (phase of selection). When an individual survives to the father with a low fitness, he is able to generate another specie of individuals: the probability of birth increases for this species and the number of individuals and their information explodes (phase of development of the biodiversity). Using this approach, the population have a continuous oscillation periodically renewing its content of information. In this figure an example of the population oscillation is reported.

The following table shows a comparison among the best results achieved by different strategies in terms of path length for the same cities locations. In the first column there are the results obtained by applying a simple greedy strategy of deep one, the second shows the simple Genetic Algorithm [18], the third columns show the outcome of the Dynamic Evolution approach [28]. The fourth column exhibits the results of the Ant Colonies Systems [22], the fifth those of the Evolutionary Programming [26] and the last column reports the results using the Artificial Societies approach described in this section.

As one can see, the results reached by the present approach are the best ones for both test cases considered.

Obviously, we cannot generalize this conclusion to every optimization problem or for the specific TSP problem (we have considered only not problem-dependent algorithms), but it is sufficient to demonstrate that the optimization power of this approach is at least similar to the more classical genetic approaches. Our interest is not only limited to the optimization power but also include to the ability to develop new configurations due the much more open structure. In fact, in respect to the genetic algorithms, the artificial society has an oscillating population, the possibility to use the space localization to develop local societies (local evolution) and finally the dimension of the self-organization.

Back to the index