遗传算法在 Dart/Flutter 中吐出奇怪的结果

Question

在我的应用程序中，我使用遗传算法对某个问题取得了很好的结果。算法本身是同步的，但调用它的函数是异步的，以防止 UI 冻结。

在我的算法中，变量 bestSolution 保留算法迄今为止生成的最佳解决方案。只要算法找到比当前 bestSolution 更好的解决方案，它就会发生变化。更改后，我还将新的 bestSolution 打印到日志中。

算法完成后（目前在500代后完成），bestSolution被传递给调用遗传算法的函数来更新UI。但是最后的 bestSolution 与之前的任何值都完全不同。我尝试了很多次，但最终结果从未在控制台中记录，而且对于算法试图实现的目标来说也是一个非常糟糕的结果。

我会把算法和一些日志输出放在这里，调用它的函数只是调用我的 GeneticAlgorithmSolver 的 solve() 函数。非常感谢任何帮助。

算法：

import 'dart:math';

import 'package:flutter/material.dart';
import 'package:meal_tracker/model/meal.dart';

class GeneticAlgorithmSolver {
  Random random = Random();

  List<Meal> breakfasts;
  List<Meal> lunches;
  List<Meal> dinners;

  double proteinGoal;
  double carbGoal;
  double fatGoal;

  int generationCount;
  int populationCount;
  double mutationChance;

  List currentGen;

  GeneticAlgorithmSolver(
      {this.breakfasts,
      this.lunches,
      this.dinners,
      this.proteinGoal,
      this.carbGoal,
      this.fatGoal,
      this.generationCount,
      this.populationCount,
      this.mutationChance})
      : assert(breakfasts.length > 0),
        assert(lunches.length > 0),
        assert(dinners.length > 0);

  List bestSolution;
  double bestSolutionFitness = 0.0;

  //This function generates the first generation, and then calls nextGen() as often as generationCount.
  //At the end it returns bestSolution, which is changed throughout the algorithm within the nextGen() function.
  List solve() {
    currentGen = generateFirstGen(
        breakfasts: breakfasts, lunches: lunches, dinners: dinners);
    print("population size: " + currentGen.length.toString());
    for (int i = 0; i < generationCount; i++) {
      print("Starting generation: " + i.toString());
      currentGen = nextGen(currentGen);
      if (generationCount - i == 1) {
        print(bestSolution[0].toJson());
      }
    }
    print(bestSolutionFitness);
    print(bestSolution[0].toJson());
    return bestSolution;
  }

  //This function returns as many random solutions as populationCount, therefore generating the first generation.
  //I'm pretty sure that the bug is not in here.
  List<List<Meal>> generateFirstGen(
      {@required List breakfasts,
      @required List lunches,
      @required List dinners}) {
    List<List<Meal>> gen = [];

    for (int i = 0; i < populationCount; i++) {
      List<Meal> list = [
        breakfasts[(random.nextDouble() * (breakfasts.length - 1)).round()],
        lunches[(random.nextDouble() * (lunches.length - 1)).round()],
        dinners[(random.nextDouble() * (dinners.length - 1)).round()]
      ];
      for (int y = 0; y < list.length; y++) {
        for (int z = 0; z < list[y].foods.length; z++) {
          list[y].setFactor(z, random.nextDouble());
        }
      }
      gen.add(list);
    }
    return gen;
  }

  double calculateFitness(num current, num max) {
    double fitness = (current / max).clamp(0, 2);
    if (fitness > 1) {
      return 2 - fitness;
    }
    assert(fitness > 0 && fitness <= 1);
    return fitness;
  }

