A Hybrid Genetic Algorithm-Particle Swarm Optimization Approach for Enhanced Text Compression

3.1. Problem Formulation

This problem uses a GA-PSO to design an almost optimal encoding scheme for text compression. In the critical aspects of data storage and transmission, text compression makes one of the significant objectives to reduce the size of the text without losing information in it. Each text character will be encoded in this formulation using a binary string of variable length. The problem is formulated as an optimization problem that aims to minimize the total length of the compressed text by optimizing the encoding for each character.

That is, let T be a source text formed by a set of characters C = {c₁,c₂,…,c_n} with frequencies f(c_i ) respectively. The task is to assign a unique binary string e(c_i ) to each character c_i in such a way, the total length of encoded text would be the least. In mathematical terms, the length L(E) of encoded text using encoding E can be written as:

where |e(c_i)| is the length of the binary string assigned to character c_i, and f(c_i ) is the frequency of c_i in the text. The objective is to minimize L(E).

The proposed method searches for the encoding scheme E* that minimizes L(E) by evolving a population of candidate encoding over successive generations. Each character’s encoding is represented as a random binary string of length from 2 to 5 bits. The population’s encoding has undergone evolution through various genetic operations such as selection, crossover, mutation, and PSO operators.

3.2. Fitness Function

The fitness function is designed to minimize the total length of the encoded text. For a given encoding E, the fitness function F(E) is defined as:

F(E) = L(E) (2)

Thus, a lower F(E) value corresponds to a better encoding scheme.

3.3. GA

The GA [35] is a robust search heuristic inspired by natural selection and genetic principles. This algorithm represents potential solutions to a problem as individuals within a population. These individuals evolve over generations to find the optimal solution to a given problem. In this study, the GA is applied to text compression by optimizing binary encodings for characters, aiming to reduce the overall size of the compressed text.

The GA begins by initializing a population of random encodings, where each encoding represents a binary string of variable length for each character in the text. This population represents potential solutions to the problem, and each individual (or solution) is evaluated using a fitness function. The fitness function is a critical component of the GA, guiding the selection of the best individuals. In this case, the fitness function f(E) is defined as the total length of the compressed text:

where E(c_i) is the binary encoding for character c_i E(c_i) is the length of the binary string, and f(c_i) is the frequency of occurrence of the character c_iin the original text. In this way, the goal of the GA will be the minimization of this fitness function, which directly reduces the size of the encoded text.

The algorithm only proceeds to execute selection after evaluating the fitness of every individual within the population. Often, roulette wheel selection is used to apply selection within GAs, where selection happens with probabilities proportional to their fitness. Thus, better solutions are more likely to be selected to contribute to the next generation. In contrast, less optimal solutions also get a chance, and the diversity in the population is preserved.

After selection, the crossover can generate new individuals, called offspring, resulting from the combination of the encoding of two-parent individuals. In this paper, the single-point crossover is adopted. The crossover point is randomly chosen, and the segments of the binary strings are exchanged between two parents. This approach thus generates new individuals with mixed features from both parents, attempting to explore new areas in the solution space. The second step in GA is provided by mutation, where random changes within the binary encoding of the offspring are performed. This is done by flipping a bit in the encoding string with some probability, which is said to be a mutation rate. Mutation prevents a population from becoming too homogeneous and allows the algorithm to avoid local optima because it maintains genetic variation. Elitism is incorporated in the algorithm, ensuring that the fittest members of each generation are passed on to the next generation without any modification. This will maintain reasonable solutions and accelerate convergence toward the optimal or near-optimal solution.

The GA iterates for a fixed number of generations. It applies to all operators in every generation, namely selection, crossover, mutation, and elitism. Eventually, the population evolves while the algorithm converges to the best binary encoding that minimizes the size of the compressed text. This evolutionary process lets the GA discover efficient encodings, balancing exploring the solution space with exploiting the best solutions.

3.4. PSO

PSO [15] is an optimization in which inspiration for the algorithm was obtained from the collective behavior of swarms. Swarms refer generally to flocks of birds or schools of fish. Each particle of the swarm represents a solution to the problem; therefore, all the particles move within the solution space due to their own best-known position and the entire swarm best known. PSO can be powerful in solving optimization problems, such as text compression because it can efficiently explore large search spaces.

