自适应分布式搜索过程中的组织变化及问题复杂度对性能的影响

Friederike WALL

doi:10.1631/FITEE.1500306

Your Location：

Home >

Browse articles >

自适应分布式搜索过程中的组织变化及问题复杂度对性能的影响

分布式计算与人工智能专辑 | Updated：2022-05-19

- 自适应分布式搜索过程中的组织变化及问题复杂度对性能的影响
- Organizational dynamics in adaptive distributed search processes: effects on performance and the role of complexity#
- 信息与电子工程前沿（英文） 2016年17卷第4期页码：283-295
- Affiliations：
  
  Department of Controlling and Strategic Management, Alpen-Adria-Universitaet Klagenfurt, 9020 Klagenfurt, Austria
- Author bio：
  
  E-mail: friederike.wall@aau.at
- Funds：
  
  #A preliminary version was presented at the 12th International Conference on Distributed Computing and Artificial Intelligence, June 3–5, 2015, Spain
- DOI：10.1631/FITEE.1500306
  中图分类号： TP13
- 收稿：2015-09-21，
  
  录用：2016-1-5，
  
  纸质出版：2016-04
- Accepted：
Scan QR Code
自适应分布式搜索过程中的组织变化及问题复杂度对性能的影响[J]. 信息与电子工程前沿（英文）, 2016,17(4):283-295.

Friederike WALL. Organizational dynamics in adaptive distributed search processes: effects on performance and the role of complexity#[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(4): 283-295.
自适应分布式搜索过程中的组织变化及问题复杂度对性能的影响[J]. 信息与电子工程前沿（英文）, 2016,17(4):283-295. DOI： 10.1631/FITEE.1500306.

Friederike WALL. Organizational dynamics in adaptive distributed search processes: effects on performance and the role of complexity#[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(4): 283-295. DOI： 10.1631/FITEE.1500306.

摘要

目的

研究组织设置变更对分布式自适应搜索过程的影响，特别关注局部搜索间的交互复杂度。

创新点

基于分布式多智能体的仿真分析了组织设置的不同模式变化对于不同复杂度的搜索问题的影响。

方法

首先介绍了所采用的智能体仿真模型，描述了构建在NK适应度曲面上的分布式搜索问题及其复杂度。接着阐述了组织设置包括搜索智能体和核心智能体的设置、搜索智能体的视角形成、不同搜索智能体之间的协调以及搜索多样性等。然后给出组织动态性的数学描述，并进行了实验分析：（1）比较了组织变化对子问题交互复杂度最大和最小两种极端搜索问题的影响（称之为“基准”）；（2）分析最终和平均优化性能对搜索问题复杂度的敏感性；（3）分析交叉智能体交互复杂度对性能影响的不稳定性。

结论

本文的研究表明组织动态变化能够增加分布式自适应搜索的有效性，比如提高最终性能表现、增加获取最优解的可能性以及发现新的解域等。这种有效性增加幅度很大程度上取决于组织变化模式以及问题的复杂度。

Abstract

In this paper

the effects of altering the organizational setting of distributed adaptive search processes in the course of search are investigated. We put particular emphasis on the complexity of interactions between partial search problems assigned to search agents. Employing an agent-based simulation based on the framework of NK landscapes we analyze different temporal change modes of the organizational set-up. The organizational properties under change include

for example

the coordination mechanisms among search agents. Results suggest that inducing organizational dynamics has the potential to increase the effectiveness of distributed adaptive search processes with respect to various performance measures like the final performance achieved at the end of the search

the chance to find the optimal solution of the search problem

or the average performance per period achieved during the search process. However

results also indicate that the mode of temporal change in conjunction with the complexity of the search problem considerably affects the order of magnitude of these beneficial effects. In particular

results suggest that organizational dynamics induces a shift towards more exploration

i.e.

discovery of new areas in the fitness landscape

and less exploitation

i.e.

stepwise improvement.

关键词

Keywords

references

L Altenberg . . NK fitness landscapes. In: Back, T., Fogel, D.B., Michalewicz, Z. (Eds.), Handbook of Evolutionary Computation . . 1997 . . Oxford University Press, UK . . B2.7:5 - - B2.7:10 . . . .

O Baumann . . Distributed problem solving in modular systems: the benefit of temporary coordination neglect . . Syst. Res. Behav. Sci. , , 2013 . . 32 ( ( 1 ): ): 124 - - 136 . . DOI: 10.1002/sres.2218 http://doi.org/10.1002/sres.2218 . .

Y Cao , , , W Yu , , , W Ren , , , 等 . . An overview of recent progress in the study of distributed multi-agent coordination . . IEEE Trans. Ind. Inform. , , 2013 . . 9 ( ( 1 ): ): 427 - - 438 . . DOI: 10.1109/TII.2012.2219061 http://doi.org/10.1109/TII.2012.2219061 . .

K.M Carley , , , L Gasser . . Computational organization theory. In: Weiss, G. (Ed.), Multiagent Systems: a Modern Approach to Distributed Artificial Intelligence . . 1999 . . MIT Press, Cambridge . . 299 - - 330 . . . .

