Генетические алгоритмы

Что такое генетический алгоритм?

Генетические алгоритмы — это тип алгоритма оптимизации и поиска, вдохновленный процессом естественного отбора в биологической эволюции.

Эти алгоритмы используют такие принципы, как мутация, скрещивание (или воспроизводство) и отбор для поиска решений сложных проблем.

Джон Генри Холланд – американский ученый, профессор электротехники и информатики в Мичиганском университете. Наиболее известен как инноватор сложных адаптивных систем и нелинейной науки, а также создатель генетических алгоритмов.

Идею генетических алгоритмов он сформулировал и обосновал в конце 60-х-начале 70-х гг. ХХ в. Он заинтересовался свойствами процессов естественной эволюции, в том числе фактом, что эволюционируют хромосомы, а не сами существа. Ученый был уверен в возможности составить и реализовать в виде компьютерной программы алгоритм, который будет решать сложные задачи так, как это делает природа – путем эволюции. Поэтому он начал трудиться над алгоритмами, оперировавшими последовательностями двоичных цифр (единиц и нулей), получившими название хромосом.

Генетические алгоритмы работают по аналогии с природой. Они оперируют с совокупностью «особей», представляющих собой строки, каждая из которых кодирует одно из решений задачи. Приспособленность особи оценивается с помощью специальной функции. Наиболее приспособленные получают шанс скрещиваться и давать потомство. Наихудшие особи удаляются. Таким образом, приспособленность нового поколения в среднем выше предыдущего. На практике генетические алгоритмы используются для решения таких, задач, как оптимизация запросов в базах данных, настройка и обучение искусственной нейронной сети, составление игровых стратегий, создание искусственной жизни. Вышедшая в 1975 г. книга Джона Холланда «Адаптация в естественных и искусственных системах» [Adaptation in Natural and Artificial Systems] является основополагающим трудом в этой области исследований

Population

Это относится к набору возможных решений (или хромосом) проблемы. На каждой итерации (или поколении) генетические алгоритмы работают с популяцией хромосом.

Fitness Function

Эта функция измеряет качество или «пригодность» решения для популяции, направляя поиск оптимальных решений.

Operators: Selection, Crossover, Mutation

Эти операторы имитируют естественные эволюционные процессы. Отбор выбирает подходящих особей, скрещивание объединяет два решения для создания новых, а мутация вносит в решение небольшие случайные изменения.

import random

# Количество особей в каждом поколении
POPULATION_SIZE = 100

# Валидные гены
GENES = '''abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP
QRSTUVWXYZ 1234567890, .-;:_!"#%&/()=?@${[]}'''

# Целевая строка для генерации
TARGET = "In principio erat Verbum 2000"

class Individual(object):
	'''
	Класс, представляющий отдельную особь (индивида) в популяции
	'''
	def __init__(self, chromosome):
		self.chromosome = chromosome
		self.fitness = self.cal_fitness()

	@classmethod
	def mutated_genes(self):
		'''
		Создаем случайные гены для мутации
		'''
		global GENES
		gene = random.choice(GENES)
		return gene

	@classmethod
	def create_gnome(self):
		'''
		Создаем хромосому или набор генов
		'''
		global TARGET
		gnome_len = len(TARGET)
		return [self.mutated_genes() for _ in range(gnome_len)]

	def gene_transfer(self, par2):
		'''
		Передаем гены новому поколению индивидов
		'''

		child_chromosome = []
		for gp1, gp2 in zip(self.chromosome, par2.chromosome):

			prob = random.random()

			# если вероятность меньше 0,45, берем ген
			# от родителя 1
			if prob < 0.45:
				child_chromosome.append(gp1)

			# если вероятность между 0.45 и 0.90, берем
			# ген от родителя 2
			elif prob < 0.90:
				child_chromosome.append(gp2)

			# в противном случае берем случайный ген (мутация),
			else:
				child_chromosome.append(self.mutated_genes())


		return Individual(child_chromosome)

	def cal_fitness(self):
		'''
		Рассчитываем показатель соответствия, это количество
		символов в строке, которые отличаются от целевой
		строки.
		'''
		global TARGET
		fitness = 0
		for gs, gt in zip(self.chromosome, TARGET):
			if gs != gt: fitness+= 1
		return fitness

