Генетический алгоритм. Часть 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.
public class Entity extends Sprite { public static const NUCLEOBASES:String = "wasdqezc"; //возможные нуклеотиды(символы DNA) для мутации public var DNA:String; //оставим возможность доставать DNA снаружи класса, на всякий случай }
В переменные:
Основные необходимые методы.
Ну что-ж, выходит - всё?
Давайте теперь перейдём к конструктору.
public function Entity(DNA:String = "sdsdesaaasdewasdaedsaeas") //не будем заморачиваться генерацией случайного DNA, всё равно он будет постоянно мутировать, и уж точно он не окажется сразу у цели { super(); this.DNA = DNA; addEventListener(Event.ADDED_TO_STAGE, init); }
Единственное, что нам нужно сделать - нарисовать нашу сущность.
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(); }
private function init(e:Event):void { removeEventListener(Event.ADDED_TO_STAGE, init); draw(); }
Для этого нужна ещё пара переменных.
Ну и громадный метод, который будет вызываться перед рендером каждого кадра снаружи класса:
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 пикселей в секунду. /*у нас всё почти по системе Си*/
Теперь займёмся функционалом собственно самого генетического алгоритма:
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)); }
В следующий раз возьмёмся за класс Population.
Листинг полного кода класса Entity.
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
Комментарии
20.06.2017 18:46 | |
ZackMercury, а можно нейронную сеть совместить с генетическим алгоритмом, чтобы нейронная сеть улучшала сама себя?
|
20.06.2017 19:29 | |
Да, и об этом я собираюсь рассказать в будущем. Вот тут можно почитать бумаги из MIT на эту тему:
http://nn.cs.utexas.edu/downloads/pa...anley.ec02.pdf Это называется NEAT(Neuroevolution through augmenting topologies). Собственно, чтобы разобраться в этой теме я и решил начать цикл статей. И начал с генетического алгоритма. |
20.06.2017 19:40 | |
Класс-класс-класс.
|
20.06.2017 21:09 | |
Никогда не знаешь, дети какой особи окажутся ближе к цели Вполне возможно, что реальная эволюция - наиболее качественная.
К тому же, подумай о том, что если ты будешь повторять "полезные" мутации по всей цепочке, твоя особь окажется по ту сторону цели. Это ведь не то, что нам нужно, верно? Хотя возможен вариант повторять их, пока не начнёшь отдаляться от цели. Но тем не менее, это всё равно не совсем то, что нужно. |
|
Обновил(-а) ZackMercury 21.06.2017 в 09:47
|
21.06.2017 11:55 | |
Так задача-то алгоритма - научиться что-то делать, а не просто в случайном порядке мутировать. Иначе какой от него толк?
|
21.06.2017 11:58 | |
Научиться что-то делать - это задача нейронных сетей, а не генетического алгоритма.
|
Последние записи от ZackMercury
- Вывод формулы для бесконечного цикла. (11.01.2019)
- Как заменить цикл на формулу. (10.01.2019)
- Конечные и бесконечные суммы, Ч. 1 (08.01.2019)
- Как легко запомнить тригонометрические функции (07.01.2019)
- Движение по треугольнику, квадрату, пентагону, хексагону, ... (05.01.2019)