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

Во вкладке оператора мутации выбирается тип оператора мутации. Доступны следующие варианты:

1)      Gaussian – добавляет небольшое случайное число (согласно распределению Гаусса) ко всем компонентам каждого вектора-особи;

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

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

4)      Custom – позволяет задать собственную функцию.

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

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

Вкладка специальных опций алгоритма позволяет настраивать параметры решения системы нелинейных ограничений, налагаемых на алгоритм. Значение параметра Initial penalty определяет начальное числовое значение критики алгоритма, Penalty factor используется как множитель этого значения в случаях, когда разработчика не устраивает точность оптимизации или при выходе за границы, определенные во вкладке ограничений. Как правило, эти опции детально настраиваются для решения задач высокой сложности.

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

1)  none (не использовать гибридную функцию);

2)  fminsearch (поиск минимального из значений);

3)  patternsearch (поиск по образцу);

4)  fminunc (для неограниченного алгоритма);

5)  fmincon (для алгоритма с заданными ограничениями).

Во вкладке критерия остановки (Stopping criteria) указываются ситуации, при которых алгоритм совершает остановку. При этом, настраиваемыми являются следующие параметры:

1)                Generations – максимальное число поколений, после превышения которого произойдет остановка;

2)                Time limit – лимит времени на работу алгоритма;

3)                Fitness limit – если оптимизируемое значение меньше или равно данного лимита, то алгоритм остановится;

4)                Stall generations – количество мало отличающихся поколений, по прошествии которых алгоритм остановится;

5)                Stall time limit – то же, что и предыдущий параметр, но применимо к времени работы алгоритма;

6)                Function tolerance и Nonlinear constraint tolerance – минимальные значения изменений оптимизируемой и ограничивающей функций соответственно, при которых алгоритм продолжит работу.

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

1)                Plot interval – число поколений, по прошествии которого происходит очередное обновление графиков;

2)                Best fitness – вывод наилучшего значения оптимизируемой функции для каждого поколения;

3)                Best individual – вывод наилучшего представителя поколения при наилучшем оптимизационном результате в каждом из поколений;

4)                Distance – вывод интервала между значениями особей в поколении;

5)                Expectation – выводит ряд вероятностей и соответствующие им особи поколений;

6)                Genealogy – вывод генеалогического дерева особей;

7)                Range – вывод наименьшего, наибольшего и среднего значений оптимизируемой функции для каждого поколения;

8)                Score diversity – вывести гистаграмму рейтинга в каждом поколении;

9)                Scores – вывод рейтинга каждой особи в поколении;

10)            Selection – вывод гистограммы родителей;

11)            Stopping – вывод информации о состоянии всех параметров, влияющих на критерии остановки;

12)            Custom – отображение на графике некоторой указанной пользователем функции.

Вкладка вывода результатов в виде новой функции (Output function) позволяет включить вывод истории работы алгоритма в отдельном окне с заданным интервалом поколений (флаг History to new window и поле Interval соответственно), а также позволяет задать и вывести произвольную выходную функцию, задаваемую в поле Custom function.

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

Наконец, вкладка Display to command window позволяет настраивать информацию, которая отображается в основном командном окне MATLAB при работе алгоритма. Возможны следующие значения: Off — нет вывода в командное окно, Iterative — вывод информации о каждой итерации работающего алгоритма, Diagnose — вывод информации о каждой итерации и дополнительных сведениях о возможных ошибках и измененных ключевых параметрах алгоритма, Final – выводится только причина остановки и конечное значение.

По умолчанию стоят настройки классического ГА и без особой надобности их не стоит менять.

Шаг 5. Поиск решения.

После того, как все необходимые данные и параметры заданы, можно приступить к поиску оптимального решения. Для этого необходимо обратиться к панели Run Solver, которая содержит управляющие элементы (кнопки Start, Pause и Stop для начала, временной и полной остановки работы генетического алгоритма). Также она содержит поля Status and results, в которое выводятся текущие результаты работы запущенного генетического алгоритма, и Final point, в котором выводится значение конечной точки работы алгоритма — наилучшей величины оптимизируемой функции (то есть, искомое значение). Для запуска ГА нужно нажать кнопку Start.

1 Запуск

После первого запуска был найден вектор X=(8,206; 0,374; 0,006; 20,937; 0,242). Теперь подставим эти значения в функцию принадлежности и ограничение на объем затрат:

12*8,206+15*0,374+5*0,006+20*20,937+30*0,242=530,143