T Gross , , , B Blasius . . Adaptive coevolutionary networks: a review . . J. Royal Soc. Interf. , , 2008 . . 5 ( ( 20 ): ): 259 - - 271 . . DOI: 10.1098/rsif.2007.1229 http://doi.org/10.1098/rsif.2007.1229 . .

M.T Hansen . . The search-transfer problem: the role of weak ties in sharing knowledge across organization subunits . . Administr. Sci. Quart. , , 1999 . . 44 ( ( 1 ): ): 82 - - 111 . . DOI: 10.2307/2667032 http://doi.org/10.2307/2667032 . .

R.M Karp , , , E Upfal , , , A Wigderson . . The complexity of parallel search . . J. Comput. Syst. Sci. , , 1988 . . 36 ( ( 2 ): ): 225 - - 253 . . DOI: 10.1016/0022-0000(88)90027-X http://doi.org/10.1016/0022-0000(88)90027-X . .

S Kauffman . . The Origins of Order: Self-Organization and Selection in Evolution , , 1993 . . : : UK Oxford University Press , , . .

S Kauffman , , , S Levin . . Towards a general theory of adaptive walks on rugged landscapes . . J. Theor. Biol. , , 1987 . . 128 ( ( 1 ): ): 11 - - 45 . . DOI: 10.1016/S0022-5193(87)80029-2 http://doi.org/10.1016/S0022-5193(87)80029-2 . .

A Law . . Simulation Modeling and Analysis , , 2007 . . : : USA McGraw- Hill , , . .

B Levitan , , , S Kauffman . . Adaptive walks with noisy fitness measurements . . Mol. Divers. , , 1995 . . 1 ( ( 1 ): ): 53 - - 68 . . DOI: 10.1007/BF01715809 http://doi.org/10.1007/BF01715809 . .

R Li , , , M.T.M Emmerich , , , J Eggermont , , , 等 . . Mixed-integer NK landscapes . . 2006 . . Proc. 9th Int. Conf. on Parallel Problem Solving from Nature . . 42 - - 51 . . DOI: 10.1007/11844297_5 http://doi.org/10.1007/11844297_5 . .

C Peterson . . Parallel distributed approaches to combinatorial optimization: benchmark studies on traveling salesman problem . . Neur. Comput. , , 1990 . . 2 ( ( 3 ): ): 261 - - 269 . . DOI: 10.1162/neco.1990.2.3.261 http://doi.org/10.1162/neco.1990.2.3.261 . .

J.W Rivkin , , , N Siggelkow . . Patterned interactions in complex systems: implications for exploration . . Manag. Sci. , , 2007 . . 53 ( ( 7 ): ): 1068 - - 1085 . . DOI: 10.1287/mnsc.1060.0626 http://doi.org/10.1287/mnsc.1060.0626 . .

N Siggelkow , , , D.A Levinthal . . Temporarily divide to conquer: centralized, decentralized, and reintegrated organizational approaches to exploration and adaptation . . Organ. Sci. , , 2003 . . 14 ( ( 6 ): ): 650 - - 669 . . . .

N Siggelkow , , , J.W Rivkin . . Speed and search: designing organizations for turbulence and complexity . . Organ. Sci. , , 2005 . . 16 ( ( 2 ): ): 101 - - 122 . . DOI: 10.1287/orsc.1050.0116 http://doi.org/10.1287/orsc.1050.0116 . .

J.D Thompson . . Organizations in Action: Social Science Bases of Administrative Theory , , 1967 . . : : USA McGraw-Hill , , . .

F Wall . . The (beneficial) role of informational imperfections in enhancing organisational performance . . 2010 . . Progress in Artificial Economics . . 115 - - 126 . . DOI: 10.1007/978-3-642-13947-5_10 http://doi.org/10.1007/978-3-642-13947-5_10 . .

F Wall . . Comparing basic design options for management accounting systems with an agent-based simulation . . 2013 . . Proc. 10th Int. Conf. on Distributed Computing and Artificial Intelligence . . 409 - - 418 . . DOI: 10.1007/978-3-319-00551-5_50 http://doi.org/10.1007/978-3-319-00551-5_50 . .

F Wall . . Effects of organizational dynamics in adaptive distributed search processes . . 2015 . . Proc. 12th Int. Conf. on Distributed Computing and Artificial Intelligence . . 121 - - 128 . . DOI: 10.1007/978-3-319-19638-1_14 http://doi.org/10.1007/978-3-319-19638-1_14 . .

F Wall . . Agent-based modeling in managerial science: an illustrative survey and study . . Rev. Manag. Sci. , , 2016a . . 10 ( ( 1 ): ): 135 - - 193 . . DOI: 10.1007/s11846-014-0139-3 http://doi.org/10.1007/s11846-014-0139-3 . .

F Wall . . Beneficial effects of randomized organizational change on performance . . Adv. Complex Syst. , , 2016b . . 18 ( ( 5-6 ): ): 1550019 DOI: 10.1142/S0219525915500198 http://doi.org/10.1142/S0219525915500198 . .

B.L Welch . . The significance of the difference between two means when the population variances are unequal . . Biometrika , , 1938 . . 29 ( ( 3/4 ): ): 350 - - 362 . . . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

An efficient and coordinated mapping algorithm in virtualized SDN networks