On Fri, 30 Apr 2021 at 16:40, Avijit Basak <avijit.ba...@gmail.com> wrote:
> > >> Then some examination of the data-structures is required (a > binary chromosome is currently stored as a "List<Integer>"). > -- I have recently done some work on this. Could you please > check this article and share your thought. > "*https://arxiv.org/abs/2103.04751 > <https://arxiv.org/abs/2103.04751>*" > Looking at the paper it relates to the efficiency of storing binary values for many indexes. The conclusion being you should use each bit of the byte to store each binary value, i.e. a bitset. In the example repository the binary chromosome is stored using a List<Long> with each long representing 64 alleles. This is basically an unoptimised BitSet. So I would look at how this is done in java.util.BitSet and write a custom version for optimised genetic algorithm operations. It would also be faster than the List<Long> and avoid the boxing of each long with a Long object wrapper thus save a lot of memory. Note: You cannot easily just use java.util.BitSet as you wish to have access to the underlying long[] to store the chromosome to enable efficient crossover. This can be done with bit manipulation of the longs containing the crossover point and then a System.arraycopy via a temp array: For a single point crossover of two long[] chromosomes: long[] c1 = ... long[] c2 = ... // The chosen allele for the crossover int cross = ... // Find the index and bit in the 64-bit per long representation int index = cross >> 6; // i.e. cross / 64 // This is not actually required... // int bit = cross & 64; // i.e. cross % 64 // The following will create the mask for all bits up to the target bit // long mask = -1 << bit; long mask = -1 << index; // Swap the bits before/after the crossover at the target index long tmp = c1[index]; c1[index] = (tmp & mask) | (c2[index] & ~mask); c2[index] = (tmp & ~mask) | (c2[index] & mask); // Copy the rest long[] data = new long[index]; System.arraycopy(c2, 0, data, 0, index); System.arraycopy(c1, 0, c2, 0, index); System.arraycopy(data, 0, c1, 0, index); This is untested code but contains the main idea. Setting and unsetting bits in the binary chromosome for mutation is much easier as you just pick the mutation point, find the index and the bit and then set it or unset it as appropriate using a xor operation of the bit (see the source code for BitSet.flip). Alex
