如何更快地生成约束多目标优化中的初始种群

Question

我使用 NSGA-II 来解决受约束的 MOOP、饲料配方问题。在初始化步骤中，我总是在接受并放入种群之前验证生成的随机染色体是否需要约束。但是这一步需要的时间比较长，大约需要24小时。

如果我没有验证染色体，给出的解不满足约束条件。大多数解决方案仅满足 8 的 1 - 2 营养限制。

在这种情况下，如何快速生成初始种群？

// method to generate a chromosome
public Variable[] createVariables() {
    Variable[] variables = new Variable[problem_.getNumberOfVariables()];

    Random random = new Random();
    boolean variablesConfirmed = false;
    FeedFormulation feedF = (FeedFormulation) problem_;

    while (!variablesConfirmed) {

        // generate a chromosome randomly, each genes in a chromosome have different lower and upper limit
        for (int var = 0; var < problem_.getNumberOfVariables(); var++) {
            variables[var] = new RealCustom(random, problem_.getLowerLimit(var), problem_.getUpperLimit(var));
        }

        // check if the generated chromosome meet constraint (nutrient needs)
        variablesConfirmed = checkVariable(feedF, variables);
    }

    return variables;
}

// method to check if the generated chromosome meet constraint (nutrient needs)
private boolean checkVariable(FeedFormulation feedF, Variable[] variables) {

    int numberConfirmedNutrient = 0;
    int numberUnconfirmedNutrient = 0;
    float unconfirmedNutrientPercentation = 75f;

    Set<String> nutrients = getnutrients(feedF.getIngredients());
    Map<String, Double> sumOfNutrientI;

    sumOfNutrientI = getSumOfNutrientI(getSumOfProportion(variables),
            nutrients,
            feedF.getIngredients(),
            getVariables(variables));

    NutrientNeeds nutrientNeeds = feedF.getAnimal().getNutrientNeeds();

    Set nutrientKeys = sumOfNutrientI.keySet();

    for (Iterator ky = nutrientKeys.iterator(); ky.hasNext();) {
        String key = (String) ky.next();

        // if nutrient (key) need has min and max limit
        if (nutrientNeeds.getNutrientNeed(key).getMax() != 0) {
            if ((sumOfNutrientI.get(key) > nutrientNeeds.getNutrientNeed(key).getMin()
                    || sumOfNutrientI.get(key) == nutrientNeeds.getNutrientNeed(key).getMin())
                    && (sumOfNutrientI.get(key) < nutrientNeeds.getNutrientNeed(key).getMax()
                    || sumOfNutrientI.get(key) == nutrientNeeds.getNutrientNeed(key).getMax())) {

                numberConfirmedNutrient++;

            } else {

                numberUnconfirmedNutrient++;

                if (numberUnconfirmedNutrient > 0) { break; }

            }
        } else { // if max nutrient (key) need = infinity
            if (sumOfNutrientI.get(key) > nutrientNeeds.getNutrientNeed(key).getMin()
                    || sumOfNutrientI.get(key) == nutrientNeeds.getNutrientNeed(key).getMin()) {

                numberConfirmedNutrient++;

            } else {

                numberUnconfirmedNutrient++;

                if (numberUnconfirmedNutrient > 0) { break; }
            }
        }
    }

    // return true if all nutrient need satisfied
    return numberConfirmedNutrient == nutrientKeys.size();
}

private double[] getVariables(Variable[] variables) {

    double[] x = new double[problem_.getNumberOfVariables()]; // variable values

    for (int i = 0; i < problem_.getNumberOfVariables(); i++) {
        x[i] = variables[i].getValue();
    }

    return x;
}

private double getSumOfProportion(Variable[] variables) {

    double[] x = getVariables(variables);
    double sumOfProportion = 0d;

    for (int i = 0; i < x.length; i++) {
        sumOfProportion += x[i];
    }

    return sumOfProportion;
}

private Map<String, Double> getSumOfNutrientI(double sumOfProportion, Set<String> nutrients,
        Ingredients choosenIngredients, double[] variables) {

    // store set of sum of i-th nutrient
    // key = nutrient name, value = nutrient content in feed ration
    Map<String, Double> sumOfNutrientI = new HashMap<>();

    for (String nutrien : nutrients) {
        double sumOfNutrientContent = 0;

        for (int j = 0; j < choosenIngredients.getIngredients().size(); j++) {

            // sum  = (j-th_ingredient_proportion / sum_of_proportion) * i-th_nutrient_content_in_j-th_ingredient
            sumOfNutrientContent
                    += ((variables[j] / sumOfProportion)
                    * choosenIngredients.getIngredients().get(j).getNutrien(nutrien).getContent());
        }

        sumOfNutrientI.put(nutrien, sumOfNutrientContent);
    }
    return sumOfNutrientI;

}

private Set<String> getnutrients(Ingredients choosenIngredients) {

    Set<String> nutrients = new HashSet<>();

    for (int i = 0; i < choosenIngredients.getIngredients().size(); i++) {

        Ingredient ingredient = choosenIngredients.getIngredients().get(i);
        for (int j = 0; j < ingredient.getNutrients().size(); j++) {
            nutrients.add(ingredient.getNutrients().get(j).getNutrientName());
        }
    }

    return nutrients;
}

createVariables 方法评估 n 次，其中 n = 人口规模。下面的代码用于生成实数。

public class RealCustom extends Variable {

    private double value_;
    private double lowerBound_;
    private double upperBound_;

    public RealCustom(Random random, double lowerBound, double upperBound) {
        lowerBound_ = lowerBound;
        upperBound_ = upperBound;
        value_ = (random.nextInt((int) ((upperBound - lowerBound) * 10 + 1)) + (lowerBound * 10)) / 10.0;
    }

    public RealCustom(double lowerBound, double upperBound, double value) {
        lowerBound_ = lowerBound;
        upperBound_ = upperBound;
        value_ = value;
    }

    public double getValue() {
        return value_;
    }

    public void setValue(double value) {
        value_ = value;
    }

    ....
    ....
}

我需要快速生成初始种群。但是使用这些代码，人口生成需要太多时间，因为新生成的 chromosome/variables 将不会被放入人口中，直到所有营养需求都满足 createVariables 方法中确认。

我不认为这个问题是由MOOP（CMIIW）的设计引起的。我想到的是我必须使用并发或多线程来加快人口生成速度，但我对此表示怀疑。那么有什么建议吗？

Answer 1

我在控制语句中犯了一个错误，导致种群生成速度变慢。

// if nutrient (key) need has min and max limit
if (nutrientNeeds.getNutrientNeed(key).getMax() != 0) {
     if ((sumOfNutrientI.get(key) > 
          ...
     } 
}

应该是

if (nutrientNeeds.getNutrientNeed(key).getMax() != Double.POSITIVE_INFINITY) {
     if ((sumOfNutrientI.get(key) > 
         ...
     } 
}

如何更快地生成约束多目标优化中的初始种群

How to generate initial population in constrained multiobjective optimization faster

java

genetic-algorithm