A genetic search algoritm
Project description
Primitive Genetic Search Algorithm
Overview
Given a function, decoder
, which establishes a a bijection between solution-type objects, 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.
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.4-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d2a957a23cd7da0b58d425c481acf836ffbe4df9dd65883cf38d2991b4f39e3a |
|
MD5 | d71d026cdaad8c3e395e91ce2763939a |
|
BLAKE2b-256 | 140536b918ec57f6fd0c45f1f172f0be8ba085328cb5e25e39f8682b3a1c4f4a |