Description and composition of bio-inspired design patterns: a complete overview <s> Morphogenesis pattern <s> The Generalized Assignment Problem consists in assigning a set of tasks to a set of agents with minimum cost. Each agent has a limited amount of a single resource and each task must be assigned to one and only one agent, requiring a certain amount of the resource of the agent. We present new metaheuristics for the generalized assignment problem based on hybrid approaches. One metaheuristic is a MAX-MIN Ant System (MMAS), an improved version of the Ant System, which was recently proposed by Stutzle and Hoos to combinatorial optimization problems, and it can be seen has an adaptive sampling algorithm that takes in consideration the experience gathered in earlier iterations of the algorithm. Moreover, the latter heuristic is combined with local search and tabu search heuristics to improve the search. A greedy randomized adaptive search heuristic (GRASP) is also proposed. Several neighborhoods are studied, including one based on ejection chains that produces good moves without increasing the computational effort. We present computational results of the comparative performance, followed by concluding remarks and ideas on future research in generalized assignment related problems. <s> BIB001 </s> Description and composition of bio-inspired design patterns: a complete overview <s> Morphogenesis pattern <s> In this paper we review the exact algorithms based on the branch and bound approach proposed in the last years for the solution of the basic version of the vehicle routing problem (VRP), where only the vehicle capacity constraints are considered. These algorithms have considerably increased the size of VRPs that can be solved with respect to earlier approaches. Moreover, at least for the case in which the cost matrix is asymmetric, branch and bound algorithms still represent the state-of-the-art with respect to the exact solution. Computational results comparing the performance of different relaxations and algorithms on a set of benchmark instances are presented. We conclude by examining possible future directions of research in this field. <s> BIB002
The goal of the Morphogenesis Pattern is to select different agent's behaviour depending on the agent's position in the system. The Morphogenesis Pattern exploits the Gradient Pattern: relative spatial position information is assessed through one or multiple gradient sources generated by other agents. Morphogenesis was proposed as a selforganising mechanism in BIB001 BIB002 . The morphogenesis process in biology has been considered as an inspiration source for gradient fields. Alias: none to our knowledge. Problem: in large-scale decentralised systems, agents decide on their roles or plan their activities based on their spatial position. Solution: specific agents spread morphogenetic gradients. Agents assess their positions in the system by computing their relative distance to the morphogenetic gradients sources. Inspiration: in the biological morphogenetic process some cells create and modify molecules (through aggregation) which diffuse (through spreading), creating gradients of molecules. The spatial organisation of such gradients is the morphogenesis gradient, which is used by the cells to differentiate the role that they play inside the body, e.g. in order to produce cell differentiations. Forces: the forces presented in this pattern are the same as the ones of the Gradient Pattern (Sect. 5.2.1). Entities-Dynamic-Environment: the entities involved in the morphogenesis process are Agents, Hosts, and Infrastructural Agents. At the beginning, some of the agents spread one or more morphogenesis gradients, implemented using the Gradient Pattern. Other agents sense the morphogenetic gradient in order to calculate their relative positions. Depending on their relative positions, the agents adopt different roles and coordinate their activities in order to achieve collaborative goals. Given Transition Rule (7) that creates the gradient, Transition Rule (12) models an agent sensing its local gradient values and adapting its behaviour depending on its relative position with respect to the gradient source. ) the motion coordination of a swarm of robots is implemented by using both Morphogenesis and Chemotaxis Patterns (Sect. 5.3.2). Diagram 16a, b show agents estimating their position in response to gradient information propagated by neighbouring hosts. Known uses: the Morphogenesis Pattern is used to implement control techniques for modular self-reconfigurable robots (meta-morphic robots)  . Morphogenesis is also employed to create a robust process for shape formation on a sheet of identically programmed agents (origami) (Nagpa 2002) . Consequences: the Morphogenesis Pattern equips the agents with a mechanism to coordinate their activities based on their relative positions. Like the other mechanisms previously presented, robustness and scalability are properties ensured by this pattern. Related Patterns: the Morphogenesis Pattern extends the Gradient Pattern (Sect. 5.2.1). The Morphogenesis Pattern can be combined with the Digital Pheromone Pattern where the role and behaviour of the agents depend on the distances to the pheromone sources.