GotAI.NET

Форум: Проблемы искусственного интеллекта

 

Регистрация | Вход

 Все темы | Новая тема Стр.1 (1)   Поиск:  
 Автор Тема: Вопрос по реализации генетического алгоритма
ilkz
Сообщений: 20
Вопрос по реализации генетического алгоритма
Добавлено: 26 ноя 07 21:44
Всем доброго времени суток!
Уже достаточно давно изучаю материалы по ГА, но написать свою реализацию решился только сейчас )))
Реализация написана на Матлабе.
В качестве задачи взял классическую задачу коммивояжера.

Начальные условия такие:
- сколько-то городов (задается);
- один коммивояжер;
- максимальная дистанция между двумя соседними городами (для генерации начальной популяции);
- размер эволюции (количество поколений);
- количество особей;
- коммивояжер каждый город может посетить только один раз;

Генная структура хромосомы такая: (далее все примеры будут для 5 городов)
X X X X X, где Х - номер города, например: 1 4 2 3 5. Таким образом, коммивояжер, выйдя и 1 города, в него же и вернется. Хромосомы генерируются с учетом условия однократного посещения каждого города, так что повторов в генах нет.

Сразу оговорюсь что пока решил гены не кодировать в двоичный формат.

Однако, при написании кроссовера столкнулся с интересной (для меня на данном этапе ) проблемой. Если, например, два родителя имеют хромосомы:
X1 = 3 4 2 1 5;
X2 = 5 2 1 4 5;
И если точка разрыва хромосомы пришлась так, что для формирования потомка берутся гены:
X1(1,2) и X2(3,4,5), то потомок будет выглядеть следующим образом:
Y = 3 4 1 4 5.
Как видим, в хромосоме потомка появляется дублирующий ген (со значением 4). Применительно к пути коммивояжера это некорректно, так как получается, что он дважды посетит город с номером 4, что несоответствует условиям задачи.

Я сделал так, что сейчас повторные гены (в слуае, если они есть, конечно же) заменяются так, чтобы в хромосоме потомка не было дублей. Таким образом, хромосома Y в данном примере будет выглядеть так:
Y = 3 4 1 2 5.

Тут у меня возникает вопрос. Так как я пока не храню гены в двоичном формате, а работаю сразу с реальными числами, то правильно ли делать так как делаю я (я имею в виду кроссовер)? И даже, если кодировать в бин, то все равно могут появляться дубли...

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

И вопрос третий. Я пока не очень понял следующий момент. Если, допустим, было 50 родителей, и после скрещивания каждой пары появляется ОДИН потомок, то получается, что очень быстро уменьшается объем популяций. В моем случае это выливается в то, что фитнесс-функция не успевает максимизироваться до приемлемого (по результатам опытов) значения. Так что сейчас я порождаю ДВУХ потомков, обеспечивая тем самым поддержание численности особей на уровне первоначальной популяции. Благодаря этому фитнесс-функция в конце всей эволюции у всех конечных особей получается примерно одинакова (различается в числах после запятой). А теперь вопрос: существуют ли какие-то критерии выбора количества потомков? Или какие-то правила?

Заранее спасибо всем за ответы!!!
[Ответ][Цитата]
daner
Сообщений: 4593
На: Вопрос по реализации генетического алгоритма
Добавлено: 27 ноя 07 15:46
мне кажется вы не должны придерживаться того что геном включает только по одному узлу.
Т.е. ваша фитнес функция, просто должна давать таким генам меньшую оценку и все.
сразу много проблем убирается.
Да на счет размножения. Что то я не увидел , что где у вас особи с более высокой фитнес функцией получают вероятность на скрещивание выше остальных?!
а то что они по 2 ребенка рожают, так это не плохо. Это (имхо) даже правильно.

Кстати, я уже писал это про ИНС. Обычно в книгах, есть только конечные результаты (типа делай так и делай так) или теория (по которой сам догадайся как делать).
Форум же как раз могбы восполнить промежуточное звено.
Т.е. мелкии эксперименты с уже изветными технологиями, могли бы быть очен и очень полезны.
Вот вы бы взяли и провели полноценное исследование ГА. Т.е. попробовали бы так , попробовали бы иначе. Записали бы все в деталях, как экспер. проводился, какие результаты и все такое. И все бы на это посмотретли!!! это был бы очень ценный материал.
[Ответ][Цитата]
ilkz
Сообщений: 20
На: Вопрос по реализации генетического алгоритма
Добавлено: 27 ноя 07 22:06
Daner, спасибо за рекомендации! Постараюсь их учесть максимально полно!

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

Когда писал первый пост, не упомянул о некоторых важных деталях. А именно, стратегии отбора. Я решил выбрать рулеточный отбор. Реализацию сделал на основе рулеточного отбора из пакета gatool в Матлабе. Там он работает примерно следующим образом:
есть массив вероятностей (expectations по-ихнему (ожидания?)) для каждой особи.

