Оптимизация плана производства автоматизированным способом

       дети замещают родителей

       новое поколение составляется из совокупности и детей, и их родителей

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

Использование второй стратегии и элитизма не допускает потери лучших решений.

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

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

1.3.5 Факторы, создающие сложность для ГА

Свойства функций приспособленности, создающие сложность для ГА.

         Многоэкстремальность: создается множество ложных аттракторов.

Пример — функция Растригина:
 

На картинке изображен график функции Растригина с одним аргументом.

         Обманчивость (deception): функция построена так, что шаблоны малого порядка уводят популяцию к локальному экстремуму.

Пример: пусть строка состоит из 10-ти четырехбитных подстрок. Пусть равно количеству единиц в i-той подстроке. Зададим функцию g(u) следующей таблицей:

и пусть функция приспособленности равна сумме g() по всем i = 1..10:

                   

         Изолированность («поиск иголки в стоге сена»): функция не предоставляет никакой информации, подсказывающей, в какой области искать максимум. Лишь случайное попадание особи в глобальный экстремум может решить задачу.

          

         Дополнительный шум (noise): значения приспособленности шаблонов сильно разбросаны, поэтому часто даже хорошие гиперплоскости малого порядка не проходят отбор, что замедляет поиск решения.

          

1.3.6. Выводы

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

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

Следует помнить, что применение ГА полезно лишь в тех случаях, когда для данной задачи нет подходящего специального алгоритма решения.

2 Практическое решение задачи

2.1 Экономико-математическая модель задачи

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

Обозначения:

 X1 - батон

 X2 - рогалики

 X3 - булочка

 X4 - ржаной хлеб

 X5 - пончики

Все необходимые данные для решения задачи представлены в наглядном виде в таблице 2.1

Таблица 2.1 - исходные данные

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

1) Целевая функция, которая минимизирует удельную стоимость каждого ингредиента

12x1+15x2+5x3+20x4+30x5→ max

2) Ограничения на объем выделенных средств

3x1+5x2+7x3+2x4+6x5≤120;

14x1+12x2+10x3+8x4+12x5≤400;

10x1+13x2+8x3+10x4+15x5≤300.

2.2 Решение задачи с применением Matlab

MATLAB (сокращение от англ. «Matrix Laboratory») — пакет прикладных программ для решения задач технических вычислений и одноимённый язык программирования, используемый в этом пакете. MATLAB используют более          1 000 000 инженерных и научных работников, он работает на большинстве современных операционных систем, включая Linux, Mac OS, Solaris (начиная с версии R2010b поддержка Solaris прекращена) и Microsoft Windows.

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

Шаг 1. Создание фитнесс-функции.

Прежде чем приступить к решению задачи с помощью Matlab, необходимо создать m-file, содержащий нашу функцию приспособленности. Для этого в пакете Matlab выберем пункт меню File – New – Script. В появившимся окне вводим функцию приспособленности, описанную выше и сохраним ее под именем fitnessfun в каталоге Matlab, в папке bin.

Рисунок 2.1 – Формирование целевой функции

Шаг 2. вызов окна мастера генетического алгоритма

Для того чтобы вызвать мастер генетического алгоритма нужно в командном окне набрать команду gatool.

Рисунок 2.2 – Окно мастера ГА

Шаг 3. задание исходных данных.

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

1)                Fitness function - вводим название нашей фитнесс-функции с символом @: @fitnessfun.

2)                Number of variables – вводим количество проектов равное 5.

В панели Constraints можно задать ограничения или ограничивающую нелинейную функцию. В поле Bounds необходимо задать нижнюю границу равную 0, в поле Linear inequalities задается линейное ограничение неравенством вида:

3x1+5x2+7x3+2x4+6x5≤120;

14x1+12x2+10x3+8x4+12x5≤400;

10x1+13x2+8x3+10x4+15x5≤300.

Рисунок 2.3 – Вввод исходных данных

Шаг 4. задание опций

