摘要
群智能是指众多行为简单的个体在相互作用过程中涌现产生的整体智能行为,劳动分工是其最重要特征之一.本文首先根据个体与个体、个体与环境的交互模式,给出群智能劳动分工的一个框架描述,分析其个体专职化、角色可塑性和自组织等特性.然后从自组织的角度对激发—抑制、刺激—响应、个体排序和寻觅工作等四类劳动分工模型进行对比分析,旨在归纳提炼群智能自组织劳动分工模型的构建规律.进而结合群智能自组织劳动分工的应用情况,针对其适用范围和求解思路进行了评述和讨论.最后从劳动分工机制、劳动分工模型、分配问题求解和优化问题求解四个方面展望了群智能自组织劳动分工的发展前景.
Swarm intelligence refers to a collective intelligent behavior that emerged from the interactions of individuals obeying simple behavioral rules,and labor division is one of its most profound features.According to the individual-individual interactions and individual-environment interactions,we present a framework description of labor division in swarm intelligence and analyzes its characteristics of individual specialization,role plasticity,and self-organization.From the perspective of self-organization,four kinds of labor division models,namely,activator-inhibitor,stimulus-response,individual sorting,and foraging for work,are compared and analyzed in detail,with the aim of concluding the general modeling regularities for self-organized labor division.As well as the applications of self-organized labor division,its application range,and solving methods are further analyzed.Finally,some perspectives on the development of self-organized labor division in swarm intelligence are drawn from the mechanisms and models of labor division,as well as the solving methods for allocation problems and optimization problems.Keywords
引文
[1] Bonabeau E,Dorigo M,Theraulaz G.Swarm intelligence:From natural to artificial systems[M].New York:Oxford University Press,1999.
[2] Kennedy J,Eberhart R C,Shi Y H.Swarm intelligence[M].San Francisco:Morgan Kaufmann Publishers,2001.
[3] 肖人彬.面向复杂系统的群集智能[M].北京:科学出版社,2013.Xiao R B.Swarm intelligence for complex systems[M].Beijng:Science Press,2013.
[4] 张燕,康琦,汪镭,等.群体智能[J].冶金自动化,2005,2:1-4.Zhang Y,Kang Q,Wang L,et al.Swarm intelligence[J].Metallurgical Industry Automation,2005,2:1-4.
[5] 肖人彬,陶振武.群集智能研究进展[J].管理科学学报,2007,10(3):80-96.Xiao R B,Tao Z W.Research process of swarm intelligence[J].Journal of Management Sciences in China,2007,10(3):80-96.
[6] Bonabeau E,Dorigo M,Theraulaz G.Inspiration for optimization from social insect behavior[J].Nature,2000,406(6791):39-42.
[7] Theraulaz G,Bonabeau E.Modelling the collective building of complex architectures in social insects with lattice swarms[J].Journal of Theoretical Biology,1995,177(4):381-400.
[8] Bonabeau E,Sobkowski A,Theraulaz G,et al.Adaptive task allocation inspired by a model of division of labor in social insects[J].Biocomputing and Emergent Computation,1997(8):36-45.
[9] Kube C R,Zhang H.Collective robotics:From social insects to robots[J].Adaptive behavior,1993,2(2):189-218.
[10] Wilson M,Melhuish C,Sendova-Franks A B,et al.Algorithms for building annular structures with minimalist robots inspired by brood sorting in ant colonies[J].Autonomous Robots,2004,17(2/3):115-136.
[11] Martin M,Chopard B,Albuquerque P.Formation of an ant cemetery:Swarm intelligence or statistical accident[J].Future Generation Computer Systems,2002,18(7):951-959.
[12] 彭喜元,彭宇,戴毓丰.群智能理论及应用[J].电子学报,2003,31(12A):1982-1988.Peng X Y,Peng Y,Dai Y F.Theory and applications of swarm intelligence[J].Acta Electronica Sinica,2003,31(12A):1982-1988.
[13] Dorigo M,Blum C.Ant colony optimization theory:A survey[J].Theoretical Computer Science,2005,344(2):243-278.
[14] Poli R,Kennedy J,Blackwell T.Particle swarm optimization[J].Swarm Intelligence,2007,1(1):33-57.
[15] Karaboga D,Akay B.A comparative study of artificial bee colony algorithm[J].Applied Mathematics and Computation,2009,214(1):108-132.
[16] 李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式——鱼群算法[J].系统工程理论与实践,2002,22(11):32-38.Li X L,Shao Z J,Qian J X.An optimizing method based on autonomous animals:Fish-swarm algorithm[J].System Engineering Theory and Practice,2002,22(11):32-38.
[17] 吴虎胜,张凤鸣,吴庐山.一种新的群体智能算法——狼群算法[J].系统工程与电子技术,2013,35(11):2430-2438.Wu H S,Zhang F M,Wu L S.New Swarm intelligence algorithm — wolf pack algorithm[J].Systems Engineering and Electronics,2013,35(11):2430-2438.
[18] 李荣雨,戴睿闻.改进型社会蜘蛛优化算法[J].信息与控制,2017,46(4):443-451.Li R Y,Dai R W.Modified social spider optimization algorithm[J].Information and Control,2017,46(4):443-451.
[19] 肖人彬.群集智能特性分析及其对复杂系统研究的意义[J].复杂系统与复杂性科学,2006,3(3):10-19.Xiao R B.Analysis of characteristics of swarm intelligence and its significance to the research of complex systems[J].Complex Systems and Complexity Science,2006,3(3):10-19.
[20] Naug D.From division of labor to collective behavior:behavioral analyses at different levels[J].Behavioral Ecology and Sociobiology,2016,70(7):1113-1115.
[21] Robinson G E.Regulation of labor division in insect societies[J].Annual Review of Entomology,1992,37(1):637-665.
[22] Xiao R B,Wang Y C.Labour division in swarm intelligence for allocation problems:A survey[J].International Journal of Bio-Inspired Computation,2018,12(2):71-86.
[23] 汤可宗,杨静宇.群智能优化方法及应用[M].北京:科学出版社,2015.Tang K Z,Yang J Y.Swarm intelligence optimization method and its application[M].Beijing:Science Press,2015.
[24] Waibel M,Floreano D,Magnenat S,et al.Division of labor and colony efficiency in social insects:Effects of interactions between genetic architecture,colony kin structure and rate of perturbations[J].Proceedings of the Royal Society of London B:Biological Sciences,2006,273(1595):1815-1823.
[25] Beshers S N,Fewell J H.Models of labor division in social insects[J].Annual Review of Entomology,2001,46(1):413-440.
[26] Duarte A,Weissing F J,Pen I,et al.An evolutionary perspective on self-organized labor division in social insects[J].Annual Review of Ecology,Evolution,and Systematics,2011,42:91-110.
[27] H?lldobler B,Wilson E O.The Superorganism:The beauty,elegance,and strangeness of insect societies[M].New York:W.W.Norton & Company,2009.
[28] Johnson B R.Division of labor in honeybees:form,function,and proximate mechanisms[J].Behavioral Ecology and Sociobiology,2010,64(3):305-316.
[29] Lattorff H M G,Moritz R F A.Genetic underpinnings of division of labor in the honeybee (Apis mellifera)[J].Trends in Genetics,2013,29(11):641-648.
[30] Pamminger T,Foitzik S,Kaufmann K C,et al.Worker personality and its association with spatially structured labor division[J].PLoS ONE,2014,9(1):e79616.
[31] Arcaute E,Christensen K,Sendova-Franks A,et al.Division of labour in ant colonies in terms of attractive fields[J].Ecological Complexity,2009,6:396-402.
[32] Franks N R,Tofts C.Foraging for work:How tasks allocate workers[J].Animal Behaviour,1994,48(2):470-472.
[33] Huang Z Y,Robinson G E.Honeybee colony integration:Worker-worker interactions mediate hormonally regulated plasticity in division of labor[J].Proceedings of the National Academy of Sciences of the United States of America,1992,89(24):11726-11729.
[34] Huang Z Y,Robinson G E.Regulation of honey bee labor division by colony age demography[J].Behavioral Ecology and Sociobiology,1996,39(3):147-158.
[35] Huang Z Y,Plettner E,Robinson G E.Effects of social environment and worker mandibular glands on endocrine-mediated behavioral development in honey bees[J].Journal of Comparative Physiology A,1998,183(2):143-152.
[36] Leoncini I,Le Conte Y,Costagliola G,et al.Regulation of behavioral maturation by a primer pheromone produced by adult worker honey bees[J].Proceedings of the National Academy of Sciences of the United States of America,2004,101(50):17559-17564.
[37] Bonabeau E,Theraulaz G,Deneubourg J L.Fixed response thresholds and the regulation of division of labor in insect societies[J].Bulletin of Mathematical Biology,1998,60(4):753-807.
[38] Tripet F,Nonacs P.Foraging for work and age-based polyethism:The roles of age and previous experience on task choice in ants[J].Ethology,2004,110(11):863-877.
[39] Robinson E J H,Feinerman O,Franks N R.Flexible task allocation and the organization of work in ants[J].Proceedings of the Royal Society of London B:Biological Sciences,2009,276:4373-4380.
[40] Ravary F,Lecoutey E,Kaminski G,et al.Individual experience alone can generate lasting division of labor in ants[J].Current Biology,2007,17(15):1308-1312.
[41] Ulrich Y,Saragosti J,Tokita C K,et al.Fitness benefits and emergent division of labour at the onset of group living[J].Nature,2018,560(7720):635-638.
[42] Jeanne R L.Division of labor is not a process or a misleading concept[J].Behavioral ecology and sociobiology,2016,70(7):1109-1112.
[43] Crall J D,Gravish N,Mountcastle A M,et al.Spatial fidelity of workers predicts collective response to disturbance in a social insect[J].Nature Communications,2018,9(1):1201-1-113.
[44] Zhu L,Chen J,Di Z,et al.The mechanisms of labor division from the perspective of individual optimization[J].Physica A:Statistical Mechanics and its Applications,2017,488:112-120.
[45] Gordon D M.From division of labor to the collective behavior of social insects[J].Behavioral Ecology and Sociobiology,2016,70(7):1101-1108.
[46] Frank E T,Linsenmair K E.Flexible task allocation and raid organization in the termite-hunting ant Megaponera analis[J].Insectes Sociaux,2017,64(4):579-589.
[47] Duarte A,Pen I,Keller L,et al.Evolution of self-organized division of labor in a response threshold model[J].Behavioral Ecology and Sociobiology,2012,66:947-957.
[48] Hilbun A,Karsai I.Task allocation of wasps governed by common stomach:A model based on electric circuits[J].PloS One,2016,11(11):e0167041-1-18.
[49] Page R E,Mitchell S D.Self-organization and the evolution of division of labor[J].Apidologie,1998,29:171-190.
[50] Bonabeau E,Theraulaz G,Deneubourg J L,et al.Self-organization in social insects[J].Trends in Ecology & Evolution,1997,12(5):188-193.
[51] Naug D,Gadagkar R.Flexible labor division mediated by social interactions in an insect colony-a simulation model[J].Journal of Theoretical Biology,1999,197(1):123-133.
[52] Gadagkar R.Division of labor and organization of work in the primitively eusocial wasp ropalidia marginata[J].Proceedings of the Indian National Science Academy-Part B:Biological Sciences,2001,67(6):397-422.
[53] Beshers S,Huang Z Y,Oono,Y,et al.Social inhibition and the regulation of temporal polyethism in honey bees[J].Journal of Theoretical Biology,2001,213(3):461-479.
[54] Zahadat P,Crailsheim K,Schmickl T,et al.Social inhibition manages division of labour in artificial swarm systems[C]//Proceedings of the 12th European Conference on Artificial Life (ECAL 2013).Cambridge,MA,USA:MIT Press,2013:609-616.
[55] Bonabeau E,Theraulaz G,Deneubourg J L.Quantitative study of the fixed threshold model for the regulation of division of labour in insect societies[J].Proceedings of the Royal Society of London.Series B:Biological Sciences,1996,263(1376):1565-1569.
[56] Theraulaz G,Bonabeau E,Denuebourg J N.Response threshold reinforcements and division of labour in insect societies[J].Proceedings of the Royal Society of London.Series B:Biological Sciences,1998,265(1393):327-332.
[57] Gautrais J,Theraulaz G,Deneubourg J L,et al.Emergent polyethism as a consequence of increased colony size in insect societies[J].Journal of Theoretical Biology,2002,215(3):363-373.
[58] Merkle D,Middendorf M.Dynamic polyethism and competition for tasks in threshold reinforcement models of social insects[J].Adaptive Behavior,2004,12(3/4):251-262.
[59] Richardson T O,Christensen K,Franks N R,et al.Ants in a labyrinth:A statistical mechanics approach to the division of labour[J].PLoS One,2011,6(4):e18416.
[60] Backen S J,Sendova-Franks A B,Franks N R.Testing the limits of social resilience in ant colonies[J].Behavior Ecology and Sociobiology,2000,48(2):125-131.
[61] Sendova-Franks A B,Franks N.Spatial relationships within nests of the ant Leptothorax unifasciatus (Latr.) and their applications for the division of labour[J].Animal Behaviour,1995,50(1):121-136.
[62] Sendova-Franks A B,Van Lent J.Random walk models of worker sorting in ant colonies[J].Journal of Theoretical Biology,2002,217(2):255-274.
[63] Tofts C.Algorithms for task allocation in ants.(A study of temporal polyethism:Theory)[J].Bulletin of Mathematical Biology,1993,55(5):891-918.
[64] Franks N R,Tofts C.Foraging for work:How tasks allocate workers[J].Animal Behaviour,1994,48(2):470-472.
[65] Zahadat P,Hahshold S,Thenius R,et al.From honeybees to robots and back:Division of labour based on partitioning social inhibition[J].Bioinspiration & Biomimetics,2015,10(6):066005.
[66] Zahadat P,Schmickl T.Division of labor in a swarm of autonomous underwater robots by improved partitioning social inhibition[J].Adaptive Behavior,2016,24(2):87-101.
[67] 肖人彬,王英聪.一种面向时间分配问题的群智能劳动分工新方法[J].智能系统学报,2019,14(3).Xiao R B,Wang Y C.A new approach to labor division in swarm intelligence for time allocation problem[J].CAAI Transactions on Intelligent Systems,2019,14(3).
[68] 胡亮,肖人彬,李浩.一种蜂群双抑制劳动分工算法及其在交通信号配时中的应用[J].计算机应用,2019.Hu L,Xiao R B,Li H.Bee colony double inhibition labor division algorithm and its application in traffic signal timing[J].Journal of Computer Applications,2019.
[69] 肖人彬,陶振武.面向虚拟企业的蚁群劳动分工建模与仿真[J].管理科学学报,2009,12(1):57-69.Xiao R B,Tao Z W.Modeling and simulation of ant colony′s labor division for virtual enterprises[J].Journal of Management Sciences in China,2009,12(1):57-69.
[70] 肖人彬,易文明,陶振武,等.面向拉式生产系统的蚁群劳动分工建模及仿真[J].计算机集成制造系统,2010,16(9):1866-1874.Xiao R B,Yi W M,Tao Z W,et al.Modeling and simulation of ant colony′s labor division for pull production systems[J].Computer Integrated Manufacturing Systems,2010,16(9):1866-1874.
[71] Xiao R B,Yu T Y,Gong X G.Modeling and simulation of ant colony′s labor division with constraints for task allocation of resilient supply chains[J].International Journal on Artificial Intelligence Tools,2012,21(3):1240014.
[72] Xiao R B,Chen W M,Chen T G.Modeling of ant colony′s labor division for the multi-project scheduling problem and its solution by PSO[J].Journal of Computational and Theoretical Nanoscience,2012,9(2):223-232.
[73] 肖人彬,王英聪.面向群体利益分配的蚁群劳动分工建模与仿真[J].管理科学学报,2016,19(10):1-15.Xiao R B,Wang Y C.Modeling and simulation of ant colony′s labor division for interests allocation of social groups[J].Journal of Management Sciences in China,2016,19(10):1-15.
[74] Wang Y C,Xiao R B,Wang H M.A flexible labour division approach to the polygon packing problem based on space allocation[J].International Journal of Production Research,2017,55(11):3025-3045.
[75] 王英聪,肖人彬.基于蚁群劳动分工的空间分配方法求解带平衡约束的圆形装填问题[J].计算机集成制造系统,2019,25(2):359-372.Wang Y C,Xiao R B.Space allocation method based on ant colony′s labor division for the circular packing problem with equilibrium constraints[J].Computer Integrated Manufacturing Systems,2019,25(2):359-372.
[76] Low K H,Leow W K,Jr Ang M H.Autonomic mobile sensor network with self-coordinated task allocation and execution[J].IEEE Transactions on Systems,Man,and Cybernetics,Part C:Applications and Reviews,2006,36(3):315-327.
[77] Yang Y,Qiu X,Meng L,et al.Task coalition formation and self-adjustment in the wireless sensor networks[J].International Journal of Communication Systems,2014,27(10):2241-2254.
[78] 王艳,纪志成.生物启发的无线传感执行网络协同方法[J].控制理论与应用,2014,31(2):188-194.Wang Y,Ji Z C.Bio-inspired collaborative method for wireless sensor and actor network[J].Control Theory & Applications,2014,31(2):188-194.
[79] Kim M H,Baik H,Lee S.Response threshold model based UAV search planning and task allocation[J].Journal of Intelligent & Robotic Systems,2014,75(3/4):625-640.
[80] Wu H S,Li H,Xiao R B,et al.Modeling and simulation of dynamic ant colony′s labor division for task allocation of UAV swarm[J].Physica A,2018,491:127-141.
[81] dos Santos F,Bazzan A L C.Towards efficient multiagent task allocation in the RoboCup Rescue:A biologically-inspired approach[J].Autonomous Agents and Multi-Agent Systems,2011,22(3):465-486.
[82] Jr Ferreira P R,dos Santos F,Bazzan A L C,et al.RoboCup Rescue as multiagent task allocation among teams:Experiments with task interdependencies[J].Autonomous Agents and Multi-Agent Systems,2010,20(3):421-443.
[83] 阎静,曾建潮,张国有.基于劳动分工的群机器人地图创建探索策略研究[J].计算机应用,2013,30(1):94-98.Yan J,Zeng J,Zhang G.Research on exploration strategy in map building of swarm roboics based on model of labor division[J].Application Research of Computers,2013,30(1):94-98.
[84] 张国有,曾建潮.基于黄蜂群算法的群机器人全区域覆盖算法[J].模式识别与人工智能,2011,24(3):431-437.Zhang G,Zeng J.Area coverage algorithm in swarm robotics based on wasp swarm algorithm[J].Pattern Recognition and Artificial Intelligence,2011,24(3):431-437.
[85] Krieger M J B,Billeter J B.The call of duty:Self-organised task allocation in a population of up to twelve mobile robots[J].Robotics and Autonomous Systems,2000,30(1):65-84.
[86] Castello E,Yamamoto T,Nakamura Y,et al.Foraging optimization in swarm robotic systems based on an adaptive response threshold model[J].Advanced Robotics,2014,28(20):1343-1356.
[87] Sendova-Franks A B,Franks N.Social resilience in individual worker ants and its role in division of labour[J].Proceedings of the Royal Society of London.Series B:Biological Sciences,1994,256(1347):305-309.
[88] Teng H,Wang Y,Zhang B.Emergency design framework:Satellite preliminary scheme design[J].Frontiers of Mechanical Engineering in China,2007,2(2):184-192.
[89] Wang Y,Liu J,Teng H.Social ant colony-inspired modelling approach for rapid response design[J].International Journal of Computer Applications in Technology,2013,46(4):361-368.
[90] Wang Y C,Xiao R B.Research on social resilient control structure based on SFZ[J].International Journal of Computing Science and Mathematics,2015,6(4):323-335.
[91] Wang Y C,Xiao R B.An ant colony based resilience approach to cascading failures in cluster supply network[J].Physica A,2016,462:150-166.
[92] 贺政纲,黄娟,帅宇红.基于蚁群劳动分工的多式联运利益分配研究[J].铁道学报,2018,40(11):19-26.He Z G,Huang J,Shuai Y H.Research on benefit allocation of multimodal transport based on ant colony′s labor division[J].Journal of the China Railway Society,2018,40(11):19-26.
[93] 张超群,郑建国,王翔.蜂群算法研究综述[J].计算机应用研究,2011,28(9):3201-3205.Zhang C Q,Zheng J G,Wang X.Overview of research on bee colony algorithms[J].Application Research of Computers,2011,28(9):3201-3205.
[94] Akbari R,Mohammadi A,Ziarati K.A novel bee swarm optimization algorithm for numerical function optimization[J].Communications in Nonlinear Science and Numerical Simulation,2010,15(10):3142-3155.