Форум Flasher.ru
Ближайшие курсы в Школе RealTime
Список интенсивных курсов: [см.]  
  
Специальные предложения: [см.]  
  
 
Блоги Правила Справка Пользователи Календарь Поиск рулит! Сообщения за день Все разделы прочитаны
 

Вернуться   Форум Flasher.ru > Блоги > ZackMercury

Оценить эту запись

Генетический алгоритм. Часть 2 - Класс Entity

Запись от ZackMercury размещена 15.06.2017 в 22:16

Entity.as

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

Опишем движения:
  • w - up
  • a - left
  • s - down
  • d - right
  • e - top right
  • q - top left
  • z - bottom left
  • c - bottom right
Основные необходимые свойства.

Так как наша сущность имеет графическое представление и должна двигаться по экрану, базовый класс нашей сущности будет Sprite.

Код AS3:
public class Entity extends Sprite
{
	public static const NUCLEOBASES:String = "wasdqezc"; //возможные нуклеотиды(символы DNA) для мутации
 
	public var DNA:String; //оставим возможность доставать DNA снаружи класса, на всякий случай
}
Теперь вспомним, какие ещё параметры необходимы нашей сущности. В константы допишем:

Код AS3:
public static const MUTATION_RATE:Number = 0.01;
В переменные:

Код AS3:
public var fitness:Number;
Основные необходимые методы.

Ну что-ж, выходит - всё?
Давайте теперь перейдём к конструктору.

Код AS3:
public function Entity(DNA:String = "sdsdesaaasdewasdaedsaeas") //не будем заморачиваться генерацией случайного DNA, всё равно он будет постоянно мутировать, и уж точно он не окажется сразу у цели
{
	super();
	this.DNA = DNA;
	addEventListener(Event.ADDED_TO_STAGE, init);
}
Что же произойдёт при добавлении на сцену?
Единственное, что нам нужно сделать - нарисовать нашу сущность.

Код AS3:
private function draw():void
{
	graphics.beginFill(0xFFCC22);
	graphics.moveTo(10, 0);
	graphics.lineTo(-10, -10);
	graphics.lineTo(-10, 10);
	graphics.lineTo(10, 0); //ну да, а чего вы ожидали? треугольника будет вполне достаточно для демонстрации
	graphics.endFill();
}
Код AS3:
private function init(e:Event):void 
{
	removeEventListener(Event.ADDED_TO_STAGE, init);
	draw();
}
Теперь каким-то магическим способом нам необходимо заставить сущность выполнять команды из DNA.
Для этого нужна ещё пара переменных.

Код AS3:
private var lifetime:Number = 0;
private var velocity:Point = new Point(0, 0);
Ну и громадный метод, который будет вызываться перед рендером каждого кадра снаружи класса:

Код AS3:
public function update(deltaS:Number):void
{
	lifetime += deltaS; //здесь мы прибавляем к времени, которое прожила наша особь, разницу между кадрами(иногда не только её :D, дальше поймёте, почему)
	if (lifetime >= DNA.length) return; //если время жизни больше, чем прописано в нашей библии - всё, вызываем сердечный приступ
	switch(DNA.charAt(lifetime))
	{
		case "w":
			velocity.x = 0;
			velocity.y = -100; //ну да, именно так тру программисты задают вектор скорости
			break;
		case "a":
			velocity.x = -100;
			velocity.y = 0;
			break;
		case "s":
			velocity.x = 0;
			velocity.y = 100;
			break;
		case "d":
			velocity.x = 100;
			velocity.y = 0;
			break;
		case "q":
			velocity.x = -1;
			velocity.y = -1;
			velocity.normalize(100); //такого поворота вы точно не ожидали?
			break;
		case "e":
			velocity.x = 1;
			velocity.y = -1;
			velocity.normalize(100); //почему это так смешно?
			break;
		case "z":
			velocity.x = -1;
			velocity.y = 1;
			velocity.normalize(100); //говорят, в жизни надо всё попробовать
			break;
		case "c":
			velocity.x = 1;
			velocity.y = 1;
			velocity.normalize(100); //нет, я не буду использовать константы-вектора, посчитанные по углам
			break;
	}
 
	this.rotation = Math.atan2(velocity.y, velocity.x)/Math.PI*180;
	x += velocity.x * deltaS;
	y += velocity.y * deltaS;
}
Из кода выше ясно одно: мне не стоит торопиться, когда я пишу код для /*в идеале - красиво написанной*/ демонстрации работы алгоритма.
Ещё ясно то, что скорость нашей особи равна 100 пикселей в секунду. /*у нас всё почти по системе Си*/