  //This function takes the current generation and sorts the results based on their fitness(how good they are)
  //Then it merges results and returns a new generation.
  List<List<Meal>> nextGen(List<List<Meal>> currentGen) {
    List<List<Meal>> nextGen = [];

    List<Map<String, dynamic>> fitnessMap = [];

    currentGen.forEach((f) {
      double protein = 0.0;
      double fat = 0.0;
      double carb = 0.0;

      for (int i = 0; i < f.length; i++) {
        protein += f[i].calculateProtein();
        fat += f[i].calculateFat();
        carb += f[i].calculateCarbs();
      }

      fitnessMap.add({
        "day": f,
        "fitness": (calculateFitness(protein, proteinGoal) +
                calculateFitness(fat, fatGoal) +
                calculateFitness(carb, carbGoal)) /
            3
      });
    });

    List sortedGen = [];

    //Simple Bubblesort to sort the results based on their fitness.
    bool sorted = false;

    for (int i = 0; i < fitnessMap.length && !sorted; i++) {
      sorted = true;
      for (int y = 0; y < fitnessMap.length - i - 1; y++) {
        if (fitnessMap[y]["fitness"] > fitnessMap[y + 1]["fitness"]) {
          sorted = false;
          Map temp = fitnessMap[y];
          fitnessMap[y] = fitnessMap[y + 1];
          fitnessMap[y + 1] = temp;
        }
      }
    }

    print(List.generate(fitnessMap.length, (i) => fitnessMap[i]["fitness"]));

    //Since fitnessMap is sorted, the last item should be the best(the one with the highest fitness)
    Map bestResult = fitnessMap[fitnessMap.length - 1];

    //If then the current best result is better than the overall best result, the current best becomes the new overall best.
    if (bestResult["fitness"] > bestSolutionFitness) {
      print("=======NEW BEST======= : " + bestResult["fitness"].toString());
      print(List.generate(
          bestResult["day"].length, (i) => bestResult["day"][i].toJson()));

      double protein = 0.0;
      double fat = 0.0;
      double carb = 0.0;

      for (int i = 0; i < bestResult["day"].length; i++) {
        protein += bestResult["day"][i].calculateProtein();
        fat += bestResult["day"][i].calculateFat();
        carb += bestResult["day"][i].calculateCarbs();
      }

      var calcut = (calculateFitness(protein, proteinGoal) +
              calculateFitness(fat, fatGoal) +
              calculateFitness(carb, carbGoal)) /
          3;

      print("=======Calculat======= : " + calcut.toString());
      bestSolution = bestResult["day"];
      print(bestSolution[0].toJson());
      print(bestResult["day"][0].toJson());
      bestSolutionFitness = bestResult["fitness"];
    }

    sortedGen = List.generate(fitnessMap.length, (i) => fitnessMap[i]["day"]);

    //Here is the merging process, it's very messy and the bug is not here for sure.
    for (int i = 0; i < populationCount; i++) {
      List child;
      List firstParent = sortedGen[min(
          (sqrt(random.nextDouble()) * (sortedGen.length - 1)).round(),
          sortedGen.length - 1)];
      child = firstParent;
      int firstIndex = random.nextInt(child.length);
      int secondIndex = random.nextInt(child.length);
      List secondParent = sortedGen[min(
          (sqrt(random.nextDouble()) * (sortedGen.length - 1)).round(),
          sortedGen.length - 1)];
      for (int i = min(firstIndex, secondIndex);
          i < max(firstIndex, secondIndex);
          i++) {
        child[i] = secondParent[i];
      }

      for (int i = 0; i < child.length; i++) {
        if (random.nextDouble() <= mutationChance) {
          switch (i) {
            case 0:
              child[i] = breakfasts[
                  (random.nextDouble() * (breakfasts.length - 1)).round()];
              break;
            case 1:
              child[i] =
                  lunches[(random.nextDouble() * (lunches.length - 1)).round()];
              break;
            case 2:
              child[i] =
                  dinners[(random.nextDouble() * (dinners.length - 1)).round()];
              break;
          }
        }
      }

      for (int i = 0; i < child.length; i++) {
        for (int y = 0; y < child[i].getItemCount; y++) {
          if (random.nextDouble() <= mutationChance) {
            child[i].setFactor(y, random.nextDouble());
          }
        }
      }

      nextGen.add(child);
    }

    return nextGen;
  }
}

这是一个示例日志输出，我将生成数减少到 20，这样 Whosebug 就不会抱怨垃圾邮件了：

