Efficient Fitness Function Computation of Genetic Algorithm in Virtual Machine Placement for Greener Data Centers

摘要

Energy efficiency is a critical issue in the management and operation of data centers, which form the backbone of cloud computing. Virtual machine (VM) placement has a significant impact on energy efficiency improvement for data centers. Among various methods to solve the VM placement problem, genetic algorithm (GA) has been well accepted for its quality of solutions. However, GA is also computationally demanding, particularly in its fitness, limiting further improvement in energy efficiency of data centers in the scenarios where a fast solution is required. To address this issue, this paper formulates the VM placement problem for energy efficiency as a constrained optimization problem. Then, employing GA to solve the optimization, it presents an approach for efficient computation of GA fitness function. The improved computational efficiency is achieved through a new data structure design, which reduces the complexity of the computation from quadratic to linear, to the input size of the problem. Experimental studies show a huge computation time saving from our approach over the existing technique, which is basically Brute-force.