2
\$\begingroup\$

My code denotes an open source library that makes creating genetic algorithms easier. It's an encapsulated library and is called using the new constructor.

Initialize the genetic algorithm by writing:

var my_algo = new olog.GeneticAlgorithm("target", config)

and evolve it by writing:

my_algo.progress([however many times I want it to run, leave blank if you want it to run till found fittest])

You can find the CodeShare here. Any review is great. Also, I chose object over class due to preference.

(function(exports) {

"use strict";

exports.GeneticAlgorithm = function(input, configurations = {mutation_rate: 0.005, maximum_population: 1500, expansion_multiplier: 10}) {

        /*
        METHODS:
        generate_population => population Array (has no fitness scores)
        assess_population => populaton Array (has fitness scores)
        generate_mating_pool => mating_pool Array (not connected to parent object)
        crossover => population Array (adaptation of generate_population)
        mutate => population Array (mutates the existing population)
        evaluate => results Object (contains a resultation of the algorithm)

        */

        var genetic_algorithm = {
            //Setting up data and variables
            input: input,
            configurations: {
                mutation_rate: (configurations.mutation_rate),
                maximum_population: (configurations.maximum_population),
                expansion_multiplier: (configurations.expansion_multiplier)
            },
            algorithm_data: {
                generations: 0,
                input_type: undefined,
      average_fitness_score: 0,
      time_began: Date.now()
            },
            population: {
                current_population: [],
                mating_pool: []
            },
            //Defining library methods

            //Generates the population
            generate_population: (function(input, input_type, maximum_population, string_generator, number_generator, expansion_multiplier) {

      /*
                input => The input, or target of the algorithm (...)
                input_type => The type of the input, as defined by another method ("string" | "number")
                maximum_population => The maximum number of individuals that the population can hold (0,Inf)
                string_generator => The function that generates a random string (func)
                number_generator => The function that generates a random number (func)
                expansion_multiplier => A number that determines how far the algorithm should look (0, Inf)
                */

                //The population that this method returns
                var return_population = [];

                if (input_type === "string") {
                    for (let i = 0; i < maximum_population; i++) {
                        //Add an individual (string) to the population, baby boom that thing!
                        return_population.push({
                            individual: string_generator(input.length, number_generator),
                            fitness_score: undefined
                        });
                    }

                    return return_population;
                } else if (input_type === "number") {
                    for (let i = 0; i < maximum_population; i++) {
                        //Add an individual (number) to that population, it's a boy!
                        return_population.push({
                            individual: number_generator((input * -1 * expansion_multiplier), (input * expansion_multiplier)),
                            fitness_score: undefined
                        });
                    }

        return return_population;

                }
            }),
            //Assesses the population
            assess_population: (function(input, population, input_type) {

                /*
                input => The input to the algorithm, showing a or the prime example (...)
                population => The collection of individuals (...)
                input_type => The type of the or a prime example ("string" | "number")
                */

                //The population that this method returns
                var return_population = [];
                var fitness_score;

                if (input_type === "string") {
                    //Checks the population individual by the input character-by-character
                    for (let i = 0; i < population.length; i++) {
                        fitness_score = 0;
                        if (population[i].fitness_score === undefined) {
                            for (let j = 0; j < population[i].individual.length; j++) {
                                if (population[i].individual[j] === input[j]) {
                                    fitness_score++;
                                }
                            }
                            return_population.push({
                                individual: population[i].individual,
                                fitness_score: fitness_score
                            });
                        } else {
                            return_population.push(population[i]);
                        }

                    }

        return return_population;

                } else if (input_type === "number") {

                    //Finds by how much the individual deviates from the input
                    for (let i = 0; i < population.length; i++) {

                        fitness_score = Math.abs(population[i].individual - input);

                        return_population.push({
                            individual: population[i].individual,
                            fitness_score: fitness_score
                        });

                        return return_population;
                    }
                }

            }),
            //Generates the mating pool
            generate_mating_pool: (function(population) {

                /*
                population => The collection of individuals in the population (...)
                */

                var maximum_fitness = 0;
                //The mating_pool that this method returns
                var return_mating_pool = [];

                for (let i = 0; i < population.length; i++) {
                    //Gets the maximum fitness scored individual
                    if (population[i].fitness_score > maximum_fitness) {
                        maximum_fitness = population[i].fitness_score;
                    }
                }

                for (let i = 0; i < population.length; i++) {

                    for (let j = 0; j < ((Math.floor(population[i].fitness_score / maximum_fitness) * 100) || 1); j++) {
                        return_mating_pool.push(population[i]);
                    }
                }

                return return_mating_pool;
            }),
            //Cross the individuals over
            crossover: (function(mating_pool, number_generator) {

                /*
                mating_pool => A pool of biased individuals (...)
                number_generator => A function that generates a random number (func)
                */

                //The population that this method returns
                var return_population = [];
                var dividing_point;
                var male;
                var male_genes;
                var female;
                var female_genes;
                var child;
                var child_genes;

                for (let i = 0; i < mating_pool.length; i++) {

                    male = true;
                    female = true;
                    child = "";
                    child_genes = [];
                    dividing_point = 0;

                    //Keeps repeating until the male individual does not equal the female individual
                    while (male === female) {
                        male = mating_pool[Math.floor(number_generator(0, mating_pool.length))];
                        female = mating_pool[Math.floor(number_generator(0, mating_pool.length))];

                        male_genes = male.individual.split("");
                        female_genes = female.individual.split("");
                    }

                    dividing_point = Math.floor(number_generator(0, male_genes.length));

                    //Splits genes up for child crossover
                    for (let j = 0; j < male_genes.length; j++) {
                        if (j < dividing_point) {
                            child_genes.push(male_genes[j]);
                        } else {
                            child_genes.push(female_genes[j]);
                        }
                    }

                    child = {
                        individual: child_genes.join(""),
                        fitness_score: undefined
                    };

                    return_population.push(child);

                }

                return return_population;

            }),
            //Mutates the population
            mutate: (function(input, input_type, population, mutation_rate, number_generator, string_generator, expansion_multiplier) {

                /*
                input => The or a perfect example the algorithm should pursue (...)
                input_type => The type of the or a perfect example the algorithm should pursue (string | number)
                population => Collection of individuals (...)
                mutation_rate => The rate at which the population mutates [0,1]
                number_generator => A function that generates a random number (func)
                string_generator => A function that generates a random string (func)
                expansion_multiplier => A value that tells the algorithm how far it should look for a number (0, Inf)
                */

                //The population that this method returns
                var return_population = [];
                var mutation_determiner = number_generator(0, 1);

                for (let i = 0; i < population.length; i++) {
                    if (mutation_determiner < mutation_rate) {
                        if (input_type === "string") {
                            return_population.push({
                                individual: string_generator(population[i].individual.length, number_generator),
                                fitness_score: undefined
                            });
                        } else if (input_type === "number") {
                            return_population.push({
                                individual: number_generator((input * -1 * expansion_multiplier), (input * expansion_multiplier)),
                                fitness_score: undefined
                            });
                        }
                    } else {
                        return_population.push({
                            individual: population[i].individual,
                            fitness_score: undefined
                        });
                    }
                }

                return return_population;

            }),
            //Evaluates the current fittest
            evaluate_population: (function(input, population, generations, mutation_rate, expansion_multiplier, maximum_population, average_fitness_score, time_began) {

                /*
                input => The or a prime example that the algorithm should model (...)
                population => The collection of individuals (...)
                generations => Measures how many generations the algorithm has been through (0,Inf)
                mutation_rate => Is here to tell the user what they set the mutation rate to [0,1]
                expansion_multiplier => Here to tell what the user set the expansion multiplier to (0, Inf)
                maximum_population => Tells the user what they set the maximum population to (0, Inf)
      average_fitness_score => Tells the method the average fitness score of the algorithm (0, Inf)
      time_began => The point in time where the genetic algorithm was started
                */

                //The results the program returns
                var return_results = {};
                var has_found_fittest = false;
                var fittest = {};
      var average_accuracy = 0;
      var time_elapsed = 0;

                for (let i = 0; i < population.length; i++) {
                    if (population[i].individual === input) {
                        has_found_fittest = true;
                        fittest = population[i];
                        break;
                    }
                }

      average_accuracy = (average_fitness_score / input.length);

      time_elapsed = (Date.now() - time_began);

                //Telling the receiver that the algorithm found the fittest
                return_results.has_found_fittest = has_found_fittest;
                return_results.fittest_individual = fittest;
                return_results.population = population;
                return_results.generations = generations;
                return_results.mutation_rate = mutation_rate;
                return_results.expansion_multiplier = expansion_multiplier;
                return_results.maximum_population = maximum_population;
      return_results.average_fitness_score = average_fitness_score;
      return_results.average_accuracy = average_accuracy;
      return_results.time_elapsed = time_elapsed;

                return return_results;

            }),
            //Generates a random number
            generate_random_number: (function(minimum, maximum) {

                /*
                minimum => The minimum number the function should generate (-Inf, Inf)
                maximum => The maximum number the function should generate (-Inf, Inf)
                */

                //The return number the method returns
                var return_number = 0;

                return_number = Math.random() * (maximum - minimum) + minimum;

                return return_number;
            }),
            //Generates a random string
            generate_random_string: (function(length, number_generator) {

                /*
                length => Tells the method how long the return string should be (0,Inf)
                */

                //The string that this method will be returning
                var return_string = "";

                for (let i = 0; i < length; i++) {
                    return_string += String.fromCharCode(number_generator(0, 65535));
                }

                return return_string;

            }),
            //Identifies the data type
            get_algorithm_data_type: (function(input) {

      /*
      input => Tells the method the input so it can find out the data type (...)
      */

                if (typeof input === "undefined") return;
                if (typeof input === "string") return "string";
                if (typeof input === "number") return "number";
                if (typeof input === "boolean") {
                    input = input.toString();
                    return "string";
                }
                if (Array.isArray(input)) {
                    input = input.join(" ");
                    return "string";
                }
                if (typeof input === "object") {
                    input = JSON.stringify(input);
                    return "string";
                }
            }),
    //Gets the average fitness score
    get_average_fitness_score: (function(population) {

      /*
      population => Feeds the method the fitness scores (...)
      */

      //The average number the method returns
      var return_average = 0;
      var population_sum = 0;

      for (let i = 0; i < population.length; i++) {
        population_sum += (population[i].fitness_score || 0);
      }

      return_average = population_sum / population.length;

      return return_average;

    }),
            //Progresses the algorithm
            progress: (function(iterations) {

                /*
                iterations => The amount of iterations that the algorithm should progress through (0, Inf)
                */

                var return_results = {};
                var found_fittest = false;

                for (let i = 0; i < (iterations || Infinity); i++) {

                    //Asses has a lot of parameters: input, population, input_type
                    this.population.current_population = this.assess_population(this.input, this.population.current_population, this.algorithm_data.input_type);

                this.algorithm_data.average_fitness_score = this.get_average_fitness_score(this.population.current_population);

                    this.population.mating_pool = this.generate_mating_pool(this.population.current_population);

                    this.population.current_population = this.crossover(this.population.mating_pool, this.generate_random_number);

                    //Mutate has a lot of parameters: input, input_type, population, mutation_rate, number_generator, string_generator, expansion_multiplier
                    this.population.current_population = this.mutate(this.input, this.algorithm_data_type, this.population.current_population, this.configurations.mutation_rate, this.generate_random_number, this.generate_random_string, this.configurations.expansion_multiplier);

        //Add a generation to the count
        this.algorithm_data.generations++;

                    //Evaluation takes in a lot of arguments: input, population, generations, mutation_rate, expansion_multiplier, maximum_population, average_fitness_score, time_began
                    return_results = this.evaluate_population(this.input, this.population.current_population, this.algorithm_data.generations, this.configurations.mutation_rate, this.configurations.expansion_multiplier, this.configurations.maximum_population, this.algorithm_data.average_fitness_score, this.algorithm_data.time_began);

                    found_fittest = return_results.has_found_fittest;

                    if (found_fittest === true) {
                        break;
                    }

                }

                return return_results;

            })
        };

  if (input) {

            genetic_algorithm.algorithm_data.input_type = genetic_algorithm.get_algorithm_data_type(genetic_algorithm.input);
            //Due to generate's large number of parameters, these are all of them: input, input_type, maximum_population, string_generator, number_generator, expansion_multiplier
            genetic_algorithm.population.current_population = genetic_algorithm.generate_population(genetic_algorithm.input, genetic_algorithm.algorithm_data.input_type, genetic_algorithm.configurations.maximum_population, genetic_algorithm.generate_random_string, genetic_algorithm.generate_random_number, genetic_algorithm.configurations.expansion_multiplier);

            return genetic_algorithm;

  } else {

    throw TypeError("NO_INPUT_FOUND: No input found. Try giving the GeneticAlgorithm() function a argument; the argument represents what you want the algorithm to pursue.");

  }

    }

})(typeof exports === 'undefined'? this['olog']={}: exports)
\$\endgroup\$
  • \$\begingroup\$ Could you please fix code formatting? \$\endgroup\$ – Igor Soloydenko May 19 '18 at 5:18
