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

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

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

Генетический алгоритм. Часть 1 - Теория

Запись от ZackMercury размещена 14.06.2017 в 21:42

Генетический алгоритм
  1. Рассчитать соответствие(fitness) каждой особи поставленной задаче, и перевести его в число, которое будет возрастать по мере приближения к цели.
  2. Выбрать из населения 2 особи таким образом, чтобы вероятность выпадения каждого зависела от его соответствия(fitness) поставленной цели.
  3. Скрестить их, так, чтобы половина DNA была от мамы, половина от папы(что от чего выбирается с вероятностью 0.5)
  4. Вызвать случайные мутации в их DNA. (Найлучшим образом работает вероятность мутации для каждого символа - 0.01)

1. Рассчитывание соответствия

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

Название: Снимок.JPG
Просмотров: 288

Размер: 20.0 Кб

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

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

2. Селекция

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

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

3. Скрещивание

Как уже писалось выше, процесс скрещивания представляет собой смешивание DNA двух особей, которые были отобраны для получения нового поколения. При этом скрещивание происходит случайным образом, взяв либо половину DNA папы + половину DNA мамы, либо половину DNA мамы + половину 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));
}
4. Мутация

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

Код AS3:
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);
}
Не обязательно DNA состоит из направлений, он также может состоять из операторов и значений, что угодно, и в том числе веса нейронов нейронной сети. В таком случае весам присваивается случайное значение, но об этом позже.
Всего комментариев 0

Комментарии

 

 


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


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