Every particle in the swarm computes the new position and the velocity using the formulas:

v_i(t+1) = wv_i(t)+c₁r₁(p_i−x_i(t))+c₂r₂ (g−x_i (t)) (4)

x_i(t+1) = x_i(t)+v_i(t+1) (5)

In the formulas below, v_i(t) denotes the velocity of particle i at step t, x_i(t) is the position of particle i, p_i does that particle find the personal best position so far, and g represents the global best position the swarm has found. Parameters w, c_1, and c₂ are the weights for inertia, personal influence, and social influence correspondingly, and r₁ and r₂ are random variates introducing diversity.

Due to the variation in their velocities and positions, particles move toward the optimal solution through every iteration. PSO can efficiently search for the best compressive settings in text compression, obtaining a minimum file size while retaining text quality. The algorithm is said to terminate at the swarm’s convergence point to an optimal or near-optimal solution.

3.5. Proposed Method

This work presents a hybrid algorithm incorporating a GA with PSO for optimal text compression. The proposed hybrid algorithm splits the population into two groups at every iteration. Half of the population undergoes the evolutionary process of GA, while the other half is optimized using PSO. This approach represents an effort to combine the strengths of two optimization techniques: One is GA, which effectively explores the diverse solutions space through mutation and crossover operators, and the other is PSO, which converges well in refining solutions with its velocity and position updates. The hybrid method starts with creating random encoding schemes using the GA component. Each scheme here will map characters into a unique bitstring of variable lengths. These encoding schemes then evolve generation by generation through selection, cross-over, and mutation operations to reduce the size of the compressed text. The fitness function ranks each encoding scheme according to the compactness of a given text that it manages to achieve. The best encoding schemes are carried over to the next generation; genetic operations generate newer candidates.

In contrast, the PSO component views the encoding scheme as a particle in a search space. Every particle’s position represents a solution, while its velocity describes the amount of movement in the search space. PSO updates each particle’s position through its personal and global best positions found by the swarm. This, in turn, allows PSO to converge very fast onto promising solutions using efficient exploitation of the search space. It initializes a population of encoding schemes and splits them into one for the GA algorithm to process and the other sub-population for PSO to optimize. After every iteration, the best solutions from both groups are pooled into a new population for the next iteration. This hybrid ensures that, through GA, the algorithm explores many possible solutions and then refines the best ones with PSO. It checks the balance between exploration and exploitation by dividing the population to find the optimal text compression scheme. This approach allows the algorithm to balance exploration and exploitation in finding the optimal text compression scheme.

The flow of the algorithm can be briefed as follows:

This hybrid method is quite suitable for text compression problems, as it efficiently investigates the large and complicated solution space of possible encoding schemes. A combination of GA with PSO may provide solutions to the algorithm such that the obtained solution reduces the length of the compressed text and does so efficiently over multiple iterations. Fig. 1 illustrates the overall process of the proposed method.

Fig. 1. General process of the proposed method.

4.1. System Specification

The methods are executed on Google Colab Pro, a cloud environment offering powerful computational facilities to implement the proposed method. It entertains Colab Pro with GPU and TPU resources, among other benefits, with enhanced RAM and higher execution speed than basic Colab. The advantages derived from this environment are rather attractive for optimization algorithms such as GA-PSO, which deal with massive population sizes and multiple generations.

The virtual machine applied in Colab Pro uses an Intel Xeon processor running at 2.20GHz, with 25GB of RAM and an NVIDIA Tesla P100 or V100 GPU, whichever is available. With this configuration, the hybrid algorithm will have enough processing power to handle large datasets and iterate over many generations within reasonable time limits. Besides, the available disk space is 166 GB; thus, there is ample room to store intermediate results or log experimental data.

Besides that, Google Colab Pro supports Python libraries such as Numpy and Scipy, which provide support for effectively handling data structures and the mathematical operations at the heart of both components of the hybrid algorithm.

4.2. Dataset

