Several engineering optimization problems like routing, freight transportation, exploration, or layout design in their more complex and realistic versions present a series of characteristics that make them very difficult to solve. Among these we find the absence of centralized updated information about all the variables, due to the spread out nature of the problems or lack of appropriate communications, or the dynamism of real-time operation. In fact, most optimization approaches assume that the problems they address are static, meaning that there is an optimal solution that does not change in time, but this is not always the case and there are problems that require following an optimum that changes in time. Distributed population-based techniques, such as swarms, have provided promising results in this context. They obtain a solution through the concurrent behavior of several adequately constructed processing elements. However, constructing these swarms is not straightforward, and most approaches have just mimicked swarm behaviors found in nature, adapting them to particular problems. The objective of this work is to study the application of a novel evolutionary paradigm, distributed Embodied Evolution (dEE), to obtain heterogeneous swarms that solve a set of realistic problems. In particular, we address here non-separable dynamic fitness landscapes, where interdependences between individuals imply that the contribution provided by one of them to the whole depends on the behavior of the others. This study is carried out applying a canonical version of dEE, which has been developed to generalize the main features of this type of evolutionary paradigm. We analyze the canonical dEE response in a series of scenarios of increasing complexity related to two highly representative dynamic engineering problems: a Dynamic Fleet Size and Mix Vehicle Routing Problem with Time Windows (DFSMVRPTW) and a collective surveillance task with realistic location degradation.
AhmadkhanlouF. and AdeliH., Optimum cost design of reinforced concrete slabs using neural dynamics model, Engineering Applications of Artificial Intelligence18(1) (2005), 65-72.
2.
AgoginoA. and TumerK., Efficient evaluation functions for evolving coordination, Evolutionary Computation16(2) (2008), 257-288.
3.
BelfioreP. and YoshizakiH., Heuristic methods for the fleet size and mix vehicle routing problem with time windows and split deliveries, Computers and Industrial Engineering, 64(2) (Feb 2013), 589-601.
4.
BonabeauE., DorigoM. and TheraulazG., Swarm Intelligence: From Natural to Artificial Systems, New York, NY: Oxford University Press, 1999.
5.
BoulkaibetI., MthembuL., De Lima NetoF. and MarwalaT., Finite element model updating using fish school search and volitive particle swarm optimization, Integrated Computer-Aided Engineering22(4) (2015), 361-376
6.
BredecheN. and MontanierJ.M., Environment-driven embodied evolution in a population of autonomous agents, Proceedings PPSN 2010, Part II, LNCS 6239, Springer, 2010, 290-299.
7.
BredecheN., MontanierJ.M., LiuW. and WinfieldA., Environment-driven distributed evolutionary adaptation in a population of autonomous robotic agents, Mathematical and Computational Modelling of Dynamical Systems18(1) (2012), 101-129.
8.
BräysyO., PorkkaP., DullaertW., RepoussisP. and TarantilisC., A well-scalable metaheuristic for the fleet size and mix vehicle routing problem with time windows, Expert Systems with Applications36(4) (2009), 8460-8475.
9.
CaamañoP., BellasF., BecerraJ.A. and DuroR.J., Evolutionary algorithm characterization in real parameter optimization problems, Applied Soft Computing13(4) (2013), 1902-1921.
10.
ChatterjeeA., RakshitA. and SinghN., Vision based autonomous robot navigation: Algorithms and implementations, Studies in Computational Intelligence, Springer455 (2013).
11.
ChowJ.Y.J., Activity-based travel scenario analysis with routing problem reoptimization, Computer-Aided Civil and Infrastructure Engineering29(2) (2014), 91-106.
12.
De CastroL.N. and Von ZubenF.J., Artificial immune systems, Part I. Basic Theory And Applications, Technical Report No. Rt Dca 01/99, Feec/Unicamp, Brazil, 1999.
13.
DorigoM., ManiezzoV. and ColorniA., Ant system: Optimization by a colony of cooperating agents, Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on26(1) (1996), 29-41.
14.
DuroR.J., BellasF., PrietoA. and Paz-LópezA., Social learning for collaboration through ASiCo based neuroevolution, J of Intelligent and Fuzzy Systems22 (2011), 125-139.
15.
EibenA.E., HaasdijkE. and BredecheN., Embodied, on-line, on-board evolution for autonomous robotics, Symbiotic Multi-Robot Organisms: Reliability, Adaptability, Evolution, Springer, (2010), 361-382.
16.
ElfwingS., UchibeE., DoyaK. and ChristensenH., Darwinian embodied evolution of the learning ability for survival, Adaptive Behavior19(2) (2011), 101-120.
17.
ForcaelE., GonzálezV., OrozcoF., VargasS., MoscosoP. and PantojaA., Ant colony optimization model for tsunamis evacuation routes, Computer-Aided Civil and Infrastructure Engineering29(10) (2014), 723-737.
18.
FrankeH. and DangelmaierW., Decentralized management for transportation-logistics: A multi agent based approach, Integrated Computer-Aided Engineering10(2) (2003), 203-210.
19.
GomesJ., MarianoP. and ChristensenA.L., Cooperative coevolution of partially heterogeneous multiagent systems, in: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (AAMAS '15) (2015), 297-305.
20.
GomezF. and MiikkulainenR., Incremental evolution of complex general behavior, Adaptive Behavior5 (1997), 317-342.
21.
FiciciS., WatsonR. and PollackJ., Embodied evolution: A response to challenges in evolutionary robotics, Eighth European Workshop on Learning Robots (1999), 14-22.
22.
HaasdijkE., EibenA.E. and KarafotiasG., On-line evolution of robot controllers by an encapsulated evolution strategy, Proceedings IEEE CEC2010 (2010), 1-7.
23.
HaasdijkE., Atta-ul-QayyumA. and EibenA.E., Racing to improve on-line, on-board evolutionary robotics, in: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation (GECCO '11) (2011), 187-194.
24.
HaasdijkE., BredecheN. and EibenA.E., Combining environment-driven adaptation and task-driven optimisation in evolutionary robotics, PLoS ONE, VasilakiE., ed., 9(6) (2014), pp. e98466. doi: 10.1371/journal.pone0098466.
25.
HedayatzadehR., SalmassiF.A., KeshtgariM., AkbariR. and ZiaratiK., Termite colony optimization: A novel approach for optimizing continuous problems, in: Electrical Engineering (ICEE), 2010 18th Iranian Conference on (2010), 553-558.
26.
IqbalS., KaykobadM. and RahmanM.S., Solving the multi-objective vehicle routing problem with soft time windows with the help of bees, Swarm and Evolutionary Computation, Available online 23 Jun 2015.
27.
IslamA., IqbalU., LangloisJ.M. and NoureldinA., Implementation methodology of embedded land vehicle positioning using an integrated GPS and multi sensor system, Integrated Computer-Aided Engineering17(1) (2010), 69-83.
28.
JeanneR.L., The evolution of the organization of work in social insects, Monit Zool Ital20 (1986), 267-287.
29.
JiaL., WangY. and FanL., Multiobjective bilevel optimization for production-distribution planning problems using hybrid genetic algorithm, Integrated Computer-Aided Engineering21(1) (2014), 77-90.
30.
KallelL., NaudtsB. and ReevesC.R., Properties of fitness functions and search landscapes, in: Theoretical Aspects of Evolutionary Computing, Springer Berlin Heidelberg, (2001), 175-206.
31.
KarabogaD., An idea based on honey bee swarm for numerical optimization, Technical Report-tr06, Erciyes University, Engineering Faculty, Computer Engineering Department, Vol. 200, 2005.
32.
KarabogaD. and BasturkB., A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (ABC) algorithm, Journal of Global Optimization39(3) (2007), 459-471.
33.
KimH. and AdeliH., Discrete cost optimization of composite floors using a floating point genetic algorithm, Engineering Optimization33(4) (2001), 485-501.
34.
KoçÇ., BektaşT., JabaliO. and LaporteG., A hybrid evolutionary algorithm for heterogeneous fleet vehicle routing problems with time windows, Computers and Operations Research64 (2015), 11-27.
35.
LippielloV., LoiannoG. and SicilianoB., MAV indoor navigation based on a closed-form solution for absolute scale velocity estimation using optical Flow and inertial data, Proceedings CDC-ECC, 2011, 3566-3571.
36.
MalanK.M. and EngelbrechtA.P., A survey of techniques for characterising fitness landscapes and some possible ways forward, Information Sciences241 (2013), 148-163.
37.
NguyenN.T., Transactions on computational collective intelligence series, Springer, 2015,
38.
NitschkeG.S., SchutM.C. and EibenA.E., Evolving behavioral specialization in robot teams to solve a collective construction task, Swarm and Evolutionary Computation2 (Feb 2012), 25-38.
39.
OlsonE., AprilTag: A robust and flexible visual fiducial system, Proc IEEE Intl Conf on Robotics and Automation (ICRA), 2011, 3400-3407.
40.
OmidvarM.N., LiX., MeiY. and YaoX., Cooperative co-evolution with differential grouping for large scale optimization, IEEE Transactions on Evolutionary Computation18(3) (2014), 378-393.
41.
OsterG. and WilsonE.O., Castes and Ecology in the Social Insects, Princeton, NJ: Princeton University Press, 1978.
PrietoA., BellasF. and DuroR.J., Adaptively coordinating heterogeneous robot teams through asynchronous situated coevolution, LNCS5864 (2009), 75-82.
44.
PrietoA., BecerraJ.A., BellasF. and DuroR.J., Open-ended evolution as a means to self-organize heterogeneous multi-robot systems in real time, Robotics and Autonomous Systems58 (2010), 1282-1291.
45.
PrietoA., BellasF., TruebaP. and DuroR.J., Towards the standardization of distributed embodied evolution, Information Sciences, Elsevier312 (2015), 55-77.
46.
RodríguezA. and ReggiaJ.A., Collective-movement teams for cooperative problem solving, Integrated Computer-Aided Engineering12(3) (2005), 217-235.
47.
SchutM.C., HaasdijkE. and GarcíaA.P., Is situated evolution an alternative for classical evolution? Proceedings of the Eleventh Conference on Congress on Evolutionary Computation, 2009, 2971-2976.
48.
ShenS., MichaelN. and KumarV., Autonomous multi-floor indoor navigation with a computationally constrained MAV, Proceedings ICRA (2011), 20-25.
49.
ShabbirF. and OmenzetterP., Particle swarm optimization with sequential niche technique for dynamic finite element model updating, Computer-Aided Civil and Infrastructure Engineering30(5) (2015), 359-375.
50.
SilvaF., UrbanoP., CorreiaL. and ChristensenA.L., odNEAT: An algorithm for decentralised online evolution of robotic controllers, Evol. Computation, in press, 2015.
51.
StopfordM., Is the drive for ever bigger containerships irresistible? Lloyds List Shipping Forecasting Conf2002.
52.
TereshkoV., Reaction-diffusion model of a honeybee colony's foraging behaviour, Parallel Problem Solving From Nature VI, Lecture Notes in Computer Science,SchoenauerM.} et al., eds, Springer-Verlag: Berlin, 1917 (2000), 807-816.
53.
TothP. and VigoD., The vehicle routing problem, Monographs on Discrete Mathematics and Applications, SIAM, 2002.
54.
TruebaP., PrietoA., BellasF., CaamañoP. and DuroR.J., Specialization analysis of embodied evolution for robotic collective tasks, Robotics and Autonomous Systems61(7) (2013), 682-693.
55.
VillaverdeI., GrañaM. and d'AnjouA., Morphological neural networks and vision based simultaneous localization and mapping, Integrated Computer-Aided Engineering14(4) (2007), 355-363.
56.
WatsonR., FiciciS. and PollackJ., Embodied evolution: Distributing an evolutionary algorithm in a population of robots, Robotics and Autonomous Systems39(1) (2002), 1-18.
57.
WiegandR.P., An analysis of cooperative coevolutionary algorithms, PhD Thesis, George Mason University, 2003.
58.
WischmannA., StammK. and WörgötterF., Embodied evolution and learning: The neglected timing of maturation, in: Advances in Artificial Life: 9th European Conference on ArtificialLife, LNCS 4648, 2007, 284-293.
59.
YangZ., TangK. and YaoX., Large scale evolutionary optimization using cooperative coevolution, Information Sciences17815 (2008), 2985-2999.
60.
YongC.H. and MiikkulainenR., Coevolution of role-based cooperation in multiagent systems, IEEE Transactions on Autonomous Mental Development1(3) (2009), 170-186.
