| EMERGENCE FROM LOCAL EVALUATION FUNCTION |
| |
| 作者姓名： | HANJing CAIQingsheng |
| |
| 作者单位： | [1]InstituteofSystemsScience,AcademyofMathematicsandSystemsSciences,Belting100080,China [2]DepartmentofComputerScience,UniversityofScienceandTechnologyofChina,Hefei230026,China |
| |
| 基金项目： | This paper is supported by the International Program of Santa Fe Institute and the grant of China National Science Foundation(No.70171052). |
| |
| 摘 要： | This paper presents a new look on emergence from the aspect of locality and globality of evaluation functions for solving traditional computer problems. We first translate the Constraint Satisfaction Problem (CSP) into the multi-agent system, and then show how a global solution emerges from the system in which every agent uses a local evaluation function to decide its action, while comparing to other traditional algorithms,such as Local search and Simulated Annealing which use global evaluation functions. We also give some computer experimental results on large-scale N-queen problems and k-Coloring problems, and show that emergence only depends on problem instance, not details of agent settings, i.e. in some CSPs, the system can self-organize to a global solution~ but can not in some other CSPs no matter what settings of agents have.
|
| 关 键 词： | 约束满足问题 局部评价函数 多Agent系统 自组织系统 |
EMERGENCE FROM LOCAL EVALUATION FUNCTION |
| |
| HANJing CAIQingsheng.EMERGENCE FROM LOCAL EVALUATION FUNCTION[J].Journal of Systems Science and Complexity,2003,16(3):372-390. |
| |
| Authors: | HAN Jing |
| |
| Abstract: | This paper presents a new look on emergence from the aspect of locality and globality of evaluation functions for solving traditional computer problems. We first translate the Constraint Satisfaction Problem (CSP) into the multi-agent system, and then show how a global solution emerges from the system in which every agent uses a local evaluation function to decide its action, while comparing to other traditional algorithms, such as Local search and Simulated Annealing which use global evaluation functions. We also give some computer experimental results on large-scale N-queen problems and k-Coloring problems, and show that emergence only depends on problem instance, not details of agent settings, i.e. in some CSPs, the system can self-organize to a global solution, but can not in some other CSPs no matter what settings of agents have. |
| |
| Keywords: | Constraint satisfaction problem evolution function multi-agent system |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
