Введение 3
Аппроксимация функций нескольких переменных 5
Общие сведения о генетических алгоритмах 15
Решение задачи аппроксимации функции на основе генетических алгоритмов 23
Заключение 35
Список используемой литературы 37
Приложение
На практике, в ходе обработки экспериментальных данных, часто встречается задача установления аналитического вида зависимости входных и выходных данных, что является очень затратной процедурой. Восстановление
конкретного вида функции в аналитическом виде при этом, как правило, невозможно и поэтому для дальнейшего анализа выбирается относительно простая конструкция, приближающая исходную.
Полиномы, сплайны, вейвлеты – все они имеют право на существование
в качестве аппарата приближения. В данной работе используются многочлены, ввиду простоты оперирования ими для дальнейшего интегрирования,
дифференцирования, а также установления промежуточных значений.
Для минимизирования отклонения между двумя функциями в заданных
точках, использовалась формула метода наименьших квадратов, а для поиска
неизвестных параметров использовалась рабочая конструкция естественного
отбора. Широкий простор для выбора метода решения подобных задач дают
эволюционные алгоритмы, моделирующие известные процессы селекции, мутации и скрещивания индивидов популяции. Алгоритмы используют такие
разделы биологии, как нейробиологию – источник идей искусственных
нейронных сетей и генетику – средство расшифровки геномов и использования операции рекомбинации решений. Используя генетические алгоритмы и
генетическое программирование, созданное на основе генетики, удалось реализовать модель отбора наиболее приспособленной особи – коэффициентов
полинома. Данный алгоритм, появившийся в результате работ Д. Холланда и
его коллег в начале 70-х годов, популярен и по сей день, поскольку областей
его применения существует немало:
экстремальные задачи;
задачи о кратчайшем пути;
задачи компоновки;4
составление расписаний;
аппроксимация функций;
отбор (фильтрация) входных данных;
настройка искусственной нейронной сети [1].
Не мало работ по генетическим алгоритмам посвящены задачам оптимизации, например [2] Паротькина Н.Ю, [3] Семенкиной М.Е., а также вопросам принятия решения [4] Штуца И.М.
Целью нашей работы являлось построение математической модели,
основанной на применении генетических алгоритмов, для аппроксимации
функции многих переменных с некоторой наперед заданной точностью.
Для достижения цели необходимо было решить следующие задачи:
1) изучить теорию аппроксимации функции, обобщить задачу на
случай многих переменных и выбрать метод оценки близости
точного и приближенного решений;
2) исследовать схему работы генетического алгоритма и возможности ее модификаций для улучшения результата по точности
или по времени.
3) разработать программное обеспечение, реализующее построенную математическую модель.
Существуют различные методы приближения для заданного дискретного множества точек некоторого интервала. Чаще всего для задачи минимизации отклонения выбирают среднеквадратичную метрику метода наименьших квадратов. В качестве аппроксимирующей функции, ввиду несложности
построения и дальнейшего оперирования, в работе был использован полином,
который представим своими коэффициентами. Для функций нескольких переменных, был проведен анализ построения алгебраического полинома заданной
степени. Обобщенный многочлен представлялся в виде дерева, где каждый
узел соответствует моному, а каждое ребро – домножению на одну из переменных. Также для сравнения было разобрано приближение ортогональными
полиномами Чебышева и системы комбинаций степеней переменных. Отличаются они тем, что в первом случае необходимы механические замены на полином следующей степени, когда встречаются повторяющиеся комбинации
переменных в узлах дерева.
Классический метод наименьших квадратов приводит к СЛАУ, для решения которой использовался метод адаптивного поиска параметров полинома – генетический алгоритм, поскольку он предъявляет минимальные требования к исходным данным. ГА хорошо приспособлен к работе с вычислительной техникой и не предъявляет жестких ограничений к исходным данным.
Генетический алгоритм для функции нескольких переменных не претерпевает
больших изменений при переходе от одномерного случая к многомерному.
Достаточно лишь следить за количеством коэффициентов полинома и соответствовать порядку следования базисной системы на всех этапах. В программной реализации алгоритма также была проанализирована работа нескольких
существующих методов селекции. Наиболее приемлемым по скорости выполнения оказался турнирный.36
Основная проблема генетических алгоритмов – предварительная
сходимость – решалась посредством использования островной модели
развития отдельно живущих популяций. С помощью параллелизма
удалось добиться уменьшения временных затрат, так как каждая популяция
обрабатывалась отдельным потоком.
