我有一个令我困惑的大学作业。我必须实现一个将进程分配到处理器的遗传算法具体来说，问题如下：
“你有一个在并行处理器系统中计算的程序。程序由n个进程组成，这些进程需要在n个处理器上分配（其中n比n小）。在整个过程中，进程之间的通信可能非常耗时，因此最佳做法是将需要相互通信的进程分配给同一个处理器。
为了减少进程之间的通信时间，可以将这些进程分配给同一个处理器，但这会否定并行处理的想法，即每个处理器都需要对整个进程作出贡献。
考虑以下情况：假设cij是进程i和进程j之间的通信总量。假设每个进程需要相同的计算能力，以便通过将相同数量的进程分配给一个处理器来处理处理进程的限制。使用遗传算法将n个进程分配给n个处理器。”
以上是对问题的大致描述。现在我有一个令我困惑的问题。
1）为了使遗传算法能够运行，什么是最可行的解决方案。我有他们背后的理论，我推断你需要一个最好的可能的解决方案，以检查每一代的生产人口。
2）如何正确设计整个问题，以便由程序处理。
我正计划用java实现这一点，但欢迎对其他编程语言提出任何其他建议。
最佳答案
那家伙还活着。或者如果你不喜欢简洁的话。
你所问的其实是一个分为两部分的问题，但遗传算法部分可以很容易地用概念来说明我发现，做一个基本的开始是有帮助的，但这个问题作为一个“整体”太复杂了，在这里无法解决。
正如您所注意到的，遗传算法（GA）可以用作优化器为了将GA应用于流程执行计划，您需要能够对执行计划进行评分，然后克隆和变异最佳计划遗传算法的工作原理是运行几个计划，克隆出最好的计划，然后对其中一些计划稍加变异，看看后代（克隆的）计划是否得到改善或恶化。
在这个例子中，我创建了一个100个随机整数的数组。每个整数都是要运行的“进程”，整数的值是运行单个进程的“成本”。
List<Integer> processes = new ArrayList<Integer>();
然后将这些进程添加到
ExecutionPlan，即List<List<Integer>>。此整数列表将用于表示执行25轮处理的4个处理器：class ExecutionPlan implements Comparable<ExecutionPlan> {
List<List<Integer>> plan;
int cost;
执行计划的总成本
cost将通过取每轮的最高过程成本（最大整数）和所有轮的成本之和来计算。因此，优化器的目标是将最初的100个整数（进程）分布到4个“处理器”上的25轮“处理”中，从而使总成本尽可能低。// make 10 execution plans of 25 execution rounds running on 4 processors;
List<ExecutionPlan> executionPlans = createAndIntializePlans(processes);
// Loop on generationCount
for ( int generation = 0; generation < GENERATIONCOUNT; ++generation) {
computeCostOfPlans(executionPlans);
// sort plans by cost
Collections.sort(executionPlans);
// print execution plan costs
System.out.println(generation + " = " + executionPlans);
// clone 5 better plans over 5 worse plans
// i.e., kill off the least fit and reproduce the best fit.
cloneBetterPlansOverWorsePlans(executionPlans);
// mutate 5 cloned plans
mutateClones(executionPlans);
}
当程序运行时，成本最初是随机确定的，但随着每一代的改进如果运行1000代并绘制结果，典型的运行将如下所示：
遗传算法的目的是
Optimize或试图确定最佳可能的解决方案。它可以应用于你的问题的原因是你的ExecutionPlan可以被评分、克隆和变异。因此，通往成功的道路是把你心中的问题分开。首先，找出如何制定一个执行计划，该计划可以根据实际在一组假定的硬件上运行所需的成本进行评分。添加Rountines克隆并突变一个ExecutionPlan。一旦你把它插入到这个GA示例中祝你好运，保持冷静。public class Optimize {
private static int GENERATIONCOUNT = 1000;
private static int PROCESSCOUNT = 100;
private static int MUTATIONCOUNT = PROCESSCOUNT/10;
public static void main(String...strings) {
new Optimize().run();
}
// define an execution plan as 25 runs on 4 processors
class ExecutionPlan implements Comparable<ExecutionPlan> {
List<List<Integer>> plan;
int cost;
public ExecutionPlan(List<List<Integer>> plan) {
this.plan = plan;
}
@Override
public int compareTo(ExecutionPlan o) {
return cost-o.cost;
}
@Override
public String toString() {
return Integer.toString(cost);
}
}
private void run() {
// make 100 processes to be completed
List<Integer> processes = new ArrayList<Integer>();
// assign them a random cost between 1 and 100;
for ( int index = 0; index < PROCESSCOUNT; ++index) {
processes.add( new Integer((int)(Math.random() * 99.0)+1));
}
// make 10 execution plans of 25 execution rounds running on 4 processors;
List<ExecutionPlan> executionPlans = createAndIntializePlans(processes);
// Loop on generationCount
for ( int generation = 0; generation < GENERATIONCOUNT; ++generation) {
computeCostOfPlans(executionPlans);
// sort plans by cost
Collections.sort(executionPlans);
// print execution plan costs
System.out.println(generation + " = " + executionPlans);
// clone 5 better plans over 5 worse plans
cloneBetterPlansOverWorsePlans(executionPlans);
// mutate 5 cloned plans
mutateClones(executionPlans);
}
}
private void mutateClones(List<ExecutionPlan> executionPlans) {
for ( int index = 0; index < executionPlans.size()/2; ++index) {
ExecutionPlan execution = executionPlans.get(index);
// mutate 10 different location swaps, maybe the plan improves
for ( int mutationCount = 0; mutationCount < MUTATIONCOUNT ; ++mutationCount) {
int location1 = (int)(Math.random() * 100.0);
int location2 = (int)(Math.random() * 100.0);
// swap two locations
Integer processCostTemp = execution.plan.get(location1/4).get(location1%4);
execution.plan.get(location1/4).set(location1%4, execution.plan.get(location2/4).get(location2%4));
execution.plan.get(location2/4).set(location2%4, processCostTemp);
}
}
}
private void cloneBetterPlansOverWorsePlans(List<ExecutionPlan> executionPlans) {
for ( int index = 0; index < executionPlans.size()/2; ++index) {
ExecutionPlan execution = executionPlans.get(index);
List<List<Integer>> clonePlan = new ArrayList<List<Integer>>();
for ( int roundNumber = 0; roundNumber < 25; ++roundNumber) {
clonePlan.add( new ArrayList<Integer>(execution.plan.get(roundNumber)) );
}
executionPlans.set( index + executionPlans.size()/2, new ExecutionPlan(clonePlan) );
}
}
private void computeCostOfPlans(List<ExecutionPlan> executionPlans) {
for ( ExecutionPlan execution: executionPlans) {
execution.cost = 0;
for ( int roundNumber = 0; roundNumber < 25; ++roundNumber) {
// cost of a round is greatest "communication time".
List<Integer> round = execution.plan.get(roundNumber);
int roundCost = round.get(0)>round.get(1)?round.get(0):round.get(1);
roundCost = execution.cost>round.get(2)?roundCost:round.get(2);
roundCost = execution.cost>round.get(3)?roundCost:round.get(3);
// add all the round costs' to determine total plan cost
execution.cost += roundCost;
}
}
}
private List<ExecutionPlan> createAndIntializePlans(List<Integer> processes) {
List<ExecutionPlan> executionPlans = new ArrayList<ExecutionPlan>();
for ( int planNumber = 0; planNumber < 10; ++planNumber) {
// randomize the processes for this plan
Collections.shuffle(processes);
// and make the plan
List<List<Integer>> currentPlan = new ArrayList<List<Integer>>();
for ( int roundNumber = 0; roundNumber < 25; ++roundNumber) {
List<Integer> round = new ArrayList<Integer>();
round.add(processes.get(4*roundNumber+0));
round.add(processes.get(4*roundNumber+1));
round.add(processes.get(4*roundNumber+2));
round.add(processes.get(4*roundNumber+3));
currentPlan.add(round);
}
executionPlans.add(new ExecutionPlan(currentPlan));
}
return executionPlans;
}
}
关于java - 遗传算法的流程分配，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36923303/