Adaptive Hybrid Genetic Algorithm

The research addresses the limitations of traditional genetic algorithms (GAs) where parameters and operators remain fixed throughout the run. The study proposes a novel adaptive hybrid GA to overcome this limitation, allowing parameters and operators to evolve during the execution. The core idea is to enhance GA performance by dynamically selecting between binary and real-coded crossover and mutation operators. The Traveling Salesman Problem (TSP), known for its NP-hard complexity, serves as the benchmark problem. The hypothesis is that an adaptive hybrid GA, capable of using either binary or real operators depending on the evolving search space, will outperform traditional GAs (purely binary or purely real) in finding optimal or near-optimal solutions. Two main variations in adaptation are explored: global (population-wide decision) and local (individual chromosome pair decision). The study uses two datasets – a smaller one (Harrol) expected to converge quickly and a larger one (Bier) to test the algorithm's scalability and robustness across diverse problem instances. The performance is measured by plotting mean and standard deviation of best fitness recorded and running average of best fitness in each generation; variations in curves are used to establish relative performance.

The research delves into the mechanisms for adaptive operator selection within the hybrid GA. The adaptation is achieved by augmenting each chromosome with additional genes that dictate the choice of operator (binary or real) for crossover and mutation. Two key strategies are compared: global adaptation and local adaptation. In global adaptation, the proportion of binary and real operators used in each generation is determined by the overall composition of the population. If, for instance, 70% of the chromosomes favor real operators, approximately 70% of the mating pairs will use real operators for that generation. In local adaptation, each chromosome pair autonomously decides on which operator type to employ, offering a more decentralized and potentially more responsive approach. This study compares the effectiveness of both global and local adaptation in guiding the GA towards better solutions. The choice of operators for both binary and real encoding is also discussed, with consideration given to the properties of each operator and their compatibility with the TSP's constraints. The selection process itself plays a vital role in the evolution of the genetic algorithm; it determines which individuals are chosen for mating and mutation, therefore driving the search toward better solutions.

The experimental design involves comparing the performance of the adaptive hybrid GA against purely binary and purely real GAs. Two datasets are used: Harrol (smaller, faster convergence) and Bier (larger, more challenging). The smaller dataset aids initial parameter tuning and analysis. In the Harrol dataset experiments, optimal parameters were discovered (population size of 100, crossover rate 0.6, and mutation rate 0.01). These parameters were then used for the main experiment on both datasets. For each GA type and dataset, multiple runs are conducted to provide statistically sound results (20 runs for Harrol, 10 for Bier). The primary metric for comparison is the fitness of the best chromosome found in each run and the average fitness throughout generations. Both local and global adaptation schemes are tested. The impact of using a repair mechanism to handle illegal chromosomes produced by binary operators is also assessed. The choice of operators (crossover and mutation) for both binary and real-coded representations is discussed, emphasizing the importance of choosing operators suitable for the TSP's characteristics and constraints.

The results reveal that both local and global adaptation schemes in the hybrid GA show better or comparable performance to the purely real-coded GA, particularly on the Harrol dataset. The purely binary GA underperforms significantly. Notably, local adaptation consistently outperforms global adaptation, suggesting that decentralized decision-making at the chromosome level is more efficient. However, the larger Bier dataset presented a less conclusive picture; the performance was not greatly different for the real, local and global GA's. This might be attributed to an insufficient population size for the global adaptation strategy to be fully effective. Analysis of the generations at which the best solution was found for each GA also reveals trends of when optimal or near-optimal results were obtained for each GA. An interesting phenomenon is observed with the global adaptation strategy; the percentage of binary operators used per generation shows large fluctuations, which wasn't predicted and is speculated to be due to the smaller population size. The results highlight the relative strengths and weaknesses of local versus global adaptation and underscore the importance of population size in achieving effective self-adaptation.

The research concludes that for solving the TSP, the hybrid GA with local adaptation excels in finding optimal solutions, particularly for smaller problem instances. While offering better results, the computational overhead associated with managing the adaptation codes needs further evaluation. For problems where finding a good solution (not necessarily the best) is sufficient, a purely real-coded GA might prove more efficient. Global adaptation, despite its potential, shows limitations due to population size constraints and less consistent results. The study highlights the significant impact of local adaptation in converging toward real-coded operators. Future research involves applying the hybrid GA to a wider array of problems, including larger TSP instances, and investigating online performance metrics to better understand the population dynamics in adaptive GAs. Further exploration of population size effects and alternative adaptation strategies is also recommended.

