Ytukyg

In my app i use a genetic algorithm to get a good result to a certain problem. The algorithm itself is synchronous, but the function calling it is asynchronous to keep the UI from freezing.

In my algorithm, the variable bestSolution keeps the best solution the algorithm has produced so far. It gets changed whenever the algorithm finds a solution that is better than the current bestSolution. When it's changed i also print the new bestSolution into the log.

After the algorithm is finished(currently finishes after 500 generations), bestSolution is passed to the function that called the genetic algorithm to update the UI. But the bestSolution at the end is completely different to any value it has been before. I tried it multiple times, and the end result was never logged in the console, and also was a very bad result for what the algorithm is trying to achieve.

I'll put the algorithm aswell as some log output here, the function calling it just calls the solve() function of my GeneticAlgorithmSolver. Any help is very much appreciated.

The algorithm:

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;

  }

}

Here is a sample log output, i decreased the number of generations to 20 so StackOverflow doesn't complain about spam:

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}]}

As you can see every time the algorithm prints =======NEW BEST======= : //new best score, followed by the JSON of the new best solution. The JSON text at the end is what the function solve() returns. As you can see the ending JSON Text is unlike any previously printed JSON.

Thanks in advance for anyone even reading this and trying to help me!

You need to be copying Meals and List<Meals> instead you are mutating them in place in your mutation procedure. Notice how you do

      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];

      }

And then you do:

  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());

      }

    }

  }

In this case you are just mutating meals that compose parents. Instead you need to do a deep copy.