Genetics

In this assignment, you will implement main parts of genetic algorithms.
There are lots of algorithms that researchers use in each part and your are going to implement the famous ones. And of course there are some rare ideas to implement here(the harder you work the better grade you get)!

Implementations

1. First of all, you should implement everything only using numpy or built-in libraries.
2. You should only implement functions to do the task for each module. This means that you have to assume some predefined code and implement your own code,using that.
3. You can define sub functions for simplifying your task.
4. We've provided a sample class of chromosomes with some attributes. You can assume that this class will be parsed as the chromosome in your functions.
5. In some of the modules, you need to change the class to add some new attributes. To do so, you should extend the class and add new attributes to your new implemented class.

Grading

1. Modules have weighted grades so the more work you put in the more points you get.
2. Some modules are optional for some groups.
3. Groups are categorized based on theirs skills. So the more skilled you are the more tasks and different points for each task you get.
4. (optional) Unit testing has bonus points. If you use online CI tools like Travis CI or Azure DevOps for testing, you'll get more bonus points!!!

Note: If you want to use unit testing in your codes, please provide high quality tests. writing low quality test is just a waste time (Go play GTA instead!)

Documentation

1. For god's sake write something! maybe someday you have to use your own project(hopefully).
2. You have to provide documentation for all of the function arguments and return values and of course a simple explanation about your function and a numerical example of how would your function work. 3.Don't know how to write docs in python? OK, google it!

This tutorial may help you to write better docs.

Modules

1. we've provided some modules for each section.
2. Each module will be a function as described in implementation section.
3. There is a little description on what each module is and some links as reference. You must read those links and implement modules based on algorithms provided in the references. In some modules, we've provided a paper,related to the module. It is your task to study the papers and find out how to implement the modules.

Genetics

This assignment includes these parts:

1. Initialization (Population and Chromosome)
2. Selection Methods
3. Crossover Methods
4. Mutation Methods

We will describe each section later on

Initialization

In this step we talk about initializing chromosomes and population. So here are the contents:

1. Chromosome
2. Population

Chromosome

Here we assume that every problem can be encoded to chromosomes with 1 dimensional vector genes.
But the structure of this genes depends on the problem. We describe most famous ones here so we have 3 types of gene vectors:

1. A binary vector in which 1 represents the existence of the genes and 0 represents non-existence.
   Numeric example:
   

genes = [0, 1, 0, 0, 0, 1, ... , 0]
print(chromosome.genes)
output: [0, 1, 0, 0, 0, 1, ... , 0]

2. An integer vector of vectors which each element represents a vector of the batch of the genes with the same size. something like a flatten 2 dimensional matrix.
   

genes = [
    [1,2,3],
    [2,1,3],
    [3,2,1],
    [3,1,2]
        ]
chromosome.genes = genes.flatten()
print(chromosome.genes)
output: [1,2,3,2,1,3,3,2,1,3,1,2]

3.An integer vector of vectors like state 2, but each element has different size. So this is your duty to think about the best encoding way for it.

genes = [
    [1,2,3,4,5],
    [3,2,1],
    [2,3,1,4],
    [1]
        ]
chromosome.genes = genes.flatten()
print(chromosome.genes)
output: [1,2,3,4,5,3,2,1,2,3,1,4,1]

lengths is important. So we add another attribute to the chromosome class.

chromosome.lengths = [5,3,4,1]

So every time you want to apply any operation on these features, you have to do it with respect to lengths.

Note: These numbers are just for demonstration purposes and in real world example, they are data points (features).

We've provided a class representing a simple chromosome. You need to complete all the functions with respect to this class.

import numpy as np

class chromosome():
    def __init__(self, genes, id=None, fitness=-1, flatten= False, lengths=None):
        self.id = id
        self.genes = genes
        self.fitness = fitness
        
        # if you need more parameters for specific problem, extend this class
    def flatten_feaures():
        # in this function you should implement your logic to flatten features
        pass
    
    
    def describe(self):
        print('ID=#{}, fitenss={}, \ngenes=\n{}'.format(self.id, self.fitness, self.genes))

c = chromosome(genes=np.array([1,2,3]),id=1,fitness = 125.2)
c.describe()

c2 = chromosome(genes = np.array([[1,2],[2,1]]).flatten(), id=2,
                fitness=140, flatten=True)
c2.describe()

ID=#1, fitenss=125.2, 
genes=
[1 2 3]
ID=#2, fitenss=140, 
genes=
[1 2 2 1]

Population

In the population,chromosomes are like friends and enemies. So all operators in mutation and crossover will be applied on these chromosomes based on nature selection ideas and survival of the fittest.

