Keywords

1 Introduction

Genetic algorithms (GAs) have been successfully applied to various optimization problems where one intends to find an optimum or approximate solution to a problem that has a huge size of solution space. However, one of the major concerns in using evolutionary algorithms to search a complex state space is the problem of premature convergence, especially for combinatorial optimization problems like multidimensional knapsack problem (MKP), where the landscape is multipeaked; the probability of search sticking to local optima is all the more high. Because genetic programming is highly stochastic, we do not expect to obtain clear rules about exact levels of diversity. We aim to draw general conclusions and “rules of thumb” from the investigation of evolving populations with different measures of diversity. Given a specific landscape structure—defined by the search space, objective function, then relying on problem-specific knowledge for navigating this structure in order to extract helpful information from the search space, would make the optimization faster and more effective. This paper investigates the characteristic issues of BTCS [1] (which incorporates this strategy) and compares it with IHAGA [2] for solving test instances of combinatorial optimization problem on MKP. The simulation results show that the proposed strategy significantly improves the computational efficiency of GAs. The rest of the chapter is organized as follows. In the section that follows, a brief review of the BTCS scheme and the research work going on in the field of using adaptive crossover and mutation operators for achieving diversity is provided. Section 3 describes the BTCS bucket updation phase vis-a-vis population diversity. Experimental results are presented in Sect. 4. Section 5 summarizes the main contributions of the chapter.

2 Related Work

2.1 Binary Trie Coding Scheme

Binary trie coding scheme [BTCS] creates and maintains a diverse population of highly fit individuals capable of adapting quickly to fitness landscape change [1]. BTCS provides three major contributions related to duplicate elimination and premature convergence in a steady-state GA. The first contribution of BTCS is the virtually compressed binary trie structure (VCBT). VCBT when integrated with GA proves to be beneficial in determining duplicates among all the generations and replacing them with unique individuals [1, 3]. The second contribution is to demonstrate that preventing duplicates results in improved performance. It effectively avoids what is usually a difficult trade-off between achieving fast search and sustaining diversity and thereby provides means to avoid premature convergence. The third contribution of BTCS is that it relies on problem-specific knowledge in fragmenting the search space into feasible and infeasible regions and then pruning the infeasible regions. This chapter discusses as to how bucket updation phase of BTCS incorporates the effective measures pertaining to population diversity without using adaptive crossover and mutation operators.

2.2 Adaptive Crossover and Mutation Rate

The significance of crossover operator in controlling GA performance has long been acknowledged in GA research which can be dated back to 1980s [4]. A number of guidelines exist in the literature for setting the values of crossover probability [5]. Some studies particularly focused on finding optimal crossover rates [6]. These heralded the need for self-adaption of the crossover or mutation rates. In [7], an adaptive genetic algorithm was proposed, in which crossover and mutation probabilities were varied according to the fitness values of the solutions. There were also works on devising adaptive crossover operators instead of varying the crossover rates [8]. Several operators were employed, and the probabilities of applying each operator were adapted according to the performance of the offsprings generated by the operator. Since then, several similar works have also been done [9].

The choice of mutation rate is also critical to GA’s performance [10]. Various researchers have come up with novel approaches to implement the adaptive mutation into a GA. Some approaches to adaptive mutation control employ parent fitness in determining mutation probability [11]. If selected, highly fit individuals undergo low levels of mutation (minimal disruption), while low-fitness individuals are subjected to large rates of disruptive mutation. A measure of population diversity is employed by [12] and [13] in adapting mutation probabilities. In a similar vein, Zhang et al. [14] adapt crossover and mutation according to parameters extracted from a K-means clustering algorithm. Thus, many researchers have emphasized on using adaptive mutation so as to improve GA’s performance as it facilitates the finding of global optimum more efficiently [15].

Although the adaptive crossover and mutation rates are hot spots in the study of genetic search, the BTCS scheme proposed by us [1] does not explicitly employ any scheme to adaptively mutate or crossover. For analyzing the robustness of BTCS, we compare it with informed hybrid adaptive genetic algorithm (IHAGA). This scheme works by adjusting its cross-adaptive rate and mutation rate according to the situation surrounding the fitness of the individual [2]. In the course of crossover and mutation, the probabilities of crossover and mutation are adjusted adaptively according to the following formulas:

$$\begin{aligned} Pc&=\left\{ \begin{array}{ll} \displaystyle \frac{Pc_{\text {max}}-Pc_{\text {min}}}{1+\text {exp}\left( {\displaystyle \textit{Ax}\left( {\frac{2\left( {f^{{\prime }}-f_{\text {avg}}}\right) }{f_{\text {max}}-f_{\text {avg}}}-1}\right) }\right) }+Pc_{\text {min}} &{} {f^{{\prime }}\ge f_{\text {avg}}} \\ {Pc_{\text {min}} } &{} {f^{{\prime }}\le \quad \textit{f}_{\text {avg}} }\end{array}\right. \\ Pm&=\left\{ {{\begin{array}{ll} {\displaystyle \frac{Pm_{\text {max}} -Pm_{\text {min}} }{1+\text {exp}\left( {\displaystyle \textit{Ax}\left( {\frac{2\left( {f^{{\prime }}-f_{\text {avg}} } \right) }{f_{\text {max}} -f_{\text {avg}} }-1} \right) } \right) }+Pm_{\text {min}}} &{} {f^{{\prime }} \ge f_{\text {avg}}} \\ {Pm_{\text {min}}} &{} {f^{{\prime }}\le f_{\text {avg}} }\end{array} }} \right. \end{aligned}$$

where Pc \(_{\text {max}}\) and Pc \(_{\text {min}}\) denote the lower limit and the upper limit of probability of crossover, respectively. \(\textit{f}_{\text {max}}\) and f \(_{\text {avg}}\) denote the maximal fitness and the average fitness of population, respectively, f’ denotes the higher fitness of two crossover individuals, f denotes the fitness of the individuals, and A = 9.903438 [2].

3 BTCS Bucket Updation Phase

3.1 Buckets and Their Significance

The buckets correspond to the leaf nodes in a VCBT [1, 3]. The aim of buckets is to maintain a continuous presence on as many peaks as possible. Population’s spatial information is obtained with computationally inexpensive buckets. It provides important information in addition to the address of the trie structure existing under it. This information is used to identify potentially local convergence. Buckets are significant in dividing the population into an exploration section and exploitation section. It monitors and measures diversity at synchronized time intervals and accordingly attempts to control or promote diversity during the evolution. Identifying such measures allows better prediction for run performance and improved understanding of the population and enables the design of efficient operators.

3.2 Bucket Updation

The contribution of updation phase in the BTCS scheme is twofold [1, 3]. The first contribution of updation phase is to manage the size of VCBT structure. The size of VCBT structure can be kept small by pruning fully explored regions of the search space. The second contribution is to monitor convergence and introduce diversity so as to avoid local entrapment.

3.2.1 Guided Crossover Operator

The proposed procedure works by randomly selecting buckets with criterion value 1, and then exchanges information by copying their best strings [1, 3]. The copying of best feasible boundary solution of one to another is done only if (new bucket_sum + old bucket_best_sum) are feasible and new bucket_sum is greater than old bucket_sum. Doing this restricts the copying of strings between any two selected buckets randomly. Bucket_sum and bucket_best_sum are two variables that are unique to each bucket. They are used for storing the sum of included objects from root to bucket_position and sum of bucket + 1 position till n (the number of objects), respectively. GA with the proposed method distributes the individuals more widely compared to simple GA, where the individuals represent the local optima for that region. The aim is to identify feasible regions in the landscape that could replace less fit individuals by more promising samples from the unexplored sections of the search space. This prevents entrapment in local optima by including new individuals from the unexplored regions of the search space.

Table 1 Average execution time of BTCS in comparison with IHAGA
Full size table

3.2.2 Adaptive Selection Parameter Control

This takes place when there is some form of feedback from the search that serves as input to the mechanism used to determine the change in the strategy parameters. During this phase, the avg corresponding to the worst and best individuals within that bucket is checked. It is computed as the average of all the individuals within that bucket. The new avg value will drop if more boundary solutions between the worst and average interval are generated and would increase if more boundary solutions between average and best interval are generated. During this phase, that bucket is selected, whose new avg has increased and at least approximately more than 60 % of the region within that bucket has already been explored. The aim of phase 2 in bucket updation is to prevent the unnecessary delay caused in exploring those regions of search space where the probability of best solution to exist is very limited. The phase 2 describes the buckets’ solution space diversity from a fitness perspective, i.e., a measure of diversity of healthy individuals. BDS Bucket Updation employs ASPC to regulate selection pressure. ASPC’s objective is to create a diversity of health in the population, i.e., the diversity of high-fitness individuals.

Table 2 Percentage gaps for BTCS and IHAGA
Full size table

4 Experimental Results

Tables 1 and 2 illustrate the comparison of results of BTCS with those of IHAGA [2] for solving the MKP. The results of BTCS and IHAGA are based on our own computations. Table 1 provides the average best solution time (ABST) and the average execution time (AET) for both BTCS and IHAGA. The bold highlights in Table 1 show the optimal average execution time among the two for varying n and m values, where n is the number of objects and m is the number of constraints. It is clear from Table 1 that IHAGA outperforms BTCS computationally, for smaller values of n. The cost of constructing VCBT results in an increase in the average execution time. However, for larger instances, despite the time utilized in the construction of VCBT structure, BTCS is effective in reaching the optimal solution in comparison with IHAGA. The ability to work with unique boundary individuals facilitates faster convergence. The probability of recurrence of individuals in the subsequent generations results in deviation from path, leading to optimality, for larger set of individuals in the case of IHAGA despite its ability to guide the search. Table 2 further provides the average percentage gaps for the two approaches. For both, the BTCS and IHAGA, the percentage gaps (100 \(\times \) (optimum LP – optimum GA)/optimum LP) relative to the solution of LP relaxation were computed. Here GA refers to special cases of GA, i.e., BTCS and IHAGA. It can be inferred from the results of Table 2 that BTCS outperforms IHAGA for all test instances under consideration. BTCS has provided better coverage of the search space and has been found to be successful in providing solutions of better quality in comparison with IHAGA.

5 Conclusion

The aim of updation phase in the BTCS scheme has been the exploring of promising regions while concentrating the search on hyperplanes that are likely to contain good solutions. The GCO and ASPC focus on extracting information about the selected buckets before deciding on the introduction of diversity. Its advantage is that at the point of near convergence, late in a GA run, such diversion reduces the probability of GA to entrap in local convergence and thus provides better solutions.

In our approach, we have not used a mutation parameter, which should be adapted explicitly. Instead, it is the principle of working with unique chromosomes (or individuals) in the VCBT structure, which guarantees automatic mutation. Furthermore, our approach still concentrates on using one-point crossover operator with a fixed probability of 0.70. This is attributed to the deeper nature of BTCS scheme, which permits only good optimal solutions from the search space to participate in the process of evolution. Working with unique boundary solutions assists in maintaining an optimum level of diversity among the individuals.