key: cord-0047500-dlooiipf authors: Jiang, Jingzhou; Xiong, Xiaojun; Ou, Yikun; Wang, Hong title: An Improved Bacterial Foraging Optimization with Differential and Poisson Distribution Strategy and its Application to Nurse Scheduling Problem date: 2020-06-22 journal: Advances in Swarm Intelligence DOI: 10.1007/978-3-030-53956-6_28 sha: 6c00766dfa994b01e940c9513467a7bf6278e1e4 doc_id: 47500 cord_uid: dlooiipf Bacterial Foraging Optimization (BFO) has been predominately applied to some real-world problems, but this method has poor convergence speed over complex optimization problems. In this paper, an improved Bacterial Foraging Optimization with Differential and Poisson Distribution strategies (PDBFO) is proposed to promote the insufficiency of BFO. In PDBFO, the step size of bacteria is segmented and adjusted in accordance with fitness value to accelerate convergence and enhance the search capability. Moreover, the differential operator and the Poisson Distribution strategy are incorporated to enrich individual diversity, which prevents algorithm from being trapped in the local optimum. Experimental simulations on eleven benchmark functions demonstrate that the proposed PDBFO has better convergence behavior in comparison to other six algorithms. Additionally, to verify the effectiveness of the method in solving the real-world complex problems, the PDBFO is also applied to the Nurse Scheduling Problem (NSP). Results indicate that the proposed PDBFO is more effective in obtaining the optimal solutions by comparing with other algorithms. In a seminal paper published in 2002, Passino showed how bacterial individuals and groups find nutrients and how to model it as a distributed optimization process, which he named the Bacterial Foraging Optimization (BFO) [1] . The algorithm is designed to simulate foraging behavior of animals in nature, which has excellent capability to search optimal value of functions with steep function images [2] . Moreover, in the standard BFO, bacteria can avoid falling into the local optimum to some extent and also cooperating [3] . However, this approach often leads to the problem of slow convergence speed [1] . In recent decades, many researchers have optimized BFO to enhance the performance. In the improvement of BFO scholars focus on two aspects: BFO's operational strategy and algorithm combination. In terms of algorithm strategy improvement, Mishra et al. combined the fuzzy rule system of Takagi-Sugeno (TS) in the BFO and then put forward a Fuzzy Bacterial Foraging (FBF) algorithm [4] . Besides, compared with classical algorithms, adaptive chemotactic operators have better performance. Ben Niu proposed an improved BFO with adaptive chemotaixs step and a non-linearly decreasing exponential modulation model [5] . The BFO of automatic chemoattractant step size is brought up by Majhi [6] . In regards to algorithm combination, Tang suggested a multi-level threshold method using the modified Bacterial Foraging Optimization (MBFO) [7] so as to enhance the practicability of the optimal threshold technology. Researchers found that bacteria could learn from the best position in the population by integrating Particle Swarm Optimization (PSO) into each chemotactic step, which enhanced the global search capability of the algorithm [8] . D.H. Kim et al. combined the crossover and mutation operators of the Genetic Algorithm (GA) with the BFO [9] . Luh considered biological evolution and came up with Bacterial Evolutionary Algorithm (BEA) [10] . Combining the Bacterial Foraging and Particle Swarm Optimization, Biswas proposed the hybrid optimization algorithm and applied it to solve the optimization of multi-modal functions [11] . Despite the great efforts of the researchers, the problems of premature convergence and slow convergence speed remain tricky. In order to promote the development of BFO algorithm, this paper proposes an improved BFO with Differential and Poisson Distribution strategies (PDBFO) to shed some light on the problems. To begin with, differential operators are incorporated into standard BFO to increase the convergence accuracy. Meanwhile, the segmentation step size change strategy is adopted. Finally, the Poisson Distribution strategy is used to disperse the bacteria. Optimization algorithms are widely used to solve practical problems with high complexity. Alireza Goli applied the Accelerated Cuckoo Algorithm to the vehicle routing problem [12] . Precup, R.E. suggests the use of Grey Wolf Optimizer algorithms to optimize the parameters of Takagi-Sugeno proportionalintegral-fuzzy controllers [13] . To further demonstrate the effectiveness of PDBFO in solving the real-world problem, a real Nurse Scheduling Problem (NSP) which improves the working efficiency and quality of nurses is employed [14] . This paper is organized as follows. Section 2 introduces the standard BFO algorithm. Then, the proposed algorithm is illustrated in details in Sect. 3. Section 4 presents the model of NSP. Section 5 shows the performance comparisons. Finally, conclusions and further work are presented in Sect. 6. Chemotaxis is the most important process of BFO, in which bacteria gradually approach the optimal value through rotation and swimming. This process simulates the behaviour of swimming and tumbling through flagella of E. coll. Suppose θ i (j, k, l) represents the ith bacterium at jth chemotactic, kth reproductive, and lth elimination-dispersal process. The movement of ith bacterium is expressed as follows: where C (i) > 0 represents the step size of each step forward, and ϕ (j) represents a random forward direction vector selected after tumbling. For reproduction, bacteria are ranked according to their health degree Jhealth. The smaller Jhealth is, the healthier the bacterium is. The larger half population will be replaced by the better half. In this way, the population of bacteria remains the same. The algorithm runs N re times reproduction operations. The health degree of bacteria Jhealth is calculated as follows: where J represents fitness value computed by objective function, i represents each individual, j represents the number of chemotactic, k represents the number of reproduction and l represents the number of migration. In the evolutionary process, elimination and dispersal events may occur, which bacteria in one area are killed or a group of them are dispersed to a new environment. Dispersal may disrupt chemotaxis, whereas may also assist chemotaxis since it may direct the bacteria approaching better places with fruitful nutrition. This operation simulates the migration of bacteria to new environments by water currents or other organisms and the bacteria will be dispersed to random locations within the search area. The algorithm runs the dispel operation N ed times. The specific operation is to give a fixed value of P ed which is chosen within [0,1]. When the random number of bacterial individual is less than P ed , the bacteria will die. Otherwise, a new individual will be generated randomly so as to achieve the purpose of migration. In order to improve the search capability and convergence speed of the BFO, step size segmentation strategies are introduced by adjusting the step size according to the fitness values. Additionally, the differential operators and greedy selection strategies are employed at the end of swimming operations. During the migration process, Poisson Distribution strategy is used to choose the individuals to be dispelled. The Pseudocode of PDBFO has been provided in Algorithm 1. In [15] , experiment results have indicated that with the change of the current fitness value, changing of Chemotaxis step size can lead to better convergence performance in comparison to the case when the step size is fixed. In this paper, Chemotaxis step size is exploited by adopting a segmentation strategy. The fitness values of the bacteria are sorted in ascending order. Individuals with the smaller fitness values indicate good localization and could be assigned with small step size, whereas individuals with larger fitness values indicate poor bacterial localization and are assigned with a large step size. Thus, the Chemotaxis step size can be adjusted as follows: where S represents the population number, N c is the total number of swimming, j is the current swimming times, and C represents the step size. From BFO, we can find that the chemotactic operator searches the field through random movement to ensure the local search capability of bacteria. However, the bacteria do not make full use of the information of other bacteria in the environment. Consequently, the convergence speed of the algorithm is slow, resulting in premature convergence of the algorithm and difficulty in obtaining the global optimal [16] . Therefore, differential operator and greedy selection mechanism are embedded in the proposed algorithm. After the swimming operation, the bacteria enter the stage of differential operation. The differential vector is established first, and then the vector is synthesized with the individual to generate the new individual. Then the fitness values of each new individual and the corresponding original individual are compared, and the greedy strategy is used to retain the better performing individuals [17] . In addition, an adaptive scaling operator F is introduced in the process of generating intermediate individuals. The adaptive scaling factor changes according to the following equation: where, F 0 is the initial mutation operator, F 0 = 0.4. N c and j represent the total number of chemotaxis and the current number of chemotaxis. The generation equation of intermediate individuals is where, G is the intermediate individual, and P is the corresponding original individual. R 1 and R 2 are two random individuals which are different from P . The selection process is expressed as follows: Compute F by Eq.(4) and G i by Eq. (5) 12 Select G i and P i by Eq. (6) Elimination-dispersal is an integral part of BFO. By means of eliminationdispersal, the bacteria trapped in local optimum can reposition themselves to avoid premature convergence. Elimination-dispersal makes the algorithm have a better random searching capability, and increases the diversity of the population. However, for high-dimensional optimization problems, elimination-dispersal will greatly slow down the convergence speed due to the increasing of dimensionality and complexity. Worse still, it is possible to drive away the best-performing bacteria, resulting in redundant computation [18] . This paper proposes a bacterial selection mechanism based on Poisson Distribution (PD) strategy to solve this problem. When the algorithm enters the dissipation process, the bacteria are firstly sorted according to the fitness value from small to large. Generate S random numbers that conform to the PD, and then compare the serial number of the bacteria with the corresponding random number to determine whether the bacterium should be dispersed. Through this mechanism, it is possible to ensure that most of the excellent bacteria will not be dispersed, and the bad bacteria will have the opportunity to be retained for further search. The probability function for the PD is where k is a random number, λ is the mean and variance of the PD. After experiments, when λ takes 25, the algorithm performs better. NSP refers to scheduling a specific group of nurses within a given scheduling period. The scheduling of nurses should meet some constraints (such as hard and soft constraints) and minimize the total salary of nurses [19] . The worksheet of nurse can be probably divided into three kinds: the early shift (0a. where, nn is the total number of nurses, sk is the grade, ss is the type of shifts and sd is the period of scheduling. x ijkd represents the i nurse belonging to j level has k shift in the d day, w j k is the wage of nurse on the k shift at the j level and m jkd means the amount of unsatisfied shifts. And c is the penalty coefficient, whose value is 1000. Equations (9) (10) (11) are hard constraints of NSP and Eq. 12 is the soft constraint: Equation (9) means that each nurse can have no more than one shift per day. Equation (10) represents each nurse cannot be on consecutive shifts within two days. Equation (11) presents that the working hour of nurses cannot exceed the lower or upper limit in a scheduling period. Equation (12) shows that the number of nurses on one shift is no less than the actual demand. This section illustrates the PDBFO's performance and comparisons among the proposed PDBFO and the other BFOs, the GA [20] , the HCO [21] and the PSO [22] . In this experiment, for above algorithms, the running times is 30, the swarm size is 50, 10000 is the maximum iterations and the dimension of the search space is 30. Specifically, as for GA, the crossover probability is 0.8 and the mutation probability is 0.1. While for BFO methods, the number of swimming, chemotaxis, reproduction and elimination-dispersal are respectively N s = 4, N c = 1000, N re = 5 and N ed = 2. In addition, in PDBFO, the λ in Eq. (7) is 25 and the F 0 in Eq. (4) is 0.4. While for PSO, the parameter setting is c 1 = c 2 = 1.5, w = 0.8. More parameters settings of HCO is: the maximum flow times is 3, the evaporation and rainfall probability is 0.2. We have selected eleven well-known benchmark functions [23] . Table 1 summarizes the search scope of all functions. Table 2 provides the average results and the variances on benchmark functions over 30 runs. For the sake of observation, the results are treated with logarithms. Noted that the mean of minimum values and the variance of each group have been bolded to highlight the best performing algorithm. From Table 2 and convergence Fig. 1 , it can be observed that the PDBFO outperforms other algorithms. For one thing, PDBFO obtains high quality mean of results in comparison to those of other algorithms in most cases. Although PDBFO performs worse than GA in f 2 , it still has the edge over its counterparts. When others BFOs, GA, PSO and HCO find a solution that is close to the optimal value, they get stuck in poor local optimal and have trouble getting rid of it, while PDBFO can improved its solutions steadily (such as in f 3 , f 4 and f 6 ). Because differential operators and Poisson distribution strategies keep PDBFO from falling into poor local optima. Consequently, the proposed PDBFO has desirable global search capability and strong robustness. For another thing, although the convergence speed of PDBFO is slower than GA (such as in f 2 and f 7 ) or PSO (such as in f 9 ) in the early stage of some cases, PDBFO has a satisfactory convergence speed in comparison to other BFOs. Furthermore, PDBFO also has excellent performance in terms of stability. As can be seen from Table 2 , in most cases, the variance given by PDBFO is much smaller than the corresponding variance given by other algorithms, which reflects that the PDBFO comes with very small volatility. Except that the variance of PDBFO is greater than GA in f 2 , PDBFO shows sufficiently competitive stability in the other ten benchmark function experiments. Overall, the PDBFO maintains splendid global searching capability and satisfactory convergence speed in most benchmark function experiments and hence it is more competitive than other algorithms. In addition, the low variance of experimental results computed by PDBFO indicates that it is capable of delivering stable results. PDBFO is compared with other BFOs, PSO, GA and HCO on solving the Nurse Scheduling Problem in this experiment. The schedule of 20 nurses for a week will be presented after calculation. Equation (8) is the objective function. The Function dimension is 30 dimension and the number of iterations is 5000. As it is shown in Fig. 2 , the proposed PDBFO has an edge over other algorithms on the Nurse Scheduling Problem. PDBFO has a better searching capability and convergence speed. An efficient shifts roster is shown in Table 3 to meet the needs of health care as well as improve the job satisfaction of nurses. The combination of scientific and reasonable nurse scheduling model and PDBFO can replace the low efficiency and low quality of manual scheduling scheme, contributing to enhancing the availability and optimization of the scheduling shifts. Due to the excellent search capability of PDBFO, an optimal scheduling scheme is more likely to be realized. PDBFO algorithm is proposed to improve the performance of BFO. The convergence speed is accelerated by introducing the change of segmentation step size. The Differential and Poisson Distribution strategies are used to reduce the problem of being trapped into local optimal. The benchmark function experiment results prove that the PDBFO significantly can deliver solutions with good quality and stability. Such an excellent performance demonstrates that PDBFO can balance different nursing requirements efficiently, making it an outstanding choice to solve the Nurse Scheduling Problem. Due to the fact that PDBFO has shortcomings in the benchmark functions experiments, PDBFO can be further improved. More efficient bacterial swimming methods will be sought to improve the rate of convergence. Meanwhile, the improvement direction of the replication process will also be taken into consideration to improve the global optimization capability of the algorithm. Biomimicry of bacterial foraging for distributed optimization and control Solution of optimal power flow subject to security constraints by a new improved bacterial foraging method Traffic signal timing optimization for isolated intersections based on differential evolution bacteria foraging algorithm A hybrid least square-fuzzy bacterial foraging strategy for harmonic estimation Improved BFO with adaptive chemotaxis step for global optimization Efficient prediction of stock market indices using adaptive bacterial foraging optimization (ABFO) and BFO based techniques An improved multilevel thresholding approach based modified bacterial foraging optimization A hybrid PSO-BFO evolutionary algorithm for optimization of fused deposition modelling process parameters A biologically inspired intelligent PID controller tuning for AVR systems A hybrid evolutionary algorithm for the job shop scheduling problem Synergy of PSO and bacterial foraging optimization-a comparative study on numerical benchmarks Accelerated cuckoo optimization algorithm for capacitated vehicle routing problem in competitive conditions Grey wolf optimizer-based approach to the tuning of pi-fuzzy controllers with a reduced process parametric sensitivity An indirect genetic algorithm for a nurse-scheduling problem Bacteria foraging optimization algorithm based on self-adaptative method Numerical optimization using synergetic swarms of foraging bacterial populations Analysis of a greedy active learning strategy Improving bacterial foraging algorithm using non-uniform elimination-dispersal probability distribution Variable neighborhood search algorithm for nurse rostering problem Classifier systems and genetic algorithms Hydrologic cycle optimization part i: background and theory Particle swarm optimization Virtual library of simulation experiments: test functions and datasets