A Pyramidal Evolutionary Algorithm with Different Inter-Agent Partnering Strategies for Scheduling Problems

Uwe AickelinSsrn 2001 · DOI · OpenReview

TL;DR

This paper introduces a hierarchical "pyramidal" genetic algorithm for complex scheduling problems, where different sub-populations optimize parts of the solution. The key innovation is exploring how different strategies for selecting partners between these sub-populations impact the final solution quality, finding that problem-specific knowledge in partner selection significantly improves results.

What Problem Does This Paper Address?

Many real-world scheduling problems, like nurse rostering and mall tenant selection, are notoriously difficult to solve. Traditional genetic algorithms struggle with these problems due to "epistasis" – where the interaction between different parts of a solution (e.g., a nurse's shift and a specific day) makes it hard to evaluate individual components in isolation. This paper tackles the challenge of improving genetic algorithm performance on such problems by using a hierarchical, distributed approach and, crucially, by investigating how agents (sub-populations) should intelligently choose partners from other sub-populations to collaborate effectively.

Methods

The core method is a Pyramidal Genetic Algorithm (PGA). This is a hierarchical structure where sub-populations are organized in a pyramid. Lower-level sub-populations focus on optimizing smaller, more constrained parts of the problem (e.g., specific nurse grades or mall areas), while higher-level sub-populations combine these partial solutions to optimize larger chunks or the entire problem.

The novelty lies in the inter-agent partnering strategies. Instead of random mating or simple selection within a single population, this paper examines seven strategies for how agents in one sub-population choose partners from another:

  • Rank-Selection (S): Standard selection based on sub-fitness.
  • Random (R): Partners chosen randomly.
  • Best (B): Partners are the best agents from other sub-populations.
  • Distributed (D): Agents are paired with similar agents in other sub-populations based on a grid layout.
  • Joined (J): A traditional parallel genetic algorithm where all sub-populations solve the full problem.
  • Attractiveness (A): Partnering is probabilistic, favoring pairs whose combined fitness is high.
  • Partner Choice (C): The first parent is chosen by rank, but the second parent is selected from a random pool to create the fittest child with the first parent.

Strategies A and C are highlighted for their use of problem-specific knowledge.

Datasets

The paper evaluates its approach on two benchmark scheduling problems:

  • Nurse Scheduling Problem: Creating weekly schedules for up to 30 nurses, satisfying contracts, demand for different grades, and nurse preferences. The paper uses 52 data sets with an average of 30 nurses and up to 411 shift-patterns per nurse.
  • Mall Tenant Selection Problem: Deciding which types of shops to place in a mall and where, to maximize rental revenue. The paper uses 50 artificially constructed problem instances, each with 100 locations grouped into five areas, varying in shop types and constraint tightness.

Key Insights and Ideas

  • Hierarchical structure helps with epistasis: By breaking down complex problems into smaller, more manageable sub-problems, the PGA reduces the impact of epistasis, making optimization easier.
  • Partnering strategy is crucial: The way sub-populations collaborate is as important as the hierarchical structure itself. Simple strategies like random or best-agent pairing are often outperformed by more sophisticated methods.
  • Problem-specific knowledge pays off: Strategies that leverage knowledge about the problem (like "Attractiveness" and "Partner Choice") significantly improve solution quality, especially when sub-fitness measures are less predictive.
  • Sub-fitness measure matters: The effectiveness of partnering strategies is highly dependent on how well the "sub-fitness" (fitness of a partial solution) predicts the quality of the final, complete solution. This was more reliable for the nurse scheduling problem than the mall problem.
  • "Post-birth" selection can overcome sub-fitness limitations: For the mall problem, where sub-fitness was less reliable, strategies that evaluated potential children after recombination (like Partner Choice) performed well because they used the full fitness score.

Key Results

  • Nurse Scheduling: The PGA with rank-based selection (S) improved upon a standard GA but still lagged behind Tabu Search. However, strategies A and C significantly outperformed S, with C generally being the best among the tested partnering strategies.
  • Mall Problem: The standard GA performed reasonably well. The PGA with rank-based selection (S) surprisingly deteriorated results, likely due to unreliable sub-fitness measures. Here, the random strategy (R) performed better than expected, and strategies A and C again showed the best performance, particularly because they evaluated full solutions after recombination.
  • Overall: While no partnering strategy outperformed the highly specialized Tabu Search, the advanced strategies (A and C) consistently improved solution quality and mitigated shortcomings of the sub-fitness measures.

Limitations and Future Work

  • No Tabu Search/Bound Beating: The paper acknowledges that even the best strategies did not outperform specialized Tabu Search algorithms or theoretical bounds. This is attributed to the highly problem-specific nature of those algorithms.
  • Sub-fitness reliability: The paper highlights that the predictive power of sub-fitness measures varies between problems, impacting the effectiveness of certain partnering strategies.
  • Future Work: The authors suggest exploring fitness sharing mechanisms to further improve partnering strategies and investigating more gradual build-ups of sub-populations for a smoother optimization process. They also note that incorporating more specific hill-climbing components could potentially bridge the gap to state-of-the-art methods.

Summary updated

Abstract

This paper combines the idea of a hierarchical distributed genetic algorithm with different inter-agent partnering strategies. Cascading clusters of sub-populations are built from bottom up, with higher-level sub-populations optimising larger parts of the problem. Hence higher-level sub-populations search a larger search space with a lower resolution whilst lower-level sub-populations search a smaller search space with a higher resolution. The effects of different partner selection schemes amongst the agents on solution quality are examined for two multiple-choice optimisation problems. It is shown that partnering strategies that exploit problem-specific knowledge are superior and can counter inappropriate (sub-) fitness measurements.
BibTeX
@misc{aickelin2001pyramidal,
  author = {Uwe Aickelin},
  title = {{A Pyramidal Evolutionary Algorithm with Different Inter-Agent Partnering Strategies for Scheduling Problems}},
  year = {2001},
  eprint = {0801.3209},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0801.3209},
  howpublished = {Ssrn},
}
Figure