Hash function floating point inputs for genetic algorithm

Question

I am implementing a genetic algorithm to use as an optimisation algorithm to evolve robots. The robots have certain parameters (represented as floats) which can lie anywhere within a certain range defined for each parameter. My goal is to optimise these parameters to produce the fittest robot.

There are about 25 parameters to optimise over, all of which are >= 0. A generation consists of 32 robots and a typical evolutionary run may have 6000 generations, so that is 192000 robots in total.

One problem I was noticing was that many times, the same robot was being produced by the random mutation function and its fitness was re-evaluated. I want to try and minimise this from happening as the physics simulation engine has a large time expense.

It would be impractical (especially from a memory point of view) to remember all robot parameters that have ever been produced and use a brute force solution.

One solution I thought of was to use a hash function to and a large array of booleans, and everytime a mutation occurs, largeArray[hash(robotParameters)] is checked to see if it is set. If it is, the mutation occurs again to produce a different set of parameters, and if it isn't, largeArray[hash(robotParameters)] is then set.

What is a good hash function implementation that would work for me? Preferably, there would already be an implementation in Python or C++.

Answer 1

Hashing an array of floats

You need some hash function that:

• low computational cost
• low probability of generating the same hash value for two input vectors = evenly distributed hashes

If you language/library have some function for hashing float array, it should be ok.

For example, this function is what Java would do with an float array (it's not a direct copy of Java library):

int hashFloatArray(float[] arr) {
    //this is done in Arrays.hashCode()
    int h = 1;
    for (int i = 0; i < arr.length; i++){
        int floatAsInt = Float.floatToIntBits(arr[i]); 
        //in C: int floatAsInt = *(int*)(&arr[i]);
        h = 31 * h + floatAsInt;
    }
    //this is done in HashMap
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

Finding matching hashes

Storing hashes instead of whole float arrays reduces amount of memory needed. Space of hashes is smaller than the space of float arrays, so matching hashes never give 100% certainty that original objects (float arrays) where identical. The longer hashes the smaller is the change of hash collision (situation when two different inputs produce the same hash).

Array indexed with hashes (as OP proposed)

Indexing array with hashes means that the length of the array must be 2^k where k is length of key in bits. For example: Assuming single field of array occupies 1 byte (boolean variable usually occupy 1 byte). Using 30 bit key requires 2^30 * 1 bytes = 1GB of memory (O(2^k) space complexity). As mentioned before:

• shorter key = smaller array = higher chance of hash collision
• longer key = bigger array = lower chance of hash collision

Hash table (Hash set)

Hash table is a data structure that can be used to implement hash set. Main advantage of hash set is it's O(1) average time complexity combined with O(n) space complexity.

You can use hash set to store and effectively find:

• long hashes (64 bit?) of float arrays without wasting memory
• float arrays themselves (if you have enough memory)

Hash sets are available in standard libraries of almost all programming languages.

• java.util.HashSet in Java
• unordered_set in C++11
• set in Python

Why comparing and hashing floats is a problem?

Let's take two float numbers: 1.2345678 and 1.2345679 The difference between them is small enough to have no influence on the quality of your Robot, but comparing 1.2345678 and 1.2345679 results in "not equal" and hashing them results in two different hashes. Introducing an "almost equal" term may be a good idea, but that can't be done with hashes.

Answer 2

I'll describe how I solved this problem in Python. To combat the problem of two similar floats not mapping to the same hash, I used the function below to round the parameters to a certain no. of significant figures

def roundToNSigFigs(x, n):
  return 0 if (x == 0) else round(x, -int(math.floor(math.log10(abs(x)))) + (n - 1))

Within the Robot class, the self.args member variable was a list holding all the floating point parameters. I started with

hashTable = set()

And every time a Robot was created I used:

hashTable.add(hash(tuple([roundToN(i, sigFigs) for i in self.args])))

The tuple cast is needed because you cannot take the hash of a mutable object

And in my mutation member method, I checked to see if the new mutated parameters (newArgs) were already tested by checking hash(tuple(newArgs)) not in hashTable

Answer 3

If you're interested, I just made a hash function that uses floating point and can hash floats. It also passes SMHasher ( which is the main bias-test for non-crypto hash functions ). It's a lot slower than normal non-cryptographic hash functions due to the float calculations.

I'm not sure if tifuhash will become useful for all applications, but it's interesting to see a simple floating point function pass both PractRand and SMHasher.

The main state update function is very simple, and looks like:

function q( state, val, numerator, denominator ) {
  // Continued Fraction mixed with Egyptian fraction "Continued Egyptian Fraction"
  // with denominator = val + pos / state[1]
  state[0] += numerator / denominator;
  state[0] = 1.0 / state[0];

  // Standard Continued Fraction with a_i = val, b_i = (a_i-1) + i + 1
  state[1] += val;
  state[1] = numerator / state[1];
}

Anyway, you can get it on npm Or you can check out the github

Using is simple:

const tifu = require('tifuhash');

const message = 'The medium is the message.';
const number = 333333333;
const float = Math.PI;

console.log( tifu.hash( message ), 
  tifu.hash( number ),
  tifu.hash( float ),
tifu.hash( ) );