pith. sign in

arxiv: 2406.01215 · v2 · submitted 2024-06-03 · 💻 cs.NE

The hop-like problem nature -- unveiling and modelling new features of real-world problems

Pith reviewed 2026-05-24 00:31 UTC · model grok-4.3

classification 💻 cs.NE
keywords hop-based analysisLeading Blocks ProblemLeading Onesgenetic algorithmsreal-world optimizationbenchmarksevolutionary computationNP-hard problems
0
0 comments X

The pith

A hop-based analysis of a real-world NP-hard problem reveals structural features shared with the Leading Ones benchmark, which the new Leading Blocks Problem models in a more general form.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proposes a hop-based analysis to examine how optimizers navigate real-world problems. When applied to a large-scale NP-hard instance, the analysis detects features similar to those in the classic Leading Ones problem. To represent these features accurately, the authors define the Leading Blocks Problem as a broader benchmark that supports construction of new hard instances. Experiments with a state-of-the-art genetic algorithm on both the real-world problem and LBP instances show that current mechanisms fall short and indicate the changes required for better performance.

Core claim

The optimization process on the examined real-world problem exhibits hop-like characteristics that match key aspects of Leading Ones. The Leading Blocks Problem is introduced as a generalization that assembles leading blocks to control difficulty, allowing new benchmark families that standard genetic algorithms solve poorly and thereby highlighting the mechanisms needed to improve effectiveness on LBP and the original problem.

What carries the argument

The hop-based analysis of the optimization trajectory combined with the Leading Blocks Problem (LBP), a generalization of Leading Ones that uses sequences of leading blocks to generate controllable hardness for genetic algorithms.

If this is right

  • LBP can be used to assemble new families of hard optimization problems not handled well by existing genetic algorithms.
  • The hop-based analysis can identify similar structural features in additional real-world problems.
  • Specific operator or selection changes are required to raise genetic-algorithm performance on LBP and on problems sharing its hop profile.
  • LBP instances provide controlled test cases for measuring progress toward solving the real-world problem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the hop features prove common across real-world instances, benchmark design could shift from purely theoretical constructions toward feature extraction from actual problems.
  • LBP could be extended with additional block-assembly rules to test a wider range of evolutionary operators beyond the genetic algorithm examined here.
  • The same hop-analysis pipeline might be applied to other search methods to check whether the identified weaknesses are GA-specific or more general.

Load-bearing premise

The hop-based analysis must correctly detect load-bearing structural features of the optimization landscape that govern difficulty for genetic algorithms, and these features must be general enough to justify a new benchmark family rather than being specific to the single instance studied.

What would settle it

Construct LBP instances whose hop statistics match those of the real-world problem and test whether a state-of-the-art genetic algorithm exhibits the same relative performance drop on both; a clear mismatch in difficulty patterns would falsify the claim that LBP models the relevant features.

Figures

Figures reproduced from arXiv: 2406.01215 by Bartosz Frej, Marcin M. Komarnicki, Michal W. Przewozniczek.

