Add HilbertGridSearchOptimizer for space-filling curve traversal #70
Conversation
Signed-off-by: Aryan Yadav <[email protected]>
|
Could you provide a source for this implementation? I would like to understand this algorithm and why/how it works in n-dimensions on a mathematical level. A reference to a paper or something similar would be enough. |
|
Sure sir, here is the link of research paper: |
|
@SimonBlanke Sir, can you please this review this PR. |
|
@aryan0931, |
|
I do not want to add a dependency to a project, that was abandoned 5 years ago to implement one algorithm. My goal is to use current dependencies to create this algorithm in gfo. |
|
Okay sir, I will work on it and raise a new PR. Could you please guide me on the follow-ups or next steps I should keep in mind while working on this? |
|
Implementing an algorithm for gfo would require to understand its mathematics. For some algorithms (like random-search or hill-climbing) this is quite easy to do. The implementation of an n-dimensional hilbert-curve is a bigger challenge. But if you feel comfortable with the mathematics you can try. An alternative would be to work on a simpler algorithm. I read the paper for the harmonic search algorithm. It is an easy read and should not be too difficult to implement. |
ok sir I am working on it. |
|
@SimonBlanke |
|
@aryan0931 |
Fixes: #65
Motivation
The current grid-search implementation in Gradient-Free-Optimizers, as noted in issue #65, starts traversal from a corner of the search space and follows paths close to previously explored points. This leads to poor exploration when the number of iterations is much smaller than the search space size, limiting the algorithm’s ability to effectively cover n-dimensional spaces. By introducing a Hilbert curve-based traversal, this PR aims to improve exploration by generating points in a space-filling manner, ensuring better coverage across all dimensions, particularly for high-dimensional problems with limited iterations
Description of the changes
This PR adds a new HilbertGridSearchOptimizer class that uses a Hilbert curve to traverse the search space, addressing the exploration limitations outlined in issue #65. The changes include:
New File: Created hilbert_grid_search.py with the HilbertGridSearchOptimizer class:
Inherits from BaseOptimizer, maintaining consistency with OrthogonalGridSearchOptimizer and DiagonalGridSearchOptimizer.
Implements a hilbert_move method that generates grid points along a Hilbert curve using the numpy-hilbert-curve package’s decode function.
Supports the step_size parameter to skip points and filters out-of-bounds coordinates for non-cubic grids.
Uses conv2pos to convert indices to search space positions, ensuring compatibility with existing logic.
Updated grid_search.py:
Added import: from .hilbert_grid_search import HilbertGridSearchOptimizer.
Modified the GridSearchOptimizer class to support a new "hilbert" direction, instantiating HilbertGridSearchOptimizer when selected.