{'fraction_non_alphanumeric': 0.016088365950294153, 'fraction_numerical': 0.0038419978388762157, 'mean_word_length': 5.067006554989075, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Memory Optimized Data Structure for Binary Chromosomes in Genetic Algorithm

This paper presents a memory-optimized metadata-based data structure for implementation of binary chromosome in Genetic Algorithm. In GA different types of genotypes are used depending on the problem domain. Among these, binary genotype is the most popular one for non-enumerated encoding owing to its representational and computational simplicity. This paper proposes a memory-optimized implementation approach of binary genotype. The approach improves the memory utilization as well as capacity of retaining alleles. Mathematical proof has been provided to establish the same.


INTRODUCTION
Genetic algorithm was introduced by John Holland as a search and optimization algorithm for unimodal and multimodal problem space. The algorithm has been used to solve numerous engineering problems of NP-complete category. The algorithm is based on few components such as encoding of the problem domain as chromosomes, a fitness function for selection of individual chromosome, crossover for exchange of allele values between chromosomes and mutation to alter randomly selected alleles. Being superior to gradient descent, genetic algorithm has been used for optimization in unimodal and multimodal problem space along with training of machine learning models like neural network. However, GA also suffers from the drawback of excessive resource consumption owing to its population-based approach for optimization.
For several decades the algorithm has been improved by numerous researchers in different ways. Improvements have been done for selection, crossover and mutation operators. The adaptive GA was also introduced for the same purpose. But there is not much work related to minimization of resource consumption which has been a bottleneck towards its use in large scale problems. This work is an endeavour to minimize memory consumption for binary encoding.

UTILITY AND IMPLEMENTATION OF BINARY ENCODING 2.1. SCHEMA THEOREM AND BINARY ENCODING
Holland's Schema theorem provides the mathematical foundation for evolutionary dynamics of Genetic algorithm. In Schema theorem, a schema is defined as a template that identifies a subset of chromosomes with similarities at certain allele positions. Acceptable allele values in a schema are the set of alphabets used in the genotype and the wildcard character * which represents don't care symbol. So, for a genotype of length L and alphabet cardinality k there can be maximum ( + ) schemata as described in Equation 1. Schema theorem states, schemas having lower defining length, lower order and above average fitness increases exponentially in frequency over generations. The order of a schema is defined as the number of fixed positions in the template and the distance between first and last specific alleles of a schema is termed as defining length. The theorem is expressed as an equation (Equation 2) given below: determines the disruption probability of a schema due to crossover and pm determines the probability of disruption due to mutation of an allele. The ratio ( ) implies for a given defining length ( ), higher length of chromosome ensures lower minimum probability of schema disruption, which eventually improves the quality of optimization. However, the quality also depends on the number of schemata processed over generations during convergence. Higher number of processed schemata ensures better quality of search result. According to Equation 1 higher chromosome length also ensures more possible schemata count.
In any real-life problem choice of genotype decides the alphabet cardinality and hence length of the chromosome. Lower cardinality ensures higher length of chromosome. Due to minimum cardinality, use of binary encoding thus ensures processing of maximum possible schemata over generations with minimum probability of schema disruption due to crossover. This makes binary genotype an obvious choice for any critical search and optimization problem.

IMPLEMENTATION OPTIONS AND MEMORY UTILIZATION
There are several approaches for implementation of a binary chromosome. Few obvious approaches are to represent it as an array of Character, Boolean or Integral data type and store each binary allele as one array element. All these approaches consume minimum 1 byte of memory for a single binary allele. This results in memory utilization of 12.5% eventually wasting 87.5% of memory. The amount of unused memory increases with problem dimension. This becomes a bottleneck for problem domain with millions of dimensions and makes the usage of binary encoding nearly impossible.

METADATA-BASED IMPLEMENTATION & BENEFITS 3.1. IMPLEMENTATION APPROACH
The metadata-based implementation of binary chromosome proposed here minimizes the problems mentioned in the previous section. A binary chromosome is represented as an array of an integral data type. The first element of the array should contain the number of alleles used in this chromosome and represent the metadata. Rest of the elements in the array should contain binary allele information as bits. Each single bit represents a binary allele. The data type can be either signed or unsigned. However, MSB of each element should not be used to retain allele data to avoid any semantic conflict of the underlying implementation. The number of array elements (m) required to represent a chromosome of length L is expressed by Equation 3 given below. A sample chromosome containing randomly generated binary values of length 10 is shown below in a tabular form in Figure 1. Unsigned Byte is used as the elementary data type of the array. The first row represents the indexes of array elements. The second row represents the index of each binary allele within the element and the bottom row contains actual data. The first element of the array retains the length of the chromosome as metadata and the rest of the elements contain the actual allele information as placed within the respective cells. Few of the bits (marked as X) of the second array element might be left unused depending on the length of the chromosome. Similar representation using the signed Byte is shown in Figure 2. The difference between these two representations can be noted for MSB of the 3rd array element which is left unused for signed data type.

PSEUDOCODE
Pseudocode for the proposed approach has been provided below.

BENEFITS
The proposed implementation approach is effective both in accommodating more alleles in a chromosome as well as ensuring better memory utilization. In a conventional representation of binary chromosome as character or Boolean data type, the number of alleles in a chromosome is limited to the maximum number of elements an array can hold. Contrary to that in this newly proposed approach number of alleles is dependent on the maximum number of bits an array can contain depending on the data type used as well as the maximum positive number the corresponding data type can represent, whichever is smaller. Memory utilization also depends on chromosome length and data type as represented by the equations (Equation 4 & 5) given below. The tables (Table 1 & 2) list calculated values of the same for different data types (signed and unsigned) of varying capacity which clearly demonstrates the superiority of the proposed approach. The maximum number of elements in an array is considered as 2 16 for the comparison. The results clearly demonstrate that the proposed scheme improves the memory utilization to a considerable extent and higher capacity of data type ensures better utilization of memory.

CONCLUSION
Genetic Algorithm is proven to be very effective compared to gradient descent for finding global optimum in both unimodal and multimodal problem space. Considering the diverse domain of machine learning GA has immense potential of being utilized both in classical machine learning as well as deep learning. Due to its population-based approach, excessive memory consumption of GA is considered as a bottleneck towards its use in large scale problem. The implementation approach presented here would minimize memory wastage. Better memory utilization has been proven mathematically, which is improved from 12.5% to around 90%. Pseudocode is also provided to demonstrate the feasibility of the approach.