Figure 1
Figure 1. Figure 1: HOP-based analysis of the WP_LFL instances [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Median FFE until finding the optimal solution by LT-GOMEA and LT [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
read the original abstract

Benchmarks are essential tools for the optimizer's development. Using them, we can check for what kind of problems a given optimizer is effective or not. Since the objective of the Evolutionary Computation field is to support the tools to solve hard, real-world problems, the benchmarks that resemble their features seem particularly valuable. Therefore, we propose a hop-based analysis of the optimization process. We apply this analysis to the NP-hard, large-scale real-world problem. Its results indicate the existence of some of the features of the well-known Leading Ones problem. To model these features well, we propose the Leading Blocks Problem (LBP), which is more general than Leading Ones and some of the benchmarks inspired by this problem. LBP allows for the assembly of new types of hard optimization problems that are not handled well by the considered state-of-the-art genetic algorithm (GA). Finally, the experiments reveal what kind of mechanisms must be proposed to improve GAs' effectiveness while solving LBP and the considered real-world problem.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 1 minor

Summary. The paper proposes a hop-based analysis of the optimization process and applies it to an NP-hard large-scale real-world problem. The analysis is said to reveal features similar to those of the Leading Ones problem. To model these features, the authors introduce the Leading Blocks Problem (LBP), claimed to be more general than Leading Ones and related benchmarks. LBP is presented as enabling construction of new hard optimization problems that challenge a state-of-the-art genetic algorithm (GA), with experiments purportedly identifying mechanisms needed to improve GA performance on both LBP and the real-world instance.

Significance. If the hop analysis were shown to isolate causally load-bearing landscape features and LBP were validated through controlled comparisons, the work could help generate more realistic benchmarks for evolutionary computation. However, the manuscript supplies no methods, quantitative results, or ablation studies, so the potential contribution cannot be assessed and the significance remains speculative.

major comments (3)
  1. [Abstract] Abstract: the abstract asserts that hop-based analysis 'indicates the existence of some of the features' of Leading Ones and that LBP 'models these features well,' yet provides no description of the hop analysis procedure, the real-world instance, quantitative similarity metrics, or any controls, making the data-to-claim link impossible to evaluate.
  2. [Abstract] Abstract and results sections: the central claim that LBP generates 'new types of hard optimization problems that are not handled well by the considered state-of-the-art GA' requires evidence that the leading-blocks structure is responsible for the observed difficulty. No controlled ablation (e.g., LBP variants differing only in block structure while holding other landscape statistics fixed) is described to establish causality rather than post-hoc pattern matching.
  3. [Abstract] Abstract: the claim that 'experiments reveal what kind of mechanisms must be proposed to improve GAs' effectiveness' is load-bearing for the paper's contribution, but the manuscript supplies neither the experimental design, performance tables, statistical tests, nor comparison baselines, preventing any assessment of whether the identified mechanisms are general or instance-specific.
minor comments (1)
  1. The manuscript should include a clear definition of the hop operator and the precise distance or transition measure used in the analysis.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thoughtful and detailed comments. We address each major comment below and indicate the revisions that will be incorporated to strengthen the manuscript.

read point-by-point responses
  1. Referee: [Abstract] Abstract: the abstract asserts that hop-based analysis 'indicates the existence of some of the features' of Leading Ones and that LBP 'models these features well,' yet provides no description of the hop analysis procedure, the real-world instance, quantitative similarity metrics, or any controls, making the data-to-claim link impossible to evaluate.

    Authors: The abstract serves as a concise summary; the hop-based analysis procedure is fully specified in Section 3, the real-world instance in Section 2, and the quantitative similarity metrics plus controls appear in Section 4 with explicit comparisons to Leading Ones. To improve accessibility, we will revise the abstract to include a one-sentence description of the hop procedure and the primary similarity metric used. revision: yes

  2. Referee: [Abstract] Abstract and results sections: the central claim that LBP generates 'new types of hard optimization problems that are not handled well by the considered state-of-the-art GA' requires evidence that the leading-blocks structure is responsible for the observed difficulty. No controlled ablation (e.g., LBP variants differing only in block structure while holding other landscape statistics fixed) is described to establish causality rather than post-hoc pattern matching.

    Authors: We agree that isolating the causal contribution of the block structure requires controlled ablations. In the revised version we will add a new subsection presenting LBP variants that differ solely in block length and overlap while matching other landscape statistics (e.g., fitness variance, epistasis), together with statistical comparisons of GA performance on these variants. revision: yes

  3. Referee: [Abstract] Abstract: the claim that 'experiments reveal what kind of mechanisms must be proposed to improve GAs' effectiveness' is load-bearing for the paper's contribution, but the manuscript supplies neither the experimental design, performance tables, statistical tests, nor comparison baselines, preventing any assessment of whether the identified mechanisms are general or instance-specific.

    Authors: The experimental design, performance tables, statistical tests, and baselines are reported in Section 5 and the associated tables of the full manuscript. To address the concern about the abstract, we will add a short clause summarizing the experimental protocol and the two mechanisms identified as most effective. revision: yes

Circularity Check

0 steps flagged

No circularity: empirical observation leads to benchmark proposal without reduction to inputs

full rationale

The paper applies hop-based analysis to one real-world instance, reports similarity to Leading Ones features in the abstract, and proposes LBP as a generalization to model those features. This constitutes an empirical pattern-matching step followed by a modeling suggestion, not a derivation, prediction, or uniqueness claim that reduces by construction to fitted parameters, self-citations, or prior ansatzes. No equations, self-citation chains, or load-bearing uniqueness theorems appear in the provided text that would trigger any of the enumerated circularity patterns. The derivation chain remains self-contained as an observation-to-proposal process.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 1 invented entities

The paper postulates the Leading Blocks Problem as a new modeling entity whose independent evidence rests only on the authors' hop analysis of one instance; no external falsifiable predictions or prior benchmarks are cited as grounding.

invented entities (1)
  • Leading Blocks Problem (LBP) no independent evidence
    purpose: To model Leading-Ones-like features observed in the real-world problem and to generate new hard instances
    New benchmark family introduced by the paper without reference to external validation data or proofs.

pith-pipeline@v0.9.0 · 5712 in / 1304 out tokens · 31082 ms · 2026-05-24T00:31:45.353516+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages

  1. [1]

    In: Proceedings of the Genetic and Evolutionary Computation Conference 2016

    Bosman, P.A., Luong, N.H., Thierens, D.: Expanding from discrete cartesian to permutation gene-pool optimal mixing evolutionary algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference 2016. p. 637–644. GECCO ’16, Association for Computing Machinery, New York, NY, USA (2016)

  2. [2]

    Deb, K., Goldberg, D.E.: Sufficient conditions for deceptive and easy binary func- tions. Ann. Math. Artif. Intell.10(4), 385–408 (1993)

  3. [3]

    Complex Sys- tems 7(2) (1993)

    Deb, K., Horn, J., Goldberg, D.E.: Multimodal deceptive functions. Complex Sys- tems 7(2) (1993)

  4. [4]

    In: Proc

    Dias, R.A., Camponogara, E., Farines, J.M., Willrich, R., Campestrini, A.: Imple- mentingtrafficengineeringinMPLS-basedIPnetworkswithlagrangeanrelaxation. In: Proc. of IEEE Symposium on Computers and Communications (IEEE ISCC) (2003)

  5. [5]

    In: Proceedings of the Genetic and Evolutionary Compu- tation Conference

    Doerr, B., Kelley, A.J.: Fourier analysis meets runtime analysis: Precise run- times on plateaus. In: Proceedings of the Genetic and Evolutionary Compu- tation Conference. p. 1555–1564. GECCO ’23, Association for Computing Ma- chinery, New York, NY, USA (2023). https://doi.org/10.1145/3583131.3590393, https://doi.org/10.1145/3583131.3590393

  6. [6]

    In: ProceedingsoftheGeneticandEvolutionaryComputationConferenceCompanion

    van Driessel, T., Thierens, D.: Benchmark generator for td mk landscapes. In: ProceedingsoftheGeneticandEvolutionaryComputationConferenceCompanion. p. 1227–1233. ACM (2021)

  7. [7]

    NETWORKS pp

    Fratta, L., Gerla, M., Kleinrock, L.: The flow deviation method: an approach to store-and-forward communication network design. NETWORKS pp. 97–133 (1973)

  8. [8]

    In: Proceedings of the Fifth International Conference on Genetic Algorithms

    Goldberg, D.E., Deb, K., Kargupta, H., Harik, G.: Rapid, accurate optimization of difficult problems using fast messy genetic algorithms. In: Proceedings of the Fifth International Conference on Genetic Algorithms. pp. 56–64 (1993)

  9. [9]

    In: Pro- ceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation

    Goldman, B.W., Punch, W.F.: Parameter-less population pyramid. In: Pro- ceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation. pp. 785–792. GECCO ’14, ACM, New York, NY, USA (2014). https://doi.org/10.1145/2576768.2598350,http://doi.acm.org/10.1145/ 2576768.2598350

  10. [10]

    In: Proceedings of the Genetic and Evolutionary Computation Conference

    Gomes, T.M., de Freitas, A.R.R., Lopes, R.A.: Multi-heap constraint handling in gray box evolutionary algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference. p. 829–836. GECCO ’19, Association for Computing Machinery,NewYork,NY,USA(2019).https://doi.org/10.1145/3321707.3321872, https://doi.org/10.1145/3321707.3321872

  11. [11]

    In: Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation - Volume 1

    Harik, G.R., Lobo, F.G.: A parameter-less genetic algorithm. In: Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation - Volume 1. pp. 258–265. GECCO’99 (1999)

  12. [12]

    In: Proceedings of the 2015 An- nual Conference on Genetic and Evolutionary Computation

    Hsu, S.H., Yu, T.L.: Optimization by pairwise linkage detection, incremental link- age set, and restricted / back mixing: Dsmga-ii. In: Proceedings of the 2015 An- nual Conference on Genetic and Evolutionary Computation. pp. 519–526. GECCO ’15, ACM, New York, NY, USA (2015). https://doi.org/10.1145/2739480.2754737, http://doi.acm.org/10.1145/2739480.2754737

  13. [13]

    Jansen, T., Wiegand, R.P.: The cooperative coevolutionary (1+1) ea. Evol. Comput. 12(4), 405–434 (dec 2004). https://doi.org/10.1162/1063656043138905, https://doi.org/10.1162/1063656043138905

  14. [14]

    IEEE Trans- actions on Evolutionary Computation27(5), 1498–1513 (2023) 16 M

    Komarnicki, M.M., Przewozniczek, M.W., Kwasnicka, H., Walkowiak, K.: Incre- mental recursive ranking grouping for large-scale global optimization. IEEE Trans- actions on Evolutionary Computation27(5), 1498–1513 (2023) 16 M. W. Przewozniczek, B. Frej and M. M. Komarnicki

  15. [15]

    Kullback, S., Leibler, R.A.: On information and sufficiency. Ann. Math. Statist. 22(1), 79–86 (1951)

  16. [16]

    IEEE Trans

    Kwasnicka, H., Przewozniczek, M.: Multi population pattern searching algorithm: A new evolutionary method based on the idea of messy genetic algorithm. IEEE Trans. Evolutionary Computation15, 715–734 (2011)

  17. [17]

    In: Pro- ceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Al- gorithms

    Lehre, P.K., Nguyen, P.T.H.: On the limitations of the univariate marginal dis- tribution algorithm to deception and where bivariate edas might help. In: Pro- ceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Al- gorithms. p. 154–168. FOGA ’19, Association for Computing Machinery, New York, NY, USA (2019). https://doi.org/10.1145/329990...

  18. [18]

    Swarm and Evolutionary Computation40, 238 – 254 (2018)

    Luong, N.H., Poutré, H.L., Bosman, P.A.: Multi-objective gene-pool optimal mix- ing evolutionary algorithm with the interleaved multi-start scheme. Swarm and Evolutionary Computation40, 238 – 254 (2018)

  19. [19]

    In: Proceedings of the First European Conference on Artificial Life

    Mitchell, M., Forrest, S., Holland, J.: The royal road for genetic algorithms: Fitness landscapes and ga performance. In: Proceedings of the First European Conference on Artificial Life. p. 245–254. MIT Press (11 1994)

  20. [20]

    Machine Learning 45, 77–114 (11 2001)

    Nimwegen, E., Crutchfield, J.: Optimizing epochal evolutionary search: Population-size dependent theory. Machine Learning 45, 77–114 (11 2001). https://doi.org/10.1023/A:1010928206141

  21. [21]

    Morgan Kaufmann (2004)

    Pioro, M., Medhi, D.: Routing, Flow, and Capacity Design in Communication and Computer Networks. Morgan Kaufmann (2004)

  22. [22]

    Przewoźniczek, M.: Active multi-population pattern searching algorithm for flow optimization in computer networks - the novel coevolution schema combined with linkage learning. Inf. Sci.355(C), 15–36 (Aug 2016)

  23. [23]

    In: Computational Science and Its Applications ICCSA

    Przewoźniczek, M., Walkowiak, K.: Quasi-hierarchical evolutionary algorithm for flow optimization in survivable MPLS networks. In: Computational Science and Its Applications ICCSA. pp. 330–342 (2007)

  24. [24]

    In: Proceedings of the Genetic and Evolutionary Com- putation Conference

    Przewozniczek, M.W., Komarnicki, M.M., Frej, B.: Direct linkage discovery with empirical linkage learning. In: Proceedings of the Genetic and Evolutionary Com- putation Conference. p. 609–617. GECCO ’21, ACM (2021)

  25. [25]

    In: Proceedings of the Genetic and Evolutionary Computation Conference

    Przewozniczek, M.W., Tinós, R., Frej, B., Komarnicki, M.M.: On turning black - into dark gray-optimization with the direct empirical linkage discovery and par- tition crossover. In: Proceedings of the Genetic and Evolutionary Computation Conference. p. 269–277. GECCO ’22, ACM (2022)

  26. [26]

    Swarm and Evolutionary Computation60, 100773 (2021)

    Przewozniczek, M.W., Dziurzanski, P., Zhao, S., Indrusiak, L.S.: Multi-objective parameter-less population pyramid for solving industrial process planning prob- lems. Swarm and Evolutionary Computation60, 100773 (2021)

  27. [27]

    In: Proceedings of the 2020 Annual Conference on Genetic and Evolutionary Computation

    Przewozniczek, M.W., Frej, B., Komarnicki, M.M.: On measuring and improv- ing the quality of linkage learning in modern evolutionary algorithms applied to solve partially additively separable problems. In: Proceedings of the 2020 Annual Conference on Genetic and Evolutionary Computation. p. (in press). GECCO ’20 (2020)

  28. [28]

    IEEE Trans- actions on Evolutionary Computation p

    Przewozniczek, M.W., Komarnicki, M.M.: Empirical linkage learning. IEEE Trans- actions on Evolutionary Computation p. (in press) (2020)

  29. [29]

    Applied Soft Computing113, 107864 (2021)

    Przewozniczek, M.W., Komarnicki, M.M.: Empirical problem decomposition — the key to the evolutionary effectiveness in solving a large-scale non-binary discrete real-world problem. Applied Soft Computing113, 107864 (2021)

  30. [30]

    In: Proceedings of the Genetic and Evolutionary Computation Conference

    Przewozniczek, M.W., Tinós, R., Komarnicki, M.M.: First improvement hill climber with linkage learning – on introducing dark gray-box optimization into Title Suppressed Due to Excessive Length 17 statistical linkage learning genetic algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference. p. 946–954. GECCO ’23, ACM (2023)

  31. [31]

    IEEE Communications Magazine41(6), 60–70 (June 2003)

    Sengupta, S., Kumar, V., Saha, D.: Switched optical backbone for cost-effective scalable core ip networks. IEEE Communications Magazine41(6), 60–70 (June 2003)

  32. [32]

    Algorithmica83(4), 976–1011 (apr 2021)

    Sudholt, D.: Analysing the robustness of evolutionary algorithms to noise: Refined runtime bounds and an example where noise is beneficial. Algorithmica83(4), 976–1011 (apr 2021)

  33. [33]

    In: Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation

    Thierens, D., Bosman, P.A.: Hierarchical problem solving with the linkage tree genetic algorithm. In: Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation. pp. 877–884. GECCO ’13, ACM, New York, NY, USA (2013). https://doi.org/10.1145/2463372.2463477,http://doi.acm.org/10.1145/ 2463372.2463477

  34. [34]

    In: Pro- ceedings of the Genetic and Evolutionary Computation Conference

    Tinós, R., Przewozniczek, M.W., Whitley, D.: Iterated local search with pertur- bation based on variables interaction for pseudo-boolean optimization. In: Pro- ceedings of the Genetic and Evolutionary Computation Conference. p. 296–304. GECCO ’22, ACM (2022)

  35. [35]

    In: Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII

    Tinós, R., Whitley, D., Chicano, F.: Partition crossover for pseudo-boolean opti- mization. In: Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII. p. 137–149. FOGA ’15, ACM (2015)

  36. [36]

    In: Proc

    Walkowiak, K.: A new approach to survivability of connection oriented networks. In: Proc. of International Conference on Computational Science (ICCS) (2003)

  37. [37]

    In: Mitrou, N., Kontovasilis, K., Rouskas, G.N., Iliadis, I., Merakos, L

    Walkowiak, K.: A new method of primary routes selection for local restoration. In: Mitrou, N., Kontovasilis, K., Rouskas, G.N., Iliadis, I., Merakos, L. (eds.) Network- ing 2004. pp. 1024–1035. Springer Berlin Heidelberg, Berlin, Heidelberg (2004)

  38. [38]

    In: Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat

    Watson, R.A., Pollack, J.B.: Hierarchically consistent test problems for ge- netic algorithms. In: Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406). vol. 2, p. 1413 Vol. 2 (1999). https://doi.org/10.1109/CEC.1999.782647

  39. [39]

    In: Parallel Problem Solving from Nature - PPSN V, 5th International Conference, Amsterdam, The Netherlands, September 27-30, 1998, Proceedings

    Watson, R.A., Hornby, G., Pollack, J.B.: Modeling building-block interdependency. In: Parallel Problem Solving from Nature - PPSN V, 5th International Conference, Amsterdam, The Netherlands, September 27-30, 1998, Proceedings. pp. 97–108 (1998)

  40. [40]

    In: Handbook of Metaheuristics, pp

    Whitley, D.: Next generation genetic algorithms: a user’s guide and tutorial. In: Handbook of Metaheuristics, pp. 245–274. Springer (2019)

  41. [41]

    Evolutionary Computation24(3), 491–519 (2016)

    Whitley, L.D., Chicano, F., Goldman, B.W.: Gray box optimization for mk land- scapes (nk landscapes and max-ksat). Evolutionary Computation24(3), 491–519 (2016)

  42. [42]

    Zhan, Z.H., Shi, L., Tan, K., Zhang, J.: A survey on evolutionary com- putation for complex continuous optimization. Artif. Intell. Rev. (2021). https://doi.org/10.1007/s10462-021-10042-y