Генетический алгоритм. Урок 1. Решение многочлена
Что бы смотреть урок полностью, подпишитесь на платный раздел.
В платном разделе статья находиться здесь.
Исходники к уроку можно скачать в платном разделе.
Разговор двух блондинок:
- Ну что, поступила в Институт?
- Нет, не поступила.
- А что-ж так?
- Дык, задали мне решить какой то там квадратный трехчлен.
А я даже представить себе такого не могу!
Сегодня мы рассмотрим применение генетического алгоритма для решения многочлена степени три и более (поскольку уравнение степени два решаются легко любым адекватным школьником). Как можно решить, например, вот такое уравнение 5x5+7x4-8x3+4x2-11x-202? Ясно, что тупым перебором тут не отделаться, ибо нереально перебрать все числа. К тому же, у многочлена может быть не один корень. И тут на выручку нам приходит генетический алгоритм. Его муть состоит в том, оптимизируемые параметры кодируются в специальный формат, называемый генетическим кодом. Наборы таких параметров называются "особи", а совокупность "особей" - "популяцией". Для каждой "особи" вычисляется целевая функция, затем происходит сортировка и из "популяции" удаляются "особи" с наихудшим значением целевой функции. "Особи" могут "скрещиваться" между собой. Этот процесс происходит следующим образом: два "гена" рассекаются в случайном месте, и новый "ген" получается из соединения частей этих двух генов. Так же "особи" могут "мутировать". Суть мутации состоит в том, что случайным образом изменяется какой нибудь бит "гена".
Таким образом, путем естественно отбора, в выборе остаются только те комбинации параметров, которые лучшим образом соответствуют решению, например, имеют наименьшую целевую функцию. Если мы вычислим значение многочлена, и возьмем его по модулю, то это значение у нас должно стремиться к нулю....
....
....При нажатии на кнопочку "Тест шаг" у нас будет выполнятся переход к следующему поколению:
|
private void lbTest_Click(object sender, EventArgs e) { pop.NextGeneration(); show(); } |
При нажатии на кнопочку "Обучение" у нас должно происходить генерация множества поколений, например, 100:
|
private void btnStudy_Click(object sender, EventArgs e) { for(int i=1; i<100; i++) { pop.NextGeneration(); } show(); } |
...
... Теперь перейдем к тестированию. И так, вот первоначальное поколение:
Как видим, и целевая функция даже близко не валяется с нулем. Жмем кнопочку "Тест шаг":
Жмем еще раз:
Как видим, количество видов лучшей целевой функцией увеличилась. В идеале, конечно, что бы она (целевая функция) достигла нуля. Жмем еще раз:
Что же мы видим? У нас появился вид с целевой функцией лучше, чем на прошлом шаге. В общем, с каждым шагам качество популяции улучшается. что будет, если мы пропустим 100 поколений? Вот, смотрите:
Фактически, у нас все особи имеют значение целевой функции, близкой к нулю (к идеальному значению). Тоесть, мы решили уравнение. Давайте проверим:
5x5+7x4-8x3+4x2-11x-202=5*25+7*24-8*23+4*22-11*2-202=5*32+7*16-8*8+4*4-22-202=160+112-64+16-22-202=0
Правда, все виды имеют только одно значение - 2. Но у многочлена, как вы знаете, могут быть несколько корней. но этим вопросом мы уже озадачимся на следующем уроке.
Скриншоты, помеченные знаком *, являются цитатами и иллюстрациями программного продукта "Microsoft Visual Studio 2010 Professional", авторское право на который принадлежит корпорации Microsoft..