GeneticAlg.java import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.List;import java.util.Random;import org.cloudbus.cloudsim.CloudletSchedulerSpaceShared;import org.cloudbus.cloudsim.Vm;/**
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
import org.cloudbus.cloudsim.CloudletSchedulerSpaceShared;
import org.cloudbus.cloudsim.Vm;
/**
* A class for running Genetic Algorithm.
* @author Guoxi
*
*/
public class GeneticAlg {
private static Population population;
private static Individual fittest;
private static Individual secondFittest;
public static int generationCount = 0;
public static void main(String[] args) {
Random rn = new Random();
initPopulation(48);
while (generationCount < 32) {
selection();
System.out.println(fittest);
if (rn.nextDouble() < 0.75)
crossover();
if (rn.nextDouble() < 0.05)
mutation();
addFittestOffspring();
generationCount ++;
}
}
public static void initPopulation(int popSize) {
population = new Population(popSize);
}
/**
* Select two most suitable individuals and assign them to instance variables.
*/
public static void selection() {
fittest = population.getFittest();
secondFittest = population.getSecondFittest();
}
/**
* Exchange nodes of two most suitable individuals.
*/
public static void crossover() {
Random rn = new Random();
int nodeNum = fittest.nodeNum;
int crossoverIndex1 = rn.nextInt(nodeNum);
int crossoverIndex2 = rn.nextInt(nodeNum);
List
rearrangeVms1 = new ArrayList<>();
List
rearrangeVms2 = new ArrayList<>(); List
exchangeNodes1 = fittest.nodes.get(crossoverIndex1).genes; List
exchangeNodes2 = secondFittest.nodes.get(crossoverIndex2).genes; rearrangeVms1 = exchangeNodes1; for (Vm vm : exchangeNodes2) { if (rearrangeVms1.contains(vm)) { rearrangeVms1.remove(vm); } else { for (Node node : fittest.nodes) { if (node.genes.contains(vm)) { if (rearrangeVms1.addAll(node.genes)) { System.out.println("Success");; } else { System.out.println("Failed"); } node.clearAll(); } } } } for (Vm vm : exchangeNodes2) { if (!fittest.nodes.get(crossoverIndex1).allocateVm(vm)) { System.out.println("[crossvoer()]: Can't allocate VM" + vm); break; } } rearrangeVms2 = exchangeNodes2; for (Vm vm : exchangeNodes1) { if (rearrangeVms2.contains(vm)) { rearrangeVms2.remove(vm); } else { for (Node node : secondFittest.nodes) { if (node.genes.contains(vm)) { if (rearrangeVms2.addAll(node.genes)) { System.out.println("Success");; } else { System.out.println("Failed"); } node.clearAll(); } } } } for (Vm vm : exchangeNodes1) { if (!secondFittest.nodes.get(crossoverIndex2).allocateVm(vm)) { System.out.println("[crossover()]: Can't allocate VM" + vm); } } arrangeVms(fittest, rearrangeVms1); arrangeVms(secondFittest, rearrangeVms2); } /** * Select the most suitable individual and mutate its genes. */ public static void mutation() { Random rn = new Random(); int nodeNum = fittest.nodeNum; int mutationIndex = rn.nextInt(nodeNum); List
mutationVmList = fittest.nodes.get(mutationIndex).genes; fittest.nodes.get(mutationIndex).clearAll(); arrangeVms(fittest, mutationVmList); } /** * Replace the least suitable individual from the most suitable offspring. */ public static void addFittestOffspring() { // Update the crowding distance of each individual population.getDomination(); population.crowdingDistance(); int replaceIndex = population.getLeastFitIndex(); if (replaceIndex == -1) { System.out.println("[addFittestOffspring()]: Can't find the least fit individual."); } population.individuals.set(replaceIndex, getFittestOffspring()); } /** * Try to allocate given vms on a given individual. * @param individual the individual for vms to allocate * @param vmList the vms need to be arranged */ private static void arrangeVms(Individual individual, List
vmList) { for (Node node:individual.nodes) { for (Vm vm:vmList) { if (node.allocateVm(vm)) { vmList.remove(vm); } } } if (!vmList.isEmpty()) { System.out.println("Can't arrange vms on individual!"); } } /** * Get fittest offspring from the parents. * @return fittestOffspring */ private static Individual getFittestOffspring() { if (population.distances[fittest.id] > population.distances[secondFittest.id]) { return fittest; } return secondFittest; } } /** * Class Population * @author Guoxi * */ class Population { int popSize; List
individuals; List
> dominatingSet; int[] beDominatedNumber; int[] rank; int[] distances; List
> CHSet; /** * Constructors */ public Population() {} public Population(int size) { this(size, 4); } public Population(int size, int num) { popSize = size; individuals = new ArrayList
(); individuals.add(new Individual()); dominatingSet = new ArrayList
>(popSize); CHSet = new ArrayList
>(); beDominatedNumber = new int[popSize+1]; rank = new int[popSize+1]; distances = new int[popSize+1]; for (int i = 0; i <= popSize; i++) { List
tmp1 = new ArrayList
(); dominatingSet.add(tmp1); } for (int i = 0; i < popSize; i++) { Individual element = new Individual(i+1, num); individuals.add(element); } getDomination(); crowdingDistance(); } /** * Get the non-domination set */ public void getDomination() { CHSet.add(new ArrayList
()); CHSet.add(new ArrayList
()); for (Individual individual1 : individuals) { beDominatedNumber[individual1.id] = 0; for (Individual individual2 : individuals) { if (Individual.dominate(individual1, individual2) == 1) { dominatingSet.get(individual1.id).add(individual2.id); } else if (Individual.dominate(individual1, individual2) == 0) { beDominatedNumber[individual1.id]++; } } if (beDominatedNumber[individual1.id] == 0) { rank[individual1.id] = 1; CHSet.get(1).add(individual1); } } int i = 1; while (!CHSet.get(i).isEmpty()) { List
tmpSet = new ArrayList<>(); for (Individual individual1 : CHSet.get(i)) { for (Integer individualId : dominatingSet.get(individual1.id)) { beDominatedNumber[individualId]--; if (beDominatedNumber[individualId] == 0) { rank[individualId] = i + 1; tmpSet.add(individuals.get(individualId)); } } } i++; CHSet.add(tmpSet); } } /** * Calculate the crowding distances of each individual */ public void crowdingDistance() { for (int i = 1; i < CHSet.size(); i++) { if (!CHSet.get(i).isEmpty()) { int len = CHSet.get(i).size(); Collections.sort(CHSet.get(i), new SortObj()); distances[CHSet.get(i).get(0).id] = distances[CHSet.get(i).get(len-1).id] = Integer.MAX_VALUE; for (int j = 1; j < len-1; j++) { distances[CHSet.get(i).get(j).id] = (int) (((CHSet.get(i).get(j+1).stableTime-CHSet.get(i).get(j-1).stableTime)/(getMaxStableTime()-getMinStableTime())) +((CHSet.get(i).get(j+1).migrateTimes-CHSet.get(i).get(j-1).migrateTimes)/(getMaxMigraTimes()-getMinMigraTimes()))); } } } } /** * Get the most suitable individual from the population. * @return the most suitable individual */ public Individual getFittest() { int maxDistance = Integer.MIN_VALUE; Individual fittest = null; for (int i = 1; i <= popSize; i++) { int tmp = distances[individuals.get(i).id]; if (tmp > maxDistance) { maxDistance = tmp; fittest = individuals.get(i); } } return fittest; } /** * Get the second most suitable individual from the population. * @return the second most suitable individual */ public Individual getSecondFittest() { int distance1 = Integer.MIN_VALUE; int distance2 = Integer.MIN_VALUE; Individual secondFittest = null; for (int i = 1; i <= popSize; i++) { int tmp = distances[individuals.get(i).id]; if (tmp > distance1) { distance1 = distances[individuals.get(i).id]; } else if (tmp > distance2) { distance2 = tmp; secondFittest = individuals.get(i); } } return secondFittest; } /** * Get the least suitable individual from the population * @return index of least suitable individual */ public int getLeastFitIndex() { int minDistance = Integer.MAX_VALUE; int resIndex = -1; for (int i = 1; i <= popSize; i++) { int tmp = distances[individuals.get(i).id]; if (tmp < minDistance) { minDistance = tmp; resIndex = i; } } return resIndex; } /** * Get the maximum stable time among the population * @return maxStableTime */ private double getMaxStableTime() { double maxStableTime = Double.MIN_VALUE; for (Individual individual : individuals) { double tmp = individual.stableTime; if (tmp > maxStableTime) { maxStableTime = tmp; } } return maxStableTime; } /** * Get the minimum stable time among the population * @return minStableTime */ private double getMinStableTime() { double minStableTime = Double.MAX_VALUE; for (Individual individual : individuals) { double tmp = individual.stableTime; if (tmp < minStableTime) { minStableTime = tmp; } } return minStableTime; } /** * Get the maximum migration times among the population * @return maxMigraTimes */ private int getMaxMigraTimes() { int maxMigraTimes = Integer.MIN_VALUE; for (Individual individual : individuals) { int tmp = individual.migrateTimes; if (tmp > maxMigraTimes) { maxMigraTimes = tmp; } } return maxMigraTimes; } /** * Get the minimum migration times among the population * @return minMigraTimes */ private int getMinMigraTimes() { int minMigraTimes = Integer.MAX_VALUE; for (Individual individual : individuals) { int tmp = individual.migrateTimes; if (tmp < minMigraTimes) { minMigraTimes = tmp; } } return minMigraTimes; } } /** * Class Individual * @author Guoxi * */ class Individual { int id; int nodeNum; List
nodes; int migrateTimes; double stableTime; /** * Constructors */ public Individual() {} public Individual(int no) { this(no, 4); } public Individual(int no, int num) { id = no; nodeNum = num; migrateTimes = 0; stableTime = 0; nodes = new ArrayList
(); Random rn = new Random(); for (int i = 0; i < nodeNum; i++) { int geneNum = 1 + rn.nextInt(2); Node element = new Node(i, geneNum); nodes.add(element); migrateTimes += element.migrateTimes; stableTime += element.stableTime; } } /** * Decide if one individual dominates another * @param ch1 Individual 1 * @param ch2 Individual 2 * @return true if Individual 1 dominates Individual 2, false otherwise. */ public static int dominate(Individual ch1, Individual ch2) { if (ch1.migrateTimes
ch2.stableTime) return 1; else if (ch1.migrateTimes>ch2.migrateTimes && ch1.stableTime
genes; int migrateTimes; double stableTime; int availableMips; int availableRam; /** virtual machine params */ int [] mipss = new int[]{209, 289, 132}; long size = 10000; int ram = 512; long bw = 1000; int pesNumber = 1; /** * Constructors */ public Node() {} public Node(int nodeId) { this(nodeId, 0); } public Node(int nodeId, int num) { id = nodeId; geneNum = num; availableMips = 850; availableRam = 2048; genes = new ArrayList
(); Random rn = new Random(); migrateTimes = rn.nextInt(5); stableTime = 10 + rn.nextDouble()*200; for (int i = 0; i < geneNum; i++) { Vm tmp = new Vm(i, 0, mipss[i%mipss.length], pesNumber, ram, bw, size, "Xen", new CloudletSchedulerSpaceShared()); if (!allocateVm(tmp)) { System.out.println("[Node.Constructor()]: Allocate vm failed on node" + id); } } } /** * Determine if given vm can be allocated on the node. * If yes, allocate it on the node and return true; Otherwise, return false. * @param vm the virtual machine need to be allocated * @return allocation result */ public boolean allocateVm(Vm vm) { if (availableRam < vm.getRam()) { return false; } else if (availableMips < vm.getMips()) { return false; } else { genes.add(vm); availableMips -= vm.getMips(); availableRam -= vm.getRam(); return true; } } /** * Deallocate given vm from the node. * @param vm the virtual machine need to be deallocated * @return deallocation result */ public boolean deallocateVm(Vm vm) { if (genes.remove(vm)) { availableMips += vm.getMips(); availableRam += vm.getRam(); return true; } else { return false; } } /** * Deallocate all vms from the node. */ public void clearAll() { for (Vm vm : genes) { if (!deallocateVm(vm)) { System.out.println("[Node.clearAll()]: Failed to deallocate VM " + vm.getId()); break; } } } @Override public String toString() { String str = "--------Node " + id + "--------\n"; for (Vm vm : genes) { str += "Vm " + vm.getId() + ", mips: " + vm.getMips() + "\n"; } str += "availableMips: " + availableMips + "\n"; str += "availableRam: " + availableRam + "\n"; str += "migrateTimes: " + migrateTimes + "\n"; str += "stableTime: " + stableTime + "\n"; str += "--------Node " + id + "--------\n"; return str; } } /** * Class SortObj for comparing two individuals. * @author Guoxi * */ class SortObj implements Comparator
{ @Override public int compare(Individual o1, Individual o2) { int flag = 0; if (o1.stableTime > o2.stableTime) { flag = 1; } else if (o1.stableTime < o2.stableTime) { flag = -1; } else { if (o1.migrateTimes > o2.migrateTimes) { flag = 1; } else if (o1.migrateTimes < o2.migrateTimes) { flag = -1; } } return flag; } }