Теперь займёмся функционалом собственно самого генетического алгоритма:

Код AS3:
public function clone():Entity
{
	return new Entity(this.DNA);
}
 
public function mutate():void
{
	for (var i:int = 0; i < DNA.length; i ++)
		if (Math.random() < MUTATION_RATE)
			DNA = DNA.substr(0, i) + NUCLEOBASES.charAt(int(Math.random() * NUCLEOBASES.length)) + DNA.substr(i + 1);
}
Как должно быть /*не*/понятно из кода выше, метод clone возвращает объект с идентичной DNA, а метод mutate проходится по символам и с вероятностью MUTATION_RATE(0.01) перезаписывает текущий символ любым случайным из даного алфавита нуклеотидов(символов DNA).

Код AS3:
public function crossbreed(e:Entity):void
{
	if (Math.random() < 0.5)
		DNA = DNA.substr(0, int(DNA.length / 2)) + e.DNA.substr(int(e.DNA.length / 2));
	else
		DNA = e.DNA.substr(0, int(e.DNA.length / 2)) + DNA.substr(int(DNA.length / 2));
}
В методе скрещивания мы изменяем текущую особь, смешивая её DNA описанным в теории образом.
В следующий раз возьмёмся за класс Population.

Листинг полного кода класса Entity.

Код AS3:
package com.zackmercury.test 
{
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.geom.Point;
 
	/**
	 * ...
	 * @author ZackMercury
	 */
	public class Entity extends Sprite 
	{
		public static const MUTATION_RATE:Number = 0.01;
		public static const NUCLEOBASES:String = "wasdqezc";
		/* w - up
		 * a - left
		 * s - down
		 * d - right
		 * e - top right
		 * q - top left
		 * z - bottom left
		 * c - bottom right
		 * */
 
		public var DNA:String;
		public var fitness:Number;
		public var lifetime:Number = 0;
		private var velocity:Point = new Point(0, 0);
 
		public function Entity(DNA:String = "sdsdesaaasdewasdaedsaeas") 
		{
			super();
			this.DNA = DNA;
			addEventListener(Event.ADDED_TO_STAGE, init);
		}
 
		public function clone():Entity
		{
			return new Entity(this.DNA);
		}
 
		public function mutate():void
		{
			for (var i:int = 0; i < DNA.length; i ++)
				if (Math.random() < MUTATION_RATE)
					DNA = DNA.substr(0, i) + NUCLEOBASES.charAt(int(Math.random() * NUCLEOBASES.length)) + DNA.substr(i + 1);
		}
 
		public function crossbreed(e:Entity):void
		{
			if (Math.random() < 0.5)
				DNA = DNA.substr(0, int(DNA.length / 2)) + e.DNA.substr(int(e.DNA.length / 2));
			else
				DNA = e.DNA.substr(0, int(e.DNA.length / 2)) + DNA.substr(int(DNA.length / 2));
		}
 
		private function draw():void
		{
			graphics.beginFill(0xFFCC22);
			graphics.moveTo(10, 0);
			graphics.lineTo(-10, -10);
			graphics.lineTo(-10, 10);
			graphics.lineTo(10, 0);
		}
 
		private function init(e:Event):void 
		{
			removeEventListener(Event.ADDED_TO_STAGE, init);
			draw();
		}
 
		public function update(deltaS:Number):void
		{
			lifetime += deltaS;
			if (lifetime >= DNA.length) return;
			switch(DNA.charAt(lifetime))
			{
				case "w":
					velocity.x = 0;
					velocity.y = -100;
					break;
				case "a":
					velocity.x = -100;
					velocity.y = 0;
					break;
				case "s":
					velocity.x = 0;
					velocity.y = 100;
					break;
				case "d":
					velocity.x = 100;
					velocity.y = 0;
					break;
				case "q":
					velocity.x = -1;
					velocity.y = -1;
					velocity.normalize(100);
					break;
				case "e":
					velocity.x = 1;
					velocity.y = -1;
					velocity.normalize(100);
					break;
				case "z":
					velocity.x = -1;
					velocity.y = 1;
					velocity.normalize(100);
					break;
				case "c":
					velocity.x = 1;
					velocity.y = 1;
					velocity.normalize(100);
					break;
			}
 
			this.rotation = Math.atan2(velocity.y, velocity.x)/Math.PI*180;
			x += velocity.x * deltaS;
			y += velocity.y * deltaS;
		}
	}
}
Всего комментариев 13

