УДК 004.41

НАХОЖДЕНИЕ МАКСИМУМА ФУНКЦИИ С ПОМОЩЬЮ ГЕНЕТИЧЕСКОГО АЛГОРИТМА

Щукова Кристина Борисовна
Национальный исследовательский Томский политехнический университет

Аннотация
В статье рассматривается одна из важных задач оптимизации - нахождение максимума функции. В качестве метода предлагается использовать генетический алгоритм. Освящены краткие теоретические аспекты идеи генетического алгоритма. Разработана программа на C#, в которой реализован генетический алгоритм для нахождения максимума функции.

Ключевые слова: генетический алгоритм, задача оптимизации, максимум функции


FINDING THE MAXIMUM OF THE FUNCTION USING THE GENETIC ALGORITHM

Shchukova Kristina Borisovna
National Research Tomsk Polytechnic University

Abstract
The article considers one of the most important issues. The task is to find the maximum of the function. In order to solve the task, the genetic algorithm is offered to apply as the effective method. The brief theoretic aspects of the genetic algorithm are discussed. The author developed the program via the C# in that the genetic algorithm has been successfully implemented.

Keywords: C#


Библиографическая ссылка на статью:
Щукова К.Б. Нахождение максимума функции с помощью генетического алгоритма // Современная техника и технологии. 2015. № 11 [Электронный ресурс]. URL: http://technology.snauka.ru/2015/11/8187 (дата обращения: 27.05.2017).

На сегодняшний день задачи оптимизации возникают в различных областях знаний. В частности, в математического анализе, существует важная задача нахождения максимума функции.

Решения такой задачи методами математического анализа не всегда могут дать точные результаты [1]. В данной статье предлагается использовать генетический алгоритм для решения одной из задач оптимизации. Эффективным инструментом для разработки генетического алгоритма является C#.

Постановка задачи следующая: найти максимум любой функции от двух переменных, на заданном интервале, используя целочисленное (бинарное) кодирование. Например, найти максимум функции f (x,y) = sin (2*PI*x) + cos (2*PI*y) + 18 на интервале [-2, 2] по x и y.

Поставленная задача была решена посредством метода генетического алгоритма.

Генетический алгоритм включает в себя следующие шаги:

1. формирование начальной популяции.

2. оценивание популяции.

3. селекция.

4. скрещивание.

5. мутация [2].

На рисунке 1 приведена структурная схема генетического алгоритма.

Рисунок 1. Схема генетического алгоритма

В качестве кодирования генотипов X и Y было выбрано целочисленное или бинарное кодирование. В качестве метода селекции был выбран рулеточный отбор наиболее приспособленных особей в популяции. В качестве метода скрещивания выбранных особей был использован одноточечный кроссинговер. Мутация особей была реализована посредством инверсии битов хромосом по всей длине, то есть многоточечный подход. Длительность эволюции в программе была определена посредством ограниченности числа поколений.

В качестве целевой функции может быть использована любая функция от двух переменных. Таким образом, в программе было задано два генотипа X и Y, то есть два параметра. Каждая хромосома представляет собой битовую строку, разрядность  которой  = 10. Для преобразования каждого генотипа к его фенотипу была использована формула:

 

Оценка особи происходит на основании вычисления приспособленности каждой особи на основании целевой функции. Если f(Gi) > f(Gj), то i-я особь считается более приспособленной, чем j-я особь [3].

Основные параметры, которые задаются для генетического алгоритма:

1)    количество поколений;

2)    численность популяции;

3)    вероятность скрещивания;

4)    тип скрещивания – одноточечный кроссинговер;

5)    вероятность мутации;

6)    тип оператора мутации – побитовая инверсия хромосомы (битовая мутация).

Каждая особь в популяции описывается с помощью класса Individual. Каждая особь имеет два генотипа по X и Y, фенотипа для X и Y, который вычисляется по формуле перехода, значения функции приспособленности для особи, вероятность попадания в родительский массив, границы попадания в родительский массив (левая и правая).

В качестве примера была использована  функция от двух переменных f (x,y) = sin (2*PI*x) + cos (2*PI*y) + 18 на интервале [-2, 2] по x и y.

На рисунке 1 приведены результаты работы генетического алгоритма, а также заданные параметры.

Рисунок 1. Результаты работы генетического оператора

Если использовать классические метода математического анализа, то при вычислении максимума функции значение будет равно 20. Однако, используя генетический алгоритм может получить более точное значение. В данном случае при 100 поколениях получено значение = 20.57. Разница 0.57 может показаться незначительной. Но при решении задач оптимизации эта разница играет важную роль.


Библиографический список
  1. Данута Рутковская, Мачей Пилиньский, Лешек Рутковский. Нейронные сети, генетические алгоритмы и нечеткие системы. Горячая Линия – Телеком, 2007.
  2. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы: Учебное пособие. 2-е изд. М: Физматлит, 2006.
  3. Скобцов Ю. А. Основы эволюционных вычислений. Донецк: ДонНТУ, 2008.


Все статьи автора «Щукова Кристина Борисовна»


© Если вы обнаружили нарушение авторских или смежных прав, пожалуйста, незамедлительно сообщите нам об этом по электронной почте или через форму обратной связи.

Связь с автором (комментарии/рецензии к статье)

Оставить комментарий

Вы должны авторизоваться, чтобы оставить комментарий.

Если Вы еще не зарегистрированы на сайте, то Вам необходимо зарегистрироваться: