”’
An easy implementation of genetic-algorithm (GA) to solve continuous and combinatorial optimization problems with real, integer, and mixed variables in Python
”’
###############################################################################
###############################################################################
###############################################################################
import numpy as np
import sys
import time
from func_timeout import func_timeout, FunctionTimedOut
import matplotlib.pyplot as plt
###############################################################################
###############################################################################
###############################################################################
class GeneticAlgorithm():
”’ Genetic Algorithm (Elitist version) for Python
An implementation of elitist genetic algorithm for solving problems with
continuous, integers, or mixed variables.
Implementation and output:
methods:
run(): implements the genetic algorithm
outputs:
output_dict: a dictionary including the best set of variables
found and the value of the given function associated to it.
{‘variable’: , ‘function’: }
report: a list including the record of the progress of the
algorithm over iterations
”’
#############################################################
def __init__(self, function, dimension, variable_type=’bool’, \
variable_boundaries=None,\
variable_type_mixed=None, \
function_timeout=10,\
algorithm_parameters={‘max_num_iteration’: None,\
‘population_size’:100,\
‘mutation_probability’:0.1,\
‘elit_ratio’: 0.01,\
‘crossover_probability’: 0.5,\
‘parents_portion’: 0.3,\
‘crossover_type’:’uniform’,\
‘max_iteration_without_improv’:None},\
convergence_curve=True,\
progress_bar=True):
”’
@param function
NOTE: This implementation minimizes the given objective function.
(For maximization multiply function by a negative sign: the absolute
value of the output would be the actual objective function)
@param dimension
@param variable_type
‘int’ if all variables are integer; and ‘real’ if all variables are
real value or continuous (for mixed type see @param variable_type_mixed)
@param variable_boundaries
None if variable_type is ‘bool’; otherwise provide an array of tuples
of length two as boundaries for each variable;
the length of the array must be equal dimension. For example,
np.array([0,100],[0,200]) determines lower boundary 0 and upper boundary 100 for first
and upper boundary 200 for second variable where dimension is 2.
@param variable_type_mixed
None if all variables have the same type; otherwise this can be used to
specify the type of each variable separately. For example if the first
variable is integer but the second one is real the input is:
np.array([‘int’],[‘real’]). NOTE: it does not accept ‘bool’. If variable
type is Boolean use ‘int’ and provide a boundary as [0,1]
in variable_boundaries. Also if variable_type_mixed is applied,
variable_boundaries has to be defined.
@param function_timeout
output before function_timeout (unit is seconds) the algorithm raise error.
For example, when there is an infinite loop in the given function.
@param algorithm_parameters:
@ max_num_iteration
@ population_size
@ mutation_probability
@ elit_ration
@ crossover_probability
@ parents_portion
@ crossover_type
‘two_point’ are other options
@ max_iteration_without_improv
successive iterations without improvement. If None it is ineffective
@param convergence_curve
Default is True.
@progress_bar
”’
self.__name__ = GeneticAlgorithm
#############################################################
# input function
assert (callable(function)),”function must be callable”
self.f = function
#############################################################
#dimension
self.dim = int(dimension)
#############################################################
# input variable type
assert(variable_type==’bool’ or variable_type==’int’ or\
variable_type==’real’), \
“\n variable_type must be ‘bool’, ‘int’, or ‘real'”
#############################################################
# input variables’ type (MIXED)
if variable_type_mixed is None:
if variable_type==’real’:
self.var_type=np.array([[‘real’]]*self.dim)
else:
self.var_type=np.array([[‘int’]]*self.dim)
else:
assert (type(variable_type_mixed).__module__==’numpy’),\
“\n variable_type must be numpy array”
assert (len(variable_type_mixed) == self.dim), \
“\n variable_type must have a length equal dimension.”
for i in variable_type_mixed:
assert (i==’real’ or i==’int’),\
“\n variable_type_mixed is either ‘int’ or ‘real’ “+\
“ex:[‘int’,’real’,’real’]”+\
“\n for ‘boolean’ use ‘int’ and specify boundary as [0,1]”
self.var_type=variable_type_mixed
#############################################################
# input variables’ boundaries
if variable_type!=’bool’ or type(variable_type_mixed).__module__==’numpy’:
assert (type(variable_boundaries).__module__==’numpy’),\
“\n variable_boundaries must be numpy array”
assert (len(variable_boundaries)==self.dim),\
“\n variable_boundaries must have a length equal dimension”
for i in variable_boundaries:
assert (len(i) == 2), \
“\n boundary for each variable must be a tuple of length two.”
assert(i[0]<=i[1]),\
"\n lower_boundaries must be smaller than upper_boundaries [lower,upper]"
self.var_bound = variable_boundaries
else:
self.var_bound = np.array([[0,1]]*self.dim)
#############################################################
#Timeout
self.funtimeout = float(function_timeout)
#############################################################
#convergence_curve
if convergence_curve==True:
self.convergence_curve=True
else:
self.convergence_curve=False
#############################################################
#progress_bar
if progress_bar==True:
self.progress_bar=True
else:
self.progress_bar=False
#############################################################
#############################################################
# input algorithm's parameters
self.param=algorithm_parameters
self.pop_s=int(self.param['population_size'])
assert (self.param['parents_portion']<=1\
and self.param['parents_portion']>=0),\
“parents_portion must be in range [0,1]”
self.par_s = int(self.param[‘parents_portion’]*self.pop_s)
trl = self.pop_s-self.par_s
if trl % 2 != 0:
self.par_s+=1
self.prob_mut=self.param[‘mutation_probability’]
assert (self.prob_mut<=1 and self.prob_mut>=0), \
“mutation_probability must be in range [0,1]”
self.prob_cross = self.param[‘crossover_probability’]
assert (self.prob_cross<=1 and self.prob_cross>=0), \
“mutation_probability must be in range [0,1]”
assert (self.param[‘elit_ratio’]<=1 and self.param['elit_ratio']>=0),\
“elit_ratio must be in range [0,1]”
trl=self.pop_s*self.param[‘elit_ratio’]
if trl<1 and self.param['elit_ratio']>0:
self.num_elit=1
else:
self.num_elit=int(trl)
assert(self.par_s>=self.num_elit), \
“\n number of parents must be greater than number of elits”
if self.param[‘max_num_iteration’]==None:
self.iterate=0
for i in range (0,self.dim):
if self.var_type[i]==’int’:
self.iterate+=(self.var_bound[i][1]-self.var_bound[i][0])*self.dim*(100/self.pop_s)
else:
self.iterate+=(self.var_bound[i][1]-self.var_bound[i][0])*50*(100/self.pop_s)
self.iterate=int(self.iterate)
if (self.iterate*self.pop_s)>10000000:
self.iterate=10000000/self.pop_s
else:
self.iterate=int(self.param[‘max_num_iteration’])
self.c_type=self.param[‘crossover_type’]
assert (self.c_type==’uniform’ or self.c_type==’one_point’ or\
self.c_type==’two_point’),\
“\n crossover_type must ‘uniform’, ‘one_point’, or ‘two_point’ Enter string”
self.stop_mniwi=False
if self.param[‘max_iteration_without_improv’]==None:
self.mniwi=self.iterate+1
else:
self.mniwi=int(self.param[‘max_iteration_without_improv’])
#############################################################
def run(self):
#############################################################
# Initial Population
self.integers = np.where(self.var_type==’int’)
self.reals = np.where(self.var_type==’real’)
pop = np.array([np.zeros(self.dim+1)]*self.pop_s)
solo = np.zeros(self.dim+1)
var = np.zeros(self.dim)
for p in range(0,self.pop_s):
for i in self.integers[0]:
var[i] = np.random.randint(self.var_bound[i][0],\
self.var_bound[i][1]+1)
solo[i] = var[i].copy()
for i in self.reals[0]:
var[i]=self.var_bound[i][0]+np.random.random()*\
(self.var_bound[i][1]-self.var_bound[i][0])
solo[i]=var[i].copy()
obj = self.sim(var)
solo[self.dim] = obj
pop[p] = solo.copy()
#############################################################
#############################################################
# Report
self.report=[]
self.test_obj=obj
self.best_variable=var.copy()
self.best_function=obj
##############################################################
t=1
counter=0
while t<=self.iterate:
if self.progress_bar==True:
self.progress(t,self.iterate,status="GA is running...")
#############################################################
#Sort
pop = pop[pop[:,self.dim].argsort()]
if pop[0,self.dim]
pop = pop[pop[:,self.dim].argsort()]
if pop[0,self.dim]>=self.best_function:
t=self.iterate
if self.progress_bar==True:
self.progress(t,self.iterate,status=”GA is running…”)
time.sleep(2)
t+=1
self.stop_mniwi=True
#############################################################
#Sort
pop = pop[pop[:,self.dim].argsort()]
if pop[0,self.dim]
x[i]=np.random.randint(p2[i],p1[i])
else:
x[i]=np.random.randint(self.var_bound[i][0],\
self.var_bound[i][1]+1)
for i in self.reals[0]:
ran=np.random.random()
if ran < self.prob_mut:
if p1[i]
x[i]=p2[i]+np.random.random()*(p1[i]-p2[i])
else:
x[i]=self.var_bound[i][0]+np.random.random()*\
(self.var_bound[i][1]-self.var_bound[i][0])
return x
###############################################################################
def evaluate(self):
return self.f(self.temp)
###############################################################################
def sim(self,X):
self.temp=X.copy()
obj=None
try:
obj=func_timeout(self.funtimeout,self.evaluate)
except FunctionTimedOut:
print(“given function is not applicable”)
assert (obj!=None), “After “+str(self.funtimeout)+” seconds delay “+\
“func_timeout: the given function does not provide any output”
return obj
###############################################################################
def progress(self, count, total, status=”):
bar_len = 50
filled_len = int(round(bar_len * count / float(total)))
percents = round(100.0 * count / float(total), 1)
bar = ‘|’ * filled_len + ‘_’ * (bar_len – filled_len)
sys.stdout.write(‘\r%s %s%s %s’ % (bar, percents, ‘%’, status))
sys.stdout.flush()
###############################################################################
###############################################################################