The Performance of Frequency Fitness Assignment on JSSP for Different Problem Instance Sizes

Pijning, Iris; Koppenhol, Levi; Dijkzeul, Danny; Brouwer, Nielis; Thomson, Sarah L; van den Berg, Daan

Abstract

The Frequency Fitness Assignment (FFA) method steers evolutionary algorithms by objective rareness instead of objective goodness. Does this mean the size of the combinatorial search space influences its performance when compared to more traditional evolutionary algorithms? Our results suggest it does. To address to which extent the search space size matters for the effectiveness of the FFA-principle, we compare the algorithms on 420 Job Shop Scheduling Problem (JSSP) instances systematically generated in gridwise sizes. The comparison of the FFA-hillclimber and the standard hillclimber is done in both EQ setting, accepting equally good (or fitness-frequent) solutions, and NOEQ setting, only accepting improvement. FFA-hillclimbers are more successful than standard hillclimbers on smaller problem instances, but not on larger ones. It seems that the ratio between jobs and machines, influences the success of the respective algorithms for fixed computational budgets.

Citation

Pijning, I., Koppenhol, L., Dijkzeul, D., Brouwer, N., Thomson, S. L., & van den Berg, D. (2024, November). The Performance of Frequency Fitness Assignment on JSSP for Different Problem Instance Sizes. Presented at ECTA 2024: 16th International Conference on Evolutionary Computation Theory and Applications, Porto, Portugal

• Presentation Conference Type: Conference Paper (published)
• Conference Name: ECTA 2024: 16th International Conference on Evolutionary Computation Theory and Applications
• Start Date: Nov 20, 2024
• Acceptance Date: Sep 12, 2024
• Publication Date: 2024
• Deposit Date: Sep 30, 2024
• Publicly Available Date: Jan 9, 2025
• Publisher: Scitepress Digital Library
• Peer Reviewed: Peer Reviewed
• Volume: 1
• Pages: 250-260
• Book Title: Proceedings of the 16th International Joint Conference on Computational Intelligence
• ISBN: 978-989-758-721-4
• DOI: https://doi.org/10.5220/0012970500003837
• Keywords: Optimization; Frequency Fitness Assignment; HillClimber; Job Shop Scheduling Problem; Neutrality