Requisitos previos: algoritmo genético , problema del viajante
de comercio En este artículo, se propone un algoritmo genético para resolver el problema del viajero de comercio .
Los algoritmos genéticos son algoritmos de búsqueda heurística inspirados en el proceso que sustenta la evolución de la vida. El algoritmo está diseñado para replicar el proceso de selección natural para llevar a cabo la generación, es decir, la supervivencia del más apto de los seres. Los algoritmos genéticos estándar se dividen en cinco fases que son:
- Creación de población inicial.
- Cálculo de la aptitud.
- Selección de los mejores genes.
- Cruzando.
- Mutar para introducir variaciones.
Estos algoritmos se pueden implementar para encontrar una solución a los problemas de optimización de varios tipos. Uno de esos problemas es el problema del viajante de comercio . El problema dice que a un vendedor se le da un conjunto de ciudades, tiene que encontrar la ruta más corta para visitar cada ciudad exactamente una vez y regresar a la ciudad de origen.
Enfoque: En la siguiente implementación, las ciudades se toman como genes, la string generada usando estos caracteres se llama cromosoma, mientras que una puntuación de aptitud que es igual a la longitud de la ruta de todas las ciudades mencionadas, se usa para apuntar a una población.
Fitness Score se define como la longitud del camino descrito por el gen. Cuanto menor sea el ajuste de la longitud del camino es el gen. El más apto de todos los genes del acervo genético sobrevive a la prueba de población y pasa a la siguiente iteración. El número de iteraciones depende del valor de una variable de enfriamiento. El valor de la variable de enfriamiento continúa disminuyendo con cada iteración y alcanza un umbral después de un cierto número de iteraciones.
Algoritmo:
1. Initialize the population randomly.
2. Determine the fitness of the chromosome.
3. Until done repeat:
1. Select parents.
2. Perform crossover and mutation.
3. Calculate the fitness of the new population.
4. Append it to the gene pool.
pseudo-código
Initialize procedure GA{
Set cooling parameter = 0;
Evaluate population P(t);
While( Not Done ){
Parents(t) = Select_Parents(P(t));
Offspring(t) = Procreate(P(t));
p(t+1) = Select_Survivors(P(t), Offspring(t));
t = t + 1;
}
}
¿Cómo funciona la mutación?
Supongamos que hay 5 ciudades: 0, 1, 2, 3, 4. El vendedor está en la ciudad 0 y tiene que encontrar la ruta más corta para viajar a través de todas las ciudades de regreso a la ciudad 0. Un cromosoma que representa la ruta elegida puede ser representado como:
Este cromosoma sufre una mutación. Durante la mutación, la posición de dos ciudades en el cromosoma se intercambia para formar una nueva configuración, excepto la primera y la última celda, ya que representan el punto inicial y final.
El cromosoma original tenía una longitud de ruta igual a INT_MAX , según la entrada definida a continuación, ya que la ruta entre la ciudad 1 y la ciudad 4 no existía. Después de la mutación, el nuevo niño formado tiene una longitud de camino igual a 21 , que es una respuesta mucho más optimizada que la suposición original. Así es como el algoritmo genético optimiza las soluciones a problemas difíciles.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
// Number of cities in TSP
#define V 5
// Names of the cities
#define GENES ABCDE
// Starting Node Value
#define START 0
// Initial population size for the algorithm
#define POP_SIZE 10
// Structure of a GNOME
// string defines the path traversed
// by the salesman while the fitness value
// of the path is stored in an integer
struct individual {
string gnome;
int fitness;
};
// Function to return a random number
// from start and end
int rand_num(int start, int end)
{
int r = end - start;
int rnum = start + rand() % r;
return rnum;
}
// Function to check if the character
// has already occurred in the string
bool repeat(string s, char ch)
{
for (int i = 0; i < s.size(); i++) {
if (s[i] == ch)
return true;
}
return false;
}
// Function to return a mutated GNOME
// Mutated GNOME is a string
// with a random interchange
// of two genes to create variation in species
string mutatedGene(string gnome)
{
while (true) {
int r = rand_num(1, V);
int r1 = rand_num(1, V);
if (r1 != r) {
char temp = gnome[r];
gnome[r] = gnome[r1];
gnome[r1] = temp;
break;
}
}
return gnome;
}
// Function to return a valid GNOME string
// required to create the population
string create_gnome()
{
string gnome = "0";
while (true) {
if (gnome.size() == V) {
gnome += gnome[0];
break;
}
int temp = rand_num(1, V);
if (!repeat(gnome, (char)(temp + 48)))
gnome += (char)(temp + 48);
}
return gnome;
}
// Function to return the fitness value of a gnome.
// The fitness value is the path length
// of the path represented by the GNOME.
int cal_fitness(string gnome)
{
int map[V][V] = { { 0, 2, INT_MAX, 12, 5 },
{ 2, 0, 4, 8, INT_MAX },
{ INT_MAX, 4, 0, 3, 3 },
{ 12, 8, 3, 0, 10 },
{ 5, INT_MAX, 3, 10, 0 } };
int f = 0;
for (int i = 0; i < gnome.size() - 1; i++) {
if (map[gnome[i] - 48][gnome[i + 1] - 48] == INT_MAX)
return INT_MAX;
f += map[gnome[i] - 48][gnome[i + 1] - 48];
}
return f;
}
// Function to return the updated value
// of the cooling element.
int cooldown(int temp)
{
return (90 * temp) / 100;
}
// Comparator for GNOME struct.
bool lessthan(struct individual t1,
struct individual t2)
{
return t1.fitness < t2.fitness;
}
// Utility function for TSP problem.
void TSPUtil(int map[V][V])
{
// Generation Number
int gen = 1;
// Number of Gene Iterations
int gen_thres = 5;
vector<struct individual> population;
struct individual temp;
// Populating the GNOME pool.
for (int i = 0; i < POP_SIZE; i++) {
temp.gnome = create_gnome();
temp.fitness = cal_fitness(temp.gnome);
population.push_back(temp);
}
cout << "\nInitial population: " << endl
<< "GNOME FITNESS VALUE\n";
for (int i = 0; i < POP_SIZE; i++)
cout << population[i].gnome << " "
<< population[i].fitness << endl;
cout << "\n";
bool found = false;
int temperature = 10000;
// Iteration to perform
// population crossing and gene mutation.
while (temperature > 1000 && gen <= gen_thres) {
sort(population.begin(), population.end(), lessthan);
cout << "\nCurrent temp: " << temperature << "\n";
vector<struct individual> new_population;
for (int i = 0; i < POP_SIZE; i++) {
struct individual p1 = population[i];
while (true) {
string new_g = mutatedGene(p1.gnome);
struct individual new_gnome;
new_gnome.gnome = new_g;
new_gnome.fitness = cal_fitness(new_gnome.gnome);
if (new_gnome.fitness <= population[i].fitness) {
new_population.push_back(new_gnome);
break;
}
else {
// Accepting the rejected children at
// a possible probability above threshold.
float prob = pow(2.7,
-1 * ((float)(new_gnome.fitness
- population[i].fitness)
/ temperature));
if (prob > 0.5) {
new_population.push_back(new_gnome);
break;
}
}
}
}
temperature = cooldown(temperature);
population = new_population;
cout << "Generation " << gen << " \n";
cout << "GNOME FITNESS VALUE\n";
for (int i = 0; i < POP_SIZE; i++)
cout << population[i].gnome << " "
<< population[i].fitness << endl;
gen++;
}
}
int main()
{
int map[V][V] = { { 0, 2, INT_MAX, 12, 5 },
{ 2, 0, 4, 8, INT_MAX },
{ INT_MAX, 4, 0, 3, 3 },
{ 12, 8, 3, 0, 10 },
{ 5, INT_MAX, 3, 10, 0 } };
TSPUtil(map);
}
Python3
# Python3 implementation of the above approach
from random import randint
INT_MAX = 2147483647
# Number of cities in TSP
V = 5
# Names of the cities
GENES = "ABCDE"
# Starting Node Value
START = 0
# Initial population size for the algorithm
POP_SIZE = 10
# Structure of a GNOME
# defines the path traversed
# by the salesman while the fitness value
# of the path is stored in an integer
class individual:
def __init__(self) -> None:
self.gnome = ""
self.fitness = 0
def __lt__(self, other):
return self.fitness < other.fitness
def __gt__(self, other):
return self.fitness > other.fitness
# Function to return a random number
# from start and end
def rand_num(start, end):
return randint(start, end-1)
# Function to check if the character
# has already occurred in the string
def repeat(s, ch):
for i in range(len(s)):
if s[i] == ch:
return True
return False
# Function to return a mutated GNOME
# Mutated GNOME is a string
# with a random interchange
# of two genes to create variation in species
def mutatedGene(gnome):
gnome = list(gnome)
while True:
r = rand_num(1, V)
r1 = rand_num(1, V)
if r1 != r:
temp = gnome[r]
gnome[r] = gnome[r1]
gnome[r1] = temp
break
return ''.join(gnome)
# Function to return a valid GNOME string
# required to create the population
def create_gnome():
gnome = "0"
while True:
if len(gnome) == V:
gnome += gnome[0]
break
temp = rand_num(1, V)
if not repeat(gnome, chr(temp + 48)):
gnome += chr(temp + 48)
return gnome
# Function to return the fitness value of a gnome.
# The fitness value is the path length
# of the path represented by the GNOME.
def cal_fitness(gnome):
mp = [
[0, 2, INT_MAX, 12, 5],
[2, 0, 4, 8, INT_MAX],
[INT_MAX, 4, 0, 3, 3],
[12, 8, 3, 0, 10],
[5, INT_MAX, 3, 10, 0],
]
f = 0
for i in range(len(gnome) - 1):
if mp[ord(gnome[i]) - 48][ord(gnome[i + 1]) - 48] == INT_MAX:
return INT_MAX
f += mp[ord(gnome[i]) - 48][ord(gnome[i + 1]) - 48]
return f
# Function to return the updated value
# of the cooling element.
def cooldown(temp):
return (90 * temp) / 100
# Comparator for GNOME struct.
# def lessthan(individual t1,
# individual t2)
# :
# return t1.fitness < t2.fitness
# Utility function for TSP problem.
def TSPUtil(mp):
# Generation Number
gen = 1
# Number of Gene Iterations
gen_thres = 5
population = []
temp = individual()
# Populating the GNOME pool.
for i in range(POP_SIZE):
temp.gnome = create_gnome()
temp.fitness = cal_fitness(temp.gnome)
population.append(temp)
print("\nInitial population: \nGNOME FITNESS VALUE\n")
for i in range(POP_SIZE):
print(population[i].gnome, population[i].fitness)
print()
found = False
temperature = 10000
# Iteration to perform
# population crossing and gene mutation.
while temperature > 1000 and gen <= gen_thres:
population.sort()
print("\nCurrent temp: ", temperature)
new_population = []
for i in range(POP_SIZE):
p1 = population[i]
while True:
new_g = mutatedGene(p1.gnome)
new_gnome = individual()
new_gnome.gnome = new_g
new_gnome.fitness = cal_fitness(new_gnome.gnome)
if new_gnome.fitness <= population[i].fitness:
new_population.append(new_gnome)
break
else:
# Accepting the rejected children at
# a possible probability above threshold.
prob = pow(
2.7,
-1
* (
(float)(new_gnome.fitness - population[i].fitness)
/ temperature
),
)
if prob > 0.5:
new_population.append(new_gnome)
break
temperature = cooldown(temperature)
population = new_population
print("Generation", gen)
print("GNOME FITNESS VALUE")
for i in range(POP_SIZE):
print(population[i].gnome, population[i].fitness)
gen += 1
if __name__ == "__main__":
mp = [
[0, 2, INT_MAX, 12, 5],
[2, 0, 4, 8, INT_MAX],
[INT_MAX, 4, 0, 3, 3],
[12, 8, 3, 0, 10],
[5, INT_MAX, 3, 10, 0],
]
TSPUtil(mp)
Initial population: GNOME FITNESS VALUE 043210 24 023410 2147483647 031420 2147483647 034210 31 043210 24 023140 2147483647 032410 2147483647 012340 24 012340 24 032410 2147483647 Current temp: 10000 Generation 1 GNOME FITNESS VALUE 013240 21 013240 21 012430 31 012430 31 031240 32 024310 2147483647 013420 2147483647 032140 2147483647 034210 31 012430 31 Current temp: 9000 Generation 2 GNOME FITNESS VALUE 031240 32 043210 24 012340 24 042130 32 043210 24 012340 24 034210 31 014320 2147483647 014320 2147483647 023140 2147483647 Current temp: 8100 Generation 3 GNOME FITNESS VALUE 013240 21 042310 21 013240 21 013240 21 031240 32 013240 21 012430 31 034120 2147483647 041320 2147483647 043120 2147483647 Current temp: 7290 Generation 4 GNOME FITNESS VALUE 031240 32 043210 24 043210 24 043210 24 012340 24 042130 32 013240 21 014320 2147483647 021340 2147483647 043210 24 Current temp: 6561 Generation 5 GNOME FITNESS VALUE 043210 24 042310 21 042310 21 013240 21 042310 21 034210 31 013240 21 042310 21 024310 2147483647 024310 2147483647
Publicación traducida automáticamente
Artículo escrito por chitrankmishra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA