genSearch 0.0.5

A genetic search algoritm

Primitive Genetic Search Algorithm

Overview

Given a function, decoder, which establishes a a bijection between solution-type objects and bitstrings of a given length, and a cost function, which maps solution-type objects to real numbers, this algorithm finds optimum solutions to any problem.

Connection to Evolution

This algorithm solves problems by modeling evolutionary competition. Inputs to client's problem are abstracted to bitstrings, analogous to DNA sequences, via decoder. A random population is generated and winners are chosen via tournaments, using each individual's cost as its "fitness" (lower fitness wins). These individuals then reproduce, crossing over their bits (genes) and mutation possibly occuring (bits switching). This process iterates on the new population. This repeats a set number of times. When done, the best individual of the final generation is returned

Installation

Run

pip install --extra-index-url https://test.pypi.org/simple/ genSearch

in the virtual environment you will be using the package. Use --extra-index as this package uses the NumPy distribution on PyPI, while it itself is on test PyPI.

Usage

The algorithm is encapsulated in the function

genetic_simulation(decoder, cost)

which returns the optimal approximation and its cost as a tuple.

Here's an example of the algorithm's use to find the square root of 2 on the interval [0, 10]:

import genSearch

# bitstring to value in [0, 10]
def decoder(x):
    # Convert to base 10 equivalent
    xbase10 = int(x, 2)
    # Find the number divisions of the interval
    resolution = 2**len(x)
    # Return value scaled to interval
    return 10 * xbase2 / resolution

# function to be minimized
def cost(num):
    return (num**2 - 2)**2

solution = result = genSearch.genetic_simulation(cost, decoder)

print(f"Solution: {solution[0]}")
print(f"Cost: {solution[1]}")

To use this algorithm, first import the package into the current python project using

import genSearch

Then, define a decoder which converts from binary strings to your object, and a cost which ranks your object according to how well it solves your problem.

Once these parameters are defined, you can run the function and store its result:

import genSearch

def decoder(x):
    ...
    return object

def cost(object):
    ...
    return cost 


result = genSearch.genetic_simulation(cost, decoder)

Note that result[0] contains the approximate solution to your problem. solution[1] contains the cost associated with this solution.

Hyperparameters

The simulation is controlled by the following variables which are set as follows by default.

## Population size
N_POP = 100  
## Bitstring length      
N_LEN = 64         
## Crossover rate     
R_CROSS = 0.5    
## Bit mutation rate       
R_MUT = 1.0 / N_LEN
## Number of generations      
N_GEN = 100       

Clients may access and modify these via the following:

# N_POP
genSearch.getPop()
genSearch.setPop(new_x)

# N_LEN
genSearch.getLen()
genSearch.setLen(new_x)

# R_Cross
genSearch.getCross()
genSearch.setCross(new_x)

# R_Mut
genSearch.getMut()
genSearch.setMut(new_x)

# N_Gen
genSearch.getGen()
genSearch.setGen(new_x)

The setter functions return True upon execution.

Credit

The algorithm in this package is largely based on Jason Brownlee's algorithm. My contributions mainly lie in the package design and documentation.