I/flutter (21224): Starting generation: 0
I/flutter (21224): [0.5313978709043187, 0.5313978709043187, 0.5313978709043187, 0.5313978709043187, 0.5313978709043187, 0.7299423655395717, 0.7299423655395717, 0.7299423655395717, 0.7374132001763957, 0.8297048120160494]
I/flutter (21224): =======NEW BEST======= : 0.8297048120160494
I/flutter (21224): [{name: Haferflocken mit Milch, ingredients: [{food: {name: Haferflocken, fat: 7.1, saturatedFat: 1.5, carb: 56.0, sugar: 1.1, fiber: 9.7, protein: 11.0, sodium: 0.02, vitaminA: null, vitaminC: null, vitaminD: null, vitaminE: null, iron: null, calcium: null, foodtype: grain, barcode: 4019339242018}, amount: 150.0, scalability: 100.0, factor: 0.819958805652279}, {food: {name: Vollmilch, fat: 4.0, saturatedFat: 2.6, carb: 4.9, sugar: 4.9, fiber: null, protein: 3.3, sodium: 0.11, vitaminA: null, vitaminC: null, vitaminD: null, vitaminE: null, iron: null, calcium: null, foodtype: dairy, barcode: 4101530001157}, amount: 400.0, scalability: 200.0, factor: 0.2969825022643108}]}, {name: Reis mit Hänchen, ingredients: [{food: {name: Naturreis, fat: 2.2, saturatedFat: 0.6, carb: 74.0, sugar: 0.7, fiber: 2.2, protein: 7.8, sodium: 0.01, vitaminA: null, vitaminC: null, vitaminD: null, vitaminE: null, iron: null, calcium: null, foodtype: vegetables, barcode: 4019339212189}, amount: 100.0, scalability: 75.0, factor: 0.69
I/flutter (21224): =======Calculat======= : 0.8297048120160494
I/flutter (21224): {name: Haferflocken mit Milch, ingredients: [{food: {name: Haferflocken, fat: 7.1, saturatedFat: 1.5, carb: 56.0, sugar: 1.1, fiber: 9.7, protein: 11.0, sodium: 0.02, vitaminA: null, vitaminC: null, vitaminD: null, vitaminE: null, iron: null, calcium: null, foodtype: grain, barcode: 4019339242018}, amount: 150.0, scalability: 100.0, factor: 0.819958805652279}, {food: {name: Vollmilch, fat: 4.0, saturatedFat: 2.6, carb: 4.9, sugar: 4.9, fiber: null, protein: 3.3, sodium: 0.11, vitaminA: null, vitaminC: null, vitaminD: null, vitaminE: null, iron: null, calcium: null, foodtype: dairy, barcode: 4101530001157}, amount: 400.0, scalability: 200.0, factor: 0.2969825022643108}]}
I/flutter (21224): {name: Haferflocken mit Milch, ingredients: [{food: {name: Haferflocken, fat: 7.1, saturatedFat: 1.5, carb: 56.0, sugar: 1.1, fiber: 9.7, protein: 11.0, sodium: 0.02, vitaminA: null, vitaminC: null, vitaminD: null, vitaminE: null, iron: null, calcium: null, foodtype: grain, barcode: 4019339242018}, amount: 150.0, scalability: 100.0, factor: 0.819958805652279}, {food: {name: Vollmilch, fat: 4.0, saturatedFat: 2.6, carb: 4.9, sugar: 4.9, fiber: null, protein: 3.3, sodium: 0.11, vitaminA: null, vitaminC: null, vitaminD: null, vitaminE: null, iron: null, calcium: null, foodtype: dairy, barcode: 4101530001157}, amount: 400.0, scalability: 200.0, factor: 0.2969825022643108}]}
I/flutter (21224): Starting generation: 1
I/flutter (21224): [0.5283462335935579, 0.5283462335935579, 0.5283462335935579, 0.5283462335935579, 0.5283462335935579, 0.5283462335935579, 0.5283462335935579, 0.7075198382526259, 0.7075198382526259, 0.7075198382526259]
I/flutter (21224): Starting generation: 2
I/flutter (21224): [0.5283462335935579, 0.5283462335935579, 0.5283462335935579, 0.5283462335935579, 0.5283462335935579, 0.5283462335935579, 0.737783580588736, 0.737783580588736, 0.737783580588736, 0.737783580588736]
I/flutter (21224): Starting generation: 3
I/flutter (21224): [0.738428332595959, 0.738428332595959, 0.738428332595959, 0.738428332595959, 0.738428332595959, 0.738428332595959, 0.738428332595959, 0.738428332595959, 0.738428332595959, 0.738428332595959]
I/flutter (21224): Starting generation: 4
I/flutter (21224): [0.7258426264768459, 0.7258426264768459, 0.7258426264768459, 0.7258426264768459, 0.7258426264768459, 0.7258426264768459, 0.7258426264768459, 0.7258426264768459, 0.7258426264768459, 0.7258426264768459]
I/flutter (21224): Starting generation: 5
I/flutter (21224): [0.5589823816277794, 0.5589823816277794, 0.5589823816277794, 0.5589823816277794, 0.5589823816277794, 0.5589823816277794, 0.5589823816277794, 0.5589823816277794, 0.5589823816277794, 0.5589823816277794]
I/flutter (21224): Starting generation: 6
I/flutter (21224): [0.5574443375428283, 0.5574443375428283, 0.5574443375428283, 0.5574443375428283, 0.5574443375428283, 0.5574443375428283, 0.5574443375428283, 0.5574443375428283, 0.5574443375428283, 0.5574443375428283]
I/flutter (21224): Starting generation: 7
I/flutter (21224): [0.48318974082968635, 0.48318974082968635, 0.48318974082968635, 0.48318974082968635, 0.48318974082968635, 0.48318974082968635, 0.48318974082968635, 0.48318974082968635, 0.48318974082968635, 0.48318974082968635]
I/flutter (21224): Starting generation: 8
I/flutter (21224): [0.4932906839506798, 0.4932906839506798, 0.4932906839506798, 0.4932906839506798, 0.4932906839506798, 0.4932906839506798, 0.4932906839506798, 0.4932906839506798, 0.4932906839506798, 0.4932906839506798]
I/flutter (21224): Starting generation: 9
I/flutter (21224): [0.4807063467379004, 0.4807063467379004, 0.4807063467379004, 0.8154292293208805, 0.8154292293208805, 0.8154292293208805, 0.8154292293208805, 0.8154292293208805, 0.8154292293208805, 0.8154292293208805]
I/flutter (21224): Starting generation: 10
I/flutter (21224): [0.4718540151810169, 0.4718540151810169, 0.4718540151810169, 0.4718540151810169, 0.4718540151810169, 0.4718540151810169, 0.4718540151810169, 0.4718540151810169, 0.4718540151810169, 0.4718540151810169]
I/flutter (21224): Starting generation: 11
I/flutter (21224): [0.5314764343948387, 0.5314764343948387, 0.5314764343948387, 0.5314764343948387, 0.5314764343948387, 0.5314764343948387, 0.5314764343948387, 0.5314764343948387, 0.5314764343948387, 0.5314764343948387]
I/flutter (21224): Starting generation: 12
I/flutter (21224): [0.5256306490767777, 0.5256306490767777, 0.5256306490767777, 0.5256306490767777, 0.5256306490767777, 0.5256306490767777, 0.5256306490767777, 0.5256306490767777, 0.5256306490767777, 0.5256306490767777]
I/flutter (21224): Starting generation: 13
I/flutter (21224): [0.48081998808270626, 0.48081998808270626, 0.48081998808270626, 0.48081998808270626, 0.48081998808270626, 0.48081998808270626, 0.48081998808270626, 0.48081998808270626, 0.48081998808270626, 0.48081998808270626]
I/flutter (21224): Starting generation: 14
I/flutter (21224): [0.46594810317838503, 0.46594810317838503, 0.46594810317838503, 0.46594810317838503, 0.46594810317838503, 0.46594810317838503, 0.46594810317838503, 0.46594810317838503, 0.46594810317838503, 0.46594810317838503]
I/flutter (21224): Starting generation: 15
I/flutter (21224): [0.6831840326295633, 0.6831840326295633, 0.6831840326295633, 0.6831840326295633, 0.6831840326295633, 0.6831840326295633, 0.6831840326295633, 0.6831840326295633, 0.6831840326295633, 0.6831840326295633]
I/flutter (21224): Starting generation: 16
I/flutter (21224): [0.6642059362880226, 0.6642059362880226, 0.6642059362880226, 0.6642059362880226, 0.6642059362880226, 0.6642059362880226, 0.6642059362880226, 0.6642059362880226, 0.6642059362880226, 0.6642059362880226]
I/flutter (21224): Starting generation: 17
I/flutter (21224): [0.4404899494909354, 0.4404899494909354, 0.4404899494909354, 0.4404899494909354, 0.4404899494909354, 0.4404899494909354, 0.4404899494909354, 0.4404899494909354, 0.4404899494909354, 0.4404899494909354]
I/flutter (21224): Starting generation: 18
I/flutter (21224): [0.6809769097776095, 0.6809769097776095, 0.6809769097776095, 0.6809769097776095, 0.6809769097776095, 0.6809769097776095, 0.6809769097776095, 0.6809769097776095, 0.6809769097776095, 0.6809769097776095]
I/flutter (21224): Starting generation: 19
I/flutter (21224): [0.6818085009500662, 0.6818085009500662, 0.6818085009500662, 0.6818085009500662, 0.6818085009500662, 0.6818085009500662, 0.6818085009500662, 0.6818085009500662, 0.6818085009500662, 0.6818085009500662]
I/flutter (21224): {name: Haferflocken mit Milch, ingredients: [{food: {name: Haferflocken, fat: 7.1, saturatedFat: 1.5, carb: 56.0, sugar: 1.1, fiber: 9.7, protein: 11.0, sodium: 0.02, vitaminA: null, vitaminC: null, vitaminD: null, vitaminE: null, iron: null, calcium: null, foodtype: grain, barcode: 4019339242018}, amount: 150.0, scalability: 100.0, factor: 0.3877294684577154}, {food: {name: Vollmilch, fat: 4.0, saturatedFat: 2.6, carb: 4.9, sugar: 4.9, fiber: null, protein: 3.3, sodium: 0.11, vitaminA: null, vitaminC: null, vitaminD: null, vitaminE: null, iron: null, calcium: null, foodtype: dairy, barcode: 4101530001157}, amount: 400.0, scalability: 200.0, factor: 0.7549218291162099}]}
I/flutter (21224): 0.8297048120160494
I/flutter (21224): {name: Haferflocken mit Milch, ingredients: [{food: {name: Haferflocken, fat: 7.1, saturatedFat: 1.5, carb: 56.0, sugar: 1.1, fiber: 9.7, protein: 11.0, sodium: 0.02, vitaminA: null, vitaminC: null, vitaminD: null, vitaminE: null, iron: null, calcium: null, foodtype: grain, barcode: 4019339242018}, amount: 150.0, scalability: 100.0, factor: 0.3877294684577154}, {food: {name: Vollmilch, fat: 4.0, saturatedFat: 2.6, carb: 4.9, sugar: 4.9, fiber: null, protein: 3.3, sodium: 0.11, vitaminA: null, vitaminC: null, vitaminD: null, vitaminE: null, iron: null, calcium: null, foodtype: dairy, barcode: 4101530001157}, amount: 400.0, scalability: 200.0, factor: 0.7549218291162099}]}
I/flutter (21224): {name: Haferflocken mit Milch, ingredients: [{food: {name: Haferflocken, fat: 7.1, saturatedFat: 1.5, carb: 56.0, sugar: 1.1, fiber: 9.7, protein: 11.0, sodium: 0.02, vitaminA: null, vitaminC: null, vitaminD: null, vitaminE: null, iron: null, calcium: null, foodtype: grain, barcode: 4019339242018}, amount: 150.0, scalability: 100.0, factor: 0.3877294684577154}, {food: {name: Vollmilch, fat: 4.0, saturatedFat: 2.6, carb: 4.9, sugar: 4.9, fiber: null, protein: 3.3, sodium: 0.11, vitaminA: null, vitaminC: null, vitaminD: null, vitaminE: null, iron: null, calcium: null, foodtype: dairy, barcode: 4101530001157}, amount: 400.0, scalability: 200.0, factor: 0.7549218291162099}]}

正如您所看到的，每次算法都会打印 =======NEW BEST======= : //new best score，然后是新的最佳解决方案的 JSON。文末的JSON就是函数solve()returns的意思。如您所见，结尾的 JSON 文本不同于之前打印的任何 JSON.

提前感谢任何阅读本文并试图帮助我的人！

Answer 1

您需要复制 Meals 和 List<Meals> 而不是在您的变异过程中对它们进行变异。注意你是怎么做的

      List child;
      List firstParent = sortedGen[min(
          (sqrt(random.nextDouble()) * (sortedGen.length - 1)).round(),
          sortedGen.length - 1)];
      child = firstParent;
      int firstIndex = random.nextInt(child.length);
      int secondIndex = random.nextInt(child.length);
      List secondParent = sortedGen[min(
          (sqrt(random.nextDouble()) * (sortedGen.length - 1)).round(),
          sortedGen.length - 1)];
      for (int i = min(firstIndex, secondIndex);
          i < max(firstIndex, secondIndex);
          i++) {
        child[i] = secondParent[i];
      }

然后你做：

  for (int i = 0; i < child.length; i++) {
    for (int y = 0; y < child[i].getItemCount; y++) {
      if (random.nextDouble() <= mutationChance) {
        child[i].setFactor(y, random.nextDouble());
      }
    }
  }

在这种情况下，您只是改变构成 parents 的膳食。相反，您需要进行深拷贝。

遗传算法在 Dart/Flutter 中吐出奇怪的结果

Genetic algorithm spits out strange result in Dart/Flutter

genetic-algorithm

dart

flutter