GPT-4 has prepared a dataset with four different contexts to assess the hybrid GA-PSO algorithm’s performance. These contexts targeted testing the algorithm on each text length, which could range from very short to very long texts. Each context represents another challenge for the compression algorithm, enabling us to establish how well it can adapt to different compression scenarios.

These contexts provide a comprehensive range of text lengths, from short phrases to entire passages, allowing us to evaluate the hybrid algorithm’s compression ratio, encoding time, and decoding accuracy.

4.3. Evaluated Algorithms

Besides the proposed hybrid GA-PSO, we test five more algorithms to compare with. These include nature-inspired and conventional optimization algorithms, providing a broad set of algorithms for text compression. The WOA [36] is a metaheuristic inspired by the hunting strategy of humpback whales using bubble nets. It is a practical algorithm for searching for global optima in various optimization problems, including text compression. GWO [37] has been inspired by the leadership hierarchy and hunting strategy of grey wolves. This algorithm fulfilled the requirement for the proper balance between exploration and exploitation in the search space.

The AVOA [38] is one of the newer nature-inspired algorithms that model the movement characteristics of vultures when foraging for food. AVOA performed better than some state-of-the-art algorithms in significant, multi-dimensional optimization problems. Along with the nature-driven approaches, two classical algorithms are introduced: a standard GA, which is very popular in optimization problems because it searches a vast solution space using crossover and mutation, and PSO, known as an efficient fine-tuning optimizer in the search space. These two algorithms form the basis for comparing with the hybrid approach.

4.4. Computational Complexity

The time complexity of a proposed algorithm can be expressed in terms of key components such as population size, number of iteration, and the complexity of individual operations such as fitness evaluation, selection, crossover, and mutation. Initially, population generation incurs a complexity of O(P), where P is the population size. Fitness evaluation, applied to each individual in the population, has a complexity of O(G×P×F), where G is the number of generations and F is the time required for the fitness function. The selection process, involving sorting based on fitness, adds O(G×P log P) to the overall complexity. Crossover and mutation operations, with their respective complexities O(C) and O(M), further contribute O(G×P×[C+M]). Combining these factors, the total time complexity T is expressed as O(G×[P×(F+log P+C+M)]). This formula encapsulates the computational costs across all generations and operations involved in the optimization process.

4.5. Numerical Results

This section discusses how we applied the hybrid GA-PSO algorithm to our developed dataset, which includes all text types, from few-word phrases to longer texts. Our evaluation is directed at critical metrics such as compression ratio, encoding time, and decoding accuracy. We assess the algorithm’s effectiveness in diverse text handling with these metrics and deduce its performance levels across different contexts. This work investigates the performance of various algorithms on several datasets, all of which provided different results concerning the size at which data were finally compressed when using a particular method. Further, the subsequent sections compare these methods, clearly defining the best and worst performers regarding compression efficiency. The baseline size of every dataset represents the original size against which the reduction attained by an algorithm will be measured. These results are presented as tables and figures to achieve numeric and visual insights into algorithm performance. The key results are summarized for each table and figure, outlining the difference between the original and compressed size.

Table 1 presents the performance results of different algorithms concerning their performance for compressing an original size of 616 bits. Indeed, the results indicate significant gaps in the compression efficiency of the method proposed here compared to the others. The current paper will present the best compression performance that can get as low as 184 bits; thus, it is the most effective in this context. Other approaches such as GWO and WOA resulted in sizes of 204 bits and 195 bits, respectively, where the poorest performance was given by PSO and GA to sizes of 208 and 209 bits, respectively. For this case, the proposed method performed better; it achieved a minimum compressed size compared to other methods. The compressed sizes of the two differ because of the variation in algorithmic strategies to recognize the patterns and optimize accordingly. Overall, the proposed method performs better than all of these. In contrast, others have very significant size reduction compared to the original, GA and PSO being the worst in this particular context.

TABLE 1: Algorithm Performance Outcomes for Context 1

