Improvement of genetic algorithm using artificial bee colony

Received Nov 13, 2019 Revised Jan 4, 2020 Accepted Feb 8, 2020 Genetic algorithm (GA) is a part of evolutionary computing that simulates the theory of evolution and natural selection, where this technique depends on a heuristic random search. This algorithm reflects the operation of natural selection, where the fittest individuals are chosen for reproduction so that they produce offspring of the next generation. This paper proposes a method to improve GA using artificial bee colony (GABC). This proposed algorithm was applied to random number generation (RNG), and travelling salesman problem (TSP). The proposed method used to generate initial populations for GA rather than the random generation that used in traditional GA. The results of testing on RNG show that the proposed GABC was better than traditional GA in the mean iteration and the execution time. The results of testing TSP show the superiority of GABC on the traditional GA. The superiority of the GABC is clear in terms of the percentage of error rate, the average length route, and obtaining the shortest route. The programming language Python3 was used in programming the proposed methods.


INTRODUCTION
Artificial intelligence (AI) has been shown great performance in several tasks [1][2][3][4]. Genetic algorithm (GA) is an AI algorithm that is a metaheuristic method invented in 1975 by John Holland [5]. GA has a good global search capability through its operation strategy but has a slow convergence speed [6]. GA shows high performance in complex areas because it works repetitively as the research is likely to focus on typical representative area areas found to produce good behavior [7]. Artificial bee colony (ABC) algorithm was proposed by Karaboga in 2005, which is simple in concept and requires very few initialization parameters to adjust. It has properties of fast convergence speed, good quality of solutions and good robustness, etc., but it also has the disadvantages of early convergence and ease of falling into the local optimum [8].
Important problems that test the efficiency of the algorithm are RNG and TSP, which will be adopted in this thesis as a case study, which will be explained later. Random numbers are numbers generated by an operation that unpredictable it's an outcome and cannot be sequentially reliably reproduced. Random numbers are necessary for a variety of applications. For instance, a popular cryptosystem used keys that should be produced in a random mode [9]. TSP is one of the problems known as NP-hard and is a wellknown problem in the field of computer science and mathematics. This problem has been used in many fields such as semiconductor manufacturing, logistics, and transportation [10].
The rest of the paper is organized as follows: section 2 presented some related work. In section 3, background theories were displayed. In section 4, described the design of the proposed methods. In section 5, experimental results were evaluated, and in the last section, a brief conclusion was presented.

RELATED WORK
There are many pieces of research focusing on improving GA. In Abu-Almash [9] genetic algorithm used to propose a new approach to generate keys. The Five basic tests applied as a fitness function in this experiment for each chromosome. The results proved that the competence of a genetic algorithm for key generation. The optimal representation for the genetic algorithm may be seen by the initial population, size of population, crossover, and mutation. The large population size, little mutation probability, and a high crossover probability.
Alkafaween [11] has presented a new mutation called "IRGIBNNM", that was a hybrid of two mutations which were a random-based mutation and a knowledge-based mutation. The proposed mutation was used to improve the select best mutation (SBM) strategy. The proposed mutation performance was compared with three mutations, additionally to the SBM. The performance of the proposed mutation and the SBM strategy was evaluated on several experiments on twelve TSP instances were conducted. Those instances were taken from the TSPLIB. The experiential results showed the efficiency of the "IRGIBNNM" mutation and the SBM strength where both methods have benefited from the randomization and knowledge provided by the nearest neighbor approach.
Hassanat et al. [12], studied GA was improved by dividing the large-scale TSP problem into small subsets based on regression. This was achieved by using the regression line and its perpendicular line, where cities were grouped into four sub-problems and frequently, each site locates the group in which the city belongs. This process was repeated until the size of the problem became very small or reached a size that cannot be divided. Some famous TSP instances that are derived from TSPLIB were used in experiments. The experiments showed that the proposed method outperformed the other methods using population seeding techniques such as the nearest neighbor based techniques and random techniques regarding mean convergence and error rate.
Alkharji et al. [13] describe a method for using GA to generate random keys for a fully homomorphic encryption scheme (FHE) and check its efficiency. The five statistical tests used in this experiment. This paper explains that the powerful, high-quality, non-repetitive random keys generated by GA will increase the security of FEH schemes, and making it difficult for analysts to break the data. Akter et al. [14] have presented a new crossover operator for solving the TSP. The new crossover consisted of choosing two crossover points and creating new offspring by comparing the cost. The proposed crossover was performed with two traditional crossover operators a sequential crossover operator (SCX) and a triple crossover operator (TCO), and used eight benchmark instances taken from the TSPLIB. The experimental results among the proposed crossover operator, SCX, and TCO showed that the proposed operator has outperformed other operators via providing a solution in less iteration that significantly reducing time and memory.
Gupta et al. [10] have focused on the development of a heuristic technique by combining two common optimization methods: particle swarm (PSO) and GA for TSP. The main inspiration was used to improve a hybrid GA-PSO algorithm to take advantage of PSO such as the self-improvement of individuals and high convergence rate, which compensated the weakness of GA. In the GA-PSO hybrid algorithm, new individuals were generated through the PSO mechanism as well as crossover and mutation operators. The performance of the GA-PSO hybrid algorithm against GA and PSO was used ten TSP standards in terms of finding optimal and execution time. Superior GA-PSO mixed performance between GA and PSO for TSP with concern to the standard, i.e. error rate and average computational time.