Стоит отметить, что все опции в окне GATOOL имеют значения default (по умолчанию), они являются самыми оптимальными для работы данного алгоритма, и как следствие решения задачи.

В правой части основного окна утилиты GATool находится панель Options. Она позволяет устанавливать различные настройки для работы генетических алгоритмов. При щелчке мышью по кнопкам [+], которые находятся напротив названия каждого из настраиваемых параметров в панели Options, появляются выпадающие списки (вкладки), содержащие поля для ввода и изменения соответствующих параметров генетического алгоритма.

Рисунок 2.4 – Панель настроек ГА

Основными настраиваемыми параметрами в GATool являются:

1)      популяция (вкладка Population);

2)      масштабирование (вкладка Fitness Scaling);

3)      оператор отбора (вкладка Selection);

4)      оператор репродукции (вкладка Reproduction);

5)      оператор мутации (вкладка Mutation);

6)      оператор скрещивание (вкладка Crossover);

7)      перенесение особей между популяциями (вкладка Migration);

8)      специальные параметры алгоритма (вкладка Algorithm settings);

9)      задание гибридной функции (вкладка Hybrid function);

10)  задание критерия остановки алгоритма (вкладка Stopping criteria);

11)  вывод различной дополнительной информации по ходу работы генетического алгоритма (вкладка Plot Functions);

12)  вывод результатов работы алгоритма в виде новой функции (вкладка Output function);

13)  задание набора информации для вывода в командное окно (вкладка Display to command window);

14)  способ вычисления значений оптимизированной и ограничивающей функций (вкладка User function evaluation).

Рассмотрим подробнее все вышеперечисленные вкладки панели Options и элементы, которые они содержат.

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

Также вкладка популяции позволяет настраивать размер популяции (из скольких особей будет состоять каждое поколение) и каким образом будет создаваться начальное поколение (Uniform – если отсутствуют накладываемые ограничения, в противном случае — Feasible population). Кроме того, в рассматриваемой вкладке имеется возможность задать вручную начальное поколение (используя пункт Initial population) или его часть, начальный рейтинг особей (пункт Initial scores), а также ввести ограничительный числовой диапазон, которому должны принадлежать особи начальной популяции (Initial range).

Во вкладке масштабирования (Fitness Scaling) пользователь имеет возможность указать функцию масштабирования, которая конвертирует достигаемые оптимизируемой функцией значения в значения, лежащие в пределах, допустимых для оператора отбора. При выборе в качестве функции масштабирования параметра Rank масштабирование будет приводиться к рейтингу, то есть особям присваивается рейтинговый номер (для лучшей особи – единица, для следующей – двойка, и так далее). Пропорциональное масштабирование (Proportional) задает вероятности пропорционально заданному числовому ряду для особей. При выборе опции Top наибольшее рейтинговое значение присваивается сразу нескольким наиболее выдающимся особям (их число указывается в виде параметра). Наконец, при выборе масштабирования типа Shift linear имеется возможность указать максимальную вероятность наилучшей особи.

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

1)           Tournament – случайно выбирается указанное число особей, среди них на конкурсной основе выбираются лучшие;

2)           Roulette – имитируется рулетка, в которой размер каждого сегмента устанавливается в соответствии с его вероятностью;

3)           Uniform – родители выбираются случайным образом согласно заданному распределению и с учетом количества родительских особей и их вероятностей;

4)           Stochastic uniform – строится линия, в которой каждому родителю ставится в соответствие её часть определенного размера (в зависимости от вероятности родителя), затем алгоритм пробегает пот линии шагами одинаковой длины и выбирает родителей в зависимости от того, на какую часть линии попал шаг.

Вкладка Reproduction уточняет каким образом происходит создание новых особей. Пункт Elite count позволяет указать число особей, которые гарантировано перейдут в следующее поколение. Пункт Crossover fraction указывает долю особей, которые создаются путем скрещивания. Остальная доля создается путем мутации.