Introducing look-ahead into relocation rules generated with genetic programming for the container relocation problem - Genetic Programming and Evolvable Machines

The container relocation problem is a critical combinatorial optimisation problem in warehouses and container ports. The goal is to retrieve all containers while minimising unnecessary relocations. As this problem is NP-hard, various heuristics have been proposed, including relocation rules (RRs), simple constructive heuristics that iteratively build solutions by determining how containers should be relocated within the yard for efficient retrieval. However, manually designing effective RRs is challenging, leading to the use of genetic programming to generate them automatically. A key limitation of both manually and automatically designed RRs is their restricted problem view and limited decision-making scope. This often results in suboptimal relocations, negatively impacting future operations and overall efficiency. A crucial aspect of RR design is defining effective relocation schemes that enhance decision-making by considering the long-term impact of relocations. This study investigates several relocation schemes that provide RRs with lookahead capabilities, enabling them to anticipate future consequences and make more informed moves. In addition to two standard schemes, four novel relocation schemes are introduced and evaluated using an established problem set. The results demonstrate that properly adapting relocation schemes can significantly enhance the performance of automatically designed RRs, leading to significantly better results.

Quality-diversity in problems with composite solutions: a case study on body–brain robot optimization - Genetic Programming and Evolvable Machines

When considering those optimization problems where the solution is a combination of two parts, as, e.g., the concurrent optimization of the body and the brain of a robotic agent, one might want to solve them “in a quality-diversity (QD) way”, i.e., obtaining not just one very good solution, but a set of good and diverse solutions. We call them QD composite problems, and we propose a general formulation for them, as well as a set of indexes useful for comprehensively assessing solutions by measuring both quality and diversity. We experimentally compare a few QD evolutionary algorithms (EAs) on a case study of body–brain optimization of simulated robots, including several variants of MAP-elites (ME), a popular and effective EA for QD. We also propose a novel ME variant, called coevolutionary MAP-elites (CoME), that internally employs two populations, one for each part of the solution, and enforces diversity on them through user-provided descriptors, as the underlying ME does. CoME, instead of blindly combining all the respective parts to obtain full solutions, adopts a specific mapping strategy that is based on the location of each solution part in the respective descriptors space. The results of our comparative analysis show that ME works well in QD composite problems, but only if two archives, instead of just one, are employed, one for each part of the solution. Moreover, we show that the use of multi-archive variants of ME, e.g., CoME, can provide insights on the interplay between the two parts of the solution for the problem at hand, shedding light on key dynamics in co-evolution.

A comparison of representations in grammar-guided genetic programming in the context of glucose prediction in people with diabetes - Genetic Programming and Evolvable Machines

The representation of individuals in Genetic Programming (GP) has a large impact on the evolutionary process. In previous work, we investigated the evolutionary process of three Grammar-Guided GP (GGGP) methods, Context-Free Grammars GP (CFG-GP), Grammatical Evolution (GE) and Structured Grammatical Evolution (SGE), in the context of the complex, real-world problem of predicting the glucose level of people with diabetes two hours ahead of time. We concluded that representation choice is more impactful with a higher maximum depth, and that CFG-GP better explores the search space for deeper trees, achieving better results. Furthermore, we find that CFG-GP relies more on feature construction, whereas GE and SGE rely more on feature selection. Additionally, we altered the GGGP methods in two ways: using $$\epsilon$$ ϵ -lexicase selection, which solved the overfitting problem of CFG-GP and helps it to adapt to patients with high glucose variability; and with a penalization of complex trees, to create more interpretable trees. Combining $$\epsilon$$ ϵ -lexicase selection with CFG-GP performed best. In this work, we extend on the previous work and evaluated the impact of initialization methods in the quality of solutions. We found that they have no significant impact, even when the change of representation has.

Julian Togelius: Artificial General Intelligence, The MIT Press Essential Knowledge series, 2024, paperback, 230 pages, ISBN:9780262549349 - Genetic Programming and Evolvable Machines