Results across various algorithms for the original size of 2744 bits are tested and are shown in Table 2 again; the proposed method shows the best compression performance, with the data size being compressed to 744 bits, while GWO and WOA managed to compress it only up to sizes of 847 and 808 bits, respectively. The most exciting thing is that while AVOA and PSO could compress data to 811 and 847 bits, GA could achieve a compressed size of 825 bits. These compressed data size variations can increase these algorithms’ capacity to optimize the minimized data size. The proposed method does the most prominent size reduction, which could do with about a tenfold decrease compared to the original, while the most minor reduction was by PSO and GWO. Therefore, the proposed method has more power in dealing with complicated patterns and redundancy inside big datasets.

TABLE 2: Algorithm performance outcomes for context 2

Furthermore, in Table 3, with an original size of 3624 bits, the best result using the proposed method compressed the data into 1167 bits. Other methods using GWO and WOA compressed the data into 1249 and 1291 bits, respectively, while AVOA and PSO compressed the data into 1337 and 1304, respectively. In this regard, GA was relatively better, compressing the size to 1240 bits. The ranges of the compressed sizes indicate that the proposed method outperforms the other optimization algorithms in terms of efficiency. The performance differences among the methods increase when the dataset size increases, showing that the proposed method is particularly well suited for dealing with significant or complicated data structures and reducing redundancy. Although performing satisfactorily, the GA and PSO are moderately efficient, while GWO and WOA performed a little better but still lag significantly behind the proposed method.

TABLE 3: Algorithm performance outcomes for context 3

In Table 4, the original size of 3608 bits was compressed using different methods; again, the proposed method outperformed with a size reduction of 1404 bits. Other compressed sizes by various algorithms are GWO-1562 bits, WOA-1497 bits, PSO-1449 bits, and GA-1443 bits. Thus, GA reduced the size by 6 bits, a minor enhancement given PSO’s result. It showed that the proposed method had a significant advantage in size reduction compared to the other algorithms; hence, it was the top-performing method for this dataset. The methods vary more subtly in this table compared to the previous ones. The proposed one is outstanding due to its ability to reduce size and retain key data elements. While the other algorithms also show different compression levels, the proposed method remains the most efficient.

TABLE 4: Algorithm performance outcomes for context 4

Fig. 2 compares the original size with that compressed by various methods in a stacked bar plot. In all data sets, the original size is the same; this naturally serves as the apparent reference value against which the various compressed sizes achieved through different algorithms are compared. The stacked bars give evidence about the degree of compression achieved effectively by the techniques, each showing the smallest compressed size across the datasets obtained by the proposed method. This visually evidences just how effective the method proposed herein was in outperforming the others such as GWO, WOA, AVOA, PSO, and GA, which show larger sizes. This is summarized in the relative performances of each method in terms of compression, as shown in Figure below, with the proposed method yielding almost always the best size reduction. The dispersion in the plot also makes clear the variability in the other methods’ performances, with GWO, WOA, and PSO falling behind the proposed method most of the time. GA sometimes yields competitive results but often ends up worse than the proposed method. The figure confirms the numerical data presented in the tables, showing the size difference between the original and each of the methods’ compressed sizes, thereby reconfirming that the proposed method is the most efficient for any of the datasets considered.

Fig. 2. Stacked bar plot comparing original and compressed sizes across different methods.

Table 5 shows the performance results of six optimization algorithms, namely Proposed Method, GWO, WOA, AVOA, PSO, and GA, in terms of time consumption in seconds for four different contexts. For Context 1, AVOA has the best performance with a time of 2.25 s, but GWO is at 2.68 s, the worst. The performance of the Proposed Method was faster than GWO, WOA, and GA, taking 2.45 s but slower compared to AVOA and PSO.

TABLE 5: Algorithm Performance Outcomes based on time consumption criteria (s) for context 1–4

Context 2: The Proposed Method consumed 3.17 s, which defeated GWO, WOA, and GA, with performances over 4 s, whereas AVOA outperformed it at 2.94 s. In Context 3, the Proposed Method again was competitive at 4.27 s, behind only AVOA at 4.00 s yet faster than all other algorithms. Finally, for Context 4, the Proposed Method completed its process in 5.95 s, ranking above all except AVOA, which finished in 5.47 s. GWO was generally the slowest algorithm in most contexts. In general, the Proposed Method did a great job in various contexts and generally came up among the best algorithms when taking into consideration the consumption of time.