Introduction
-
To optimize the placement of virtual machines (VMs) in a data center to minimize resource wastage, power consumption, and network transmission delay.
-
To develop an efficient methodology for cloud providers to achieve economic revenue and contribute to developing green data centers.
-
To propose using NSGA-III, a multi-objective evolutionary algorithm, to simultaneously reduce resource wastage, power consumption, and network transmission delay.
-
To compare the performance metrics (Overall Nondominated Vector Generation and Spacing) of the proposed NSGA-III algorithm with other existing multi-objective algorithms, namely VEGA, MOGA, SPEA, and NSGA-II.
-
To validate the results of the proposed algorithm using ANOVA and DMRT statistical tests to ensure the reliability and accuracy of the findings.
Literature survey
Swarm intelligence
Genetic algorithm
Comparison on state of art multi-objective optimization algorithms
Algorithm | Exploration | Exploitation | Convergence Rank | Computational Complexity | Uniqueness | Cons |
---|---|---|---|---|---|---|
Genetic Algorithm (GA) | Crossover and mutation | Selection | 4 | Exponential time complexity | Simple to implement and understand. Can handle complex problems. | Exponential time complexity may not find the optimal solution for all objectives. |
Particle Swarm Optimization (PSO) | Velocity update | Inertia weight and cognitive and social factors | 5 | Quadratic time complexity | Fast and efficient. Can find suitable solutions in a short amount of time. | Slow for small problems, may not find the optimal solution for all objectives. |
Ant Colony Optimization (ACO) | Pheromone evaporation and updating | Ant recruitment and ant selection | 6 | Quadratic time complexity | Robust and scalable. Can handle large problems. | Sensitive to the initial conditions, may not find the optimal solution for all objectives. |
Multi-objective Evolutionary Algorithm (MOEA) | Genetic operators | Selection | 3 | Polynomial time complexity | Can handle multiple objectives simultaneously. It can find the Pareto optimal set. | It can be complex to implement and understand and may not find the optimal solution for all objectives. |
Non-dominated Sorting Genetic Algorithm II (NSGA-II) | Crossover and mutation | Selection | 2 | Polynomial time complexity | Based on the concept of non-dominated sorting. Ensures that the Pareto front is always represented in the population. | It can be slow for minor problems and may not find the optimal solution for all objectives. |
Non-dominated Sorting Genetic Algorithm III (NSGA-III) | Crossover and mutation | Selection | 1 | Polynomial time complexity | It uses a niching mechanism to promote diversity. Ensures that there are enough solutions in each niche of the search space. | Can be slow for small problems, may not find the optimal solution for all objectives. |
Exploration
Exploitation
Convergence
Computation complexity
Extract from the literature
Virtual machine placement objective formulation
Minimize resource wastage
Minimize power consumption
Minimize propagation time
Proposed methodology
Experimental setup
25% | 100 Instances | 200 Instances | |||
---|---|---|---|---|---|
Corr | ALG | ONVG | SP | ONVG | SP |
-0.753 | VEGA | 15.26 | 0.70 | 14.78 | 0.67 |
MOGA | 17.34 | 0.69 | 15.37 | 0.67 | |
SPEA | 16.73 | 0.65 | 16.49 | 0.56 | |
NSGA-II | 20.74 | 0.55 | 18.96 | 0.46 | |
NSGA-III | 28.51 | 0.28 | 26.56 | 0.22 | |
-0.362 | VEGA | 17.07 | 0.79 | 15.49 | 0.77 |
MOGA | 16.17 | 0.66 | 16.80 | 0.63 | |
SPEA | 17.84 | 0.60 | 17.60 | 0.52 | |
NSGA-II | 18.99 | 0.57 | 19.64 | 0.46 | |
NSGA-III | 30.38 | 0.25 | 30.43 | 0.24 | |
-0.054 | VEGA | 17.66 | 0.70 | 15.71 | 0.69 |
MOGA | 15.94 | 0.60 | 16.43 | 0.56 | |
SPEA | 16.81 | 0.59 | 17.37 | 0.50 | |
NSGA-II | 22.66 | 0.48 | 20.78 | 0.44 | |
NSGA-III | 30.67 | 0.22 | 30.95 | 0.24 | |
0.37 | VEGA | 14.71 | 0.68 | 14.77 | 0.60 |
MOGA | 16.45 | 0.53 | 16.17 | 0.49 | |
SPEA | 16.07 | 0.55 | 15.90 | 0.46 | |
NSGA-II | 18.15 | 0.49 | 18.63 | 0.40 | |
NSGA-III | 26.45 | 0.27 | 26.46 | 0.22 | |
0.752 | VEGA | 19.20 | 0.62 | 18.17 | 0.58 |
MOGA | 19.86 | 0.50 | 18.87 | 0.41 | |
SPEA | 19.35 | 0.47 | 19.05 | 0.38 | |
NSGA-II | 22.50 | 0.46 | 21.19 | 0.38 | |
NSGA-III | 33.44 | 0.26 | 32.53 | 0.20 |
35% | 100 Instances | 200 Instances | |||
---|---|---|---|---|---|
Corr | ALG | ONVG | SP | ONVG | SP |
-0.755 | VEGA | 19.05 | 0.78 | 18.23 | 0.68 |
MOGA | 19.01 | 0.69 | 18.33 | 0.62 | |
SPEA | 18.19 | 0.69 | 16.90 | 0.56 | |
NSGA-II | 23.61 | 0.54 | 21.73 | 0.52 | |
NSGA-III | 31.25 | 0.30 | 29.40 | 0.20 | |
-0.372 | VEGA | 18.07 | 0.75 | 18.24 | 0.69 |
MOGA | 21.01 | 0.67 | 19.68 | 0.58 | |
SPEA | 20.07 | 0.59 | 20.27 | 0.51 | |
NSGA-II | 20.34 | 0.48 | 21.27 | 0.44 | |
NSGA-III | 30.45 | 0.28 | 29.11 | 0.26 | |
-0.062 | VEGA | 19.11 | 0.68 | 18.83 | 0.60 |
MOGA | 18.80 | 0.60 | 18.37 | 0.56 | |
SPEA | 21.05 | 0.54 | 19.99 | 0.49 | |
NSGA-II | 23.88 | 0.40 | 22.83 | 0.35 | |
NSGA-III | 37.12 | 0.22 | 35.03 | 0.20 | |
0.384 | VEGA | 14.53 | 0.72 | 14.91 | 0.64 |
MOGA | 18.08 | 0.50 | 15.76 | 0.47 | |
SPEA | 18.85 | 0.54 | 18.46 | 0.47 | |
NSGA-II | 19.75 | 0.45 | 19.85 | 0.43 | |
NSGA-III | 27.95 | 0.28 | 28.61 | 0.19 | |
0.753 | VEGA | 19.97 | 0.62 | 18.79 | 0.50 |
MOGA | 22.19 | 0.47 | 20.59 | 0.41 | |
SPEA | 22.09 | 0.46 | 19.78 | 0.36 | |
NSGA-II | 22.52 | 0.36 | 21.03 | 0.31 | |
NSGA-III | 31.67 | 0.23 | 32.35 | 0.18 |
Performance evaluation and discussions
45% | 100 Instances | 200 Instances | |||
---|---|---|---|---|---|
corr | ALG | ONVG | SP | ONVG | SP |
-0.756 | VEGA | 19.93 | 0.71 | 18.89 | 0.66 |
MOGA | 21.90 | 0.69 | 19.69 | 0.64 | |
SPEA | 20.41 | 0.61 | 20.26 | 0.60 | |
NSGA-II | 24.41 | 0.53 | 23.73 | 0.45 | |
NSGA-III | 31.04 | 0.30 | 31.64 | 0.27 | |
-0.382 | VEGA | 20.02 | 0.74 | 20.05 | 0.68 |
MOGA | 20.08 | 0.69 | 20.69 | 0.60 | |
SPEA | 23.15 | 0.61 | 22.44 | 0.52 | |
NSGA-II | 23.46 | 0.47 | 22.88 | 0.43 | |
NSGA-III | 33.71 | 0.21 | 31.95 | 0.16 | |
-0.059 | VEGA | 20.85 | 0.68 | 21.38 | 0.60 |
MOGA | 20.82 | 0.63 | 19.54 | 0.58 | |
SPEA | 22.56 | 0.49 | 21.17 | 0.42 | |
NSGA-II | 25.25 | 0.41 | 25.01 | 0.32 | |
NSGA-III | 35.95 | 0.25 | 36.53 | 0.18 | |
0.396 | VEGA | 17.30 | 0.70 | 16.49 | 0.66 |
MOGA | 19.14 | 0.54 | 17.96 | 0.47 | |
SPEA | 21.78 | 0.50 | 19.97 | 0.44 | |
NSGA-II | 20.86 | 0.51 | 20.82 | 0.41 | |
NSGA-III | 29.22 | 0.26 | 29.35 | 0.23 | |
0.75 | VEGA | 20.93 | 0.67 | 19.60 | 0.58 |
MOGA | 21.51 | 0.47 | 21.34 | 0.36 | |
SPEA | 20.02 | 0.46 | 20.38 | 0.39 | |
NSGA-II | 22.25 | 0.36 | 22.38 | 0.38 | |
NSGA-III | 34.76 | 0.22 | 33.70 | 0.18 |
ANOVA
Duncan’s multiple range test
ANOVA | ||||||
---|---|---|---|---|---|---|
Source Factor | Sum of Squares | df | Mean Square | F | Sig | |
ONVG | Between Groups | 614.950 | 4 | 153.738 | 41.655 | .000 |
Within Groups | 73.815 | 20 | 3.691 | |||
Total | 688.766 | 24 |
Duncan Multiplier Range Test | ||||
---|---|---|---|---|
Algorithm | N | Subset for alpha = 0.05 | ||
1 | 2 | 3 | ||
NSGA-III | 5 | 29.8900 | ||
NSGA II | 5 | 20.6080 | ||
SPEA | 5 | 17.3600 | ||
MOGA | 5 | 17.1520 | ||
VEGA | 5 | 16.7800 | ||
Sig | 1.000 | 1.000 | 0.657 |
ANOVA | ||||||
---|---|---|---|---|---|---|
Source Factor | Sum of Squares | df | Mean Square | F | Sig | |
ONVG | Between Groups | 618.993 | 4 | 154.748 | 55.882 | .000 |
Within Groups | 55.384 | 20 | 2.769 | |||
Total | 674.377 | 24 |
Duncan Multiplier Range Test | ||||
---|---|---|---|---|
Algorithm | N | Subset for alpha = 0.05 | ||
1 | 2 | 3 | ||
NSGA-III | 5 | 29.3860 | ||
NSGA II | 5 | 19.8400 | ||
SPEA | 5 | 17.2820 | ||
MOGA | 5 | 16.7280 | ||
VEGA | 5 | 15.7840 | ||
Sig | 1.000 | 1.000 | 0.193 |
ANOVA | ||||||
---|---|---|---|---|---|---|
Source Factor | Sum of Squares | df | Mean Square | F | Sig | |
Spacing (SP) | Between Groups | .549 | 4 | .137 | 38.865 | .000 |
Within Groups | .071 | 20 | .004 | |||
Total | .619 | 24 |
Duncan Multiplier Range Test | |||||
---|---|---|---|---|---|
Algorithm | N | Subset for alpha = 0.05 | |||
1 | 2 | 3 | 4 | ||
NSGA-III | 5 | .2560 | |||
NSGA II | 5 | .5100 | |||
SPEA | 5 | .5720 | .5720 | ||
MOGA | 5 | .5960 | |||
VEGA | 5 | .6980 | |||
Sig | 1.000 | .115 | .530 | 1.000 |
ANOVA | ||||||
---|---|---|---|---|---|---|
Source Factor | Sum of Squares | df | Mean Square | F | Sig | |
Spacing (SP) | Between Groups | .530 | 4 | .133 | 28.734 | .000 |
Within Groups | .092 | 20 | .005 | |||
Total | .623 | 24 |
Duncan Multiplier Range Test | |||||
---|---|---|---|---|---|
Algorithm | N | Subset for alpha = 0.05 | |||
1 | 2 | 3 | 4 | ||
NSGA-III | 5 | .2240 | |||
NSGA II | 5 | .4280 | |||
SPEA | 5 | .4840 | .4840 | ||
MOGA | 5 | .5520 | |||
VEGA | 5 | .6620 | |||
Sig | 1.000 | .207 | .129 | 1.000 |
ANOVA | ||||||
---|---|---|---|---|---|---|
Source | Sum of Squares | df | Mean Square | F | Sig | |
ONVG | Between Groups | 583.408 | 4 | 145.852 | 29.349 | .000 |
Within Groups | 99.390 | 20 | 4.970 | |||
Total | 682.799 | 24 |
Duncan Multiplier Range Test | ||||
---|---|---|---|---|
Algorithm | N | Subset for alpha = 0.05 | ||
1 | 2 | 3 | ||
NSGA-III | 5 | 31.6880 | ||
NSGA II | 5 | 22.0200 | ||
SPEA | 5 | 20.0500 | 20.0500 | |
MOGA | 5 | 19.8180 | 19.8180 | |
VEGA | 5 | 18.1460 | ||
Sig | 1.000 | .154 | .216 |
ANOVA | ||||||
---|---|---|---|---|---|---|
Source | Sum of Squares | df | Mean Square | F | Sig | |
ONVG | Between Groups | 583.408 | 4 | 145.852 | 29.349 | .000 |
Within Groups | 99.390 | 20 | 4.970 | |||
Total | 682.799 | 24 |
Duncan Multiplier Range Test | ||||
---|---|---|---|---|
Algorithm | N | Subset for alpha = 0.05 | ||
1 | 2 | 3 | ||
NSGA-III | 5 | 31.6880 | ||
NSGA II | 5 | 22.0200 | ||
SPEA | 5 | 20.0500 | 20.0500 | |
MOGA | 5 | 19.8180 | 19.8180 | |
VEGA | 5 | 18.1460 | ||
Sig | 1.000 | .154 | .216 |
ANOVA | ||||||
---|---|---|---|---|---|---|
Source Factor | Sum of Squares | df | Mean Square | F | Sig | |
Spacing (SP) | Between Groups | .571 | 4 | .143 | 26.579 | .000 |
Within Groups | .107 | 20 | .005 | |||
Total | .679 | 24 |
Duncan Multiplier Range Test | |||||
---|---|---|---|---|---|
Algorithm | N | Subset for alpha = 0.05 | |||
1 | 2 | 3 | 4 | ||
NSGA-III | 5 | .2620 | |||
NSGA II | 5 | .4460 | |||
SPEA | 5 | .5640 | |||
MOGA | 5 | .5860 | |||
VEGA | 5 | .7100 | |||
Sig | 1.000 | 1.000 | .640 | 1.000 |
ANOVA | ||||||
---|---|---|---|---|---|---|
Source Factor | Sum of Squares | df | Mean Square | F | Sig | |
Spacing (SP) | Between Groups | .488 | 4 | .122 | 23.023 | .000 |
Within Groups | .106 | 20 | .005 | |||
Total | .594 | 24 |
Duncan Multiplier Range Test | |||||
---|---|---|---|---|---|
Algorithm | N | Subset for alpha = 0.05 | |||
1 | 2 | 3 | 4 | ||
NSGA-III | 5 | .2060 | |||
NSGA II | 5 | .4100 | |||
SPEA | 5 | .4780 | .4780 | ||
MOGA | 5 | .5280 | .5280 | ||
VEGA | 5 | .6220 | |||
Sig | 1.000 | .155 | .290 | .055 |
ANOVA | ||||||
---|---|---|---|---|---|---|
Source | Sum of Squares | df | Mean Square | F | Sig | |
ONVG | Between Groups | 570.996 | 4 | 142.749 | 45.027 | .000 |
Within Groups | 63.406 | 20 | 3.170 | |||
Total | 634.402 | 24 |
Duncan Multiplier Range Test | ||||
---|---|---|---|---|
Algorithm | N | Subset for alpha = 0.05 | ||
1 | 2 | 3 | ||
NSGA-III | 5 | 32.9360 | ||
NSGA II | 5 | 23.2460 | ||
SPEA | 5 | 21.5840 | 21.5840 | |
MOGA | 5 | 20.6900 | ||
VEGA | 5 | 19.8060 | ||
Sig | 1.000 | .156 | .150 |
ANOVA | ||||||
---|---|---|---|---|---|---|
Source | Sum of Squares | df | Mean Square | F | Sig | |
ONVG | Between Groups | 605.915 | 4 | 151.479 | 48.937 | .000 |
Within Groups | 61.908 | 20 | 3.095 | |||
Total | 667.823 | 24 |
Duncan Multiplier Range Test | ||||
---|---|---|---|---|
Algorithm | N | Subset for alpha = 0.05 | ||
1 | 2 | 3 | ||
NSGA-III | 5 | 32.6340 | ||
NSGA II | 5 | 22.9640 | ||
SPEA | 5 | 20.8440 | 20.8440 | |
MOGA | 5 | 19.8440 | ||
VEGA | 5 | 19.2820 | ||
Sig | 1.000 | .071 | .199 |
ANOVA | ||||||
---|---|---|---|---|---|---|
Source Factor | Sum of Squares | df | Mean Square | F | Sig | |
Spacing (SP) | Between Groups | .585 | 4 | .146 | 34.172 | .000 |
Within Groups | .086 | 20 | .004 | |||
Total | .671 | 24 |
Duncan Multiplier Range Test | |||||
---|---|---|---|---|---|
Algorithm | N | Subset for alpha = 0.05 | |||
1 | 2 | 3 | 4 | ||
NSGA-III | 5 | .2480 | |||
NSGA II | 5 | .4560 | |||
SPEA | 5 | .5340 | .5340 | ||
MOGA | 5 | .6040 | |||
VEGA | 5 | .7000 | |||
Sig | 1.000 | .074 | .106 | 1.000 |
ANOVA | ||||||
---|---|---|---|---|---|---|
Source Factor | Sum of Squares | df | Mean Square | F | Sig | |
Spacing (SP) | Between Groups | .524 | 4 | .131 | 24.472 | .000 |
Within Groups | .107 | 20 | .005 | |||
Total | .631 | 24 |
Duncan Multiplier Range Test | |||||
---|---|---|---|---|---|
Algorithm | N | Subset for alpha = 0.05 | |||
1 | 2 | 3 | 4 | ||
NSGA-III | 5 | .2040 | |||
NSGA II | 5 | .3980 | |||
SPEA | 5 | .4740 | .4740 | ||
MOGA | 5 | .5300 | |||
VEGA | 5 | .6360 | |||
Sig | 1.000 | .116 | .240 | 1.000 |