The literature review begins by establishing the foundational concepts of Genetic Algorithms (GAs). GAs are described as search programs that utilize the principle of "survival of the fittest" to find solutions to complex problems. A GA iteratively evolves a population of candidate solutions (chromosomes) through generations. Each generation involves evaluating the fitness of individuals, selecting high-fitness individuals for reproduction (crossover), and introducing minor random changes (mutation). The three main operators—selection, crossover, and mutation—are described. Selection mechanisms, such as proportional fitness (roulette wheel selection), are discussed, highlighting how fitter individuals have a higher probability of being selected for crossover and mutation. Crossover is explained as a process where two parent chromosomes combine their genetic material to produce offspring, ideally inheriting advantageous traits. Mutation introduces small, random changes to the chromosomes, maintaining diversity and preventing premature convergence to suboptimal solutions. The review highlights the importance of tuning these parameters (population size, crossover rate, and mutation rate) for optimal GA performance.

The review contrasts binary and real encoding schemes. Binary encoding is problem-independent, representing solutions using binary strings, but often requires a larger number of genes for the same problem. Real encoding is problem-specific; the genes directly represent values relevant to the problem, potentially using fewer genes. The implications of these encoding choices on convergence speed, population diversity, and the risk of deception (where low-order building blocks mislead the search) are discussed. The advantages of binary encoding, such as a maximum number of available schemata and problem-independent operators, are noted. However, the limitations of real encoding, such as faster convergence leading to premature loss of diversity and the higher likelihood of poor solutions with a higher cardinality alphabet, are also pointed out. The challenges of handling discrete values in real encoding, where the number of discrete values may not be a power of two, are explained, noting that additional mechanisms might be needed to manage illegal chromosome values.

The section focuses on crossover operators, comparing various binary and real-coded techniques. For binary GAs, n-point crossover is explained, demonstrating how chromosomes are divided into fragments and recombined. The advantages of uniform crossover over single-point and 2-point crossover are mentioned, citing Syswerda's work showing uniform crossover's superior performance, particularly at later stages of a GA run. In contrast, for real-coded GAs, operators must maintain the integrity of the chromosome (no duplicate alleles or missing elements), necessitating problem-specific operators. Several real-coded mutation operators for the Traveling Salesman Problem (TSP) are detailed, including inversion, insertion, displacement, and reciprocal exchange, and their functions explained. The relative difficulty of coding for binary versus real encoded chromosomes is mentioned.

The review examines mutation operators for both binary and real encoding. For binary GAs, a simple bit-flip operator is described, noting its problem-independence. However, the challenges of using this operator with the TSP are explained, highlighting that a bit-flip can easily introduce illegal solutions (duplicate cities). For real encoding, the mutation operators are problem-dependent. The document highlights the four real coded mutation operators (inversion, insertion, displacement and reciprocal exchange) and explains that these operators avoid the need for repair mechanisms, unlike the binary mutation operator. The section further explores constraint management techniques in GAs. Direct constraint management (penalty functions that directly incorporate constraints into fitness evaluation) and indirect constraint management techniques (filtering, repairing, and preserving) are described. The literature review shows that the different methods for handling constraints in GAs have varying effectiveness and computational costs.

The final section of the literature review focuses on self-adaptation in GAs, where parameters like the mutation rate can evolve during the run. The work of Back on self-adapting the mutation rate is discussed, showcasing how appending additional bits to chromosomes to represent the mutation rate can lead to improved performance. This approach allows for optimal mutation rates to emerge naturally through selection. The review also examines Spears' work on adapting crossover operators, using an extra bit in each chromosome to determine the type of crossover to apply. This approach, while effective for binary GAs, is unsuitable for real-coded GAs due to the unique allele requirement in problems like TSP. The tightly coupled approach of embedding adaptation codes within the chromosomes is discussed, along with the concept of global and local adaptation (population-level vs. individual-level decisions), laying the groundwork for the proposed adaptive hybrid GA.

The core of the methodology involves implementing a hybrid genetic algorithm that dynamically switches between binary and real-coded operators. A novel approach is used to integrate adaptation codes directly into the chromosomes. Unlike previous methods that appended adaptation codes to the end of binary chromosomes, this approach works with both binary and real encodings. For the binary GA, a 2-point crossover is selected. The binary mutation operator is the simple random bit flip. For the real-coded GA, the reciprocal exchange mutation operator is chosen for its simplicity and lack of need for additional information besides the mutation rate. This hybrid approach allows the GA to benefit from both the diversity introduced by binary operators and the efficiency of real-coded operators, adapting the operator selection based on the progress of the search.