Комментарии

Старый 19.06.2017 19:38 caseyryan вне форума
caseyryan
 
Аватар для caseyryan
А как она развивается? Из вышеуказанного кода, так и не увидел где особь улушается со временем. То есть получается, что, грубо говоря, по воле случая у собаки могут вырасти плавники. Нужны они ей? Да хз, но прикольно же)
Если бы эволюция шла по пути рандома, то скорее всего мы бы сейчас по деревьям лазали, но, возможно, обладали хвостами как у ящерицы и копытами

Я лично себе представлял алгоритм как-то иначе. Как минимум умеющим запоминать хорошие достижения и избавляться от неверных / ненужных, и на основе этого строящим днк
Старый 19.06.2017 23:07 ZackMercury вне форума
ZackMercury
 
Аватар для ZackMercury
caseyryan, так мы восходим к обезьянам, которые лазали по деревьям, и обладали хвостами, как у обезьяны. У некоторых людей возникает такой атавизм. Вряд ли у собаки вырастут плавники, так как предок слишком дальний, но у людей бывают хвосты и шерсть на всём теле.
Да мы сейчас вполне в состоянии лазать по деревьям, посмотри на людей, которые паркуром занимаются, там все возможности человека задействованы.

Насчёт окончания, последняя статья уже выложена, ждёт одобрения. (не пойму, к чему оно вообще в блогах)

Проблема эволюции как раз в том, что у собаки не могут вырасти плавники в связи дальности собаки от её предков рыб, от которых они произошли.
Если ты имел в виду атавизмы, конечно.
Если ты имел в виду, что рандом может привести к плавникам у собаки - это полнейшая чушь в связи с тем, что эволюция происходит настолько плавно, что если бы товарищ Дарвин и его коллеги не имели возможности лицезреть всё многообразие живой природы, им не пришла бы и в голову мысль, что один вид может происходить от другого. То генетическое разнообразие людей, которое мы сейчас имеем подарено миллионами лет разделения племён и путешествия в отдалённые уголки планеты. Отбирались самые привлекательные, сильные и смекалистые.
К примеру, ты сейчас здесь по той счастливой случайности, что твои предки получили полезную мутацию.

Нет, алгоритм не избавляется от неверных и ненужных мутаций, об этом позаботится природа, такие особи либо не достигают достаточных результатов, чтобы быть выбранными, либо умирают, врезаясь в препятствия.
Старый 19.06.2017 23:44 ZackMercury вне форума
ZackMercury
 
Аватар для ZackMercury
Впрочем это не то, как работает эволюция на самом деле, но я говорил, что это очень сильно упрощённая биологическая идея. На симуляцию эволюции как она есть в физическом мире вычислений современных компьютеров не хватит.

Серия закончена, и теперь я планирую рассказать кое-что о нейронных сетях.
Там суть та же - биологическая модель очень сильно упрощена до того, что от неё остаётся только элементарный принцип работы.
Старый 20.06.2017 06:42 caseyryan вне форума
caseyryan
 
Аватар для caseyryan
Я не верю в теорию эволюции, и тем более не верю, что люди произошли от обезьян.
Но сейчас не об этом. Про плавники у собаки и тому подобное, я утрировал. Вопрос был в том, где в твоем коде происходит запоминание удачных признаков и отсеивание неудачных? И на чем это основано? Пока я здесь вижу только случайные числа, что, конечно же, не есть самый удачный способ селекции)
Старый 20.06.2017 11:03 ZackMercury вне форума
ZackMercury
 
Аватар для ZackMercury
caseyryan, в реальности селекция происходит именно так. Даже у генетически больных людей есть шанс дать потомство. В этом мире царит энтропия, всё основано на вероятностях. Нет никаких запоминаний удачных признаков в конкретно эволюционных механизмах, это скорее всего происходит при выборе партнёра для потомства в голове особи.
Старый 20.06.2017 18:46 Ёлочка вне форума
Ёлочка
 
Аватар для Ёлочка
ZackMercury, а можно нейронную сеть совместить с генетическим алгоритмом, чтобы нейронная сеть улучшала сама себя?
Старый 20.06.2017 19:29 ZackMercury вне форума
ZackMercury
 
Аватар для ZackMercury
Да, и об этом я собираюсь рассказать в будущем. Вот тут можно почитать бумаги из MIT на эту тему:
http://nn.cs.utexas.edu/downloads/pa...anley.ec02.pdf

