验证中...
码云 Gitee IDE 全新上线——支持 Git 管理的轻量在线编码环境
GeneticAlg.java
Raw Copy
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791
package chd.cloudsim.gene;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
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 Population population;
private Individual fittest;
private Individual secondFittest;
private float timeIncAmt = 5.0f;
public static List<Vm> VMs;
public static Random rn = new Random(1); // Set random seed for debugging usage.
public static final float MAX_VALUE = 1.0f;
/**
* Main entry is here.
* @param args command line parameters
*/
public static void main(String[] args) {
GeneticAlg geneTest = new GeneticAlg();
geneTest.initPopulation(48, 10);
int generationCount = 0;
while (generationCount < 30) {
System.out.println("******************** Generation " + generationCount + " ********************");
geneTest.selection();
// Print selection results.
System.out.println(">>>>> Selection completed! <<<<<");
System.out.println("Fittest: Individual " + geneTest.fittest.id +
", Second Fittest: Individual " + geneTest.secondFittest.id);
System.out.println(geneTest.fittest);
System.out.println(geneTest.secondFittest);
if (rn.nextDouble() < 0.75) {
geneTest.crossover();
geneTest.addFittestOffspring();
// Print crossover results.
System.out.println(">>>>> Crossover completed! <<<<<");
System.out.println(geneTest.fittest);
System.out.println(geneTest.secondFittest);
}
// if (rn.nextDouble() < 0.05)
// geneTest.mutation();
geneTest.population.getDomination();
geneTest.population.crowdingDistance();
generationCount ++;
// Print distances for debugging usage.
System.out.println("Crowding distances are: ");
System.out.print("[ ");
for (int i = 1; i <= geneTest.population.popSize; i++) {
System.out.printf("%.3f ", geneTest.population.distances[geneTest.population.individuals.get(i).id]);
if (i % 10 == 0)
System.out.println("");
}
System.out.println("]\n");
}
}
/**
* Initialize virtual machine list given a number.
* @param vmNum number of vms need to create
* @return created vm list
*/
private List<Vm> initVmList(int vmNum) {
List<Vm> ret = new ArrayList<Vm>();
/** virtual machine params */
int [] mipss = new int[]{209, 183, 289, 132, 104};
long size = 10000;
int ram = 512;
long bw = 1000;
int pesNumber = 1;
for (int i = 0; i < vmNum; i++) {
Vm tmp = new Vm(i+1, 0, mipss[i%mipss.length], pesNumber, ram,
bw, size, "Xen", new CloudletSchedulerSpaceShared());
ret.add(tmp);
}
return ret;
}
/**
* Initialize population with given population size.
* @param popSize population size
* @param vmNum number of vms
*/
public void initPopulation(int popSize, int vmNum) {
VMs = initVmList(vmNum);
population = new Population(popSize);
}
/**
* Select two fittest individuals and assign them to instance variables.
*/
public void selection() {
fittest = population.getFittest();
secondFittest = population.getSecondFittest();
}
/**
* Exchange nodes of two fittest individuals.
*/
public void crossover() {
int nodeNum = fittest.nodeNum;
int crossoverIndex1 = rn.nextInt(nodeNum);
int crossoverIndex2 = rn.nextInt(nodeNum);
System.out.println("crossoverIndex1: " + (crossoverIndex1+1));
System.out.println("crossoverIndex2: " + (crossoverIndex2+1));
List<Vm> exchangeNodes1 = new ArrayList<Vm>(fittest.nodes.get(crossoverIndex1).genes);
List<Vm> exchangeNodes2 = new ArrayList<Vm>(secondFittest.nodes.get(crossoverIndex2).genes);
List<Vm> rearrangeVms1 = new ArrayList<Vm>(exchangeNodes1);
List<Vm> rearrangeVms2 = new ArrayList<Vm>(exchangeNodes2);
// Delete common vms from both two rearrange lists.
List<Vm> commonVms = new ArrayList<Vm>(rearrangeVms1);
commonVms.retainAll(rearrangeVms2);
rearrangeVms1.removeAll(commonVms);
rearrangeVms2.removeAll(commonVms);
List<Vm> tmp = new ArrayList<Vm>();
Iterator<Node> iter;
for (Vm vm:rearrangeVms2) {
iter = fittest.nodes.iterator();
while (iter.hasNext()) {
Node node = iter.next();
if (node.genes.contains(vm)) {
node.deallocateVms(rearrangeVms2);
if (node.genes.isEmpty()) {
break;
}
if (tmp.addAll(node.genes)) {
node.clearAll();
System.out.println("Succeed to add genes to rearrange list1.");
break;
} else {
System.err.println("Fail to add genes to rearrange list1.");
System.exit(0);
}
}
}
}
for (Vm vm:rearrangeVms1) {
iter = secondFittest.nodes.iterator();
while (iter.hasNext()) {
Node node = iter.next();
if (node.genes.contains(vm)) {
node.deallocateVms(rearrangeVms1);
if (node.genes.isEmpty()) {
break;
}
if (rearrangeVms2.addAll(node.genes)) {
node.clearAll();
System.out.println("Succeed to add genes to rearrange list2.");
break;
} else {
System.err.println("Fail to add genes to rearrange list2.");
System.exit(0);
}
}
}
}
rearrangeVms1.addAll(tmp);
// Exchange each other's selected node here.
fittest.nodes.get(crossoverIndex1).clearAll();
for (Vm vm : exchangeNodes2) {
if (!fittest.nodes.get(crossoverIndex1).allocateVm(vm)) {
System.err.println("[crossvoer()]: Can't allocate Vm" + vm);
break;
}
}
secondFittest.nodes.get(crossoverIndex2).clearAll();
for (Vm vm : exchangeNodes1) {
if (!secondFittest.nodes.get(crossoverIndex2).allocateVm(vm)) {
System.err.println("[crossover()]: Can't allocate Vm " + vm.getId());
break;
}
}
// Print rearrange vm list for debugging usage.
System.out.print("Rearrange Vm List 1: ");
for (int i = 0; i < rearrangeVms1.size(); i++) {
System.out.print("Vm " + rearrangeVms1.get(i).getId()+" ");
}
System.out.println("");
System.out.print("Rearrange Vm List 2: ");
for (int i = 0; i < rearrangeVms2.size(); i++) {
System.out.print("Vm " + rearrangeVms2.get(i).getId()+" ");
}
System.out.println("");
// Save rearrange vm list size for later use.
int incMigrTimes1 = rearrangeVms1.size();
int incMigrTimes2 = rearrangeVms2.size();
// Rearrange vms for the fittest and second fittest individual.
arrangeVms(fittest, rearrangeVms1);
arrangeVms(secondFittest, rearrangeVms2);
// Increase migrating times and decrease stable time for two fittest individuals.
updateStatus(fittest, incMigrTimes1, secondFittest, incMigrTimes2);
}
/**
* Select the fittest individual and mutate its genes.
*/
public void mutation() {
// TODO: Not testing yet! May need more work!
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 fit individual with the fittest offspring.
*/
public void addFittestOffspring() {
int replaceIndex = population.getLeastFitIndex();
System.out.println("Replace the least fit individual: Individual " + replaceIndex);
if (replaceIndex == -1) {
System.err.println("[addFittestOffspring()]: Can't find the least fit individual.");
return;
}
Individual fittestOffspring = new Individual(getFittestOffspring()); // deep copy
fittestOffspring.id = replaceIndex; // change individual's id
population.individuals.set(replaceIndex, fittestOffspring);
}
/**
* Get the fittest offspring from parents.
* @return fittestOffspring
*/
private Individual getFittestOffspring() {
// Update the crowding distance of each individual
population.getDomination();
population.crowdingDistance();
if (population.distances[fittest.id] > population.distances[secondFittest.id]) {
return fittest;
}
return secondFittest;
}
/**
* Try to allocate given vms on a given individual.
* @param indv the individual for vms to allocate
* @param vmList the vms need to be arranged
*/
private void arrangeVms(Individual indv, List<Vm> vmList) {
// First try used nodes.
for (int i = 0; i < indv.nodes.size(); i++) {
Node node = indv.nodes.get(i);
if (node.used) {
Iterator<Vm> it = vmList.iterator();
while (it.hasNext()) {
Vm tmp = it.next();
if (node.allocateVm(tmp)) {
it.remove();
}
}
}
}
// Then try unused nodes.
if (!vmList.isEmpty())
{
for (int i = 0; i < indv.nodes.size(); i++) {
Node node = indv.nodes.get(i);
if (!node.used) {
Iterator<Vm> it = vmList.iterator();
while (it.hasNext()) {
Vm tmp = it.next();
if (node.allocateVm(tmp)) {
it.remove();
}
}
}
}
}
// Cannot allocate vms.
if (!vmList.isEmpty()) {
System.err.println("[arrangeVms()]: Can't arrange vms on Individual " + indv.id);
System.exit(0);
}
}
/**
* After crossover, we need to update each individual's parameters.
* @param indv1 the fittest individual
* @param incAmt1 migrating times the fittest individual needs to add
* @param indv2 the second fittest individual
* @param incAmt2 migrating times the second fittest individual needs to add
*/
private void updateStatus(Individual indv1, int incAmt1, Individual indv2, int incAmt2) {
indv1.migratingTimes += incAmt1;
indv2.migratingTimes += incAmt2;
List<Individual> indvList = population.individuals;
for (int i = 1; i <= population.popSize; i++) {
Individual indv = indvList.get(i);
indv.stableTime += timeIncAmt;
}
indv1.stableTime -= timeIncAmt;
indv2.stableTime -= timeIncAmt;
}
}
/**
* Class Population
* @author Guoxi
*
*/
class Population {
int popSize;
List<Individual> individuals;
List<List<Integer>> dominatingSet;
int[] dominatingNumber;
int[] rank;
float[] 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());
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() {
// Initialize necessary variables.
dominatingSet = new ArrayList<List<Integer>>();
CHSet = new ArrayList<List<Individual>>();
dominatingNumber = new int[popSize+1];
rank = new int[popSize+1];
for (int i = 0; i <= popSize; i++) {
List<Integer> tmp1 = new ArrayList<Integer>();
dominatingSet.add(tmp1);
}
CHSet.add(new ArrayList<Individual>());
CHSet.add(new ArrayList<Individual>());
// Here we begin to get each individual's dominating set.
for (int i = 1; i <= popSize; i++) {
Individual indv1 = individuals.get(i);
dominatingNumber[indv1.id] = 0;
for (int j = 1; j <= popSize; j++) {
Individual indv2 = individuals.get(j);
if (dominate(indv1, indv2) == 1) {
dominatingSet.get(indv1.id).add(indv2.id);
} else if (dominate(indv1, indv2) == 0) {
dominatingNumber[indv1.id]++;
}
}
if (dominatingNumber[indv1.id] == 0) {
rank[indv1.id] = 1;
CHSet.get(1).add(indv1);
}
}
int i = 1;
while (!CHSet.get(i).isEmpty()) {
List<Individual> tmpSet = new ArrayList<>();
for (Individual indv1 : CHSet.get(i)) {
for (Integer indvId : dominatingSet.get(indv1.id)) {
dominatingNumber[indvId]--;
if (dominatingNumber[indvId] == 0) {
rank[indvId] = i + 1;
tmpSet.add(individuals.get(indvId));
}
}
}
i++;
CHSet.add(tmpSet);
}
}
/**
* Calculate the crowding distances of each individual.
*/
public void crowdingDistance() {
distances = new float[popSize+1];
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());
// TODO: Always select first two individuals with MAX_VALUE distance!
distances[CHSet.get(i).get(0).id] = distances[CHSet.get(i).get(len-1).id] = GeneticAlg.MAX_VALUE;
for (int j = 1; j < len-1; j++) {
distances[CHSet.get(i).get(j).id] = (((CHSet.get(i).get(j+1).stableTime-CHSet.get(i).get(j-1).stableTime)/(getMaxStableTime()-getMinStableTime()))
+((CHSet.get(i).get(j+1).migratingTimes-CHSet.get(i).get(j-1).migratingTimes)/(getMaxMigraTimes()-getMinMigraTimes())));
}
}
}
}
/**
* Get the fittest individual from the population.
* @return the fittest individual
*/
public Individual getFittest() {
float maxDistance = Integer.MIN_VALUE;
Individual fittest = null;
for (int i = 1; i <= popSize; i++) {
float tmp = distances[individuals.get(i).id];
if (tmp > maxDistance) {
maxDistance = tmp;
fittest = new Individual(individuals.get(i));
}
}
return fittest;
}
/**
* Get the second fittest individual from the population.
* @return the second fittest individual
*/
public Individual getSecondFittest() {
float distance1 = Float.MIN_VALUE;
float distance2 = Float.MIN_VALUE;
Individual secondFittest = null;
for (int i = 1; i <= popSize; i++) {
float tmp = distances[individuals.get(i).id];
if (tmp > distance1) {
distance1 = distances[individuals.get(i).id];
} else if (tmp > distance2) {
distance2 = tmp;
secondFittest = new Individual(individuals.get(i));
}
}
return secondFittest;
}
/**
* Get index of the least fit individual from the population.
* @return index of least fit individual
*/
public int getLeastFitIndex() {
float minDistance = Float.MAX_VALUE;
int resIndex = -1;
for (int i = 1; i <= popSize; i++) {
float tmp = distances[individuals.get(i).id];
if (tmp < minDistance) {
minDistance = tmp;
resIndex = individuals.get(i).id;
}
}
return resIndex;
}
/**
* Get the maximum stable time among the population.
* @return maxStableTime
*/
private float getMaxStableTime() {
float maxStableTime = Float.MIN_VALUE;
for (int i = 1; i <= popSize; i++) {
Individual indv = individuals.get(i);
float tmp = indv.stableTime;
if (tmp > maxStableTime) {
maxStableTime = tmp;
}
}
return maxStableTime;
}
/**
* Get the minimum stable time among the population.
* @return minStableTime
*/
private float getMinStableTime() {
float minStableTime = Float.MAX_VALUE;
for (int i = 1; i <= popSize; i++) {
Individual indv = individuals.get(i);
float tmp = indv.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 (int i = 1; i <= popSize; i++) {
Individual indv = individuals.get(i);
int tmp = indv.migratingTimes;
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 (int i = 1; i <= popSize; i++) {
Individual indv = individuals.get(i);
int tmp = indv.migratingTimes;
if (tmp < minMigraTimes) {
minMigraTimes = tmp;
}
}
return minMigraTimes;
}
/**
* Decide if one individual dominates another.
* @param ch1 Individual 1
* @param ch2 Individual 2
* @return true if Individual 1 dominates Individual 2, false otherwise.
*/
private static int dominate(Individual ch1, Individual ch2) {
if (ch1.migratingTimes<ch2.migratingTimes && ch1.stableTime>ch2.stableTime)
return 1;
else if (ch1.migratingTimes>ch2.migratingTimes && ch1.stableTime<ch2.stableTime)
return 0;
return -1;
}
}
/**
* Class Individual
* @author Guoxi
*
*/
class Individual {
int id;
int nodeNum;
List<Node> nodes;
int migratingTimes;
float stableTime;
/**
* Constructors
*/
public Individual() {}
public Individual(int no) { this(no, 4); }
public Individual(Individual indv) {
this.id = indv.id;
this.nodeNum = indv.nodeNum;
this.nodes = new ArrayList<Node>(indv.nodes);
this.migratingTimes = indv.migratingTimes;
this.stableTime = indv.stableTime;
}
public Individual(int no, int num) {
id = no; nodeNum = num;
nodes = new ArrayList<Node>();
int vmIndex = 0;
migratingTimes = GeneticAlg.rn.nextInt(4);
stableTime = 10 + GeneticAlg.rn.nextFloat()*100;
for (int i = 0; i < nodeNum; i++) {
int geneNum = 1 + GeneticAlg.rn.nextInt(2);
Node element = new Node(i+1, geneNum, vmIndex);
vmIndex += geneNum;
nodes.add(element);
}
}
@Override
/**
* Thus we can use print(individualObject) to see details of one individual.
*/
public String toString() {
String str = "------------Individual " + id + "------------\n";
for (Node node : nodes) {
str += node.toString();
}
str += "migratingTimes: " + migratingTimes + "\n";
str += "stableTime: " + stableTime + "\n";
str += "------------------------------------";
return str;
}
}
/**
* Class Node
* @author Guoxi
*
*/
class Node {
int id;
int geneNum;
List<Vm> genes;
int availableMips;
int availableRam;
boolean used = false;
/**
* Constructors
*/
public Node() {}
public Node(int nodeId) { this(nodeId, 0, 1); }
public Node(int nodeId, int num, int beginVmId) {
id = nodeId;
geneNum = num;
availableMips = 700;
availableRam = 2048;
used = true;
genes = new ArrayList<Vm>();
for (int i = 0; i < geneNum; i++) {
if (!allocateVm(GeneticAlg.VMs.get(beginVmId+i))) {
System.err.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);
used = true;
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();
if (genes.isEmpty())
used = false;
return true;
} else {
return false;
}
}
/**
* Deallocate a list of vms from the node.
* @param vmList the vm list need to be deallocated
*/
public boolean deallocateVms(List<Vm> vmList) {
List<Vm> intersection = new ArrayList<Vm>(vmList);
intersection.retainAll(genes);
if (!intersection.isEmpty()) {
for (Vm vm:intersection) {
if (!deallocateVm(vm)) {
return false;
}
}
}
return true;
}
/**
* Deallocate all vms from the node.
*/
public void clearAll() {
for (int i = 0; i < genes.size(); i++) {
Vm vm = genes.get(i);
if (!deallocateVm(vm)) {
System.err.println("[Node.clearAll()]: Failed to deallocate VM " + vm.getId());
break;
}
i--;
}
used = false;
}
@Override
/**
* Thus we can use print(nodeObject) to see details of one node.
*/
public String toString() {
String str = "Node " + id + ": ";
for (Vm vm : genes) {
str += "Vm " + vm.getId() + ", mips: " + vm.getMips() + "; ";
}
str += "\n\tavailableMips: " + availableMips;
str += ", availableRam: " + availableRam + ", used: " + used + "\n";
return str;
}
}
/**
* Class SortObj for comparing two individuals.
* For a list, the individuals are sorted from strong to weak.
* @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.migratingTimes > o2.migratingTimes) {
flag = 1;
} else if (o1.migratingTimes < o2.migratingTimes) {
flag = -1;
}
}
return flag;
}
}

Comment list( 0 )

You need to Sign in for post a comment

Help Search