Initialization can help you to find global optima faster but can even get you stuck in the local optima on the other hand. Hence, it is an important part.
There are some methods to initialize population and they are hyperparameters.
Hyperparameters are:

1. Population Size
2. Chromosome Genes

The most famous one is random initialization.

Population initialization:

1. Pseudo Random
2. Quasi Random Sequence
3. Centroid Voronoi Tessellation

Pseudo Random

This is the simplest method. Actually the random class in every programming language is a pseudo random number. And of course you can make a uniform random using this pseudo randoms.
So in your implementation, you must use numpy.random to initialize population and chromosomes.
Just do everything random! If you need more information, check more reading section below.

Quasi Random Sequence

the initial population is often selected randomly using pseudo random numbers.It’s usually more important that the points are as evenly distributed as possible than that they imitate random points. In this paper, we study the use of quasi-random sequences in the initial population of a genetic algorithm. Sample points in a quasi-random sequence are designed to have good distribution properties.

Use this link as reference.

Centroid Voronoi Tessellation

In this method, we consider data points as clusters and will separate them based on some criteria. And then initialize random points with respect to these regions.

Use this paper as reference.

More Reading

If you need to know more about random numbers, this and this about different methods.

Selection

The main purpose of selection phase is to select the fittest individuals and let them pass their genes to the next generation.

These are your tasks:

1. Truncation Selection
2. Tournament Selection
3. stochastic Universal Sampling
4. Roulette Wheel Selection
5. Roulette Wheel Selection with stochastic Acceptance
6. Linear Ranking Selection
7. Exponential Ranking Selection
8. Self-Adaptive Tournament Selection

1. Truncation Selection

Use This as reference.
More reading: Muhlenbein's Breeder Genetic Algorithm.

2. Tournament Selection

Use this as reference.

3. Stockasting Universal Sampling

Use this as reference.

4. Roulette-wheel Selection

Use this as reference.

5. Roulette-wheel Selection with Stocastic Acceptance

Use this as reference.

6. Linear Ranking Selection

Use this and this as reference.

7. Exponential Ranking Selection

Use this and this as reference.

8. Self-Adaptive Tournament Selection

Use this as reference.

More readings

1. https://1drv.ms/b/s!ApJ0ieVzUhjim0AVEP9zJ-irxfVN
2. http://www.geatbx.com/docu/algindex-02.html

Crossover

The idea is to have better individuals at the next generations. So we have to do something. Here we try to use top individuals offspring for next generations as parents. This help us to exploit.

Here is some of crossover operators:

1. Single-point Crossover
2. Multi-point Crossover (N-point)
3. Uniform Crossover
4. Flat Crossover
5. Order Crossover (OX)
6. Partially Mapped Crossover(PMX)
7. Edge Recombination Crossover (ERX)
8. Cycle Crossover (CX)
9. Alternating Edges Crossover (AEX)

Note: You must implement each operator for 3 types of chromosome classes. (See Initialization section).

Reference:

1. For 1 to 4 oeprators, use this link.
2. For 5 to 9 operators use this link.

1. Single-Point crossover

2. Multi-point Crossover (N-point)

3. Uniform Crossover

4. Flat Crossover

5. Order Crossover (OX)

6. Partially Mapped Crossover(PMX)

7. Edge Recombination Crossover (ERX)

8. Cycle Crossover (CX)

9. Alternating Edges Crossover (AEX)

Mutation

The main goal of mutation phase is to change the values of genes in a chromosome randomly and introduce new genetic material into the population,to increase genetic diversity.

These are your tasks:

1. Uniform/Random Mutation
2. Inorder Mutation
3. Twors Mutation
4. Centre inverse mutation (CIM)
5. Reverse Sequence Mutation (RSM)
6. Throas Mutation
7. Thrors Mutation
8. Partial Shuffle Mutation (PSM)
9. Scrabmle Mutation
10. Distance-Based Mutation Operator (DMO)

The reference for 9/10 of these operators here.

1. Uniform/Random Mutation

2. Inorder Mutation

3. Twors Mutation

4. Centre Inverse Mutation (CIM)

5. Reverse Sequence Mutation (RSM)

6. Throas Mutation

7. Thrors Mutation

8. Partial Shuffle Mutation (PSM)

9. Scramble Mutation

Use this link.

10. Distance-Based Mutation Operator (DMO)

You can get paper here.

License

MIT License

Copyright (c) 2018 Computational Intelligence - University of Guilan

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
Get in touch with Authors: Mohammad Doosti Lakhani, Hamed Faraji