A crucial aspect of the methodology addresses the constraint management inherent in the Traveling Salesman Problem (TSP). The use of binary operators often leads to illegal solutions (chromosomes with duplicate cities), necessitating a constraint management strategy. A penalty function was initially explored but rejected due to its poor performance (only 1% of the population being legal). Instead, a repair mechanism is employed to handle illegal chromosomes generated by binary operators. This repair mechanism is crucial for two reasons. First, it ensures that the real-coded crossover operator always receives legal parent chromosomes. Second, it allows the entire population to participate in the GA process, improving exploration and preventing the premature loss of potentially useful genetic material. The repair operator either returns the chromosome to its original state or swaps two alleles to eliminate the duplication, making the chromosome valid for the TSP.

The study uses two datasets: Harrol (a smaller dataset enabling faster convergence) and Bier (a larger dataset for comprehensive evaluation). The Harrol dataset allows for initial parameter tuning; various crossover rates (0.2, 0.6, 0.8, 0.95), mutation rates (0.1, 0.01, 0.05, 0.001), and population sizes (10, 500, 1000, 2000) are tested using the local adaptation GA. This process led to the identification of optimal parameters (population size 100, crossover rate 0.6, mutation rate 0.01) for the main experiment. For the main experiments, twenty runs were performed for the Harrol dataset and ten runs for the Bier dataset. Four different GAs are compared: local adaptation GA, global adaptation GA, a purely real GA, and a purely binary GA (with repair). The performance is evaluated based on two key criteria: (a) the best fitness achieved during each run, and (b) the running average fitness over each generation. These data points are plotted, and the shape and relative position of the curves are used to analyze the performance differences among the GAs.

The methodology incorporates two distinct adaptation strategies: global and local adaptation. Both strategies utilize the additional genes in the chromosomes to control operator selection (binary or real). In the global adaptation GA, the overall proportion of binary operators used in each generation is determined by the percentage of chromosomes with the respective adaptation code in the population. In local adaptation, the choice of operators is made independently for each pair of chromosomes selected for mating, creating a more dynamic and localized response to the evolving fitness landscape. The research carefully compares these two strategies to understand their influence on the GA's ability to discover better solutions. The global adaptation strategy, while initially expected to show smoother transitions between operator choices, actually produced unexpectedly high fluctuations across different runs, which are analyzed and discussed in the results section.

The data analysis focuses on comparing performance curves (best fitness and running average fitness) for each GA (local adaptation, global adaptation, purely real, and purely binary with repair) across both datasets. Mean and standard deviation are plotted to assess the statistical significance of the results. The shapes and relative positions of these curves are the key indicators of performance differences. For the Harrol dataset, these analyses show that both local and global adaptation lead to better results than the purely binary GA, with performance on par with the purely real GA. The analysis reveals interesting insights into the differing behaviors of global versus local adaptation. For the Bier dataset, the analysis focuses on comparing the performance of the different GAs, considering the possibility that a small population size might have hindered the global adaptation strategy. The study uses offline performance to evaluate the ability of each GA to consistently produce better solutions from one generation to the next.

The results on the smaller Harrol dataset reveal that both the local and global adaptation GAs outperformed the purely binary GA. The local and global adaptation GAs found solutions comparable to the purely real GA. The performance is analyzed through the plotting of mean and standard deviation for best fitness and running average fitness over generations. The shapes and positions of the curves show that the real GA finds better solutions initially, followed by local adaptation, then global adaptation. By generation 800, all three adaptive and non-adaptive GAs show similar performance. The binary GA, however, consistently lags behind the others, even at generation 1000. This suggests that the hybrid approach, particularly with local adaptation, can effectively balance exploration (from binary operators) and exploitation (from real operators) to achieve better solutions. The consistent superior performance of local adaptation over global adaptation on this dataset is a key finding.

The analysis extends to the larger Bier dataset to assess the scalability and robustness of the different GAs. Comparing the performance curves (best fitness and average fitness), the results show a similar trend to that observed in the Harrol dataset, but with a slower convergence rate. At approximately generations 150-200, the relative positions of the performance curves are similar to the Harrol dataset results at generation 1000. This indicates a scaling effect; the larger dataset requires more generations to achieve the same relative performance. The local adaptation GA again outperforms the global adaptation GA and the purely binary GA, maintaining its consistency across datasets. The finding that the local adaptation strategy is superior to the global adaptation strategy is further reinforced by these results. The observation that the global adaptation GA shows unpredictable fluctuations in the percentage of binary versus real operators used from generation to generation raises questions about the stability of this approach and suggests possible limitations with the smaller population size utilized.

