2
$\begingroup$

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++.

$\endgroup$
  • 1
    $\begingroup$ Why do you expect the standard library implementations not to work for you? $\endgroup$ – Raphael Feb 4 '15 at 12:03
  • $\begingroup$ @Raphael I am expecting to use the standard library. But because I need to combine an array of floats into a hash, and I can specify bounds, I was wondering what the best way to implement the standard library hash function would be and whether I could somehow use the bounds to create a more efficient implementation $\endgroup$ – texasflood Feb 4 '15 at 15:04
  • $\begingroup$ @Raphael Also, I gave the whole problem in the description as I wanted to know if my hash function solution was a good idea and whether there are alternatives to using a giant array of booleans. $\endgroup$ – texasflood Feb 4 '15 at 15:18
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So does the above code just hash the float[] arr? What does the HashMap section do? And how would I use a hash set to see if I have created a robot with the same hash before? If I can use less memory that would be really useful $\endgroup$ – texasflood Feb 4 '15 at 14:27
  • $\begingroup$ By a hash set do you just mean an array of hash values, which I would just search through to see if there is a duplicate? I probably want to avoid that as the number of robots can get very large and iterating over a large array can be time consuming if I'm doing it for every robot. Or does it have some special properties meaning it can be very efficiently searched? Though it would use less memory $\endgroup$ – texasflood Feb 4 '15 at 14:32
  • $\begingroup$ This answer seems to be more about code than about computer science (perhaps that means that the question itself has the same property; I'm not sure). $\endgroup$ – David Richerby Feb 4 '15 at 15:56
  • $\begingroup$ I have improved my answer to address your questions. Yes, the above code just hash float array. I just have noticed that the HashMap part have been changed in Java8 and now its just return h ^ (h >>> 16). It's role is to spread differences from high bits to low bits (explanation from authors). $\endgroup$ – Sumik Feb 5 '15 at 19:20
  • $\begingroup$ Ok that's perfect, I wasn't aware that sets also had O(1) access time, I thought they had to be iterated through so it would be O(n), so I was thinking I had to have a giant array. I was wrong, there was never a problem in the first place! Thanks. $\endgroup$ – texasflood Feb 5 '15 at 22:47
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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( ) );
$\endgroup$
  • $\begingroup$ OK but why would one want a floating-point hash? Why not just hash the byte-sequence that contains the floating point data? $\endgroup$ – David Richerby Jun 12 '17 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.