Исследование и практическое применение планирования производства на основе генетических алгоритмов

Аннотация

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

Ключевые слова: планирование цеха, генетический алгоритм, локальная минимизация, циклический поиск.

Введение

В зависимости от сложности объекта исследования, проблему планирования производства можно разделить на одиночное машинное планирование, параллельное машинное планирование, планирование производственного потока и производственных задач. Задача планирования работы производства является типичной проблемой, а также является одним из самых сложных комбинационно-оптимизационных задач [1]. В последнее десятилетие ученые из разных стран широко изучали проблему планирования производства, и с дальнейшими исследованиями используемые технологии все сложнее и сложнее. Поскольку проблема планирования связана со слишком большим количеством факторов, ни один из методов не может всесторонне и эффективно решить проблему планирования магазина, эти методы эффективны только для конкретной или простой ситуации планирования. Теоретически, генетический алгоритм сам по себе является очень хорошей надежной технологией, которая может решить вышеупомянутые недостатки и проблемы и получить результаты планирования производства. Основным недостатком генетического алгоритма является то, что он не может гарантировать всегда оптимальное решение, но с постоянной оптимизацией генетической структуры и алгоритма его эффективность улучшается, а недостаток кажется не столь очевидным [3-4].

В этой статье в основном изучается улучшенный генетический алгоритм циклического поиска, применяемый в задаче планирования производства, операция кроссовера и операция мутации могут иметь циклический поиск в популяции. В статье используется стандартная модель планирования магазина TF (6x6) и LA1 (1Ox5) для проверки правильности алгоритма [6-7] [10]. Благодаря проверке можно сделать вывод, что улучшенный алгоритм циклического поиска имеет характеристики быстрой сходимости и предотвращает локальное оптимальное решение.

Хромосомная конструкция

Хромосомный ген представляет проблему, с которой сталкивается генетический алгоритм. В настоящее время для задачи планирования производства большинство алгоритмов используют обозначение прямого кодирования [8-9]. И это прямое кодирование принимает последовательность операций как вид планирования, в котором каждый ген представляет операцию. Эта кодировка характеризуется любым порядком обмена; будет генерировать эффективную последовательность планирования [8]. Для задачи планирования с n заготовками и m машинами каждая хромосома имеет n*m генов, которые появятся в каждой хромосоме m раз, и каждый раз представляет собой уникальную операцию.

Поиск циклического кроссовера

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

1. Выберите оптимальную особь в текущей популяции в качестве ребенка;
2. Случайно выберите двух особей в популяции и выполните операции, описанные в пунктах (3)-(5);
3. Произвольно выбирайте две точки пересечения, генерируя две особи с кроссоверной операцией
4. Если оптимальные особи, генерируемые кроссоверной операцией, хуже худшей особи в текущей популяции или время повторного поиска меньше начальных значений, перейдите к шагу (3), чтобы продолжить поиск;
5. Выберите оптимальную особь, полученную в (4) в качестве ребенка;
6. Когда число дочерних особей будет равно заданному размеру популяции, алгоритм прекратит поиск.

Поиск циклической мутации

1. Выберите оптимальную особь в текущей популяции, как особь следующего поколения;
2. Случайно выберите особи и выполните пункты (3)-(5);
3. Когда значение приспособленности полученой в следствии мутации особи такое же, как у одного из родителей или времена циклического поиска меньше, чем начальное значение, необходимо перейти к (3), чтобы продолжить поиск;
4. Выберите оптимальную особь, полученную в результате выполнения операции (4);
5. Когда количество особей нового поколения будет равно числу популяции, алгоритм прекратит поиск.

Вывод

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

Список использованной литературы

1. He Ming, Tang Qiuhua, Wang Shenglong. Rules Design and Evaluation of Crane Scheduling in Steelmaking-Continuous Casting Plant [J]. Machinery Design & Manufacture, 2012, (9):257-259.
2. Bian Xia, Mi Liang. Development on genetic algorithm theory and its applications [J]. Application Research of Computers, 2010, 27 (7).
3. Zhou Jinrong, Huang Dao, Jiang Weisun. The Improvement of Genetic Algorithm and Its Applications [J]. Computer Integrated Manufacturing Systems, 2010, 10(3): 17-23.
4. He Wei. Flexible Job Shop Scheduling Research under Machine Failures [D]. Chong Qing: Chong Qing University doctoral dissertation, 2012:1-2.
5. Liang Yusheng, Li Xiangbo. Assembly Line Balancing Problem Research Based on Genetic Algorithm [J]. Value Engineering, 2013(05)
6. Lu M S,Romanowski R.Multicontextual dispatching rules for job shops with dynamic job arrival [J]. International Journal of Advanced Manufacturing Technology, 2013, (67): 19–33
7. Xu Y,Wang L,Wang S,et al. An effective immune algorithm based on novel dispatching rules for the flexible flow-shop scheduling problem with multiprocessor tasks [J]. International Journal of Advanced Manufacturing Technology, 2013, (67): 121–135.
8. Ji Shuxin. Research on GA Chromosome Coding of Job Shop Scheduling [J]. Information and Control, 2010, (10): 43-47.
9. Xie Qing, Zhao Xiaoqiang. Study on Genetic Algorithm Coding Strategies [J]. Gansu Science and Technology, 2013 (02).
10. Xiong Hegen, Qian Guojie, Fan Huali, Jiang Guozhang. Research on the sample size of dispatching rule-based simulation scheduling test for dynamic shop scheduling problems [J]. Manufacturing Automation, 2015, 37 (4):41-43.