3*8,206+5*0,374+7*0,006+2*20,937+6*0,242≤69,862;

14*8,206+12*0,374+10*0,006+8*20,937+12*0,242≤289,852;

10*8,206+13*0,374+8*0,006+10*20,937+15*0,242≤299,989.

Анализ результатов решения.

Так как объем затрат меньше необходимых условий, то найденное решение является пока самым оптимальным.

Рисунок 2.5 – Результат работы ГА

В левом верхнем углу указан график отображения значения целевых функций видно, что  начиная с 7 популяции, видна сходимость решения. В правом верхнем углу указанна наилучшая особь. Внизу представлен график изменения расстояния между особями в поколении, видно что в последних 45 поколениях особи становятся одинаковыми(Хемингово расстояние равно 0) представлено на рисунке 2.6.

Рисунок 2.6 – Результирующие графики

2 Запуск

После второго запуска был найден вектор X=(8;0;0,0,519;21,584;0). Теперь подставим эти значения в функцию принадлежности и ограничение на объем затрат:

12*8+15*0+5*0,519+20*21,584+30*0= 530,288

3*8+5*0+7*0,519+2*21,584+6*0≤70,8;

14*8+12*0+10*0,519+8*21,584+12*0≤289,87;

10*8+13*0+8*0,519+10*21,584+15*0≤299,958.

Анализ результатов решения.

Так как объем затрат меньше необходимых условий, то найденное решение является пока самым оптимальным.

Рисунок 2.7 – Результат работы ГА

В левом верхнем углу указан график отображения значения целевых функций видно, что начиная с 8 популяции, видна сходимость решения. В правом верхнем углу указанна наилучшая особь. Внизу представлен график изменения расстояния между особями в поколении, видно что в последних 11 поколениях особи становятся одинаковыми(Хемингово расстояние равно 0) представлено на рисунке 2.8.

Рисунок 2.8 – Результирующие графики

3 Запуск

После третьего запуска был найден вектор X=(8,086;0,23;0,02;20,79;0,538). Теперь подставим эти значения в функцию принадлежности и ограничение на объем затрат:

12*8,086+15*0,23+5*0,02+20*20,79+30*0,538= 532,543

3*8,086+5*0,23+7*0,02+2*20,79+6*0,538≤70,365;

14*8,086+12*0,23+10*0,02+8*20,79+12*0,538≤288,959;

10*8,086+13*0,23+8*0,02+10*20,79+15*0,538≤299,998.

Анализ результатов решения.

Так как объем затрат меньше необходимых условий, то найденное решение является пока самым оптимальным.

Рисунок 2.9 – Результат работы ГА

              В левом верхнем углу указан график отображения значения целевых функций видно, что начиная с 42 популяции, видна сходимость решения. В правом верхнем углу указанна наилучшая особь. Внизу представлен график изменения расстояния между особями в поколении, видно что в последних 22 поколениях особи становятся одинаковыми(Хемингово расстояние равно 0) представлено на рисунке 2.10.

Рисунок 2.10 –Результирующие графики

4 Запуск

После четвертого запуска был найден вектор X=(8;0;0;22;0). Теперь подставим эти значения в функцию принадлежности и ограничение на объем затрат:

12*8+15*0 +5*0,031+20*29,734+30*0,142= 536,001

3*8+5*0+7*0+2*22+6*0≤68,004;

14*8+12*0 +10*0+8*22+12*0≤288,001;

10*8+13*0 +8*0+10*22+15*0≤299,998.

Анализ результатов решения.

Так как объем затрат меньше необходимых условий, то найденное решение является самым оптимальным.

Рисунок 2.11 – Результат работы ГА

В левом верхнем углу указан график отображения значения целевых функций видно, что начиная с 13 популяции, видна сходимость решения. В правом верхнем углу указанна наилучшая особь. Внизу представлен график изменения расстояния между особями в поколении, видно что в последних 16 поколениях особи становятся одинаковыми(Хемингово расстояние равно 0) представлено на рисунке 2.12.

Рисунок 2.12 – Результирующие графики

Заключение

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

В результате проделанной работы были получены следующие значения для каждого из продуктов:

        батон – 8 ед;

        рогалики – 0 ед;

        булочка – 0 ед;

        ржаной хлеб – 22 ед;

        пончики – 0 ед.

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

Список использованных источников

1        Ашманов С.А. Линейное программирование. М.: Наука. 1981. – 340с.