PRELIMINARIES 3.1. Genetic algorithm
GA is a non-linear, discrete random process that does not require mathematical formulation. Optima are evolving from generation to another [15]. It has grown as important in solving large complex problems that require a long time according to traditional programming techniques, compared to GA, which has a huge amount of alternative solutions, where the solution is often optimal or near to optimal, over time [16].
At first, GA selects parents from an initial population of chromosomes, and then generates offspring using crossover and mutation. It evaluates all chromosomes to determine their fitness using a fitness function. Then, fitness values were used to determine if chromosomes are retained or disposed of. The least adapted chromosomes are eliminated and the most adapted chromosomes are retained in generating new populations according to the principle of survival of the fittest. The new population replaces the old. The processes are repeated while a specific termination condition satisfied [17]. A simple GA is illustrated in Figure 1.

Artificial bee colony (ABC)
ABC is a method of improving heuristic population-based. The populations in the algorithm represent bees. Every bee searches for the best solution (food resource). It is assumed that each solution is a food resource and the amount of nectar for each resource represents the quality of each solution [18]. ABC is a population-based improvement algorithm that aims to obtain a global minimum [19].
There are two types of bees in the ABC algorithms that are employed and unemployed bees that be consisting of the onlooker bees and the scout bees. The population of the colony usually composed two parts employed that form the first half and the rest include onlooker bees. At first, employed bees exploit the sources of nectar that have been explored, and then provide information to the onlooker bees in the beehive about the location of the food sources they exploit.
After completing the search process by the employed bees, they share information about food sources and their location with the onlooker bees in the dance space. The onlooker bees evaluate information from employed bees and choose the source of food with the probability of nectar. Scouts randomly examine the environment to identify a new food source based on potential external evidence or internal motivation. Algorithm 1 represents the main algorithm of ABC.

Travelling salesman problem
TSP is considered an optimization problem [20]. It is a problem that is an easy description tricky solution and classified as a problem that has not been solved in polynomial time. This problem belongs to NP-hard [21]. The major purpose of this problem is to detect the shortest route through a group of cities (starting from city N and ending in the same city) so that each city is visited only once [22].

Random number generators
Random numbers are a wide field with a strong theoretical and empirical basis. There are many methods used to generate random numbers such as published random number tables and throwing dice. The expansion of digital computers has opened up a new area of inquiry, such as measurement of physical parameters, random numbers of real generators, etc [23]. A valid RNG will generate a sequential series of distributed numbers, at the interval [0, 1]. Using any type of computer algorithm, if we know the initial state of the algorithm which be also called the seed, the sequence of numbers can be determined [24].

