# encoding=utf8
import logging
from math import ceil
import numpy as np
from niapy.algorithms.algorithm import Algorithm, Individual, default_individual_init, default_numpy_init
logging.basicConfig()
logger = logging.getLogger('niapy.algorithms.basic')
logger.setLevel('INFO')
__all__ = ['MonkeyKingEvolutionV1', 'MonkeyKingEvolutionV2', 'MonkeyKingEvolutionV3']
class MkeSolution(Individual):
r"""Implementation of Monkey King Evolution individual.
Data:
2018
Authors:
Klemen Berkovič
License:
MIT
Attributes:
x_pb (array of (float or int)): Personal best position of Monkey particle.
f_pb (float): Personal best fitness/function value.
MonkeyKing (bool): Boolean value indicating if particle is Monkey King particle.
See Also:
* :class:`niapy.algorithms.Individual`
"""
def __init__(self, **kwargs):
r"""Initialize Monkey particle.
Args:
**kwargs: Additional arguments
See Also:
* :class:`niapy.algorithms.Individual.__init__`
"""
super().__init__(**kwargs)
self.f_pb, self.x_pb = self.f, self.x
self.monkey_king = False
def update_personal_best(self):
r"""Update personal best position of particle."""
if self.f < self.f_pb:
self.x_pb, self.f_pb = self.x, self.f
[docs]class MonkeyKingEvolutionV1(Algorithm):
r"""Implementation of monkey king evolution algorithm version 1.
Algorithm:
Monkey King Evolution version 1
Date:
2018
Authors:
Klemen Berkovič
License:
MIT
Reference URL:
https://www.sciencedirect.com/science/article/pii/S0950705116000198
Reference paper:
Zhenyu Meng, Jeng-Shyang Pan, Monkey King Evolution: A new memetic evolutionary algorithm and its application in vehicle fuel consumption optimization, Knowledge-Based Systems, Volume 97, 2016, Pages 144-157, ISSN 0950-7051, https://doi.org/10.1016/j.knosys.2016.01.009.
Attributes:
Name (List[str]): List of strings representing algorithm names.
fluctuation_coeff (float): Scale factor for normal particles.
population_rate (float): Percent value of now many new particle Monkey King particle creates.
c (int): Number of new particles generated by Monkey King particle.
fc (float): Scale factor for Monkey King particles.
See Also:
* :class:`niapy.algorithms.algorithm.Algorithm`
"""
Name = ['MonkeyKingEvolutionV1', 'MKEv1']
[docs] @staticmethod
def info():
r"""Get basic information of algorithm.
Returns:
str: Basic information.
See Also:
* :func:`niapy.algorithms.Algorithm.info`
"""
return r"""Zhenyu Meng, Jeng-Shyang Pan, Monkey King Evolution: A new memetic evolutionary algorithm and its application in vehicle fuel consumption optimization, Knowledge-Based Systems, Volume 97, 2016, Pages 144-157, ISSN 0950-7051, https://doi.org/10.1016/j.knosys.2016.01.009."""
[docs] def __init__(self, population_size=40, fluctuation_coeff=0.7, population_rate=0.3, c=3, fc=0.5, *args, **kwargs):
"""Initialize MonkeyKingEvolutionV1.
Args:
population_size (int): Population size.
fluctuation_coeff (float): Scale factor for normal particle.
population_rate (float): Percent value of now many new particle Monkey King particle creates. Value in rage [0, 1].
c (int): Number of new particles generated by Monkey King particle.
fc (float): Scale factor for Monkey King particles.
See Also:
* :func:`niapy.algorithms.algorithm.Algorithm.__init__`
"""
super().__init__(population_size,
individual_type=kwargs.pop('individual_type', MkeSolution),
initialization_function=kwargs.pop('initialization_function', default_individual_init),
*args, **kwargs)
self.fluctuation_coeff = fluctuation_coeff
self.population_rate = population_rate
self.c = c
self.fc = fc
[docs] def set_parameters(self, population_size=40, fluctuation_coeff=0.7, population_rate=0.3, c=3, fc=0.5, **kwargs):
r"""Set Monkey King Evolution v1 algorithms static parameters.
Args:
population_size (int): Population size.
fluctuation_coeff (float): Scale factor for normal particle.
population_rate (float): Percent value of now many new particle Monkey King particle creates. Value in rage [0, 1].
c (int): Number of new particles generated by Monkey King particle.
fc (float): Scale factor for Monkey King particles.
See Also:
* :func:`niapy.algorithms.algorithm.Algorithm.set_parameters`
"""
super().set_parameters(population_size=population_size,
individual_type=kwargs.pop('individual_type', MkeSolution),
initialization_function=kwargs.pop('initialization_function', default_individual_init),
**kwargs)
self.fluctuation_coeff = fluctuation_coeff
self.population_rate = population_rate
self.c = c
self.fc = fc
[docs] def get_parameters(self):
r"""Get algorithms parameters values.
Returns:
Dict[str, Any]
See Also:
* :func:`niapy.algorithms.Algorithm.get_parameters`
"""
d = Algorithm.get_parameters(self)
d.update({
'fluctuation_coeff': self.fluctuation_coeff,
'population_rate': self.population_rate,
'c': self.c,
'fc': self.fc
})
return d
[docs] def move_p(self, x, x_pb, x_b, task):
r"""Move normal particle in search space.
For moving particles algorithm uses next formula:
:math:`\mathbf{x_{pb} - \mathit{differential_weight} \odot \mathbf{r} \odot (\mathbf{x_b} - \mathbf{x})`
where
:math:`\mathbf{r}` is one dimension array with `D` components. Components in this vector are in range [0, 1].
Args:
x (numpy.ndarray): Particle position.
x_pb (numpy.ndarray): Particle best position.
x_b (numpy.ndarray): Best particle position.
task (Task): Optimization task.
Returns:
numpy.ndarray: Particle new position.
"""
return x_pb + self.fluctuation_coeff * self.random(task.dimension) * (x_b - x)
[docs] def move_mk(self, x, task):
r"""Move Monkey King particle.
For moving Monkey King particles algorithm uses next formula:
:math:`\mathbf{x} + \mathit{fc} \odot \mathbf{population_rate} \odot \mathbf{x}`
where
:math:`\mathbf{population_rate}` is two dimensional array with shape `{c * D, D}`. Components of this array are in range [0, 1]
Args:
x (numpy.ndarray): Monkey King patricle position.
task (Task): Optimization task.
Returns:
numpy.ndarray: New particles generated by Monkey King particle.
"""
return x + self.fc * self.random((int(self.c * task.dimension), task.dimension)) * x
[docs] def move_particle(self, p, p_b, task):
r"""Move particles.
Args:
p (MkeSolution): Monkey particle.
p_b (numpy.ndarray): Population best particle.
task (Task): Optimization task.
"""
p.x = self.move_p(p.x, p.x_pb, p_b, task)
p.evaluate(task, rng=self.rng)
[docs] def move_monkey_king_particle(self, p, task):
r"""Move Monkey King Particles.
Args:
p (MkeSolution): Monkey King particle to apply this function on.
task (Task): Optimization task.
"""
p.monkey_king = False
a = np.apply_along_axis(task.repair, 1, self.move_mk(p.x, task), self.rng)
a_f = np.apply_along_axis(task.eval, 1, a)
ib = np.argmin(a_f)
p.x, p.f = a[ib], a_f[ib]
[docs] def move_population(self, pop, xb, task):
r"""Move population.
Args:
pop (numpy.ndarray[MkeSolution]): Current population.
xb (numpy.ndarray): Current best solution.
task (Task): Optimization task.
Returns:
numpy.ndarray[MkeSolution]: New particles.
"""
for p in pop:
if p.monkey_king:
self.move_monkey_king_particle(p, task)
else:
self.move_particle(p, xb, task)
p.update_personal_best()
return pop
[docs] def init_population(self, task):
r"""Init population.
Args:
task (Task): Optimization task
Returns:
Tuple(numpy.ndarray[MkeSolution], numpy.ndarray[float], Dict[str, Any]]:
1. Initialized solutions
2. Fitness/function values of solution
3. Additional arguments
"""
pop, fpop, _ = Algorithm.init_population(self, task)
for i in self.rng.choice(self.population_size, int(self.population_rate * len(pop)), replace=False):
pop[i].monkey_king = True
return pop, fpop, {}
[docs] def run_iteration(self, task, population, population_fitness, best_x, best_fitness, **params):
r"""Core function of Monkey King Evolution v1 algorithm.
Args:
task (Task): Optimization task.
population (numpy.ndarray[MkeSolution]): Current population.
population_fitness (numpy.ndarray[float]): Current population fitness/function values.
best_x (numpy.ndarray): Current best solution.
best_fitness (float): Current best solutions function/fitness value.
**params (Dict[str, Any]): Additional arguments.
Returns:
Tuple(numpy.ndarray[MkeSolution], numpy.ndarray[float], Dict[str, Any]]:
1. Initialized solutions.
2. Fitness/function values of solution.
3. Additional arguments.
"""
population = self.move_population(population, best_x, task)
for i in self.rng.choice(self.population_size, int(self.population_rate * len(population)), replace=False):
population[i].monkey_king = True
population_fitness = np.asarray([m.f for m in population])
best_x, best_fitness = self.get_best(population, population_fitness, best_x, best_fitness)
return population, population_fitness, best_x, best_fitness, {}
[docs]class MonkeyKingEvolutionV2(MonkeyKingEvolutionV1):
r"""Implementation of monkey king evolution algorithm version 2.
Algorithm:
Monkey King Evolution version 2
Date:
2018
Authors:
Klemen Berkovič
License:
MIT
Reference URL:
https://www.sciencedirect.com/science/article/pii/S0950705116000198
Reference paper:
Zhenyu Meng, Jeng-Shyang Pan, Monkey King Evolution: A new memetic evolutionary algorithm and its application in vehicle fuel consumption optimization, Knowledge-Based Systems, Volume 97, 2016, Pages 144-157, ISSN 0950-7051, https://doi.org/10.1016/j.knosys.2016.01.009.
Attributes:
Name (List[str]): List of strings representing algorithm names.
See Also:
* :class:`niapy.algorithms.basic.mke.MonkeyKingEvolutionV1`
"""
Name = ['MonkeyKingEvolutionV2', 'MKEv2']
[docs] @staticmethod
def info():
r"""Get basic information of algorithm.
Returns:
str: Basic information.
See Also:
* :func:`niapy.algorithms.Algorithm.info`
"""
return r"""Zhenyu Meng, Jeng-Shyang Pan, Monkey King Evolution: A new memetic evolutionary algorithm and its application in vehicle fuel consumption optimization, Knowledge-Based Systems, Volume 97, 2016, Pages 144-157, ISSN 0950-7051, https://doi.org/10.1016/j.knosys.2016.01.009."""
[docs] def move_mk(self, x, task, dx=None):
r"""Move Monkey King particle.
For movement of particles algorithm uses next formula:
:math:`\mathbf{x} - \mathit{fc} \odot \mathbf{dx}`
Args:
x (numpy.ndarray): Particle to apply movement on.
task (Task): Optimization task.
dx (numpy.ndarray): Difference between to random particles in population.
Returns:
numpy.ndarray: Moved particles.
"""
return x - self.fc * dx
[docs] def move_monkey_king_particle(self, p, task, pop=None):
r"""Move Monkey King particles.
Args:
p (MkeSolution): Monkey King particle to move.
task (Task): Optimization task.
pop (numpy.ndarray[MkeSolution]): Current population.
"""
p.monkey_king = False
p_b, p_f = p.x, p.f
for _i in range(int(self.c * self.population_size)):
r = self.rng.choice(self.population_size, 2, replace=False)
a = task.repair(self.move_mk(p.x, task, pop[r[0]].x - pop[r[1]].x), self.rng)
a_f = task.eval(a)
if a_f < p_f:
p_b, p_f = a, a_f
p.x, p.f = p_b, p_f
[docs] def move_population(self, pop, xb, task):
r"""Move population.
Args:
pop (numpy.ndarray[MkeSolution]): Current population.
xb (numpy.ndarray): Current best solution.
task (Task): Optimization task.
Returns:
numpy.ndarray[MkeSolution]: Moved population.
"""
for p in pop:
if p.monkey_king:
self.move_monkey_king_particle(p, task, pop)
else:
self.move_particle(p, xb, task)
p.update_personal_best()
return pop
[docs]class MonkeyKingEvolutionV3(MonkeyKingEvolutionV1):
r"""Implementation of monkey king evolution algorithm version 3.
Algorithm:
Monkey King Evolution version 3
Date:
2018
Authors:
Klemen Berkovič
License:
MIT
Reference URL:
https://www.sciencedirect.com/science/article/pii/S0950705116000198
Reference paper:
Zhenyu Meng, Jeng-Shyang Pan, Monkey King Evolution: A new memetic evolutionary algorithm and its application in vehicle fuel consumption optimization, Knowledge-Based Systems, Volume 97, 2016, Pages 144-157, ISSN 0950-7051, https://doi.org/10.1016/j.knosys.2016.01.009.
Attributes:
Name (List[str]): List of strings that represent algorithm names.
See Also:
* :class:`niapy.algorithms.basic.mke.MonkeyKingEvolutionV1`
"""
Name = ['MonkeyKingEvolutionV3', 'MKEv3']
[docs] @staticmethod
def info():
r"""Get basic information of algorithm.
Returns:
str: Basic information.
See Also:
* :func:`niapy.algorithms.Algorithm.info`
"""
return r"""Zhenyu Meng, Jeng-Shyang Pan, Monkey King Evolution: A new memetic evolutionary algorithm and its application in vehicle fuel consumption optimization, Knowledge-Based Systems, Volume 97, 2016, Pages 144-157, ISSN 0950-7051, https://doi.org/10.1016/j.knosys.2016.01.009."""
[docs] def __init__(self, *args, **kwargs):
"""Initialize MonkeyKingEvolutionV3."""
super().__init__(individual_type=kwargs.pop('individual_type', None),
initialization_function=kwargs.pop('initialization_function', default_numpy_init),
*args, **kwargs)
[docs] def set_parameters(self, **kwargs):
r"""Set core parameters of MonkeyKingEvolutionV3 algorithm.
See Also:
* :func:`niapy.algorithms.basic.MonkeyKingEvolutionV1.set_parameters`
"""
super().set_parameters(individual_type=kwargs.pop('individual_type', None),
initialization_function=kwargs.pop('initialization_function', default_numpy_init),
**kwargs)
[docs] @staticmethod
def neg(x):
r"""Transform function.
Args:
x (Union[int, float]): Should be 0 or 1.
Returns:
float: If 0 then 1 else 0.
"""
return 0.0 if x == 1.0 else 1.0
[docs] def init_population(self, task):
r"""Initialize the population.
Args:
task (Task): Optimization task.
Returns:
Tuple[numpy.ndarray, numpy.ndarray[float], Dict[str, Any]]:
1. Initialized population.
2. Initialized population function/fitness values.
3. Additional arguments:
* k (int): Starting number of rows to include from lower triangular matrix.
* c (int): Constant.
See Also:
* :func:`niapy.algorithms.algorithm.Algorithm.init_population`
"""
population, fitness, d = Algorithm.init_population(self, task)
k, c = int(ceil(self.population_size / task.dimension)), int(ceil(self.c * task.dimension))
d.update({'k': k, 'c': c})
return population, fitness, d
[docs] def run_iteration(self, task, population, population_fitness, best_x, best_fitness, **params):
r"""Core function of Monkey King Evolution v3 algorithm.
Args:
task (Task): Optimization task.
population (numpy.ndarray): Current population.
population_fitness (numpy.ndarray[float]): Current population fitness/function values.
best_x (numpy.ndarray): Current best individual.
best_fitness (float): Current best individual function/fitness value.
**params: Additional arguments
Returns:
Tuple[numpy.ndarray, numpy.ndarray[float], Dict[str, Any]]:
1. Initialized population.
2. Initialized population function/fitness values.
3. Additional arguments:
* k (int): Starting number of rows to include from lower triangular matrix.
* c (int): Constant.
"""
k = params.pop('k')
c = params.pop('c')
x_gb = np.apply_along_axis(task.repair, 1,
best_x + self.fc * population[self.rng.choice(len(population), c)] - population[self.rng.choice(len(population), c)],
self.rng)
x_gb_f = np.apply_along_axis(task.eval, 1, x_gb)
best_x, best_fitness = self.get_best(x_gb, x_gb_f, best_x, best_fitness)
m = np.ones((self.population_size, task.dimension))
for i in range(k):
m[i * task.dimension:(i + 1) * task.dimension] = np.tril(m[i * task.dimension:(i + 1) * task.dimension])
for i in range(self.population_size):
self.rng.shuffle(m[i])
population = np.apply_along_axis(task.repair, 1, m * population + np.vectorize(self.neg)(m) * best_x, self.rng)
population_fitness = np.apply_along_axis(task.eval, 1, population)
best_x, best_fitness = self.get_best(population, population_fitness, best_x, best_fitness)
iw, ib_gb = np.argmax(population_fitness), np.argmin(x_gb_f)
if x_gb_f[ib_gb] <= population_fitness[iw]:
population[iw], population_fitness[iw] = x_gb[ib_gb], x_gb_f[ib_gb]
return population, population_fitness, best_x, best_fitness, {'k': k, 'c': c}
# vim: tabstop=3 noexpandtab shiftwidth=3 softtabstop=3