# Driver code
def main():
	global POPULATION_SIZE

	#Текущее поколение
	generation = 1

	found = False
	population = []

	# Новое поколение
	for _ in range(POPULATION_SIZE):
				gnome = Individual.create_gnome()
				population.append(Individual(gnome))

	while not found:

		# Отсортируем популяцию в порядке возрастания оценки соответствия целевой функции
		population = sorted(population, key = lambda x:x.fitness)

		# Если у нас появился индивид, достигший целевой функции
		# цикл совершенствования можно прервать
		if population[0].fitness <= 0:
			found = True
			break

		# В противном случае - продолжаем создавать новые поколения
		new_generation = []

		# Определяем 10% популяции, наиболее соответствующих целевой фукнции
		# чтобы передать их гены будущим поколениям
		s = int((10*POPULATION_SIZE)/100)
		new_generation.extend(population[:s])


		s = int((90*POPULATION_SIZE)/100)
		for _ in range(s):
			parent1 = random.choice(population[:50])
			parent2 = random.choice(population[:50])
			child = parent1.gene_transfer(parent2)
			new_generation.append(child)

		population = new_generation

		print("Generation: {}\tString: {}\tFitness: {}".
			format(generation,
			"".join(population[0].chromosome),
			population[0].fitness))

		generation += 1


	print("Generation: {}\tString: {}\tFitness: {}".
		format(generation,
		"".join(population[0].chromosome),
		population[0].fitness))

if __name__ == '__main__':
	main()

результат

