Local and Global Evaluation Functions for Computational Evolution
Jing Han
Electronic mail address: hanjing@amss.ac.cn
The Santa Fe Institute,
Sante Fe, NM, 87501
and
Institute of Systems Science,
Academy of Mathematics and Systems Science,
Beijing, China, 100080
Abstract
This paper compares computational evolution using local and global evaluation functions in the context of solving two classical combinatorial problems on graphs: the k-coloring and minimum coloring problems. It is shown that the essential difference between traditional algorithms using local search (such as simulated annealing) and distributed algorithms (such as the Alife&AER model) lies in the evaluation function. Simulated annealing uses global information to evaluate the whole system state, which is called the global evaluation function (GEF) method. The Alife&AER model uses local information to evaluate the state of a single agent, which is called the local evaluation function (LEF) method. Computer experiment results show that the LEF methods are comparable to GEF methods (simulated annealing and greedy), and in some problem instances the LEF beats GEF methods. We present the consistency theorem which shows that a Nash equilibrium of an LEF is identical to a local optimum of a GEF when they are "consistent." This theorem explains why some LEFs can lead the system to a global goal. Some rules for constructing a consistent LEF are proposed.
