Для данной задачи было использовано представление хромосомы на основе номера группы [92,101]:
12324332144232423123,
где значение числа означает номер группы, а положение числа номер сборочного участка.
В качестве оператора кроссовера использовался двухточечный кроссовер, когда произвольно выбирались две точки разрыва и хромосомы обменивались серединами. При этом каждая особь имела равную вероятность участия в процессе кроссовера.
В качестве оператора мутации использовалась одноточечная мутация, когда произвольно выбирается одно число и меняет свое значение случайным образом. В каждом поколении обязательно появлялся один мутант.
В качестве оператора отбора использовалась селекционная схема 2 из раздела 4.2., с небольшой модификацией, после рангового упорядочивания по значению фитнесс функции треть оказавшаяся внизу уничтожалась.
В качестве дополнительных ограничений были применены следующие:
Был наложен запрет на появление потомков идентичных хотя бы одной из особей существующей популяции, причем в программу заложена возможность запрета появления потомков в зависимости от их степени похожести на этих особей, что позволило увеличить вариабельность популяции.
Было запрещено появление особей, у которых номера групп повторялись больше 6 раз (согласно ограничению на невозможность постройки цеха более чем на 6 сборочных участков).
В качестве фитнесс функции использовались две функции:
Значение первой фитнесс функции равнялось числу посещений определенным видом изделия различных цехов, то есть если все 35 изделий посетили бы только один цех, то фитнесс функция равна 35, если хотя бы одно изделие посетило бы два различных цеха то фитнесс функция изменила бы значение до 36 и так далее.
Значение второй фитнесс функции вычислялось по формуле:
,
где F – фитнесс функция, S – сумма всех изделий (или выполняемых операций), So – сумма нулей в диагональных блоках (упорядоченных группах), Se – сумма изделий обрабатываемых в разных группах.
Необходимо было получить ответ с максимальным значением фитнесс функции.
Для первой функции был найден ответ идентичный с решениями предложенными другими методами, а для второй функции был найден ответ представленный в приложении 1, в таблице 6. Расходы на транспортировку изделий из цеха в цех, для этого решения, представлены в таблице 18.
Ответ для второй функции был найден в виде следующей хромосомы [88]:
Как видно из таблицы 6, в приложении 1, ежемесячно необходимо транспортировать изделия 1, 3, 5, 15, 17, 29, 8, 14, 19, всего 950 изделий, т.е. 2 автопогрузчика ежедневно должны транспортировать указанные изделия между соответствующими цехами. Расчет затрат приведен в таблице 18.
Таблица 18
Результаты решения для метода генетических алгоритмов
| Количество изделий подлежащих транспортировке в месяц, шт. | |
| Количество необходимых погрузчиков, шт. | |
| Сумма на покупку погрузчиков, руб. | |
| Зарплата водителей автопогрузчиков, руб./мес. | |
| Отчисления с фонда оплаты труда и т.п., руб./мес. | |
| Текущие расходы на автопогрузчики руб./мес. |
2. Постановка и решение задачи проектирования подразделений организационной структуры. На основе постановки и решения предыдущей задачи проектирования производственных ячеек и используемого генетического алгоритма была поставлена задача проектирования подразделений организационной структуры. Для решения этой задачи нужно выполнить следующие шаги.
1) Создание исходной матрицы. Операционная система организации должна быть представлена в виде матрицы процессы/операции, аналогично матрице изделия/станки.
2) Постановка задачи. Поскольку, данная задача представляет собой комбинаторную задачу оптимизации, в качестве целевой функции могут быть предложены два варианта.
Вариант первый – сумма отрицательного эффекта от выполняемых операций должна быть минимальной:
,
где Xij – отрицательный эффект от j-ой операции i-ого процесса.
В качестве отрицательного эффекта могут быть выделены несколько критериев: увеличение затрат в результате передачи объектов входа/выхода операций (информации, материальных ресурсов) между подразделениями, количество связей, их трудоемкость и т.д.
Вариант второй – сумма положительного эффекта от выполняемых операций должна быть максимальной:
,
где Xij – положительный эффект от j-ой операции i-ого процесса.
В качестве положительного эффекта можно рассматривать синергетический рост генерируемых денежных потоков в результате объединения выполняемых операций в рамках одного подразделения.
3) Разработка алгоритма. В соответствии с рассмотренными в разделе 4.2. и в пунктах 4.3.1. и 4.3.2. принципами использования методов генетических алгоритмов необходимо разработать представление хромосомы, основных операторов и фитнесс функцию.
4) Разработка программы и решение. Для решения задачи необходимо разработать программу, учесть реализацию различных вариантов представления операторов и фитнесс функции.
С помощью решения рассматриваемой задачи можно оптимизировать структуру организации. Примером решения может послужить решение представленное в приложении 1 в таблицах 7,8,9 и 10 полученное для возможной реструктуризации ООО «Енисейский ЦБК», эффект выражается в сокращении административных затрат примерно на 10%. Что достигается сокращением управленческих должностей и упорядочением системы документооборота и принятия решений, при сохранении качества и сроков выполнения работ. Пунктирной линией разделены смежные дирекции и управления, где начальник одного подразделения выступает ответственным за все направление деятельности, а начальник соседнего подразделения его заместителем.
Аналогично можно поставить и решить задачу проектирования структуры информационной системы, если требуется уменьшить потоки данных между подразделениями.
3. Решение задачи транспортного расписания методом генетических алгоритмов. Многие предприятия народного хозяйства, в том числе и промышленные, в своей деятельности сталкиваются с необходимостью решения задач транспортного расписания. Обеспечение эффективного функционирования предприятий общественного транспорта напрямую зависит в первую очередь именно от решения подобных задач. Успешное решение задач транспортного расписания позволяет:
- повысить качество обслуживания потребителей,
- сократить время простоев транспортных средств,
- обеспечить гибкость планирования расписания,
- быстро реагировать на изменения спроса,
- добиться снижения издержек практически по всем статьям переменных затрат,
- добиться оптимального соотношения между прибылью, удовлетворением спроса и затратами.
Постановка подобной задачи применительно к промышленному предприятию может иметь отношение к оперативному планированию производства (например, к обеспечению автоматизированной транспортировки деталей между участками, цехами и т.д.), что в свою очередь даст следующие преимущества:
- сокращение времени производственного цикла,
- снижение времени реагирования на заказы клиента,
- снижение времени простоев и времени перемещения деталей между станками, участками, цехами,
- увеличение гибкости производства.
Успешное решение задачи транспортного расписания может дополнить решение задачи проектирования производственных групп в групповых технологиях, что обеспечит более эффективное их применение на промышленном предприятии, в том числе и предприятиях аэрокосмического приборостроения.
Задачи транспортного расписания относятся к комбинаторным задачам оптимизации, они нередко многокритериальны, обладают большим пространством поиска, различными многочисленными ограничениями и т.д. Пока попытки использования ГА для решения данных задач в отечественной научной литературе носят скорее эпизодический характер и предпринимаются энтузиастами, в то время как классических схем и методов, прочно вошедших в обиход нет [4,2,15,22,73].
Здесь рассматривается вариант реализации метода генетических алгоритмов для данного класса задач, предложенный автором, без сравнения с другими методами [93]. На основе предлагаемого алгоритма создана компьютерная программа. Пример работы программы представлен на рисунке 6.
В качестве исходных данных могут использоваться различные таблицы, содержащие статистику входа выхода транспортируемых объектов. Число столбцов зависит от количества мест входа-выхода (остановок). Число строк зависит от числа временных интервалов.
Так, для примера были взяты 6 остановок замкнутого автобусного маршрута по три столбца на каждую, где первый столбец - число приходящих на остановку пассажиров, второй – выходящих, третий для вычислений и остатка, поскольку некоторые пассажиры могут ждать следующего автобуса. Число строк 48, для упрощения взяты интервалы по 30 минут, что составляет 24 часа, а сутки - это обычный цикл работы автобусного парка. Для программы предусмотрен анализ исходных данных, и ограничений на число остановок и временных интервалов она практически не имеет.
Основные ограничения, задаваемые пользователем, следующие:
Число пассажиров – максимальное число объектов, помещающихся в транспортное средство. Для данного примера взяты автобусы, но для программы это не имеет значения.
Максимальное число автобусов на рейс – число транспортных средств, выходящих на маршрут в данный интервал времени. Для примера это число автобусов.
Цена проезда – плата, взимаемая за провоз одного объекта, для примера - плата в автобусе за проезд.
Себестоимость рейса – себестоимость выполнения транспортным средством одного рейса по маршруту. В данном случае себестоимость одного рейса для автобуса – бензин, износ и т.д.
Численность популяции – настройка параметров самого алгоритма, число особей в поколении.
Рисунок 6 – Пример работы программы «Расчет расписания».
Параметр ожидания – если число поколений, не давших лучшего решения, достигает числа указанного пользователем, то вычисления прекращаются.
Результатом является минимальное число транспортных средств необходимых для обеспечения работы по расписанию, которое дано в виде целочисленной строки (хромосомы) [103,109].
В качестве хромосомы используется строка целых чисел размерностью равной частоте выхода транспортного средства на маршрут, где значение каждого гена – это число транспортных средств вышедших на маршрут в данном интервале времени. Для примера принято, что длина хромосомы 48, так как интервалы взяты по 30 минут. Программа при анализе исходных данных принимает, что число строк равно числу генов в хромосоме и одна хромосома полностью охватывает весь рабочий цикл. Так как далее транспорт (автобусы) идут по расписанию, то такого представления хромосомы вполне достаточно. Недостатком можно считать, что в вычислительном алгоритме время движения между остановками совпадает с длительностью временного интервала, но при необходимости в программу можно внести незначительные изменения, и проблема будет решена. Действительно: размерность хромосомы может быть доведена до практически любой величины, так же как и длительность интервала, единственным критерием может выступать быстродействие программы, на данный момент она выдает ответ за 2 секунды при популяции 300 и параметре ожидания 50.
В качестве операторов использовался двухточечный кроссовер с обменом центральной частью хромосомы, одноточечный оператор мутации с мутацией одной хромосомы в поколение, схема отбора с использованием сортировки по рангу и уничтожении трети наименее приспособленных. Подобная схема была выбрана для быстрой сходимости.
Функция приспособленности рассчитывается как денежный поток от платы за проезд всеми транспортируемыми объектами (пассажирами) минус число рейсов умноженных на себестоимость одного рейса. Таким образом, ищем решение с максимальным значением функции приспособленности (максимальной дневной прибылью). Можно сразу отметить, что в случае выпуска на маршрут транспортных средств различной вместимости решение можно представить в виде группы хромосом, каждая из которых вариант расписания движения для данного вида транспортных средств. Подобное усовершенствование программы требует незначительных исправлений в исходном коде.
Поскольку программа изначально не имела коммерческой цели - вопрос решения данного класса задач стоял в принципе, поэтому программа имеет недостаточную универсальность, но при необходимости, учитывая простоту самих ГА и универсальное представление хромосомы и данных, изменения могут быть внесены в исходный код в любой момент.
Таким образом, при необходимости, в результате несущественных изменений программа сможет решать намного более сложные задачи, не упуская особенностей вносимых экономической частью проблемы.
Принципиальный же вопрос о возможности эффективного и быстрого решения задачи транспортного расписания успешно решен.
Выводы. Таким образом, генетические алгоритмы продемонстрировали свою эффективность и удобство использования. Они действительно легко и удобно описывают разнообразные экономические процессы и позволяют решать широкий спектр организационных задач. Более того, по сущности ГА обладают комбинаторной структурой, которая наиболее точно отображает особенности самоорганизующихся систем и их системные принципы, что позволяет заявить не только о применимости ГА к организационным и операционным задачам, задачам моделирования экономических процессов, но и об их принципиальном соответствии логике этих задач.
Сравнительный анализ основных традиционных методов моделирования и методов генетических алгоритмов показал, что методы ГА обладают по существу единственным серьезным недостатком, они не гарантируют оптимальный результат, только субоптимальный. С другой стороны, они обладают серьезными преимуществами:
- простотой;
- гибкостью;
- независимостью от сложности экономической составляющей задачи;
- обработкой комбинаций в пространстве поиска неочевидных для исследователя;
- отсутствием необходимости согласования законов распределения и ряда аналогичных трудностей, возникающих в процессе построения имитационных моделей;
- слабыми ограничениями на возможные комбинации ключевых параметров, что позволяет более полно исследовать пространство поиска решений и потенциально возможные неординарные решения;
- низким уровнем требований к математической подготовке исследователя, требуется только умение написания простейших компьютерных программ.
Таким образом, можно сделать следующий вывод: методы генетических алгоритмов обладают серьезными сравнительными преимуществами перед основными традиционными методами моделирования в решении задач организационного проектирования и могут успешно применяться при моделировании операционных систем и организационных структур.
Решение подобных задач позволит [91]:
- сократить время производственного цикла,
- сократить время инвентаризации незавершенного производства,
- улучшить качество изделия,
- снизит время реагирования на заказы клиента,
- снизит время простоев и времени перемещения деталей между станками,
- увеличит гибкость производства,
- снизит постоянные и текущие затраты,
- увеличит производительность труда,
- интенсифицирует трудовой процесс,
- упорядочит сферу государственного управления,
- снизит складские запасы,
- увеличит надежность финансовых вложений.
Совместное использование математических методов, в первую очередь ГА, и разработанного в третьей главе алгоритма, существенно повысит его эффективность и позволит рассматривать его как количественно обоснованный.