1
\$\begingroup\$

I am the wrong reviewer

Coders can be grouped into two types, those that will use libraries for anything and everything, giving automatic trust too 3rd party code, and those that see libraries as inherently slow, a potential source of unknown bugs, and will only use a library after thorough evaluation of its source, documentation, performance, and cost (kicking and screaming the whole way, "No No... dont corrupt my perfect precious code... " ;) ).

I am of the latter and thus maybe not who you want evaluating your code. However as nobody has yet provided a review I will give mine.

Why the most popular libraries are inherently slow.

A library is designed to work in unknown environments and be usable by both professional, amateur programmers, and many monkeys. A library can not trust any data or adherence to methodologies.

To protect the libraries stability it must vet anything that is exposed to the user (code that uses the library). Library code must constantly be on guard that internal state is not mutated.

Your code is lacking some basic protection and there are many ways to have it fail, not because your code logic is bad, but rather that the monkey using your code is feeding it bananas skins rather than the banana.

You need to add more vetting of arguments, and properties that come from external (un-trusted) sources.

Evaluation.

This evaluation is in terms of my expectations of a library, is subjective and is certainly not how everyone would see it. The other camp will say, does it run? Yes, does it like my data? Yes great stuff add it to the pile.

Documentation.

There is no documentation apart from that in the source. You should have a separate document that contains, at minimum, a Library overview, how too guide, abstraction explanation and complete API reference.

