voytas75/genetic-algorithm

Powershell module for genetic algorithm.

Genetic Algorithm Module in PowerShell

   

The Genetic Algorithm Module in PowerShell is a module that implements a genetic algorithm (GA). Genetic algorithms are metaheuristics inspired by the process of natural selection and belong to the class of evolutionary algorithms. They are commonly used to solve optimization and search problems by employing biologically inspired operators such as mutation, crossover, and selection. This module provides a PowerShell implementation of a genetic algorithm.

What is GA?

To understand the genetic algorithm, it is helpful to refer to the Wikipedia page that provides a comprehensive definition and explanation. In brief, a genetic algorithm is a metaheuristic that generates high-quality solutions by mimicking the process of natural selection and evolution. It was introduced by John Holland in 1960 based on the principles of Darwin's theory of evolution.

Syntax

The module provides the following command:

Start-GA [[-Generations] <int>] [[-PopulationSize] <int>] [[-ChromosomeSize] <int>] [[-CrossOverProbability] <double>] [[-MutationProbability] <double>] [[-Selection] <Object>] [-Log] [-Zeros] [-ShowGraph] [-ShowChart] [-ReturnAllGenerations] [<CommonParameters>]

Parameters

• Generations: Specifies the number of recalculation iterations for the population before completing the algorithm. The default value is 20.
• PopulationSize: Defines the size of the population used in the genetic algorithm. The size refers to the number of genomes (chromosomes), and it must be an even number. The default value is 30.
• ChromosomeSize: Determines the number of genes in each chromosome. The default value is 20.
• CrossOverProbability: Sets the probability of crossing two chromosomes at a random crossing point. The default value is 0.6.
• MutationProbability: Specifies the probability of a gene mutation in each chromosome. The default value is 0.001.
• Selection: Determines the type of selection used in the genetic algorithm. The available options are "Roulette" (default) and "Tournament".
• Log: Generates a log file from the algorithm's operation. The log file is automatically saved with a default path and filename.
• Zeros: Specifies that the initial population consists of chromosomes with all genes set to 0.
• ShowGraph: Displays an ASCII graph representing the value of the objective function for the initial population and populations from all iterations of the algorithm.
• ShowChart: Generates a PNG chart showing the value of the objective function for the initial population and populations from all iterations of the algorithm.
• ReturnAllGenerations: Returns a result table containing data for all generations, including the initial generation.

How to Use

To use the Genetic Algorithm Module, follow these steps:

Installation

Install the module from the PowerShell Gallery using the following command:

Install-Module -Name GeneticAlgorithm

You can also install it in the current user's directory by adding the -Scope CurrentUser parameter.

Running the Algorithm

Once the module is installed, you can run the genetic algorithm using the Start-GA command:

Start-GA

The algorithm will execute with default parameters and provide output with the best generation, best fitness, fitness gain percentage, and file paths for the log and PNG plot.

Examples

Here are a few examples to demonstrate different usage scenarios:

Example 1

Running the algorithm with logging and an ASCII graph:

Start-GA -Log -ShowGraph

This command will execute the genetic algorithm with default parameters, generate a log file, and display an ASCII graph representing the value of the objective function.

Output:

Best generation: [20]
Best fitness: [374]
Fitness gain: [144,44 %]
┌ GA ──────────────────────────┐
│                              │
│   380┤                    ▄  │
│   370┤                ██  █  │
│   360┤            █ █ ██▄██  │
│   350┤            █ ███████  │
│   340┤            █ ███████  │
│   330┤         █  █▄███████  │
│   320┤      ▄  █  █████████  │
│   310┤      █  █  █████████  │
│   300┤      █  █  █████████  │
│F  290┤      █▄ █▄ █████████  │
│i  280┤     ▄██ ██ █████████  │
│t  270┤     ███ ████████████  │
│n  260┤     ███▄████████████  │
│e  250┤     ████████████████  │
│s  240┤ █ ▄ ████████████████  │
│s  230┤ █ █ ████████████████  │
│   220┤ █▄█ ████████████████  │
│   210┤ ███▄████████████████  │
│   200┤ ████████████████████  │
│   190┤ ████████████████████  │
│   180┤ ████████████████████  │
│   170┤ ████████████████████  │
│   160┤▄████████████████████  │
│      └─────────┬─────────┬─  │
│               10        20   │
│            Generations       │
└──────────────────────────────┘
LOG: C:\Users\voytas\AppData\Local\Temp\GA.log
OUT DATA: C:\Users\voytas\AppData\Local\Temp\allGenerations.log
PNG: C:\Users\voytas\AppData\Local\Temp\GA.png

