1

我有以下一直困扰着我的大学作业。我必须实现一种将进程分配到处理器中的遗传算法。更具体地说，问题如下：

“您有一个在并行处理器系统中计算的程序。该程序由 N 个进程组成，这些进程需要在多个处理器上分配（其中 n 远小于 N）。在此期间进程的通信整个过程可能非常耗时，因此最佳做法是将需要相互通信的进程分配给同一处理器。

为了减少进程之间的通信时间，您可以将这些进程分配给同一个处理器，但这会否定每个处理器都需要为整个进程做出贡献的并行处理理念。

考虑以下内容：假设 Cij 是进程 i 和进程 j 之间的通信总量。假设每个进程需要相同数量的计算能力，以便可以通过将相同数量的进程分配给处理器来处理处理过程的限制。使用遗传算法将 N 个进程分配给 n 个处理器。”

以上是对问题描述的大致翻译。现在我有以下问题让我感到困惑。

1）为了让遗传算法运行，最好的可行解决方案是什么。我有他们背后的理论，我推断你需要一个最好的解决方案来检查每一代生产的人口。

2）如何正确设计整个问题以便由程序处理。

我计划在 Java 中实现这一点，但欢迎对其他编程语言提出任何其他建议。

4

1 回答 1

0

大叔坚持。或者 El Duderino，如果你不喜欢整个简洁的事情。您要问的实际上是一个两部分的问题，但是遗传算法部分可以很容易地在概念上进行说明。我发现给出一个基本的开始可能会有所帮助，但是这个问题作为一个“整体”太复杂了，无法在这里解决。

正如您所注意到的，遗传算法 (GA) 可以用作优化器。为了将 GA 应用于流程执行计划，您需要能够对执行计划进行评分，然后克隆和变异最佳计划。遗传算法的工作原理是运行多个计划，克隆最好的，然后稍微改变其中的一些，以查看后代（克隆）计划是改进还是恶化。

在这个例子中，我创建了一个包含 100 个随机整数的数组。每个 Integer 都是要运行的“进程”，Integer 的值是运行该单独进程的“成本”。

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 代并绘制结果，典型的运行将如下所示：

每一代的最佳成本

GA 的目的是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;
    }
}
于 2016-04-29T03:27:39.860 回答