В этой статье я продемонстрирую как можно написать универсальный генетический алгоритм с переопределяемыми функциями в MathCad15.
Наверное у тебя может возникнуть вопрос "Зачем?" и "Почему?". На самом деле эти вопросы имеют один ответ: "Мне очень нравятся эволюционные алгоритмы и я могу говорить о них часы напролёт, и хочу просто рассказать о том, что так тоже можно".
Разумеется написанный алгоритм будет не "вообще" универсальный, а "разумно" универсальный.
Будем пользоваться "скрытой" возможностью маткада передавать функции в качестве аргументов в другие функции. Если вы умеете в C++ вы можете увидеть сходство с указателями на функции или даже шаблонными функциями. (когда-нибудь напишу статейку для версии ГА на плюсах и на других языках до которых успел дотянутся...)
Это не гайд и не учебный материал, просто демонстрация возможности, хотите - пользуйтесь, не хотите - не пользуйтесь.
Итак, начнем с самой структуры ГА (Генетического Алгоритма), она вполне стандартна:
- Начальная популяция (nachPop)
- Мутация (mutation)
- Скрещивание (crossingover)
- Вычисление приспособленности (adaption)
- Отбор (selection)
Начальная популяция.
Для формирования ГА в обобщенном виде, нужно придумать функцию формирования начальной популяции для произвольной особи (заданной пользователем), но сама функция должна работать только на уровне популяции, т.е. функция должна обрабатывать только и только особей популяции без знания о том, как они устроены!
Устройство конкретной особи (точнее каждой особи) должно быть возложено на пользователя и быть определено позднее.
Чтобы сделать задуманное сформируем функцию например так:
передадим в неё параметр k отвечающий за количество особей в популяции,
некоторые параметры А и В, имеющие смысл минимального и максимального порога (границы) генерации начальных значений особей (мне было лень придумывать им осмысленные названия и я просто написал их так...)
и функцию osob(A,B) которая будет генерировать конкретную особь.
Именно функцию osob(A,B) впоследствии и будет определять пользователь (главное не напутать с сигнатурой, что очень легко сделать в маткаде, хаха )
Функция примитивна донельзя, она просто в цикле заполняет массив особями сгенерированными функцией osob(A,B), и всё, остальное - не её забота.
Здесь можно было бы немного обмолвиться о инвариантах, но лучше пока опустить эту тему, статья и так планируется большой.
Хорошо, дальше идут
мутации...
Их, как и предыдущую и все последующие функции, нужно будет определить так, что бы они работали сугубо на уровне популяции не зная ничего о внутреннем устройстве отдельной особи.
Например так:
На вход функция получает массив особей (популяцию) Pop,
параметр С имеющий смысл вероятности мутации некоторой особи (от 0 до 1),
функцию мутации mut и её параметр maxMut соответствующий максимальной амплитуде мутаций.
Функция работает очень просто:
- вначале определяется размер полученной популяции;
- затем инициализируется счетчик для мутированных особей;
- далее в цикле перебираются все особи и для каждой проверяется, если случайное число меньше величины С, то значит нужно мутировать особь. Получаем особь, мутируем её функцией mut и записываем в конец списка мутантов;
- в конце проверяем размер списка, если он имеет не нулевую длину, добавляем его к основной популяции, а если нулевую, то просто выводим основную популяцию.
На очереди скрещивание.
Скрещивание осуществляется между несколькими особями, как минимум двумя, поэтому функция cross определяемая пользователем должна иметь как минимум два параметра первую и вторую особь (можно зарезервировать ещё параметры на будущее, но не сейчас... ограничимся 2-мя)
Функция в принципе работает похожим на предыдущую образом, но в теле цикла отличается тем, что для каждой особи по порядку подбирает случайную особь из всей популяции и скрещивает их функцией cross. (есть разные подходы к подобному процессу, и турнирные методы и отбор из хвостов и тд, очень много вариантов придумали люди, но самое простое это отбирать особей так, или можно вообще скрещивать соседей по списку... )
Вычисление приспособленности.
Для обобщенного вычисления приспособленности нужно будет определить функцию fOpt, которая и является той функцией которая оптимизируется (ищется её минимум).
Проходим по всему списку особей и вычисляем приспособленность каждой, записываем её в список и возвращаем его как результат работы функции.
Последняя функция.
Отбор.
Отбор можно было бы тоже сделать обобщенным, но он может и обойтись.
В начале проверяем что бы размеры массивов совпадали.
Далее "склеиваем" два массива в матрицу, сортируем матрицу по нулевому столбцу и вырезаем первый столбец в количестве k особей, формируя тем самым список особей с самым низким значением функции fOpt из всей популяции.
Результат.
В итоге имеем следующий ГА на основе всех наших функций определенных выше. Я решил передавать в него управляющие параметры массивом PARAMS содержащим всё необходимое.
Что с ним делать?
Примеры.
Пример 1. Я написал что это пример, но это отчасти и так и не так. Раз мы написали алгоритм, надо бы проверить работает ли он. Для этого можно воспользоваться какой-нибудь задачей ответ на которую нам известен.
Например найти минимум квадратной параболы. Мы зададим её так, что бы минимум был в точке х=10, это легко сделать:
y(x) = (x - 10)^2
Вот её график.
Т.е. иными словами, функция минимум которой нам предстоит найти уже нам известна (нам известен и ответ, но ГА его ещё не знает, это мы и проверяем, найдет ли он его???).
Так как нам нужно только одно число - каждая особь будет просто числом, без какой-либо сложной внутренней структуры.
Функция y(x) будет применяться в вычислении приспособленности особей, и следовательно её мы поместим в определяемую пользователем функцию fOpt.
Пусть она будет такой (особь - это просто число):
Раз особь это просто число, то функция формирования случайной особи osob будет тоже простой: случайное число от минимума до максимума.
Мутация - это увеличение или уменьшение нашего числа, на случайную величину ограниченную амплитудой мутации.
И осталось определить функцию скрещивания двух особей cross, которая тоже довольно очевидна. Просто берем одно из чисел (хотя можно было бы брать взвешенную сумму этих чисел или что-то подобное)
Запускаем алгоритм с набором параметров:
И сам алгоритм с определенными выше функциями:
Что мы видим в результате:
Отлично, но хочется посмотреть на динамику поиска. Можно чуть доработать ГА, добавив запись лучшей особи в отдельный массив, и выводить этот массив, тогда можно будет посмотреть анимацию поиска решения:
Пример 2. А что на счет задачи посложнее, для поиска по 2-м параметрам, какой-нибудь функции наподобие. Пусть это будет функция:
z(x,y) = (x - X0)^2 + (y - Y0)^2
где: X0 - оптимум по оси X; Y0 - оптимум по оси Y.
В нашем случае я задал им значения: X0=27 и Y0=11.63
Ясное дело что раз нам нужны 2 числа, то особь будет состоять из двух чисел, из массива длинной = 2.
Тогда функция - генератор особи - будет такой:
Мутации аналогично предыдущему случаю, но с текущей функцией генерации особи:
Сама функция минимум которой будем искать:
Запускаем алгоритм с теми же параметрами что и раньше, выглядит он теперь так (используем свежие функции, кроме скрещивания, оно осталось прежним, я даже подумал убрать его из переопределяемых и внести в код основной программы, но да ладно... пусть пока останется так):
Раз у нас есть динамика сразу приведу её, вот так алгоритм искал точку оптимума (X0; Y0) путем скрещивания, мутаций и отбора:
Пример 3. Ну ладно, здесь оптимум заранее подавался в функцию, это может показаться не совсем честно, что будет если взять какую-нибудь задачу поинтереснее, например задачу аппроксимации экспериментальных данных некоторой кривой.
В качестве данных возьмем следующий набор, взятый мной из головы... здесь все данные целые, потому что мне так проще их записывать, в принципе никто не запрещает задать их не целыми (просто отметил).
На графике выглядят они так:
Попробуем аппроксимировать их "прямой"
y(x) = a*x + b
Я задал её отдельно в виде функции по имени polinom:
Аппроксимировать - значит найти такие значения коэффициентов a и b, что отклонение (сумма квадратов отклонений) прямой от исходного набора точек будет минимально.
Из этого сразу ясно что мы снова ищем 2 числа, то есть особь снова будет представлять собой массив из двух элементов, такая же как и в предыдущем случае.
Мутации и скрещивание тоже не изменятся.
А вот функция по которой вычисляется приспособленность изменится (она подчеркивается потому, что названа как и предыдущая, не обращайте внимания...):
В качестве приспособленности она возвращает сумму квадратов отклонений от набора точек (она просто считает чему равно значение прямой в известных из набора точках X и сравнивает эти значения с теми Y которые есть в наборе и соответствуют X)
Ну что ж, в результате запуска ГА получаем следующее решение:
И даже можно глянуть динамику поиска:
Пример 4. Попробуем посмотреть что будет в случае аппроксимации параболой:
Здесь уже нужно найти три значения, значит и особь будет соответствующая:
И вслед за этим совсем чуть-чуть изменится функция вычисления приспособленности особи (оптимизируемая функция):
После запуска имеем такое решение:
И динамика его поиска:
Выглядит достойно))) или как минимум визуально правдоподобно.
Пример 5. Попробуем аппроксимировать данные полиномом произвольной степени:
y(x) = a + b*x + c*x^2 + ... + k*x^(n-1) + p*x^n
Функция polinom для него изменится, во первых для неё нужно очень много параметров - поэтому рационально предавать в неё непосредственно особь, а во вторых она будет иметь внутри цикл вычисляющий последовательно каждый член этого полинома (можно было бы использовать встроенную сумму):
Особь будет иметь n+1 число элементов, где n - степень полинома. поэтому функция генерирующая особь, будет параметрически зависеть от параметра n:
Функция вычисления приспособленности почти не изменится:
В результате запуска ГА для n=4 (полином 4-й степени), получим следующее решение:
И динамика поиска:
Пример 6. Вообще, визуально, решение для n=4 выглядит как полином 3-й степени...
Это мы и проверим, а заодно и попробуем внедрить уникальные границы генерации и мутаций для особей. Это нужно тогда, когда одна величина в задаче меняется на несколько порядков больше другой и одним числом её так просто не задать, лучше использовать для каждой величины свои интервалы.
Искать будем решение для n=3 (количество чисел будет = 4):
Здесь параметры A и B - массивы, поэтому для каждого параметра особи имеется свой собственный минимум и максимум генерации значения. (конечно можно задать их более универсально, но пока так)
Функция полинома от особи:
Все остальное +- тоже самое, но теперь у нас появляются 3 массива с границами:
Что бы пользоваться ими внутри ГА передадим их в параметры:
И теперь параметры и функции передадим в ГА:
В результате получаем:
И динамика поиска:
Итоги.
В результате непродолжительной деятельности удалось написать "универсальный" генетический алгоритм, НО его можно сделать гораздо универсальнее если добавить возможность проводить разные отборы и скрещивания.
Если вы не знали о том, что в маткаде можно передавать функции в другие функции, то теперь знаете))) (хотя... оно вам вообще надо???)
