java - 进程分配的遗传算法

Question

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

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

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

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

以上是对问题描述的粗略翻译。现在我有以下问题困扰着我。

1) 为了运行遗传算法，最好的可行解决方案是什么。我有它们背后的理论，我推断你需要一个可能的最佳解决方案来检查每一代产生的种群。

2) 我怎样才能正确设计整个问题以便由程序处理。

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

Answer 1

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

如您所述，遗传算法 (GA) 可用作优化器。为了将 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可以被评分、克隆和变异。因此，通往成功的道路是在你的脑海中分离问题。首先，弄清楚如何制定一个执行计划，该计划可以根据在假定的一组硬件上实际运行它的成本进行评分。添加例程以克隆和变异 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;
    }
}