Generation: 1	String: GPaC)i3=A9B}reQvaS( }x5
2u-h!	Fitness: 27
Generation: 2	String: GPaC)i3=A9B}reQvaS( }x5
2u-h!	Fitness: 27
Generation: 3	String: Ig?E%Pl,bDwyRejqH:.CKSH55k=T0	Fitness: 26
Generation: 4	String: XO PCxJI1Mi.h{/vcj
_U-pm!w$u0	Fitness: 25
Generation: 5	String: I[Z1ZiOCMCCoreB }76 Rrl8wup06	Fitness: 24
Generation: 6	String: Ig pZ,mlzMCoWer!ih5WRyH}wg Td	Fitness: 23
Generation: 7	String: :2fpri3I# NgherVw7(_ISum!wWwg	Fitness: 22
Generation: 8	String: Infpr(/IV Nghe;Ywq(ul!um,w#K0	Fitness: 21
Generation: 9	String: Infpr(/IV Nghe;Ywq(ul!um,w#K0	Fitness: 21
Generation: 10	String: Igfpri3I#aso er!i7#WLSum!wWwg	Fitness: 19
Generation: 11	String: Igfpri3I#aso er!i7#WLSum!wWwg	Fitness: 19
Generation: 12	String: In pZiY.]9soDer aw
H1%umfbf-0	Fitness: 18
Generation: 13	String: Id pri3m&@No erVUQ?KQWlm
Qb00	Fitness: 17
Generation: 14	String: Id pri3m&@No erVUQ?KQWlm
Qb00	Fitness: 17
Generation: 15	String: In pri37iQxorerVwQZt"WlmW2bd0	Fitness: 16
Generation: 16	String: In p8i?I; 6o erdUGXzLhum 2bN0	Fitness: 15
Generation: 17	String: In p8i?I; 6o erdUGXzLhum 2bN0	Fitness: 15
Generation: 18	String: In p8i?I; 6o erdUGXzLhum 2bN0	Fitness: 15
Generation: 19	String: In pZi!c#95o ex#%7Z}rfum  000	Fitness: 13
Generation: 20	String: In pZi!c#95o ex#%7Z}rfum  000	Fitness: 13
Generation: 21	String: In pZi!c#95o ex#%7Z}rfum  000	Fitness: 13
Generation: 22	String: In p/c3qi9{o erdtQ?2rhum 2b00	Fitness: 12
Generation: 23	String: In p/c3qi9{o erdtQ?2rhum 2b00	Fitness: 12
Generation: 24	String: In privcX:so eraUuZ]LhumW2000	Fitness: 11
Generation: 25	String: In privcX:so eraUuZ]LhumW2000	Fitness: 11
Generation: 26	String: In p[i?/ikio er#tQZ}.fum 2000	Fitness: 10
Generation: 27	String: In p[i?/ikio er#tQZ}.fum 2000	Fitness: 10
Generation: 28	String: In p[i?/ikio er#tQZ}.fum 2000	Fitness: 10
Generation: 29	String: In p[i?/ikio er#tQZ}.fum 2000	Fitness: 10
Generation: 30	String: In p[i?/ikio er#tQZ}.fum 2000	Fitness: 10
Generation: 31	String: In p[i?/ikio er#tQZ}.fum 2000	Fitness: 10
Generation: 32	String: In prcHci"io er#tN8Wr]umf2000	Fitness: 9
Generation: 33	String: Tn privci
{o erdt Z{rfum 2000	Fitness: 8
Generation: 34	String: Tn privci
{o erdt Z{rfum 2000	Fitness: 8
Generation: 35	String: Tn privci
{o erdt Z{rfum 2000	Fitness: 8
Generation: 36	String: Tn privci
{o erdt Z{rfum 2000	Fitness: 8
Generation: 37	String: Tn privci
{o erdt Z{rfum 2000	Fitness: 8
Generation: 38	String: Tn privci
{o erdt Z{rfum 2000	Fitness: 8
Generation: 39	String: Tn privci
{o erdt Z{rfum 2000	Fitness: 8
Generation: 40	String: In princi1io erxtNZ]rRum 200V	Fitness: 7
Generation: 41	String: In princi1io erxtNZ]rRum 200V	Fitness: 7
Generation: 42	String: In princi1io erxtNZ]rRum 200V	Fitness: 7
Generation: 43	String: In princi1io erxtNZ]rRum 200V	Fitness: 7
Generation: 44	String: In pri}cipio eratN{]rbuJ 2000	Fitness: 5
Generation: 45	String: In pri}cipio eratN{]rbuJ 2000	Fitness: 5
Generation: 46	String: In pri}cipio eratN{]rbuJ 2000	Fitness: 5
Generation: 47	String: In pri}cipio eratN{]rbuJ 2000	Fitness: 5
Generation: 48	String: In pri}cipio eratN{]rbuJ 2000	Fitness: 5
Generation: 49	String: In pri}cipio eratN{]rbuJ 2000	Fitness: 5
Generation: 50	String: In pri}cipio eratN{]rbuJ 2000	Fitness: 5
Generation: 51	String: In}pri}cipio erat Z]rbum 2000	Fitness: 4
Generation: 52	String: In}pri}cipio erat Z]rbum 2000	Fitness: 4
Generation: 53	String: In}pri}cipio erat Z]rbum 2000	Fitness: 4
Generation: 54	String: In}pri}cipio erat Z]rbum 2000	Fitness: 4
Generation: 55	String: In}pri}cipio erat Z]rbum 2000	Fitness: 4
Generation: 56	String: In}pri}cipio erat Z]rbum 2000	Fitness: 4
Generation: 57	String: In}pri}cipio erat Z]rbum 2000	Fitness: 4
Generation: 58	String: In prinJipio erat V2rbum 200:	Fitness: 3
Generation: 59	String: In prinJipio erat V2rbum 200:	Fitness: 3
Generation: 60	String: In prinJipio erat V2rbum 200:	Fitness: 3
Generation: 61	String: In prinJipio erat V2rbum 200:	Fitness: 3
Generation: 62	String: In prinJipio erat V2rbum 200:	Fitness: 3
Generation: 63	String: In prinJipio erat V2rbum 200:	Fitness: 3
Generation: 64	String: In principio erat ZHrbum 2000	Fitness: 2
Generation: 65	String: In principio erat ZHrbum 2000	Fitness: 2
Generation: 66	String: In principio erat ZHrbum 2000	Fitness: 2
Generation: 67	String: In principio erat ZHrbum 2000	Fitness: 2
Generation: 68	String: In principio erat ZHrbum 2000	Fitness: 2
Generation: 69	String: In principio erat ZHrbum 2000	Fitness: 2
Generation: 70	String: In principio erat ZHrbum 2000	Fitness: 2
Generation: 71	String: In principio erat ZHrbum 2000	Fitness: 2
Generation: 72	String: In principio erat ZHrbum 2000	Fitness: 2
Generation: 73	String: In principio erat ZHrbum 2000	Fitness: 2
Generation: 74	String: In principio erat ZHrbum 2000	Fitness: 2
Generation: 75	String: In principio erat ZHrbum 2000	Fitness: 2
Generation: 76	String: In principio erat ZHrbum 2000	Fitness: 2
Generation: 77	String: In principio erat ZHrbum 2000	Fitness: 2
Generation: 78	String: In principio erat ZHrbum 2000	Fitness: 2
Generation: 79	String: In principio erat ZHrbum 2000	Fitness: 2
Generation: 80	String: In principio erat ZHrbum 2000	Fitness: 2
Generation: 81	String: In principio erat -erbum 2000	Fitness: 1
Generation: 82	String: In principio erat -erbum 2000	Fitness: 1
Generation: 83	String: In principio erat -erbum 2000	Fitness: 1
Generation: 84	String: In principio erat -erbum 2000	Fitness: 1
Generation: 85	String: In principio erat -erbum 2000	Fitness: 1
Generation: 86	String: In principio erat -erbum 2000	Fitness: 1
Generation: 87	String: In principio erat -erbum 2000	Fitness: 1
Generation: 88	String: In principio erat -erbum 2000	Fitness: 1
Generation: 89	String: In principio erat -erbum 2000	Fitness: 1
Generation: 90	String: In principio erat -erbum 2000	Fitness: 1
Generation: 91	String: In principio erat -erbum 2000	Fitness: 1
Generation: 92	String: In principio erat -erbum 2000	Fitness: 1
Generation: 93	String: In principio erat -erbum 2000	Fitness: 1
Generation: 94	String: In principio erat -erbum 2000	Fitness: 1
Generation: 95	String: In principio erat -erbum 2000	Fitness: 1
Generation: 96	String: In principio erat -erbum 2000	Fitness: 1
Generation: 97	String: In principio erat -erbum 2000	Fitness: 1
Generation: 98	String: In principio erat -erbum 2000	Fitness: 1
Generation: 99	String: In principio erat -erbum 2000	Fitness: 1
Generation: 100	String: In principio erat -erbum 2000	Fitness: 1
Generation: 101	String: In principio erat -erbum 2000	Fitness: 1
Generation: 102	String: In principio erat -erbum 2000	Fitness: 1
Generation: 103	String: In principio erat -erbum 2000	Fitness: 1
Generation: 104	String: In principio erat -erbum 2000	Fitness: 1
Generation: 105	String: In principio erat -erbum 2000	Fitness: 1
Generation: 106	String: In principio erat -erbum 2000	Fitness: 1
Generation: 107	String: In principio erat -erbum 2000	Fitness: 1
Generation: 108	String: In principio erat -erbum 2000	Fitness: 1
Generation: 109	String: In principio erat -erbum 2000	Fitness: 1
Generation: 110	String: In principio erat -erbum 2000	Fitness: 1
Generation: 111	String: In principio erat -erbum 2000	Fitness: 1
Generation: 112	String: In principio erat -erbum 2000	Fitness: 1
Generation: 113	String: In principio erat -erbum 2000	Fitness: 1
Generation: 114	String: In principio erat -erbum 2000	Fitness: 1
Generation: 115	String: In principio erat -erbum 2000	Fitness: 1
Generation: 116	String: In principio erat -erbum 2000	Fitness: 1
Generation: 117	String: In principio erat -erbum 2000	Fitness: 1
Generation: 118	String: In principio erat -erbum 2000	Fitness: 1
Generation: 119	String: In principio erat -erbum 2000	Fitness: 1
Generation: 120	String: In principio erat -erbum 2000	Fitness: 1
Generation: 121	String: In principio erat -erbum 2000	Fitness: 1
Generation: 122	String: In principio erat -erbum 2000	Fitness: 1
Generation: 123	String: In principio erat -erbum 2000	Fitness: 1
Generation: 124	String: In principio erat -erbum 2000	Fitness: 1
Generation: 125	String: In principio erat -erbum 2000	Fitness: 1
Generation: 126	String: In principio erat -erbum 2000	Fitness: 1
Generation: 127	String: In principio erat -erbum 2000	Fitness: 1
Generation: 128	String: In principio erat -erbum 2000	Fitness: 1
Generation: 129	String: In principio erat -erbum 2000	Fitness: 1
Generation: 130	String: In principio erat -erbum 2000	Fitness: 1
Generation: 131	String: In principio erat -erbum 2000	Fitness: 1
Generation: 132	String: In principio erat -erbum 2000	Fitness: 1
Generation: 133	String: In principio erat -erbum 2000	Fitness: 1
Generation: 134	String: In principio erat -erbum 2000	Fitness: 1
Generation: 135	String: In principio erat -erbum 2000	Fitness: 1
Generation: 136	String: In principio erat -erbum 2000	Fitness: 1
Generation: 137	String: In principio erat -erbum 2000	Fitness: 1
Generation: 138	String: In principio erat -erbum 2000	Fitness: 1
Generation: 139	String: In principio erat Verbum 2000	Fitness: 0

