New global optima results for the Kauffman N K model:: handling dependency

• 成果类型: Article
• 署名作者: Kaul, Hemanshu; Jacobson, Sheldon H.
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-006-0719-3
• 发表日期: 2006
• 页码: 475-494
• 关键词: expectations; statistics; EVOLUTION; bounds; walks

摘要

The Kauffman NK model has been used in theoretical biology, physics and business organizations to model complex systems with interacting components. This paper presents new global optima results for the NK model by developing tools for handling dependency in the cases where K grows with N; this generalizes the previous work that focused on the analysis of the (independent) case K=N-1. A dependency graph is defined and studied to handle dependencies among underlying random variables in the NK model. Order statistics (with dependencies) and the expected value of the global optima, E-N,E- K, are bounded using equitable coloring of the dependency graph. These bounds convert the problem of bounding order statistics of dependent random variables into that of independent random variables while incorporating quantitative information about the mutual dependencies between the underlying random variables. An alternative upper bound on E-N,E- K using direct arguments is also proposed. A detailed analysis of E-N,E- K for K close to N (K=N-alpha and K=beta N, alpha is an element of Z(+),beta is an element of (0,1)) is given for underlying uniform and normal distributions. Finally, for bounded underlying distributions, the global optima is shown to be concentrated around its mean E-N,E- K.