Реализация кроссовера в генетическом алгоритме

Для неординарных вопросов. Если вы опытный программист, попавший в трудную ситуацию, — вам сюда.

Модератор: gaidar

Правила форума
Этот раздел не предназначен для того, чтобы вы адресовали свою проблему профессионалам.
Этот раздел предназначен для профессионалов, которые столкнулись с проблемой и не могут решить ее самостоятельно.
Если вы считаете себя профессионалом, а свою проблему сложной — вам сюда.
Если модератор посчитает, что вы ошиблись, то на первый раз он перенесет ваше сообщение в основной раздел без последствий для автора. Во второй раз тема будет закрыта, а автору будет выписано нарушение. В третий раз автор будет забанен.
xenomorph
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 508
Зарегистрирован: 18.04.2004 (Вс) 11:41
Откуда: это не важно - на сегодня у меня есть алиби ...

Реализация кроссовера в генетическом алгоритме

Сообщение xenomorph » 27.12.2011 (Вт) 13:38

Доброго [localtime], уважаемое сообщество!

Полный тайтл: Реализация кроссовера в генетическом алгоритме при разных типах переменных в генотипе.

Преамбула:

Разрабатываю систему которая обрабатывает тексты.
Есть в ней основная функция F(cls_Parameters). Возвращает она dbl_Result as Double в диапазоне от 0 до 1 включительно (например 0,350098). Предвидя вопрос - функция такая как надо, т.е. она даёт однозначный и точный результат.
Время работы функции 20 секунд ровно (быстрее никак).
cls_Parameters представляет из себя следующиё класс [в квадратных скобках я обозначил мин.\макс. возможные колебания значений переменных внутри класса]:

Код: Выделить всё
    Public Class cls_Parameters
        'clustering related:
        Dim i_iClusterMinLength_Chars As Integer = 0-20000
        Dim i_iClusterMinSeqSimFpsCount As Integer = 0-2000
        Dim i_iClusteringDistance As Integer = 0-5000
        'cls_Text load\parse related:
        Dim b_iSortFPsBeforeHashing As Boolean = True [ture-false]
        Dim i_iuFP_Step As Integer = 0 - 200
        Dim i_iuFP_Lenght As Integer = 1 - 100
        Dim b_iRemovePuncSigns As Boolean = [ture-false]
        Dim b_iDoStemming As Boolean = [ture-false]
    End Class


Проблема: существует такая комбинация значений этого класса, которая даёт максимальный результат F(cls_Parameters) = Xmax (какое именно не знаю но в пределах от 0 до 1(реально-идеальный вариант - 0,97)).
Очевидное решение: перебор всех возможных комбинаций т.е.:
Количество итераций F = макс_диапазон_параметра * n параметров
Количество итераций F = 20000*2000*5000*2*200*99*2*2 = 3,168e+16
3,168e+16 * 20 секунд на итерацию = *печалька*.

В качестве решения проблемы я смотрю в сторону генетического алгоритма.
[url]http://ru.wikipedia.org/wiki/Генетический_алгоритм[/url]

Опыта нет, но "ехать надо". Насколько мог, настолько я матчасть изучил, но прошу прощения если что-нить накосячу.
Как реализовать кросс-овер (с мутацией всё ясно) по различным типам переменных?

Т.е. я себе переставляю как сделать мутацию по integer-ам, то вот что делать с парой boolean-integer, не очень :-(.
Одна идея это слить всё в один байтовый вектор, и реализовывать всё на на integer. Т.е.:

Вектор особи: 00000-0000-0000-0-000-000-0-0

(5 байт а 1 переменную, 4 байта на 2-ую, 5-на третью и т.д.)

Но чувствую 6-м чувством, что надо по-другому - например не выполнять кросовер для boolean типов с Integer, а только boolean c boolean.

если реализовать кроссовер булевых то это просто:

до кроссовера: 0-1-0 :: 0-1-0
после кроссовера: 0-0-1 :: 1-0-0

как быть integer[0-20000] и boolean[ture-false]?

Есть какие-нибудь идеи?

Огромное спасибо за советы заранее!
... Dpkjvfnm dc`xnj itdtkbnmcz, f tckb yt itdtkbnmcz hfcitdtkbnm b dpkjvfnm !!! ...

xenomorph
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 508
Зарегистрирован: 18.04.2004 (Вс) 11:41
Откуда: это не важно - на сегодня у меня есть алиби ...

Re: Реализация кроссовера в генетическом алгоритме

Сообщение xenomorph » 27.12.2011 (Вт) 13:58

Дополнение: проблема глубже чем оказалось:

Поизучав: http://www.codeproject.com/KB/recipes/b ... fr=1#xx0xx

Наткнулся на замечание к автору:

I was looking for a Genetic Algorithm written in C#, but this is not a GA.

The mutation works, but crossover is a total lark. For GAs to work on real problems, you need to invoke a true stochastic process combined with implicit parallelism. This is acheived by reducing the genome to a bit string, which is not done here. To perform a proper real-valued GA there is some good results with interpolating in the crossover, but this is better known as Differential Evolution.


Ответ автора:

I'm not entirely sure what your point is. If you think that genomes should have a binary representation, then I really suggest that you read: Field, P. (1995): A Multary Theory for Genetic Algorithms: Unifying Binary and Nonbinary Problem Representations [^]
Regards,

Barry


Ремарка:

I did not say that a GA must have a binary encoding but without reducing each of the variables to some smaller building-blocks (as is the case with binary encoding or even the multary encoding in the suggested dissertation), your GA will not work effectively.

You give an example of a two-variable problem, max f(x, y).
Since crossover only happens between x and y then you will only be able to create solutions that have any of the random values of x and y created in the initial population. You are completely relying on mutation to move from the initial populations values. You might as well systematically check every x in the initial population with every y and return the pair with the highest value.

As I stated, you may forego the low-level building block approach but you would need to introduce interpolation and extrapolation crossover operators ala differential evolution.

I realize this may sound like some rant with a misdirected or ulterior motive. My reason is simply that this is the first page that google offers for a search for [genetic algorithm C#]. I am concerned people are trying this on harder problems and not getting satisfactory results.


на что автор ушёл от дальнейшей дискуссии сославшись что это по первая работа по ГА.

Но мою проблему цепляет. Пока думаю...
Кто-нить подскажет что именно имеется ввиду под "interpolating in the crossover" в этом контексте?
... Dpkjvfnm dc`xnj itdtkbnmcz, f tckb yt itdtkbnmcz hfcitdtkbnm b dpkjvfnm !!! ...

xenomorph
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 508
Зарегистрирован: 18.04.2004 (Вс) 11:41
Откуда: это не важно - на сегодня у меня есть алиби ...

Re: Реализация кроссовера в генетическом алгоритме

Сообщение xenomorph » 27.12.2011 (Вт) 14:46

Похоже нашёл - мне нужна хромосома :-) такого типа:

Изображение

статья по ГА (годная ИМО):
http://www.codeproject.com/KB/recipes/G ... edule.aspx

и есть нормальное описание кроссовера:

A crossover operation combines data in the hash maps of two parents, and then it creates a vector of slots according to the content of the new hash map. A crossover 'splits' hash maps of both parents in parts of random size. The number of parts is defined by the number of crossover points (plus one) in the chromosome's parameters. Then, it alternately copies parts form parents to the new chromosome, and forms a new vector of slots.


Я так понял смысл кроссовера в разбиении 2х хромосом и обмене параметрами.

(утопал за сильной травкой, ибо без травки не вкурю...)
... Dpkjvfnm dc`xnj itdtkbnmcz, f tckb yt itdtkbnmcz hfcitdtkbnm b dpkjvfnm !!! ...

xenomorph
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 508
Зарегистрирован: 18.04.2004 (Вс) 11:41
Откуда: это не важно - на сегодня у меня есть алиби ...

Re: Реализация кроссовера в генетическом алгоритме

Сообщение xenomorph » 27.12.2011 (Вт) 14:51

Так, перед тем как полезу кодить свой проект, ИМО неплохо было бы написать какой-нить базовый хеллоу ворлд.

Нашёл вот что:
http://www.generation5.org/content/2003/gahelloworld.asp

За фитнес функцию возьму расстояние Левенштайна.
Цель - трансформировать набор букв в хеллоу ворлд по ГА.

Щас попробую до вечера, своими словами (на вб. нет :-)) написать это. Отпишусь и код приложу.
... Dpkjvfnm dc`xnj itdtkbnmcz, f tckb yt itdtkbnmcz hfcitdtkbnm b dpkjvfnm !!! ...

xenomorph
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 508
Зарегистрирован: 18.04.2004 (Вс) 11:41
Откуда: это не важно - на сегодня у меня есть алиби ...

Re: Реализация кроссовера в генетическом алгоритме

Сообщение xenomorph » 27.12.2011 (Вт) 19:25

Эх, пока компания вб-шных генетиков не пришла, вспомню анекдот:

с баша:
"kdt: От нечего делать бродил по форумам программистов, ответил на свой же собственный вопрос, заданный месяц назад )"


де жа вю...

Продолжим по теме:

1) Английская вики на порядок лучше русской по теме ГА:
моя попа чувствовала что функция должна быть стохастическая:
http://en.wikipedia.org/wiki/Stochastic

2) Кроссовер выполняться должен на уровне вертикальных элементов в фенотипе (геноме).
т.е. *to the best of my understanding* имеем 2 класса, и кросовер в примитивном понимании это своп (обмен) значений переменных.

т.е.

Код: Выделить всё
b_Temp As boolean = cls_text1.b_Value
cls_text1.b_Value = cls_text2.b_Value
cls_text2.b_Value = b_Temp


т.е. замена генов - вертикальная. И в моём случае менять надо буль на буль, инт на инт, и т.д.

3) Эффективность ГА можно померить при сравнении ЕГО рантайма и рантайма тотального перебора.
т.е. если ГА находит искомое\близкое к искомому быстрее чет тотал перебор, ровно во столько раз он и эффективнее.

советую посмотреть: Criticisms в англо-вики и:

http://en.wikipedia.org/wiki/Evolution_strategy
http://en.wikipedia.org/wiki/Genetic_programming

*Чего я не понял - так это того почему нет дженериков реализаций ГА на ВБ в виде бинарных векторов.
Видимо есть что-то что не позволяет это написать (специфика фит функции *?)
--
покушаю и кодить!
... Dpkjvfnm dc`xnj itdtkbnmcz, f tckb yt itdtkbnmcz hfcitdtkbnm b dpkjvfnm !!! ...

xenomorph
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 508
Зарегистрирован: 18.04.2004 (Вс) 11:41
Откуда: это не важно - на сегодня у меня есть алиби ...

Re: Реализация кроссовера в генетическом алгоритме

Сообщение xenomorph » 28.12.2011 (Ср) 4:02

По старой доброй традиции отвечаю сам себе на все свои вопросы:

1. Кросовер выполняеться *как правио* по вертикали генов. Ответ на моё 1 вопрос - буль на буль.
Интеджер на буль не катит, так как если хотите разбить геном на биты, то транслируйте всё в байтовый вектор,
а потом назад в класс.

А по-ходу - делать и тестить. Другого варианта не будет. Х.з. какие там закономерности.
--
проблемки:

1. Самое тяжёлое НЕ кроссовер и тем более не мутация - а - *пампарарурам*:
а) - СЕЛЕКЦИЯ поколения.
б) - куда тыкать и в каком порядке МУТАЦИЮ и СКРЕЩИВАНИЕ.

2. Настройка алгоритма занимает, к сожалению, БОЛЬШЕ времени чем его написание.
Готовый ГА в аттаче.

Я НЕ счастлив. т.к. для моего исследования он не подойдёт. Очень много вызовов F. *печалька*.

Изображение

Код в аттаче. Высплюсь и поем, причешу код как надо.
Вложения
GA_HelloWorld_03.rar
(87.39 Кб) Скачиваний: 125
... Dpkjvfnm dc`xnj itdtkbnmcz, f tckb yt itdtkbnmcz hfcitdtkbnm b dpkjvfnm !!! ...

xenomorph
Постоялец
Постоялец
Аватара пользователя
 
Сообщения: 508
Зарегистрирован: 18.04.2004 (Вс) 11:41
Откуда: это не важно - на сегодня у меня есть алиби ...

Re: Реализация кроссовера в генетическом алгоритме

Сообщение xenomorph » 29.12.2011 (Чт) 3:45

Всем привет,

я поел и выспался :D .

Версия ГА 2.0.
Что нового:

1. Вынес параметры на форму.
2. Добавил "Элитизм" (верхний процент от текущего поколения, который и формирует потомков).
3. Добавил "Размер мутации" (влияет на кол-во итераций при мутации генома).

Неплохо настроил параметры и поигрался -

Изображение

Пару замечаний по моим предыдущим заметкам:

1. У того человека у которого я взял идею потренироваться на ф-ии Левенштайна: http://www.generation5.org/content/2003/gahelloworld.asp
у него НЕ ПОЛНЫЙ ГА.

а) у него написано почему:

Firstly, we cheat slightly by fixing the size of the strings in the GA population to be the same size as the target string. This just makes the code easier to understand.


б) у него, как в анекдоте, ошибка в ДНК: http://www.generation5.org/content/2003/data/gahelloworld.cpp

Код: Выделить всё
void mate(ga_vector &population, ga_vector &buffer)
{
   int esize = GA_POPSIZE * GA_ELITRATE;
   int tsize = GA_TARGET.size(), spos, i1, i2;

   elitism(population, buffer, esize);

   // Mate the rest
   for (int i=esize; i<GA_POPSIZE; i++) {
      i1 = rand() % (GA_POPSIZE / 2);
      i2 = rand() % (GA_POPSIZE / 2);
      spos = rand() % tsize;

      buffer[i].str = population[i1].str.substr(0, spos) +
                     population[i2].str.substr(spos, esize - spos);

      if (rand() < GA_MUTATION) mutate(buffer[i]);
   }
}


Ибо размножаться, должна ЭЛИТА, а не "Mate the rest", ИМО это очень большой косяк как для ГА ))).

Последние замечания по 2.0 версии -
1) размер популяции ОЧЕНЬ влияет на всё.
2) при размере популяции выше определённого n - комбинаторной способности КроссОвера достаточно для
получения искомого результата. 10-20 поколений. Мутации не есть необходимыми в таком случае.
3) у меня очень мощный комп по состоянию на конец 2011 года. 9550-extreme - 6 физ\12 вирт ядер 3.7 ггц. ssd + 3chan high-freq ram.
я понятия не имею как оно будет на вашей машине, меня не пинать!

Куда копать если у Вас есть желание:

1. Перевод генома в интеджеры\байты.
2. Переписать проект так, чтоб геном был дженерик классом и реализовать механизм преобразования
класса генома в интеджеры\байты, это даст возможность юзать любые входные\выходные и т.п.
3. Добавить к генам "вес", и увеличивать его если Кросовер или Мутация увеличили F-res. При выполнении
следующего цикла кроссовера\мутации НЕ ТРОГАТЬ эти гены с большим весом в течении хотя бы 1-3 поколений.
Таким образом не давать возможность системе убить эти гены случайно, и повысить шансы на выживание.
--
Удачи!
Вложения
GA_HelloWorld_04.rar
(92.99 Кб) Скачиваний: 136
... Dpkjvfnm dc`xnj itdtkbnmcz, f tckb yt itdtkbnmcz hfcitdtkbnm b dpkjvfnm !!! ...


Вернуться в Раздел для Профессионалов

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

    TopList