Зачем использовать генетические алгоритмы?

Генетические алгоритмы способны решать сложные, многомерные проблемы, одновременно просматривая большой пул возможных решений.

Оптимальные результаты

Поскольку генетические алгоритмы основаны на принципе выживания наиболее приспособленных, они ориентированы на поиск оптимальных решений.

Обрабатывает шум и неполные данные

Генетические алгоритмы могут обрабатывать зашумленные и неполные наборы данных, часто создавая приемлемые решения там, где другие методы могут оказаться неэффективными.

Гибкий и адаптируемый

Эти алгоритмы являются гибкими и адаптируемыми, поскольку они не делают никаких предположений о проблемном пространстве и не зависят от проблемной области.

Ограничения генетических алгоритмов

Генетические алгоритмы часто требуют точной настройки таких параметров, как частота мутаций, скорость скрещивания и размер популяции, чтобы получить оптимальные результаты.

Нет гарантии оптимального решения

Хотя генетические алгоритмы хороши в поиске высококачественных решений, они не всегда гарантируют нахождение абсолютно лучшего решения.

Неясное время конвергенции

Время сходимости, время, необходимое алгоритму для достижения оптимального или близкого к оптимальному решения, не является определенным и различается от проблемы к проблеме.

Возможность преждевременной конвергенции

Генетические алгоритмы могут застрять на неоптимальных решениях — ситуация, известная как преждевременная сходимость.

Сферы применения генетических алгоритмов

Машинное обучение

Генетические алгоритмы используются в машинном обучении для оптимизации алгоритмов обучения , тем самым улучшая производительность модели.

Распознавание изображений

При распознавании изображений генетические алгоритмы играют ключевую роль в выборе признаков, тем самым повышая точность распознавания.

Инженерный дизайн

Генетические алгоритмы используются для оптимизации и предоставления надежных решений в инженерном проектировании. Способность быстро оценивать и генерировать потенциальные решения делает их ценными инструментами в этой области.

Маршрутизация трафика и поставок

Генетические алгоритмы были приняты многими торговыми компаниями для эффективного решения проблем с движением транспорта и маршрутизацией грузов. Они помогают сэкономить время и деньги за счет поиска оптимальных маршрутов.

Робототехника

Генетические алгоритмы играют важную роль в робототехнике. Их используют для создания обучающихся роботов, которые могут выполнять такие задачи, как приготовление еды или стирка. Имитируя процесс естественной эволюции, генетические алгоритмы помогают роботам вести себя больше как люди.

Colab paid products - Cancel contracts here