# Balancer Genetic Algorithm--A Novel Task Scheduling Optimization Approach in Cloud Computing
#### 3.2.2 Fitness Function  
BGA is a multi-objective technique to improve makespan and load balancing. Load balancing is achieved through a balancer operation described later. However, fitness function should measure the degree of improvement in both objectives. Hence, a multi-objective relation is unified to combine the effects of two separate inversely proportional objectives. Different mechanisms are opted to balance the load. In balancer GA a load balancing mechanism is inculcated, and the same becomes the basis for measuring the level of load balancing. The fitness function in which makespan and load balancing are combined is defined as:  
\[L(x)=\mathit{makespan}+\mathit{AvgPSUI} \tag{1}\]  
where \(0\leq\mathit{AvgPSUI}\leq 1\) is an average of all percentage of shares used by all VMs for a specific chromosome and is calculated as follows:  
\[\mathit{AvgPSUI}=1-\frac{\sum_{j=1}^{n}\mathit{PSUI}_{j}}{n} \tag{2}\]  
The value of PSU is computed to find the share used by any VM; it depends on number of tasks assigned to any VM, and this assignment is represented through the genes of chromosome. \(\mathit{PSUI}_{j}\) is calculated for each VM, and \(\mathit{ShareUsed}_{j}\) is the sum of the sizes of tasks assigned to VMj. \(\mathit{VMSharej}\) is the maximum share in terms of million instructions that should be mapped to that VM ideally. \(\mathit{PSUI}_{j}\) is calculated as:  
\[\mathit{PSUI}_{j}=\frac{\mathit{ShareUsed}_{j}}{\mathit{VMSharej}}\times 100 \tag{3}\]  
In order to keep \(\mathit{PSUI}_{j}\) within 100%, we use:  
\[\mathit{if}(\mathit{PSUI}_{j}>100)\] \[\mathit{PSUI}_{j}=\frac{100-(\mathit{PSUI}_{j}-100)}{100}\] \[\mathit{if}(\mathit{PSUI}_{j}<0)\] \[\mathit{PSUI}_{j}=0\] \[\mathit{else}\] \[\mathit{PSUI}_{j}=\frac{\mathit{PSUI}_{j}}{100}\]  
Equation (5) presents the formulation of \(\mathit{ShareUsed}_{j}\) by any VM, and it is based on accumulated size of tasks assigned to that particular VM.  
\[\mathit{ShareUsed}_{j}=\Sigma_{i=1}^{n}(\mathit{tasksize}_{i}\times\mathit{ Map}[i,j]), \tag{5}\]  
where \(\mathit{Map}[i,j]\) is a binary matrix that reflects the mapping of task 'i' to VM 'j', with 1 shows mapping and 0 shows no mapping.  
Ideally a VM should obtain the size of tasks based on the computational power of VM in mips, i.e., \(\mathit{VM}_{j}.\mathit{mips}\) as compared to other VMs. Furthermore, \(\mathit{ShareRatio}_{(\mathit{vm}_{j})}\) is a ratio that is used in the computation of maximum size of tasks in million instructions to be mapped to that \(\mathit{VM}_{j}\). The following equations have been used to calculate these ratios:  
\[\mathit{VMSharej}_{j}=\Sigma_{i=1}^{m}(\mathit{task}_{i})\times\mathit{ ShareRatio}_{(\mathit{vm}_{j})} \tag{6}\]  
\[\mathit{ShareRatio}_{(\mathit{vm}_{j})}=\frac{\mathit{VM}_{j}.\mathit{mips}}{ \Sigma_{j=1}^{n}(\mathit{VM}_{j}.\mathit{mips})} \tag{7}\]Power of all available VMs is summed, and then the individual power of VM is divided by the sum of power to compute \(\mathit{ShareRatio}_{\langle}\mathit{vm}_{j\rangle}\). The fitness function in BGA, namely \"LoadBalance\", is a minimization function, as makespan is a minimization value, and \(\mathit{AvgPSU}\) is also converted accordingly as expressed already. The value of \(\mathit{AvgPSU}\) is added to makespan, and it helps to find a solution where both objectives are improved. However, there is no advantage of better load balancing when makespan is not so good. To address this, additional information of load balancing is added to the value of makespan, and a novel load balancing mechanism is formulated. Algorithm 2 details the LoadBalance process devised by BGA.