A genetic search algorithm
Project description
Primitive Genetic Search Algorithm
Overview
Given a function, decoder
, that establishes 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 optimizes the cost
function.
Connection to Evolution
This algorithm solves problems by modeling evolutionary competition. Elements in a problem's domain are mapped 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). Winners then reproduce: offspring are generated selecting from two winners' bits (genes), and occassionally switching them, analogous to mutation. The algorithm iterates this process a set number of times. When done, it returns the best individual of the final generation.
Installation
Activate your virtual environment and run:
pip install genSearch
Usage
The algorithm is contained in the function:
genetic_simulation(decoder, cost)
which returns as a tuple an object that minimizes `cost` and `cost` evaluated at this input.
Here is an example of the algorithm in action 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 = genSearch.genetic_simulation(decoder, cost)
print(f"Solution: {solution[0]}")
print(f"Cost: {solution[1]}")
To use this algorithm, first import the package into the working python project using
import genSearch
Then, define a decoder
which converts binary strings to objects in the domain of cost
, and a cost
which assigns a real number to objects in its domain. The object type of the domain is to be defined by clients according to the problem at hand.
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(decoder, cost)
Note that result[0]
contains the approximate solution to your problem and solution[1]
contains the cost associated with this solution.
Hyperparameters
The simulation is controlled by the following variables.
## 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
This package is inspired by Jason Brownlee's algorithm. This package reorganizes and simplifies his algorithm to facilitate versatile use.
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for genSearch-0.0.10-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f36f8803d2a61c952b5c20b7836ad70b84350ad9f1d74d5749386e38cd3a69c3 |
|
MD5 | e89ce6c00e31a8698299c5f1a902a26f |
|
BLAKE2b-256 | a90494dc5d4bffdc4e926342ebd3853f804dcccfdfa2521d33732697dbfcbd5f |