LOG: C:\Users\voytas\AppData\Local\Temp\GA.log - The path of the generated log file.

Example 2

Running the algorithm with a PNG chart:

Start-GA -ShowChart

This command will execute the genetic algorithm with default parameters and generate a PNG chart representing the value of the objective function.

Output:

Example 3

Customizing the algorithm parameters:

Start-GA -Generations 100 -PopulationSize 40 -MutationProbability 0.009 -Zeros -Log -ShowGraph

This command will execute the genetic algorithm with specific parameter values, including a different number of generations, population size, mutation probability, and using an initial population consisting of chromosomes with all genes set to 0.

Output:

Example 4

Accessing the data of all populations processed by the algorithm:

$GAout = Start-GA -Generations 10 -ChromosomeSize 30 -ReturnAllGenerations
$GAout[10][2].foreach{"$_"}
$GAout[10][1]

These commands will execute the genetic algorithm with specific parameter values and store the output in the $GAout variable. You can then access the data of specific populations using array indexing (switch ReturnAllGenerations). In this example, it retrieves the data of the 10th iteration and displays the chromosomes, as well as the value of the objective function for the iteration.

Output:

> $GAout = Start-GA -Generations 10 -ChromosomeSize 30 -ReturnAllGenerations
Best generation: [10]
Best fitness: [450]
Fitness gain: [69,81 %]
OUT DATA: C:\Users\voytas\AppData\Local\Temp\allGenerations.json
PNG: C:\Users\voytas\AppData\Local\Temp\GA.png

> $GAout[10][2].foreach{"$_"}
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 0 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 0 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0
0 1 1 0 0 1 1 1 0 0

> $GAout[10][1]
450

Feel free to experiment with different parameter values and explore the generated output to analyze the results of the genetic algorithm.

Please note that the module may require additional dependencies, such as the Graphical module for displaying graphs and charts.

genetic-algorithm's Issues

Add log for param „zeros” use

Export allgenerations to excel

Export all populationa to excel. Every iteration in own worksheet.

Speed up remove PopulationStatictics

Change function ```

PopulationStatictics

For param with population size

Proposed improvement

https://www.reddit.com/r/PowerShell/comments/i5csrc/genetic_algorithm_in_powershell/g0s3xds/?utm_source=share&utm_medium=ios_app&utm_name=iossmf

Change description

Change description of generatechromosomes function. There is "one is default". Should be "default valuEs are definied"

Change condition

Line 127. Change condition for variable fitness value to use i t olerator not bool "-not"

Remove default value

... From function generateChromosome. Function in never invoke alone.

Test run without modules

... importexcel and graphical

Different approach for roulette when fitness is 0

Return population Zero with only 0s

Use fitness function

Line 126

Function for showchart

Create function showchart and move code od chart.

Function for main code

build main function and move there all main code. Add params for all important variables.

Change warning for module

... Graphical. Text fo Import module is for importexcel

Number of mutations to log file

Add global and iteration sum of mutations for population to log file.

Ad ko-fi

Add kofi label

Add log when exit

Line 128. Add log to file when script exits

Function’s execution time to log

Add global and iteration sum of function,s execution time to log file

Functions rename

Function "generategene" in fact generates chromosome. And function "generatechromosomes" generates genomes. Match right names.

Chart of max value items

graph of max values item from pop zero and every iteration.

Export all generations

Export all generations to file, xml, json...

Chceck module dependiences

I.e.

if (Get-Module -ListAvailable -Name SomeModule) {
    Write-Host "Module exists"
} 
else {
    Write-Host "Module does not exist"
}

Add pseudocode

Add pseudocode for Tournamrnt function.

Number of crossover to log

Add global and iteration sum of crossovers for population to log file.

Add if for check modules

Importexcel is not ised. Graphical module for param showgraph

create module

Create module form script.

add:

PowerShellVersion = '5.1'
DotNetFrameworkVersion = '4.7.2'
CompatiblePSEditions = 'Desktop'

Extracting fitness function logic

extracting the logic of the fitness function to simplify implementation

Add check object param to functions

Add expected data type for population for functions which take the variable $population. The data type of the variable $population is array of arrays. Every genome is array.

Bug fitness for zeros is all 0

} else {
        $_NormalizeItem = $fitness.foreach{ 0 }
    }

Not every fitness is 0

Array of max fitness item

Build array with max of fitness items from every population.

Maybe use $fitnessPopulation_max