Это называется NEAT(Neuroevolution through augmenting topologies).
Собственно, чтобы разобраться в этой теме я и решил начать цикл статей. И начал с генетического алгоритма.
Старый 20.06.2017 19:40 Ёлочка вне форума
Ёлочка
 
Аватар для Ёлочка
Класс-класс-класс.
Старый 20.06.2017 20:46 caseyryan вне форума
caseyryan
 
Аватар для caseyryan
Цитата:
caseyryan, в реальности селекция происходит именно так. Даже у генетически больных людей есть шанс дать потомство. В этом мире царит энтропия, всё основано на вероятностях. Нет никаких запоминаний удачных признаков в конкретно эволюционных механизмах, это скорее всего происходит при выборе партнёра для потомства в голове особи.
То то и оно. Если все будет только на рендоме, то не будет никакой эволюции. Нужны были рыбе ноги, чтобы выйти на сушу - они у нее выросли. Это если верить в теорию эволюции. Но если это всё будет только на рандоме, а не под воздействием каких-то факторов (как то необходимость добывать пропитание на суше), то вся эта теория затрещит по швам, потому что ноги у рыбы не вырастут никогда. Не будет планомерного их развития, а будут лишь какие-то недоразумения время от времени.
Плюс к тому, зачем тебе имитировать реальный (неидеальный) мир, когда в программе можно создавать идеальный?
Старый 20.06.2017 21:09 ZackMercury вне форума
ZackMercury
 
Аватар для ZackMercury
Никогда не знаешь, дети какой особи окажутся ближе к цели Вполне возможно, что реальная эволюция - наиболее качественная.
К тому же, подумай о том, что если ты будешь повторять "полезные" мутации по всей цепочке, твоя особь окажется по ту сторону цели. Это ведь не то, что нам нужно, верно? Хотя возможен вариант повторять их, пока не начнёшь отдаляться от цели. Но тем не менее, это всё равно не совсем то, что нужно.
Обновил(-а) ZackMercury 21.06.2017 в 09:47
Старый 21.06.2017 11:55 caseyryan вне форума
caseyryan
 
Аватар для caseyryan
Так задача-то алгоритма - научиться что-то делать, а не просто в случайном порядке мутировать. Иначе какой от него толк?
Старый 21.06.2017 11:58 ZackMercury вне форума
ZackMercury
 
Аватар для ZackMercury
Научиться что-то делать - это задача нейронных сетей, а не генетического алгоритма.
Старый 21.06.2017 12:00 Ёлочка вне форума
Ёлочка
 
Аватар для Ёлочка
caseyryan, ты неправильно понимаешь теорию эволюции, поэтому и "не веришь" в нее. Теория эволюции - это не рандом. Согласно теории эволюции у человека не может вдруг вырасти пара копыт. Основа эволюционных процессов - это естественный отбор.

Чтобы правильно понять, что такое естественный отбор и как он работает в контексте эволюции, рассмотрим для начала искусственный отбор, именуемый так же "селекцией". Как, например, выводят новые породы собак или новые сорта овощей? Очень просто! Скрещивают пару десятков пар собак или пару грядок томатов. Затем отбирают потомство по необходимым признакам, например, самые короткие лапки или самые красные плоды томатов. После этого "хорошее" потомство и урожай скрещивают дальше, а то, что "не подошло", "выбрасывают". Таким образом через несколько поколений получается такса или красный помидор.

Естественный отбор - это абсолютно тоже самое! Только в качестве селекционера выступает не человек, а окружающая среда, природа. Условия окружающей среды "позволяют" выживать и давать потомство наиболее приспособленным особям и "убивают" наименее приспособленных. Таким образом и протекает эволюция. В эволюции нет никакой случайности. Всё зависит от окружающей среды.

И пример генетического алгоритма ZackMercury совершенно правильный. В качестве "природы-селекционера" в его примере выступает точка, до которой нужно добраться. Эта точка и выполняет функцию естественного отбора. Те объекты, которые плохо добираются до точки, погибают, а те, которые добираются хорошо, плодятся и размножаются, перенося свой "генный код".

Надеюсь, это понятное и доступное для восприятия объяснение поможет тебе уверовать в силу могущественной и вездесущей теории эволюции!

ZackMercury, давай уже скорее пиши про нейронные сети! Я хочу как можно скорее скрестить их с генетическим алгоритмом и захватить этот мир!
 

 


Часовой пояс GMT +4, время: 18:48.


Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.