Генетический алгоритм верно или неверно реализовал?

[Mixim]

Стоит задача: реализовать генетический алгоритм для максимизации/минимизации функции. Пару дней посидел поразбирался с теорией, написал код, но как-то немного боязно: вдруг не так понял теоретические сведения.
Не нравится в этом алгоритме то, что значения могут получаться всякий раз разные (хотя там широко используются методы из разряда Random, но все же)
Реализовал указанную задачу в виде консольного приложения под MonoDevelop/Gtk#/Linux, исходники с которым прикладываю к посту. Ни могли бы глянуть и сказать верно реализовано или нет?
Если кому-то позже понадобиться указанный код, но под Windows, можете удалить из него модули Gtk#, добавить .NET Framework и все.

[Tayfun]

Добрый день! Реализовывал однажды задачу связанную с генетическими алгоритмами. Решал транспортную задачу. Для теории очень помогла статья из википедии, думаю Вы её читали, там все очень просто описано. Реализовывал по такому порядку как описано там:
1. Начальная популяция
Здесь я находил решение транспортной задачи несколькими способами (Метода "серверо-заподного угла", "наименьшего элементами"). Получались две таблицы с данными, это и была моя начальная популяция.
2. Скрещивание
Здесь мы объединяем решения. В моем случае я брал столбцы из одной таблицы и подставлял во вторую и получал множество таблиц (потомки). Для двух таблиц 2*3 получалось вот так:
Начальные:
0 2 1 | 1 0 2
1 0 3 | 2 1 1
Потомки (если где ошибся не судите строго):
1 2 1 | 0 0 1 | 0 2 2 | 0 0 2 | 1 2 2 | 1 0 1
2 0 3 | 1 1 3 | 1 0 1 | 1 1 1 | 2 0 1 | 2 1 3
3. Выбираем жизнеспособные решения (удовлетворяющие условиям)
4. Из оставшихся жизнеспособных выбираем значение функции для которых минимальное. Берем эти решения и переходим к пункту 1.
Вот такая мини эволюция получалась. Критерием остановки цикла было и количество повторений цикла и временные рамки.
Для мутации можно в момент, когда не оказывается жизнеспособных решений добавлять некоторые изменения (рендомные)
В результате чисто теоретически процесс сводится к оптимальному решению через определенный промежуток повторений.

Надеюсь хоть теоретически Вам немного помог.

[Mixim]

Сообщение от Tayfun

Добрый день!

Добрый

Сообщение от Tayfun

2. Скрещивание
Здесь мы объединяем решения. В моем случае я брал столбцы из одной таблицы и подставлял во вторую и получал множество таблиц (потомки). Для двух таблиц 2*3 получалось вот так:
Начальные:
0 2 1 | 1 0 2
1 0 3 | 2 1 1
Потомки (если где ошибся не судите строго):
1 2 1 | 0 0 1 | 0 2 2 | 0 0 2 | 1 2 2 | 1 0 1
2 0 3 | 1 1 3 | 1 0 1 | 1 1 1 | 2 0 1 | 2 1 3

Скрещивание, это то, что также принято называть кроссовером? Я сколько ни читал, везде скрещивание выполняется по генам, т.е. есть популяция 1 и 2, значение которых равно (пишу в двоичном коде):

популяция 1:
1001 0110

популяция 2:
1100 1110

в итоге получаем новую популяцию:

1101 1110 (скрестили по второму гену, который выбрали случайно)

выполняем ряд других операций(мутацию и прочее) и считаем значение оптимизируемой функции. Если наше решение улучшилось, "убиваем" предков (1001 0110 и 1100 1110), сохраняем потомков (1100 1110) и прогоняем алгоритм еще раз, в противном случае "убиваем" потомков и вновь прогоняем наш алгоритм. Я делал именно так, не знаю верно или нет, но если верить литературе, то так верно

[Tayfun]

сохраняем потомков (1100 1110) и прогоняем алгоритм еще раз, в противном случае "убиваем" потомков и вновь прогоняем наш алгоритм

Да все верно, и прогоняете пока не сработают критерии остановки алгоритма.
Отличная работа!

[Mixim]

Сообщение от Tayfun

Да все верно, и прогоняете пока не сработают критерии остановки алгоритма.
Отличная работа!

Спасибо! С Наступающим

[Mixim]

Сообщение от Tayfun

Да все верно, и прогоняете пока не сработают критерии остановки алгоритма.
Отличная работа!

И все же неверно работает мой код, неверно! Решил испробовать его для решения стандартной задачи оптимизации, т.е. оптимизировать функцию Химмельблау:

f(x,y)=(x^2 + y - 11)^2 + (x + y^2 -7)^2

и как итог получил, что минимальное значение функции равно ~190 и достигается оно близ нуля, но мы то с Вами знаем, что функция Химмельблау имеет минимум в точке (3;2), который равен f(3,2)=(9+2-11)^2+(3+4-7)^2=0 - существенная разница, ни правдо ли?
Сейчас буду смотреть на реализованные операторы скрещивания и селекции, т.к. судя по отладчику они работают по меньшей мере странно.
Все же может быть кто в состоянии ткнуть пальцем и с дьявольским сарказмом сказать: "А вот тут у тебя ошибка!"?