Evolving heuristically difficult instances of combinatorial problems | Zendy

Bryant A. Julstrom | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Evolving heuristically difficult instances of combinatorial problems

Author(s) -

Bryant A. Julstrom

Publication year - 2009

Publication title -

citeseer x (the pennsylvania state university)

Language(s) - English

Resource type - Conference proceedings

DOI - 10.1145/1569901.1569941

Subject(s) - knapsack problem , heuristic , continuous knapsack problem , greedy algorithm , computer science , genetic algorithm , mathematical optimization , heuristics , combinatorial optimization , evolutionary algorithm , artificial intelligence , algorithm , mathematics , machine learning

When evaluating a heuristic for a combinatorial problem, randomly generated instances of the problem may not provide a thorough exploration of the heuristic's performance, and it may not be obvious what kinds of instances challenge or confound the heuristic. An evolutionary algorithm can search a space of problem instances for cases that are heuristically difficult. Evaluation in such an EA requires an exact algorithm for the problem, which limits the sizes of the instances that can be explored, but the EA's (small) results can reveal misleading patterns or structures that can be replicated in larger instances. As an example, a genetic algorithm searches for instances of the quadratic knapsack problem that are difficult for a straightforward greedy heuristic. The GA identifies such instances, which in turn reveal patterns that mislead the heuristic.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research