Modified Biogeography Based Optimization

Modified Biogeography Based Optimization Modified Biogeography Based Optimization and enhanced simulated annealing on Travelling Tournament problem. Abstract: This paper shows the implementation of Modified BBO and Extended BBO on Travelling Tournament Problem. We modified the migration step of BBO by using probabilistic measures into it. Conventional BBO is used to solve deterministic problems but when we are dealing with real world problems which are non deterministic Conventional BBO failed to achieve the desired/expected results. Modified BBO is able to handle non deterministic problems which occurs in TTP and considered it as noise. The physical significance of noise in our modified solution is any existing parameter which can affect the fitness of the habitat. We also implemented various models of Extended BBO (Linear and Non linear models) on TTP to achieve desirable results. In this paper we compare the performance of our modified BBO to conventional BBO on TTP problem and compare results with previous methodologies. Introduction BBO is Global optimization method which represents organism distribution in our biological system in terms of mathematical model .BBO is an evolutionary algorithm whose working principle is based upon migration mechanisms of species from one habitat to other depending upon the fitness of the habitat which are favorable to them .The habitat which have high HSI (high suitability index ) have high value of species count .Therefore habitat which have high value of HSI have high emigrating rate; it is ready to send its SIV to other habitat, while the habitat having low value of HSI have low value of species count and their immigrating rate is high ;that is it as ready to accept species towards itself .HSI of a habitat can be affected on the basis of SIV (suitability index variables) which are independent variables. The above diagram illustrates the basic mechanism and relation between immigration curve and emigration curve. Here I is maximum Immigration rate, E is maximum emigration rate, is equilibrium number of species, is emigration rate and is Immigration rate. Modified BBO for TTP: Firstly the question arises why there is need of Modification of BBO .We are dealing with biological issues which are dynamic in nature so we have to modified our solution which can take care all dynamic constraints of nature. Let we have two habitats and .These habitats have their fitness’s as and .Let noise involved in two habitats are and .Due to affect of noise the measured fitness is instead of .If we consider has more fitness than ,and let n1 has huge value than n2 and both high value than and .Therefore the overall fitness becomes: 1.1 1.2 Therefore HB1 accepts the SIV from HB2 as condition of BBO gets satisfied as immigrating habitat fitness is less than emigrating habitat. But population of HB1 is already high due to its high HSI because its fitness is more if don’t consider noise .this immigration should not be done .The BBO migration procedure will corrupted .That’s why we need to modify it. In order to calculate the uncertainties, we use the concept of noisy BBO[]. U= 1.4 E= +1.5 U = 1.6 Where U is the uncertainty of the state estimate, m is the estimated fitness, z is the measured fitness, is the variance of the process noise, and is the variance of the observation noise. The uncertainty and the estimated fitness are the values from the previous iteration step before the most recent fitness measurement is updated. The process noise is assumed to be zero, therefore the uncertainty U is only related and . U = 1.7 U = 1.8 Because 0, now +1 > 1. Therefore +1 .With each step in the Kalman algorithm, the uncertainty U will be reduced according to and . Small value of uncertainty leads to high accuracy of estimated fitness. If limit tends to infinity, than Kalman filter gives an estimate value of the fitness which is equal to the real value. Proposed Modified BBO algorithm: Select habitat with the Probability . If is selected For j=1 to n Select with the probability. If is selected Use rand (0, 1) to select SIV from the habitat and pass it through Modification phases. Choose the best feasible solution based on optimal selection from the output of three Modification Phases. Replace selected SIV with End of if End End of if The above Algorithm solves all the issues that is related with Deterministic Problems. We Map this approach to different variants of BBO that can be classified as its Models. Equations used : The above equation is generalization of Baye’s rule. Probability of a habitat with fitness after accepting a selected SIV greater than fitness given that. is simply equal to where P(switch) is given by : When x > y we obtain: if x The PDF of p is as follows The PDF of q is as follows. In the Modification step we talked about three ways by which we can increase the performance of BBO. These three ways can be described as: No-reevaluation phase: In this phase we have two Habitats as immigrating habitat and act as emigrating habitat. We consider two instances of as and Firstly is going to accept optimal SIV from and then accept another best suitable SIV from and after that their performance get measured on the probabilistic measures as: = Immigrating Habitat Re-evaluation: () Emigrating habitat Re-evaluation: () From the above phases we choose the best option for the immigration step. Secondly we Map this Modification approach to all the variants of Extended BBO and implement it on TTP problem. We Modified the Immigration step and apply this Modification to all the linear and non linear Models of BBO to check whether we are able to achieve the optimal results or not. We Test our algorithm to obtain various results which provide optimal solution for TTP problem. We also apply efficient simulated annealing in order to refine our solution obtained so far. We use this technique after we produced the Schedule, so that we can optimize our solution. Efficient Simulated Annealing is applied to schedule after these five moves: 1. Swap Homes(S, 2. Swap rounds(S, 3. Swap Teams(S, 4. Partial Swap Rounds(S, 5. Partial Swap Teams(S, After these Simulated algorithm is applied on the schedule which is obtained after implementation of above moves in order to obtain best feasible schedule. The cost objective function is used in order to calculate the best feasible schedules Results of implementation of our Modified algorithm for TTP Performance comparison of best feasible cost produced by linear and non linear-models