Разметка колеса осуществляется следующим образом:
wheel=cumsum(expectations)/numParents;

функция cumsum() вычисляет кумулятивную сумму для каждого элемента данного ей на вход массива. Т.е, если был входной массив:
in=[1 2 3 4 5], то результатом работы функции out=cumsum(in) будет:
out=[1 3 6 10 15].

Вроде бы все понятно, однако лично мне пока ни фига не понятно вот что:
Если во входном массиве было несколько элементов с одинаковыми значениями, тогда эта функция с точки зрения разметки колеса даст неверные результаты, ведь особям с одинаковыми вероятностями будут соответствовать разные по угловым размерам (ширине) сектора. Это же неправильно!
Однако, с именно такой разметкой колеса алгоритм работал, и более-менее терпимо.
Но все же меня это напрягло и я решил сделать по-своему - так чтобы особям с ОДИНАКОВОЙ вероятностью соответствовали сектора ОДИНАКОВОЙ ширины (соответственно, таковых может быть несколько). Но, блин, сделав это, увидел что алгоритм стал работать из рук вон плохо...

Тогда я пошел другим путем, решив сменить алгоритм отбора. Реализовал турнирный. Он оказался предельно простым и показал отличные результаты. На нем пока и остановился.

DANER писал: а то что они по 2 ребенка рожают, так это не плохо.
У меня вопрос: так ведь тогда объем популяции будет поддерживаться на одном уровне, а это будет стоить очень дорого с точки зрения времени вычислений. Возникает вопрос об определении момента остановки ГА.

Чего-то я пока недопонимаю .
[Ответ][Цитата]
daner
Сообщений: 4593
На: Вопрос по реализации генетического алгоритма
Добавлено: 28 ноя 07 3:42
а размер самой популяции и не должен меняться.
а останавливаться надо тогда когда особь с наибольшей фитнес функцией подошла к ответу в радиусе определенной ошибки.
Ну т.е. если говорить не об TSP (коммивояжере) а о Гамельтоновском круге (тоже самое, только все переходы равны 1, т.е. нет необходимости минимум искать), то можно сказать, что нас удовлетворил бы ответ, с одним повтором узла... к примеру. Поверьте, с 20-30 узлами, это был бы совсем не плохой ответ. Я уже не говорю об 100 узлов.

Кстати, когда вы употребляете названия алгоритмов... было бы не плохо хотя бы кратко их формулы приводить, ну или суть. А то мало ли всяких алгоритмов, всэ названий и не упомнишь, особенно если не сталкиваться с этим постоянно.
А вообще, в правильном направлении. Как я уже говорил, это полезные для всех эксперименты. Хотелось бы конечно еще ваши мысли услышать по поводу, а почему это лучше, чем то. Я понимаю, что это не точно, но хоть какое-то ощущение у вас все равно возникает.
[Ответ][Цитата]
Вася
Сообщений: 180
На: Вопрос по реализации генетического алгоритма
Добавлено: 29 ноя 07 2:37
В этой задачке, на мой взгляд, рекомбинацию нет причин использовать, поскольку простейший её вариант приводит к недопустимым по условию задачи решениям. Отбрасывать такие решения не эффективно, поскольку при увеличении количества пунктов вероятность получить при скрещивании "плохие" решения быстро стремится к единице.

Зато здесь вполне достаточно бесполого размножения и простых мутаций. Такова специфика задачи. Общая формула мутации - n1 случайных перестановок n2 случайно выбранных пунктов, n1>0, n2>1. То есть, выбираем, к примеру, три пункта и вразнобой их ставим на те же места.

Размножение делаем так: (m - величина популяции)
Каждая особь производит k копий с мутациями, оставаясь в популяции. Получается популяция величины (k+1)*m. Упорядочиваем её по длине пути, оставляем m кратчайших.

Начальная популяция создаётся случайно - равномерное покрываем пространство решений точками вариантов. Смена поколений позволяет им "стекаться" к локальным оптимумам. Широта "ощупывания" пространства пропорциональна n1*n2.

Хорошо, если для каждой мутации числа n1 и n2 выбираются из диапазона от минимальных до максимальных значений, чтоб иметь широту и точность поиска одновременно. А максимальные значения должны расти вместе с числами m и k, которые желательно увеличивать с увеличением числа пунктов в условии задачи.

Условие прекращения поиска - лучшее решение не улучшается в течение числа поколений, вдвое-втрое больше номера поколения, на котором оно было получено.

Ничего не забыл?
[Ответ][Цитата]
Ko.B
Сообщений: 1549
.
Добавлено: 25 июн 18 5:50
Изменено: 28 июн 18 23:17
.
[Ответ][Цитата]
 Стр.1 (1)