pyeasyga¶
A simple and easy-to-use implementation of a Genetic Algorithm library in Python
Contents:
pyeasyga¶
Introduction¶
A simple and easy-to-use implementation of a Genetic Algorithm library in Python.
pyeasyga
provides a simple interface to the power of Genetic Algorithms
(GAs). You don’t have to have expert GA knowledge in order to use it.
- Homepage: https://github.com/remiomosowon/pyeasyga
- PyPI: https://pypi.python.org/pypi/pyeasyga
- Documentation: http://pyeasyga.readthedocs.org.
- Issues / Feedback: https://github.com/remiomosowon/pyeasyga/issues
- Free software: BSD license
Installation¶
At the command line, simply run:
$ pip install pyeasyga
Or clone this repository and run python setup.py install
from within the project directory. e.g.:
$ git clone https://github.com/remiomosowon/pyeasyga.git
$ cd pyeasyga
$ python setup.py install
For alternative install methods, see the INSTALL file or the Installation section in the documentation.
Examples¶
See the Usage section in the documentation for examples. The example files can
be found in the examples
directory.
Note¶
- Currently under active development
Installation¶
If you have pip installed, at the command line simply run:
$ pip install pyeasyga
Or, if you have virtualenvwrapper installed:
$ mkvirtualenv pyeasyga
$ pip install pyeasyga
Or, download and extract the compressed archive (or clone the repository) from github, and inside the directory run:
$ python setup.py install
Usage¶
To use pyeasyga in a project:
Simple¶
Import the module
from pyeasyga import pyeasygaSetup your data e.g.
data = [('pear', 50), ('apple', 35), ('banana', 40)]Initialise the GeneticAlgorithm class with the only required parameter:
data
ga = pyeasyga.GeneticAlgorithm(data)Define a fitness function for the Genetic Algorithm. The function should take two parameters: a candidate soultion (an individual in GA speak), and the data that is used to help determine the individual’s fitness
def fitness (individual, data): fitness = 0 if individual.count(1) == 2: for (selected, (fruit, profit)) in zip(individual, data): if selected: fitness += profit return fitnessSet the Genetic Algorithm’s
fitness_function
attribute to your defined fitness functionga.fitness_function = fitnessRun the Genetic Algorithm
ga.run()Print the best solution
print ga.best_individual()
Advanced¶
Import the module
from pyeasyga import pyeasygaSetup your data e.g.
data = [('pear', 50), ('apple', 35), ('banana', 40)]Initialise the GeneticAlgorithm class with the required
data
parameter, and all or some of the optional parametersga = pyeasyga.GeneticAlgorithm(data, population_size=10, generations=20, crossover_probability=0.8, mutation_probability=0.05, elitism=True, maximise_fitness=True)Or
ga = pyeasyga.GeneticAlgorithm(data, 10, 20, 0.8, 0.05, True, True)Or, just initialise the GeneticAlgorithm class with only the required
data
parameter, if you are content with the default parametersga = pyeasyga.GeneticAlgorithm(data)Optionally, define a function to create a representation of a candidate solution (an individual in GA speak). This function should take in the data defined in step 1. as a parameter.
def create_individual(data): return [random.randint(0, 1) for _ in xrange(len(data))]Set the Genetic Algorithm’s
create_individual
attribute to your defined functionga.create_individual = create_individualOptionally, define and set functions for the Genetic Algorithm’s genetic operators (i.e. crossover, mutate, selection)
# For the crossover function, supply two individuals (i.e. candidate # solution representations) as parameters, def crossover(parent_1, parent_2): crossover_index = random.randrange(1, len(parent_1)) child_1 = parent_1[:index] + parent_2[index:] child_2 = parent_2[:index] + parent_1[index:] return child_1, child_2 # and set the Genetic Algorithm's ``crossover_function`` attribute to # your defined function ga.crossover_function = crossover # For the mutate function, supply one individual (i.e. a candidate # solution representation) as a parameter, def mutate(individual): mutate_index = random.randrange(len(individual)) if individual[mutate_index] == 0: individual[mutate_index] = 1 else: individual[mutate_index] = 0 # and set the Genetic Algorithm's ``mutate_function`` attribute to # your defined function ga.mutate_function = mutate # For the selection function, supply a ``population`` parameter def selection(population): return random.choice(population) # and set the Genetic Algorithm's ``selection_function`` attribute to # your defined function ga.selection_function = selectionDefine a fitness function for the Genetic Algorithm. The function should take two parameters: a candidate solution representation (an individual in GA speak), and the data that is used to help determine the individual’s fitness
def fitness (individual, data): fitness = 0 if individual.count(1) == 2: for (selected, (fruit, profit)) in zip(individual, data): if selected: fitness += profit return fitnessSet the Genetic Algorithm’s
fitness_function
attribute to your defined fitness functionga.fitness_function = fitnessRun the Genetic Algorithm
ga.run()Print the best solution:
print ga.best_individual()You can also examine all the individuals in the last generation:
for individual in ga.last_generation(): print individual
Example of Simple Usage¶
This simple example uses the default pyeasyga.GeneticAlgorithm
parameters.
The problem is to select only two items from a list (the supplied data) while maximising the cost of the selected items. (Solution: Selecting the pear and apple gives the highest possible cost of 90.)
>>> from pyeasyga.pyeasyga import GeneticAlgorithm
>>>
>>> data = [('pear', 50), ('apple', 35), ('banana', 40)]
>>> ga = GeneticAlgorithm(data)
>>>
>>> def fitness (individual, data):
>>> fitness = 0
>>> if individual.count(1) == 2:
>>> for (selected, (fruit, profit)) in zip(individual, data):
>>> if selected:
>>> fitness += profit
>>> return fitness
>>>
>>> ga.fitness_function = fitness
>>> ga.run()
>>> print ga.best_individual()
Example of Advanced Usage¶
This example uses both default and optional pyeasyga.GeneticAlgorithm
parameters.
The problem is to select only two items from a list (the supplied data) while maximising the cost of the selected items. (Solution: Selecting the pear and apple gives the highest possible cost of 90.)
>>> from pyeasyga.pyeasyga import GeneticAlgorithm
>>>
>>> data = [('pear', 50), ('apple', 35), ('banana', 40)]
>>> ga = GeneticAlgorithm(data, 20, 50, 0.8, 0.2, True, True)
>>>
>>> def create_individual(data):
>>> return [random.randint(0, 1) for _ in xrange(len(data))]
>>>
>>> ga.create_individual = create_individual
>>>
>>>
>>> def crossover(parent_1, parent_2):
>>> crossover_index = random.randrange(1, len(parent_1))
>>> child_1 = parent_1[:index] + parent_2[index:]
>>> child_2 = parent_2[:index] + parent_1[index:]
>>> return child_1, child_2
>>>
>>> ga.crossover_function = crossover
>>>
>>>
>>> def mutate(individual):
>>> mutate_index = random.randrange(len(individual))
>>> if individual[mutate_index] == 0:
>>> individual[mutate_index] = 1
>>> else:
>>> individual[mutate_index] = 0
>>>
>>> ga.mutate_function = mutate
>>>
>>>
>>> def selection(population):
>>> return random.choice(population)
>>>
>>> ga.selection_function = selection
>>>
>>> def fitness (individual, data):
>>> fitness = 0
>>> if individual.count(1) == 2:
>>> for (selected, (fruit, profit)) in zip(individual, data):
>>> if selected:
>>> fitness += profit
>>> return fitness
>>>
>>> ga.fitness_function = fitness
>>> ga.run()
>>> print ga.best_individual()
>>>
>>> for individual in ga.last_generation():
>>> print individual
Examples¶
1-Dimensional Knapsack Problem¶
one_dimensional_knapsack.py
This example solves the one-dimensional knapsack problem used as the example on the Wikipedia page for the Knapsack problem. Here is the problem statement.
from pyeasyga import pyeasyga # setup data data = [{'name': 'box1', 'value': 4, 'weight': 12}, {'name': 'box2', 'value': 2, 'weight': 1}, {'name': 'box3', 'value': 10, 'weight': 4}, {'name': 'box4', 'value': 1, 'weight': 1}, {'name': 'box5', 'value': 2, 'weight': 2}] ga = pyeasyga.GeneticAlgorithm(data) # initialise the GA with data # define a fitness function def fitness(individual, data): values, weights = 0, 0 for selected, box in zip(individual, data): if selected: values += box.get('value') weights += box.get('weight') if weights > 15: values = 0 return values ga.fitness_function = fitness # set the GA's fitness function ga.run() # run the GA print ga.best_individual() # print the GA's best solutionTo run:
$ python one_dimensional_knapsack.pyOutput:
(15, [0, 1, 1, 1, 1])i.e. if you select all boxes except the first one, you get a maximum amount of $15 while still keeping the overall weight under or equal to 15kg.
Multi-Dimensional Knapsack Problem¶
multi_dimensional_knapsack.py
This solves the multidimensional knapsack problem (MKP) seen here. It is a well-known NP-hard combinatorial optimisation problem.
from pyeasyga import pyeasyga # setup data data = [(821, 0.8, 118), (1144, 1, 322), (634, 0.7, 166), (701, 0.9, 195), (291, 0.9, 100), (1702, 0.8, 142), (1633, 0.7, 100), (1086, 0.6, 145), (124, 0.6, 100), (718, 0.9, 208), (976, 0.6, 100), (1438, 0.7, 312), (910, 1, 198), (148, 0.7, 171), (1636, 0.9, 117), (237, 0.6, 100), (771, 0.9, 329), (604, 0.6, 391), (1078, 0.6, 100), (640, 0.8, 120), (1510, 1, 188), (741, 0.6, 271), (1358, 0.9, 334), (1682, 0.7, 153), (993, 0.7, 130), (99, 0.7, 100), (1068, 0.8, 154), (1669, 1, 289)] ga = pyeasyga.GeneticAlgorithm(data) # initialise the GA with data ga.population_size = 200 # increase population size to 200 (default value is 50) # define a fitness function def fitness(individual, data): weight, volume, price = 0, 0, 0 for (selected, item) in zip(individual, data): if selected: weight += item[0] volume += item[1] price += item[2] if weight > 12210 or volume > 12: price = 0 return price ga.fitness_function = fitness # set the GA's fitness function ga.run() # run the GA print ga.best_individual() # print the GA's best solutionTo run:
$ python multi_dimensional_knapsack.pyOutput:
(3531, [0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1])i.e. the indicated selection of items satisfies the required weight and volume constraints, and gives a total value of 3531.
8 Queens Puzzle¶
8_queens.py
This solves the 8 queens puzzle.
import random from pyeasyga import pyeasyga # setup seed data seed_data = [0, 1, 2, 3, 4, 5, 6, 7] # initialise the GA ga = pyeasyga.GeneticAlgorithm(seed_data, population_size=200, generations=100, crossover_probability=0.8, mutation_probability=0.2, elitism=True, maximise_fitness=False) # define and set function to create a candidate solution representation def create_individual(data): individual = data[:] random.shuffle(individual) return individual ga.create_individual = create_individual # define and set the GA's crossover operation def crossover(parent_1, parent_2): crossover_index = random.randrange(1, len(parent_1)) child_1a = parent_1[:crossover_index] child_1b = [i for i in parent_2 if i not in child_1a] child_1 = child_1a + child_1b child_2a = parent_2[crossover_index:] child_2b = [i for i in parent_1 if i not in child_2a] child_2 = child_2a + child_2b return child_1, child_2 ga.crossover_function = crossover # define and set the GA's mutation operation def mutate(individual): mutate_index1 = random.randrange(len(individual)) mutate_index2 = random.randrange(len(individual)) individual[mutate_index1], individual[mutate_index2] = individual[mutate_index2], individual[mutate_index1] ga.mutate_function = mutate # define and set the GA's selection operation def selection(population): return random.choice(population) ga.selection_function = selection # define a fitness function def fitness (individual, data): collisions = 0 for item in individual: item_index = individual.index(item) for elem in individual: elem_index = individual.index(elem) if item_index != elem_index: if item - (elem_index - item_index) == elem \ or (elem_index - item_index) + item == elem: collisions += 1 return collisions ga.fitness_function = fitness # set the GA's fitness function ga.run() # run the GA # function to print out chess board with queens placed in position def print_board(board_representation): def print_x_in_row(row_length, x_position): print '', for _ in xrange(row_length): print '---', print '\n|', for i in xrange(row_length): if i == x_position: print '{} |'.format('X'), else: print ' |', print '' def print_board_bottom(row_length): print '', for _ in xrange(row_length): print '---', num_of_rows = len(board_representation) row_length = num_of_rows #rows == columns in a chessboard for row in xrange(num_of_rows): print_x_in_row(row_length, board_representation[row]) print_board_bottom(row_length) print '\n' # print the GA's best solution; a solution is valid only if there are no collisions if ga.best_individual()[0] == 0: print ga.best_individual() print_board(ga.best_individual()[1]) else: print NoneTo run:
$ python 8_queens.pyOutput:
(0, [2, 5, 7, 0, 3, 6, 4, 1]) --- --- --- --- --- --- --- --- | | | X | | | | | | --- --- --- --- --- --- --- --- | | | | | | X | | | --- --- --- --- --- --- --- --- | | | | | | | | X | --- --- --- --- --- --- --- --- | X | | | | | | | | --- --- --- --- --- --- --- --- | | | | X | | | | | --- --- --- --- --- --- --- --- | | | | | | | X | | --- --- --- --- --- --- --- --- | | | | | X | | | | --- --- --- --- --- --- --- --- | | X | | | | | | | --- --- --- --- --- --- --- ---
Contributing¶
Contributions are welcome, and they are greatly appreciated! Every little bit helps, and credit will always be given.
You can contribute in many ways:
Types of Contributions¶
Report Bugs¶
Report bugs at https://github.com/remiomosowon/pyeasyga/issues.
If you are reporting a bug, please include:
- Your operating system name and version.
- Any details about your local setup that might be helpful in troubleshooting.
- Detailed steps to reproduce the bug.
Fix Bugs¶
Look through the GitHub issues for bugs. Anything tagged with “bug” is open to whoever wants to implement it.
Implement Features¶
Look through the GitHub issues for features. Anything tagged with “feature” is open to whoever wants to implement it.
Write Documentation¶
pyeasyga could always use more documentation, whether as part of the official pyeasyga docs, in docstrings, or even on the web in blog posts, articles, and such.
Submit Feedback¶
The best way to send feedback is to file an issue at https://github.com/remiomosowon/pyeasyga/issues.
If you are proposing a feature:
- Explain in detail how it would work.
- Keep the scope as narrow as possible, to make it easier to implement.
- Remember that this is a volunteer-driven project, and that contributions are welcome :)
Get Started!¶
Ready to contribute? Here’s how to set up pyeasyga for local development.
Fork the pyeasyga repo on GitHub.
Clone your fork locally:
$ git clone git@github.com:your_name_here/pyeasyga.git
Install your local copy into a virtualenv. Assuming you have virtualenvwrapper installed, this is how you set up your fork for local development:
$ mkvirtualenv pyeasyga $ cd pyeasyga/ $ python setup.py develop
Create a branch for local development:
$ git checkout -b name-of-your-bugfix-or-feature
Now you can make your changes locally.
When you’re done making changes, check that your changes pass flake8 and the tests, including testing other Python versions with tox:
$ flake8 pyeasyga tests $ python setup.py test $ tox
To get flake8 and tox, just pip install them into your virtualenv.
Commit your changes and push your branch to GitHub:
$ git add . $ git commit -m "Your detailed description of your changes." $ git push origin name-of-your-bugfix-or-feature
Submit a pull request through the GitHub website.
Pull Request Guidelines¶
Before you submit a pull request, check that it meets these guidelines:
- The pull request should include tests.
- If the pull request adds functionality, the docs should be updated. Put your new functionality into a function with a docstring, and add the feature to the list in README.rst.
- The pull request should work for Python 2.6, 2.7 and 3.4. Please make sure you don’t break compatibility. Check https://travis-ci.org/remiomosowon/pyeasyga/pull_requests and make sure that the tests pass for all supported Python versions.
Credits¶
Development Lead¶
- Ayodeji Remi-Omosowon <remiomosowon@gmail.com>
Contributors¶
- Yasser Gonzalez <yasserglez@gmail.com>
History¶
v0.3.0¶
2015-04-07
- Added Python 3.4 support without breaking Python 2 compatibility (thanks to yasserglez)
v0.2.5¶
2014-07-09
- Added an example that solves the 8 Queens Puzzle
2014-07-09
- Modified the GeneticAlgorithm class initialisation parameters
- Made changes to USAGE documentation
- Added EXAMPLE documentation as a separate section
v0.2.4¶
2014-07-07
- Refactored most of the code; Made GeneticAlgorithm class more OOP
- Made changes to INSTALLATION documentation
v0.2.2¶
2014-07-05
- Removed duplicate ‘Example’ documentation; now maintaining only one copy in examples/README.rst
- Added link to jeffknupp’s sandman repo in HISTORY
- Modified release option in Makefile to also upload project documentation
- Added INSTALLATION and EXAMPLE sections to README.rst
- Removed easy_install installation step from documentation (pip is sufficient)
- Added a simple example of usage to docs/usage.rst
- Reduced the default GA population and generation size (to allow applications that use the different parameters to run quickly)
- Modified tests to account for the new default population, generation size
- Added docstrings to all methods
v0.1.0¶
2014-06-23
- Start of
pyeasyga
development.
2014-07-03
Implemented all of basic GA functionality
Fix issue with odd-numbered population that causes an off-by-one error in the population size
Set default ga selection function to tournament_selection
Created examples to show how to use the library
Start versioning (better late than never); copied jeffknupp’s update_version.sh from sandman
selected versioning standard: major.minor.micro (e.g. 2.1.5)
- major => big changes that can break compatibility
- minor => new features
- micro => bug fixes