Statistical tests
This section presents several tests aimed at measuring the quality of a generator called a random bit generator. The process is done by taking a sampling of the sequence and presenting it to several statistical tests. Every one of the five tests determined whether a particular attribute sequence is likely to actually display a random sequence [25]. Let s=s 0 , s 1 , s 2 …s n−1 is a binary sequence of lengths n. The statistical tests that are used in this paper are [26]: -The frequency (mono-bit) test For a random series of length n, the number 0's should be approximately equal to the number of 1's. The statistic test used in (1): (1) where: s 0 , s 1 indicates the numbers of 0's and 1's in s, respectively.
-Poker test Suppose p is a positive integer where [s/p]≥5, (2 p ), and suppose D=[s/p]. Divide the sequence s into non-overlapping segments D whose length is p, and assume that s i is the number of sequence-type appearances of length p, 1≤I≤2p. In this test, we determine whether the length p sequence shows approximately the same number of times in seconds, as expected for the random sequence. The statistic test used in (3): -Run test The purpose of this test is to determine whether the number is either zeros or numbers from a series of different lengths in the S sequence as expected in a random sequence. The expected number of gaps (or blocks) of length i in a random sequence of length s is ⁄ . Suppose L is equals to the maximum integer i was e i ≥5. Suppose B i and G i are the numbers of block and gap respectively, of length i in n for each i, 1≤i ≤L. The statistic test is calculated by (4):  (5):

THE PROPOSED METHOD
The proposed method has employed an ABC algorithm to improve the population of GA. TSP and RNG are used as a case study. For RNG problem the five statistical tests were used to compute the fitness (each time any test was failed the counter of fitness incremented), such that the random numbers with minimum fitness was token, and the termination criterion of the proposed algorithm has reached the maximum cycle number or all the population is random numbers passed the tests. In TSP, the fitness function in this work was the minimum distance between cities. Total distance for each TSP route for cities n was calculated according to the coordinates of the cities as follows: If the coordinates of any two cities i and k are (xi, yi) and (xk, yk), the distance between them was calculated according to the Euclidean distance equation: Total tour length f can be expressed as follows: where n is the total number of cities. The termination criterion of the proposed algorithm has reached a maximum cycle number.

Improving GA population using ABC for RNG
This method consists of two stages where the first stage focuses on generating random numbers using ABC while the second stage used GA on the random numbers that are generated in the first stage. Previous hybridization work was improved by generating an initial population by ABC then GA was applied to the initial population. At last, the population produced from GA was compared with the initial population and selects the best population (replaces the original parental population) as the new population to the next generation. Reproduction imitated natural selection. ABC generated numbers randomly within the boundaries of the parameters by using the following equation: (8) where; i=1. . .SN, j=1. . .D. Where SN is the solution number and D is the number of optimization parameters The created number was converted to binary. After this, the fitness function in the proposed algorithm was that the five statistical tests might be assigned to the X ij solution by (9), in Algorithm 2.
Fitnessi ∑ (9) where if it the counter value of the solution X ij . Step1: Generate random numbers using Eq. 8 to be the initial population (I). /* using ABC*/ Step2: Evaluate (I) using the five statistical tests to compute their fitness using Eq.9.

Repeat
Step3: Call algorithm (3) that takes I and produce a new solution (S) using GA.
Step4: Evaluate S using the five statistical tests to compute their fitness using Eq. 9.
Step5: Select the best populations between S and I to be a new population (K) according to their fitness. /*Reproduction operation*/ Step6: Until the termination condition is met. /* reached the maximum cycle number or all the population is random numbers passed the tests*/ Step7: Return K. End. Based on the initial population that was generated from the ABC stage GA performed genetic operators to generate new offspring. The genetic process was performed iteratively. The new population was sorted according to its fitness value; the roulette wheel operation was used in the proposed algorithm. An ordered crossover and uniform mutation were used in Algorithm 3. Step1: Sort I according to their fitness value. /* ascending order */ Step2: Select from I the best solutions depending on their fitness value (BS). /* Using roulette wheel selection method*/ Step3: Perform crossover operation between BS to produce new solutions (NS). /* ordered crossover is used, with a crossover rate of 0.8*/ Step 4: If there is a mutation rate, perform mutation operation and update NS. /* uniform mutation was used, with a mutation rate of 0.1*/ Step5: Return NS. End.

