完整的GA算法的工程实现，包括与轮询(RR)算法效果对比：
完整项目代码地址（导入到eclipse中即可运行）： GA-cloudsim.zip
遗传算法GA的核心代码实现：
最核心：
private static ArrayList<int[]> GA(ArrayList<int[]> pop,int gmax,double crossoverProb,double mutationRate)
{
HashMap<Integer,double[]> segmentForEach=calcSelectionProbs(pop);
ArrayList<int[]> children=new ArrayList<int[]>();
ArrayList<int[]> tempParents=new ArrayList<int[]>();
while(children.size()<pop.size())
{
//selection phase:select two parents each time.
for(int i=0;i<2;i++)
{
double prob = new Random().nextDouble();
for (int j = 0; j < pop.size(); j++)
{
if (isBetween(prob, segmentForEach.get(j)))
{
tempParents.add(pop.get(j));
break;
}
}
}
//cross-over phase.
int[] p1,p2,p1temp,p2temp;
p1= tempParents.get(tempParents.size() - 2).clone();
p1temp= tempParents.get(tempParents.size() - 2).clone();
p2 = tempParents.get(tempParents.size() -1).clone();
p2temp = tempParents.get(tempParents.size() -1).clone();
if(new Random().nextDouble()<crossoverProb)
{
int crossPosition = new Random().nextInt(cloudletList.size() - 1);
//cross-over operation
for (int i = crossPosition + 1; i < cloudletList.size(); i++)
{
int temp = p1temp[i];
p1temp[i] = p2temp[i];
p2temp[i] = temp;
}
}
//choose the children if they are better,else keep parents in next iteration.
children.add(getFitness(p1temp) < getFitness(p1) ? p1temp : p1);
children.add(getFitness(p2temp) < getFitness(p2) ? p2temp : p2);
// mutation phase.
if (new Random().nextDouble() < mutationRate)
{
// mutation operations bellow.
int maxIndex = children.size() - 1; for (int i = maxIndex - 1; i <= maxIndex; i++)
{
operateMutation(children.get(i), mutationRate);
}
}
} gmax--;
return gmax > 0 ? GA(children, gmax, crossoverProb, mutationRate): children;
}
完整核心代码：
private static int[] findBestSchedule(ArrayList<int[]> pop)
{
double bestFitness=1000000000;
int bestIndex=0;
for(int i=0;i<pop.size();i++)
{
int []schedule=pop.get(i);
double fitness=getFitness(schedule);
if(bestFitness>fitness)
{
bestFitness=fitness;
bestIndex=i;
}
}
return pop.get(bestIndex);
} private static int[] getScheduleByGA(int popSize,int gmax,double crossoverProb,double mutationRate)
{
ArrayList<int[]> pop=initPopsRandomly(cloudletList.size(),vmList.size(),popSize);
pop=GA(pop,gmax,crossoverProb,mutationRate);
return findBestSchedule(pop);
} private static ArrayList<int[]> initPopsRandomly(int taskNum,int vmNum,int popsize)
{
ArrayList<int[]> schedules=new ArrayList<int[]>();
for(int i=0;i<popsize;i++)
{
//data structure for saving a schedule：array,index of array are cloudlet id,content of array are vm id.
int[] schedule=new int[taskNum];
for(int j=0;j<taskNum;j++)
{
schedule[j]=new Random().nextInt(vmNum);
}
schedules.add(schedule);
}
return schedules;
} private static double getFitness(int[] schedule)
{
double fitness=0; HashMap<Integer,ArrayList<Integer>> vmTasks=new HashMap<Integer,ArrayList<Integer>>();
int size=cloudletList.size(); for(int i=0;i<size;i++)
{
if(!vmTasks.keySet().contains(schedule[i]))
{
ArrayList<Integer> taskList=new ArrayList<Integer>();
taskList.add(i);
vmTasks.put(schedule[i],taskList);
}
else
{
vmTasks.get(schedule[i]).add(i);
}
} for(Entry<Integer, ArrayList<Integer>> vmtask:vmTasks.entrySet())
{
int length=0;
for(Integer taskid:vmtask.getValue())
{
length+=getCloudletById(taskid).getCloudletLength();
} double runtime=length/getVmById(vmtask.getKey()).getMips();
if (fitness<runtime)
{
fitness=runtime;
}
} return fitness;
} private static ArrayList<int[]> GA(ArrayList<int[]> pop,int gmax,double crossoverProb,double mutationRate)
{
HashMap<Integer,double[]> segmentForEach=calcSelectionProbs(pop);
ArrayList<int[]> children=new ArrayList<int[]>();
ArrayList<int[]> tempParents=new ArrayList<int[]>();
while(children.size()<pop.size())
{
//selection phase:select two parents each time.
for(int i=0;i<2;i++)
{
double prob = new Random().nextDouble();
for (int j = 0; j < pop.size(); j++)
{
if (isBetween(prob, segmentForEach.get(j)))
{
tempParents.add(pop.get(j));
break;
}
}
}
//cross-over phase.
int[] p1,p2,p1temp,p2temp;
p1= tempParents.get(tempParents.size() - 2).clone();
p1temp= tempParents.get(tempParents.size() - 2).clone();
p2 = tempParents.get(tempParents.size() -1).clone();
p2temp = tempParents.get(tempParents.size() -1).clone();
if(new Random().nextDouble()<crossoverProb)
{
int crossPosition = new Random().nextInt(cloudletList.size() - 1);
//cross-over operation
for (int i = crossPosition + 1; i < cloudletList.size(); i++)
{
int temp = p1temp[i];
p1temp[i] = p2temp[i];
p2temp[i] = temp;
}
}
//choose the children if they are better,else keep parents in next iteration.
children.add(getFitness(p1temp) < getFitness(p1) ? p1temp : p1);
children.add(getFitness(p2temp) < getFitness(p2) ? p2temp : p2);
// mutation phase.
if (new Random().nextDouble() < mutationRate)
{
// mutation operations bellow.
int maxIndex = children.size() - 1; for (int i = maxIndex - 1; i <= maxIndex; i++)
{
operateMutation(children.get(i), mutationRate);
}
}
} gmax--;
return gmax > 0 ? GA(children, gmax, crossoverProb, mutationRate): children;
} public static void operateMutation(int []child,double mutationRate)
{
if(new Random().nextDouble()<mutationRate)
{
int mutationIndex=new Random().nextInt(cloudletList.size());
int newVmId=new Random().nextInt(vmList.size());
while(child[mutationIndex]==newVmId)
{
newVmId=new Random().nextInt(vmList.size());
} child[mutationIndex]=newVmId;
}
} private static boolean isBetween(double prob,double[]segment)
{
if(segment[0]<=prob&&prob<=segment[1])
return true;
return false;
} private static HashMap<Integer,double[]> calcSelectionProbs(ArrayList<int[]> parents)
{
int size=parents.size();
double totalFitness=0;
ArrayList<Double> fits=new ArrayList<Double>();
HashMap<Integer,Double> probs=new HashMap<Integer,Double>(); for(int i=0;i<size;i++)
{
double fitness=getFitness(parents.get(i));
fits.add(fitness);
totalFitness+=fitness;
}
for(int i=0;i<size;i++)
{
probs.put(i,fits.get(i)/totalFitness );
} return getSegments(probs);
} private static HashMap<Integer,double[]> getSegments(HashMap<Integer,Double> probs)
{
HashMap<Integer,double[]> probSegments=new HashMap<Integer,double[]>();
//probSegments保存每个个体的选择概率的起点、终点，以便选择作为交配元素。
int size=probs.size();
double start=0;
double end=0;
for(int i=0;i<size;i++)
{
end=start+probs.get(i);
double[]segment=new double[2];
segment[0]=start;
segment[1]=end;
probSegments.put(i, segment);
start=end;
} return probSegments;
}