A detailed analysis of the adaptation behavior in the global adaptation GA reveals unexpected results. The proportion of binary operators selected fluctuates significantly across generations, ranging from 0% to 100%, even in runs that ultimately converged to the global minimum. This contrasts with the anticipated convergence to either binary or real operators. The observed oscillations are hypothesized to be caused by a relatively even spread of adaptation codes within the population, leading to unstable operator selection during reproduction. In contrast, the local adaptation GA displays a more consistent and predictable trend, converging towards the dominance of real operators. This supports the findings that locally adapting the operator choice proves more effective and stable than a global approach. The differences in the adaptation behavior between local and global adaptation strategies support the hypothesis that individual selection of operators is a more efficient approach.

The analysis further investigates the generation at which the best chromosome is found for each GA. The results reveal that there is no clear predictive pattern for when the best solution will emerge. The best chromosomes are scattered across generations, and there is no significant difference in the generation at which the best chromosome was found for local and global adaptation GAs, compared to the purely real GA. This shows that, while the local adaptation strategy is superior, it does not necessarily speed up the discovery of the very best solution in terms of number of generations. This observation is further supported by the large standard deviations in the generation at which the best solution was found. The lack of a consistent pattern for the generation of best solutions emphasizes the stochastic nature of GAs and the difficulty in predicting their convergence behavior. The purely binary GA is excluded from this comparison because its performance is significantly inferior to the other three algorithms.

In summary, the results demonstrate the superior performance of the hybrid GA, especially with local adaptation, particularly for smaller problem instances like the Harrol dataset. The local adaptation strategy consistently outperforms its global counterpart, highlighting the benefits of decentralized operator selection. Although both adaptive methods perform better than the purely binary method, their performance is comparable to the purely real GA. The findings suggest that using the hybrid GA is beneficial for finding global minimum solutions, but for merely finding adequate solutions, a purely real GA might suffice, avoiding the overhead of adaptation code management. Further investigation is needed into the influence of population size on the behavior of global adaptation and to extend the research to other problem domains and larger datasets to generalize the findings.

The conclusion emphasizes the effectiveness of the proposed hybrid genetic algorithm, particularly when employing a local adaptation strategy. The results consistently demonstrate its superior performance in finding optimal solutions for the Traveling Salesman Problem (TSP), especially for smaller problem instances. Both local and global adaptation methods outperformed the purely binary GA, achieving comparable results to the purely real GA on the smaller Harrol dataset. However, local adaptation consistently outperformed global adaptation across both datasets. This highlights the advantage of decentralized, chromosome-level decisions regarding operator selection, compared to a population-wide voting system. The unexpected fluctuation in operator selection observed in the global adaptation GA suggests a need for further investigation into the influence of population size and the dynamic interplay of binary and real operators during the search process.

The study provides practical guidance for selecting between the hybrid GA and a purely real-coded GA. For applications where finding the global minimum is paramount, the hybrid GA (with local adaptation) offers a strong advantage. However, the increased computational cost associated with the adaptation codes needs to be weighed against the potential gains in solution quality. If finding a good solution, but not necessarily the optimal one, is the goal, the results suggest that a purely real-coded GA may be a more efficient choice, offering a faster and less computationally expensive alternative. This trade-off between accuracy and computational efficiency is a significant factor to consider when choosing the most suitable approach for a particular problem. The results also highlight the limitations of the purely binary GA, indicating that its performance is not competitive with the other methods tested in this study.

The conclusion outlines several avenues for future research to extend and generalize the findings. Testing the hybrid GA on other problem types beyond the TSP is crucial to validate its effectiveness across a wider range of applications. This would confirm the algorithm's generalizability and robustness. Further experimentation with different TSP sizes will provide more insights into the scaling behavior of the local and global adaptation strategies and their potential limitations in handling significantly larger problem instances. The authors propose to explore the online performance of the algorithm, though acknowledging previous arguments against its usefulness for this specific problem, it may give insights into the population dynamics. Analyzing the online performance would reveal more detailed information on how the populations evolve in local and global adaptation GAs in contrast to purely real GAs.