Файл: Факультет компьютерных технологий и прикладной математики Кафедра информационных технологий курсовая работа организация рациона питания с применением генетического алгоритма.docx

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

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

В классическом генетическом алгоритме применяются два основных оператора: оператор скрещивания (crossover)и оператор мутации (mutation). Однако следует отметить, что оператор мутации играет явно второстепенную роль по сравнению с оператором скрещивания. Это означает, что скрещивание в классическом генетическом алгоритме производится практически всегда, тогда как мутация – достаточно редко. Вероятность скрещивания, как правило, достаточно велика, тогда как вероятность мутации устанавливается весьма малой. Это следует из аналогии с миром живых организмов, где мутации происходят чрезвычайно редко.

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

Оператор скрещивания. На первом этапе скрещивания выбираются пары хромосом из родительской популяции (родительского пула). Это временная популяция, состоящая из хромосом, отобранных в результате селекции и предназначенных для дальнейших преобразований операторами скрещивания и мутации с целью формирования новой популяции потомков. На данном этапе хромосомы из родительской популяции объединяются в пары. Это производится случайным способом в соответствии с вероятностью скрещивания. Далее для каждой пары отобранных таким образом родителей разыгрывается позиция гена (локус) в хромосоме, определяющая так называемую точку скрещивания. Если хромосома каждого из родителей состоит из L генов, то очевидно, что точка скрещивания l_kпредставляет собой натуральное число_, меньшее L. Поэтому фиксация точки скрещивания сводится к случайному выбору пары из интервала [1, L

-1]. В результате скрещивания пары родительских хромосом получается следующая пара потомков:

- потомок, хромосома которого на позициях от 1 до l_kсостоит из генов первого родителя, а на позиции от l_k+ 1 до L – из генов второго родителя;

- потомок, хромосома которого на позициях от 1 до l_kсостоит из генов второго родителя, а на позиции от l_k+ 1 до L – из генов первого родителя.

Оператор мутации изменяет значение гена в хромосоме на противоположное (т. е. с 0 на 1 или обратно). Как уже упоминалось выше, вероятность мутации обычно очень мала, и именно от нее зависит, будет данный ген мутировать или нет. Вероятность мутации может эмулироваться, например случайным выбором числа из интервала [0,1] для каждого гена и отбором для выполнения этой операции тех генов, для которых разыгранное число оказывается меньшим или равным значению вероятности.

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

Выбор «наилучшей» хромосомы. Если условие остановки алгоритма выполнено, то следует вывести результат работы, т.е. представить искомое решение задачи. Лучшим решением считается хромосома с наибольшим значением функции приспособленности.

Генетические алгоритмы унаследовали свойства естественного эволюционного процесса, состоящие в генетических изменениях популяции организмов с течением времени.

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

2.3 Преимущества и недостатки генетических алгоритмов

Эксперименты, описанные в литературе, показывают, что генетические алгоритмы очень эффективны в поиске глобальных минимумов адаптивных рельефов, так как в них исследуются большие области допустимых значений параметров нейронных сетей. Градиентные алгоритмы дают возможность находить только локальные минимумы. Другая причина того, что генетические алгоритмы не «застревают» в локальных минимумах — случайные мутации.

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

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

Однако при этом генетические алгоритмы обучения сложны для понимания и программной реализации. Есть такие случаи, где не только не желательно, но и проблематично использовать генетические алгоритмы: в случае когда необходимо найти точный глобальный оптимум; время исполнения функции оценки велико; необходимо найти все решения задачи, а не одно из них; конфигурация является не простой (кодирование решения); поверхность ответа имеет слабо изменяющийся рельеф.

3 Постановка задачи и проект решения

3.1 Постановка задачи

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

Формально постановку задачи можно определить следующим образом: пусть имеется n различных пищевых продуктов p₁, p₂, …, p_n, содержащих m различных питательных веществ. Обозначим через a_ij содержание j-го питательного вещества в i-ом продукте, через b_j – суточную потребность организма в j-ом питательном веществе, через c_i – стоимость единицы i-го продукта. Требуется составить суточный рацион питания минимальной стоимости, удовлетворяющий потребность во всех питательных веществах.

3.2 Проект решения

Поставленная задача может быть записана в виде задачи линейного программирования:

(1)

(2)
При ограничениях:

(3)
Применение генетического алгоритма к поставленной задачи приводит к следующему: популяцией является набор матриц

, где N – размерность популяции. Каждая особь популяции формируется по следующему правилу. Сначала матрица заполняется нулями. Затем случайным образом выбирается элемент матрицы (ген особи), которому присваивается значение единица. При этом должны учитываться следующие условия:

(4)
Данное условие означает, что один продукт может входить в дневной рацион только один раз.

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

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

Генерация потомков означает появления новых особей в процессе кроссинговера, при котором два родителя обмениваются генами для получения новой особи, и мутации – это, фактически, процесс клонирования, при котором происходят различные изменения при передаче информации от родителя к потомку.

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

3.3 Реализация генетического алгоритма

Для реализации генетического алгоритма использован язык программирования C#. Был разработан основной класс GA для работы алгоритма. Поля данного класса определяют такие параметры генетического алгоритма как размер особи, размер популяции, максимальное количество поколений, вероятность мутации.

Для начальной инициализации элементов класса и генерации первой популяции используется метод public void InitGA().

Метод private int Roulette() реализует выбор особей для скрещивания методом рулетки.

Метод private void CreateNextGeneration() позволяет сформировать новую популяцию, используя оператор кроссинговера и мутации.

Метод public void GetBestValues(out double[] values, out double fitness) предназначен для отбора лучших особей в популяции.

Метод private void RankPopulation() позволяет ранжировать популяцию хромосом и отсортировать их по возрастанию значения фитнесс-функции.

Также был реализован класс Chromosome, моделирующий поведение хромосомы. В данном классе реализованы следующие методы:

- public void Crossingover(ref Chromosome Chromosome2, out Chromosome child1, out Chromosome child2) позволяющий производить операцию скрещивания с получением 2 дочерних хромосом;

- public void Mutate() обеспечивающий операцию мутации хромосом;

- public static double penalty(double[] values) – метод для вычисления штрафной функции;

- public static double FitFcn(double[] values) – метод, позволяющий вычислить значение фитнесс-функции.

3.4 Результаты работы программы

В качестве примера для решения задачи были выбраны следующие параметры задачи составления оптимального рациона питания (таблица 2):
Таблица 2 – Условие задачи о рационе питания