You should not have documentation spread randomly in your code. Even if this is just a hobby project at least move the documentation to the top of the source file in one comment.

That said the documentation you have given for each function is good, though the top METHODS: comment, listing API methods, is so sparse it provides little useful information.

You are also missing details about errors that can be thrown explicitly by your code or can be expected by the JS context.

Performance.

Without running the code and based on just viewing the source I would say your code has good performance. You are not using any of the common anti performance patterns. Memory use is also good with not too much wastage and GC overhead.

Good is not great, there is thus room for improvement, anyone that has used GA's will know that they can be time costly functions with run times being very long.

I don't see any performance oriented patterns like object pools, pre-allocation, object reuse, and in-lining (Yes JS optimizers will inline for you, if anyone knows how to ensure that do tell)

Cost

This is a hobby project (I assume) and dollars and cents don't come to play, well kind of. Cost is time, does you code save the users time. The time is not just adding the library to the project, it is in learning the API and reliability, you dont want bug hunting to enter the library costing users time.

Time savings. I ask, can I write the same (and tailored to my needs) in the same or lower time cost. Based on the fact anyone using the library will already be familiar with GA's, and an effective line count at ~250 you are at the time saving border, experienced codes would see using your lib as a time cost (I can write it in less time than it takes to evaluate it), less experienced coders will see a time saving.

As the primary designer you should ask your self, "Can I add more value (time benefit) to the library?"

Source code.

Sorry to say the source code is of poor quality.

The primary reason is that you are using old school JS. The current JS version is ES8, and if it was not for the use of let (which you only use in for loops) and one function using a default parameter, your code is plain old ES5.

You need to move the source up to the current version of ECMAScript if you want people to evaluate it positively.

Code style points

There would be more but I am limiting this mostly to ES5 style points.

  • The naming convention used by JavaScript is camelCase. No library will ever be popular if you use snake_case.

  • Too much noise. You code is full of unneeded comments (I am excluding he function documentation but referring to the many // comments), redundant declarations and assignments (See snippet (A) below), and why are you wrapping () around so many expressions and functions for no reason?..

  • Exposing functions that are not part of the API generate_random_number, generate_random_string, get_algorithm_data_type

  • Lines too long, Break up long lines, You have lines over 250 characters long. Keep em under 80 characters, or 120 max. (needs to fit the display)

  • ES6+ offers many ways to improve the source code and will remove many lines from your code see snippet (B) moving one function from ES5 style to the current ES8 (I am still learning it so may have missed a feature)


Snippet (A) Noise

        //Generates a random number
        generate_random_number: (function(minimum, maximum) {

            /*
            minimum => The minimum number the function should generate (-Inf, Inf)
            maximum => The maximum number the function should generate (-Inf, Inf)
            */

            //The return number the method returns
            var return_number = 0;

            return_number = Math.random() * (maximum - minimum) + minimum;

            return return_number;
        }),

With my comments

         /* This function should not be part of the exposed API */
         //Generates a random number /* NOISE This comment adds an "a" and is of no benefit at all */
         generate_random_number: (function(minimum, maximum) { 
            /* min and max are acceptable common names without ambiguity
               preference the shorter names to reduce noise levels */

             /* Move following comment to documentation */ 
             /*
             minimum => The minimum number the function should generate (-Inf, Inf)
             maximum => The maximum number the function should generate (-Inf, Inf)
             */

             //The return number the method returns /* NOISE really is that what return_number is for???? :P */
             var return_number = 0; /* REDUNDANT no need for assignment of 0 */ 
             /* REDUNDANT the variable is not needed */
             return_number = Math.random() * (maximum - minimum) + minimum;

             return return_number; /* Can return the random number directly rather than via a variable. */

         }),

Rewrite moves function out of genetic_algorithm also include the string function, the first is as you would write it if you included it in the API the second is how it can be written outside the API and thus trust the caller

      const randomNum = (min, max) => Math.random() * (max - min) + min;

      // as property of genetic_algorithm
      randomString(len, generator = randomNum) => {
         var result = "";
         if(!isNaN(len) && typeof generator === "function"){
             len = Math.floor(len); // Or same as len |= 0
             len = len > 0 ? len : 0;
             while (len--) { result += String.fromCharCode(generator(0, 65535)) }
             return result;
         }
         // You add your error policy here
      }

      // as hidden private function 
      const randomString = (len, generator = randomNum) => {
         var result = "";
         while (len--) { result += String.fromCharCode(generator(0, 65535)) }
         return result;
      }

Snippet (B) Old school to New

        evaluate_population: (function (input, population, generations, mutation_rate, expansion_multiplier, maximum_population,average_fitness_score,time_began) {
            var return_results = {};
            var has_found_fittest = false;
            var fittest = {};
            var average_accuracy = 0;
            var time_elapsed = 0;
            for (let i = 0; i < population.length; i++) {
                if (population[i].individual === input) {
                    has_found_fittest = true;
                    fittest = population[i];
                    break;
                }
            }
            average_accuracy = (average_fitness_score / input.length);
            time_elapsed = (Date.now() - time_began);
            return_results.has_found_fittest = has_found_fittest;
            return_results.fittest_individual = fittest;
            return_results.population = population;
            return_results.generations = generations;
            return_results.mutation_rate = mutation_rate;
            return_results.expansion_multiplier = expansion_multiplier;
            return_results.maximum_population = maximum_population;
            return_results.average_fitness_score = average_fitness_score;
            return_results.average_accuracy = average_accuracy;
            return_results.time_elapsed = time_elapsed;
            return return_results;
        }),

Commented

          /* Use function shorthand */
          /* Destructure arguments so that order is not important 
             Extract needed properties and properties you don't want in the return object*/
         evaluate_population: (function (input, population, generations, mutation_rate, expansion_multiplier, maximum_population,average_fitness_score, time_began) { 
             var return_results = {}; /* Not needed return directly
             var has_found_fittest = false;
             var fittest = {}; /* UNNEEDED assignment I think as I would use undefined so that it would throw if treated as a individual */
             var average_accuracy = 0;  /* UNNEEDED variable */
             var time_elapsed = 0;  /* UNNEEDED variable */
             for (let i = 0; i < population.length; i++) { /* Unsafe array */
                 if (population[i].individual === input) { /* Unsafe property access*/
                     has_found_fittest = true;
                     fittest = population[i];
                     break;
                 }
             }
             average_accuracy = (average_fitness_score / input.length); /* UNNEEDED assignment */
             time_elapsed = (Date.now() - time_began); /* UNNEEDED assignment */

             /* Use spreed operator most of the following can be done in a single line (8 characters).  ...args, */
             return_results.has_found_fittest = has_found_fittest;
             return_results.fittest_individual = fittest;
             return_results.population = population;
             return_results.generations = generations;
             return_results.mutation_rate = mutation_rate;
             return_results.expansion_multiplier = expansion_multiplier;
             return_results.maximum_population = maximum_population;
             return_results.average_fitness_score = average_fitness_score;
             return_results.average_accuracy = average_accuracy;
             return_results.time_elapsed = time_elapsed;

             return return_results; /* Return directly */
         }),

Rewrite

        evaluatePopulation({input, population, timeBegan, ...args})
            var hasFoundFittest = false;
            var fittestIndividual;
            if (Array.isArray(population) && Array.isArray(input)) {
                for (let i = 0; i < population.length; i++) {
                    if (population[i] && population[i].individual === input) {
                        hasFoundFittest = true;
                        fittestIndividual = population[i];
                        break;
                    }
                }
                return {
                    hasFoundFittest, 
                    fittestIndividual, /* This will be undefined if no fittest found, This may not be what you want */
                    population,
                    averageAccuracy : args.averageFitnessScore / input.length,
                    timeElapsed : Date.now() - timeBegan,
                    ...args
                };
            }
            /* There is no established error methology so just throwing */
            throw new Error("Bad banana!");
        }),
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.