验证中...
私信发送成功
GeneticAlg.java
原始数据 复制代码
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598
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<Vm> rearrangeVms1 = new ArrayList<>();
List<Vm> rearrangeVms2 = new ArrayList<>();
List<Vm> exchangeNodes1 = fittest.nodes.get(crossoverIndex1).genes;
List<Vm> 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<Vm> 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<Vm> 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<Individual> individuals;
List<List<Integer>> dominatingSet;
int[] beDominatedNumber;
int[] rank;
int[] distances;
List<List<Individual>> CHSet;
/**
* Constructors
*/
public Population() {}
public Population(int size) { this(size, 4); }
public Population(int size, int num) {
popSize = size;
individuals = new ArrayList<Individual>();
individuals.add(new Individual());
dominatingSet = new ArrayList<List<Integer>>(popSize);
CHSet = new ArrayList<List<Individual>>();
beDominatedNumber = new int[popSize+1];
rank = new int[popSize+1];
distances = new int[popSize+1];
for (int i = 0; i <= popSize; i++) {
List<Integer> tmp1 = new ArrayList<Integer>();
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<Individual>());
CHSet.add(new ArrayList<Individual>());
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<Individual> 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<Node> 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<Node>();
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.migrateTimes && ch1.stableTime>ch2.stableTime)
return 1;
else if (ch1.migrateTimes>ch2.migrateTimes && ch1.stableTime<ch2.stableTime)
return 0;
return -1;
}
@Override
public String toString() {
String str = "------------Individual " + id + "------------\n";
for (Node node : nodes) {
str += node.toString();
}
str += "migrateTimes: " + migrateTimes + "\n";
str += "stableTime: " + stableTime + "\n";
str += "------------Individual " + id + "------------\n";
return str;
}
}
/**
* Class Node
* @author Guoxi
*
*/
class Node {
int id;
int geneNum;
List<Vm> 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<Vm>();
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<Individual> {
@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;
}
}

评论列表( 0 )

你可以在登录后,对此项目发表评论

4_float_left_people 4_float_left_close