TL;DR
This paper explores how different "partnering strategies" for evaluating solutions in a hierarchical evolutionary algorithm can significantly improve performance on complex scheduling and allocation problems. They found that random and diverse pairing of sub-solutions leads to better overall results than strategies that rely solely on the "best" performing sub-solutions.
What Problem Does This Paper Address?
Evolutionary algorithms (EAs) are powerful tools for optimization, but they can struggle with problems where the fitness of a solution depends on many interacting parts (high epistasis). This is particularly true for complex, real-world problems like nurse scheduling or mall tenant selection, where a single decision (e.g., assigning a shift pattern to a nurse) has cascading effects. Standard EAs can get stuck in local optima or fail to find feasible solutions.
The authors are working with a "pyramidal" or hierarchical evolutionary algorithm. In this setup, the problem is broken down into smaller sub-problems, each handled by a "sub-population." Higher-level sub-populations then combine the solutions from lower levels to tackle larger parts of the problem. A key challenge in such a system is how to assign a meaningful "sub-fitness" to these partial solutions. If sub-fitness is poorly defined, it can mislead the search. This paper specifically investigates how the way sub-solutions "partner" with each other to get their sub-fitness evaluated impacts the overall optimization performance.
Methods
The core of this paper is the investigation of seven different "partnering strategies" for fitness evaluation within a pyramidal evolutionary algorithm. These strategies dictate how sub-solutions from different sub-populations are paired up to calculate their fitness.
- Standard Approach (Rank-Selection): Solutions are ranked based on their sub-fitness, and selection is done using a roulette wheel based on these ranks.
- Random (R): Solutions randomly choose partners from their paired sub-population.
- Best (B): Solutions are paired with the best solution from the other sub-population.
- Distributed (D): A more complex strategy that aims to match similar solutions across sub-populations, simulating local mating.
- Combined Strategies (BR, SR, RR): These strategies pair a solution with both the "best" and a "random" partner (BR), or with "rank-selected" and "random" partners (SR), or with two "random" partners (RR). The better of the two fitness values is used.
The authors apply these strategies to two specific problems: nurse scheduling and mall tenant selection, both of which are known to be difficult for standard optimization methods. They use a pyramidal structure with multiple levels of sub-populations, where each level optimizes a progressively larger part of the problem.
Datasets
The paper uses two types of problem instances for evaluation:
- Nurse Scheduling: 52 datasets were used, with an average size of 30 nurses per ward and up to 411 possible shift patterns per nurse.
- Mall Tenant Selection: 50 problem instances were created, each with 100 locations grouped into five areas. These instances varied in the number of shop types and the tightness of constraints.
The authors note that these datasets are based on real-world problem structures but are constructed artificially due to confidentiality issues in real-life data.
Key Insights and Ideas
- The "Best" is Not Always Best: The strategy of pairing with the absolute "best" sub-solution (strategy B) consistently performed poorly. This suggests that focusing too narrowly on the best might lead to premature convergence and a lack of exploration.
- Randomness and Diversity are Key: Strategies involving random partner selection (R, BR, RR) generally performed much better. This highlights the importance of exploring a wider range of pairings to avoid getting stuck in local optima and to maintain diversity in the population.
- Double Strategies Outperform Singles: Combining two partnering schemes (BR, SR, RR) consistently improved results over single strategies. This indicates that a more robust evaluation can be achieved by considering multiple perspectives.
- The Power of Random Pairing (RR): The "Random/Random" (RR) strategy, where a solution is paired twice with random partners and the better fitness is taken, yielded the overall best results for both problems. This reinforces the idea that broad exploration is crucial.
- Pyramidal Structure Benefits: The pyramidal structure itself significantly reduces epistasis, making the problem easier for the EA. The partnering strategies then further refine this benefit by improving the quality of the sub-fitness assignments.
- Mall Problem Challenges: For the mall problem, the sub-fitness measures were less effective predictors of overall solution quality compared to the nurse scheduling problem. This suggests that the way sub-problems are defined and evaluated is critical and problem-dependent.
Key Results
- Nurse Scheduling: All partnering strategies performed better than a standard genetic algorithm (SGA). The "Random/Random" (RR) strategy achieved the best results, with a cost of 12.1 and 83% feasibility, significantly outperforming the SGA's 54.2 cost and 33% feasibility. Combining RR with a hillclimber further improved feasibility to 95%.
- Mall Problem: While single strategies showed some improvement over SGA, the double strategies, particularly RR, provided substantial gains. The paper suggests that the success of RR in the mall problem, despite initial sub-fitness challenges, is due to its ability to provide a better overall fitness score for the partial solutions.
Limitations and Future Work
- Sub-fitness Definition for Mall Problem: The authors acknowledge that the sub-fitness measures for the mall problem were not as effective as for the nurse scheduling problem. They suggest that future work could explore alternative ways to define sub-fitness that better capture the problem's constraints.
- Gradual Build-up of Sub-populations: The paper mentions that a more gradual, multi-level hierarchical design (more sub-populations, smaller size) might be beneficial for problems like the mall tenant selection, allowing for a slower, more controlled build-up of solutions. This is identified as a promising area for future research.
- Hillclimber Integration: The paper demonstrates that integrating a local search (hillclimber) with the best partnering strategies (RR) can further enhance performance, particularly in achieving higher feasibility. This suggests that hybrid approaches combining evolutionary search with local search are powerful.
Summary updated