Improving GA population using ABC for TSP
This method consists of two stages in the first stage ABC generates a new route by using (8), and in the second stage, the population generated in the first stage will be using GA operators to find the best route. ABC generated random routes by using the index of cities in the default route within the boundaries of the indices by using (8). After this, (7) was used to calculate the distance for each route. The proposed method to find the shortest path is shown in Algorithm 4. Step2: Evaluate the new routes using equation (7). Repeat Step3: Call algorithm (5) that takes NR and produces NS using GA.
At the GA stage, the population produced from the ABC stage was sorted depending on their fitness value. Roulette wheel operation ordered crossover and swap mutation were used in the proposed algorithm to generate a new gene. The GA stage is shown in Algorithm 5. Step1: Sort the NR according to their fitness value. /* ascending order */ Step2: Select from NR the best solutions depending on their fitness value (BS). /* Using roulette wheel selection method*/ Step3: Perform crossover operation between BS to produce new solutions (NS). /* ordered Crossover is used, with a crossover rate of 0.85 */ Step4: If there is a mutation rate, perform the mutation operation/*swap mutation, with a mutation rate of 0.01*/ Step5: Return NS.

EXPERIMENTAL RESULTS AND DISCUSSION
The proposed method was evaluated in this section. Two experiments were carried out where the first experiment aimed to solve RNG while the second problem aimed to solve TSP. Then the solutions were compared with the traditional GA. All computational experiments were conducted on Intel Core i7-4600U 2.70 GHz machine and coded using Python 3 programming language.

RNG experiment parameters
The proposed method tested on data comprises 64, 120,128,192,256 and 512 keys' length respectively. The process was executed 5 times with various recommended parameters for the three variations of data. The population size was 10, 20, and 30, respectively, and the maximum iteration number

2131
(MIN) was 100. The rate of the crossover was 0.8 and the rate of mutation was 0.1. The goal was that all keys were random according to the five statistical tests. It is based on the number of iterations to achieve the best solution (7), and the average time execution.
Mean= ∑ Where the rate is the number of iterations to achieve stop condition, and n is the number of run times. The summary of the simulation is presented in Tables 1-3. Through the tables below, the proposed algorithm showed better results than the traditional GA, as generated random numbers in the least number of iterations and at the lowest execution time, which is what was required to get better solutions in the least time.

TSP experiment parameters
Experiments were performed to calculate the percentage of relative error, the best tour, and the average of the tour. The rate of crossover and rate of mutation was 0.85 and 0.01 respectively. The population size equaled the number of cities, and the number of generations was 5000. The simulation was performed 5 times with various recommended parameters. The percentage of relative error (%) was calculated using (11).
These algorithms were tested using five real TSP problems taken from the TSPLIB which include eil51, st70, pr76, eil76, and rd100 (the numbers attached to the problem names represent the number of cities). The default tour is taken from the library of TSPLIB for each instance. Through a Table 4, the proposed algorithm showed better results than the traditional GA in all five instances, which was what is required to get a speed convergence to an optimal solution in the least time. When comparing the proposed algorithm with the GA-PSO algorithm [6] and IRGIBNNM algorithm [7] it is showed that the results obtained from the proposed algorithm were better than the previous two algorithms. Table 5 showed the comparison among the algorithms.

CONCLUSION
In this paper, GA was improved using ABC (GABC) by using ABC to generate an initial population rather than randomly generation that used in traditional GA. Through experimental results , ‫‬ ‫‬ it was concluded that it using a hybrid between GA with ABC has improved GA in RNG by minimizing the number of iterations in less execution time. And using the five statistical tests has provided a good fitness function for the RNG problem. The final generated keys that were unique (not repeated), random and cryptographically strong (successfully passed the five statistical tests). The result of the proposed method in TSP was compared with traditional GA based on the percentage of relative error rate and the average of the tour's average. Results showed GABC was better than traditional GA with a lower error rate and high convergence rate.