Планирование генетических алгоритмов
 | Эта статья включает список литературы , связанную литературу или внешние ссылки , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . ( июнь 2020 г. ) |
Генетический алгоритм — это метод оперативного исследования , который можно использовать для решения планирования задач производства .
Важность планирования производства
Чтобы быть конкурентоспособными, корпорации должны минимизировать неэффективность и максимизировать производительность. В производстве производительность по своей сути связана с тем, насколько хорошо фирма может оптимизировать имеющиеся ресурсы, сократить отходы и повысить эффективность. Найти лучший способ максимизировать эффективность производственного процесса может быть чрезвычайно сложно. Даже в простых проектах требуется множество входных данных, несколько шагов, множество ограничений и ограниченность ресурсов. В целом задача планирования с ограниченными ресурсами состоит из:
- Набор заданий, которые необходимо выполнить
- Ограниченный набор ресурсов, которые можно использовать для выполнения каждой работы.
- Набор ограничений, которые должны быть удовлетворены
- Временные ограничения – временное окно для выполнения задачи.
- Процедурные ограничения – порядок выполнения каждой задачи.
- Ресурсные ограничения – доступен ли ресурс
- Набор целей для оценки эффективности планирования
Хорошим примером этого является типичный заводской цех, где необходимо запланировать, какие работы должны быть выполнены, на каких машинах, какими сотрудниками, в каком порядке и в какое время.
Использование алгоритмов при планировании [ править ]
В очень сложных задачах, таких как планирование, не существует известного способа получить окончательный ответ, поэтому мы прибегаем к его поиску, пытаясь найти «хороший» ответ. В задачах планирования чаще всего используются эвристические алгоритмы для поиска оптимального решения. Методы эвристического поиска страдают, поскольку входные данные становятся более сложными и разнообразными. Этот тип задач известен в информатике как NP-сложная задача. Это означает, что не существует известных алгоритмов поиска оптимального решения за полиномиальное время.
Генетические алгоритмы хорошо подходят для решения задач планирования производства , поскольку в отличие от эвристических методов генетические алгоритмы работают с совокупностью решений, а не с одним решением. При планировании производства эта совокупность решений состоит из множества ответов, которые могут иметь разные, иногда противоречивые цели. Например, в одном решении мы можем оптимизировать производственный процесс, который должен быть завершен за минимальное время. В другом решении мы можем оптимизировать минимальное количество дефектов. Увеличивая скорость производства, мы можем столкнуться с увеличением дефектов в нашем конечном продукте.
По мере увеличения количества целей, которых мы пытаемся достичь, мы также увеличиваем количество ограничений на проблему и аналогичным образом увеличиваем ее сложность. Генетические алгоритмы идеально подходят для задач такого типа, когда пространство поиска велико, а количество возможных решений невелико.
Применение генетического алгоритма [ править ]
Чтобы применить генетический алгоритм к задаче планирования, мы должны сначала представить его как геном. Один из способов представления генома планирования — определить последовательность задач и время начала этих задач относительно друг друга. Каждая задача и соответствующее ей время начала представляют собой ген.
Определенная последовательность задач и время начала (гены) представляют собой один геном нашей популяции. Чтобы убедиться, что наш геном является возможным решением, мы должны позаботиться о том, чтобы он подчинялся нашим ограничениям приоритета. Мы генерируем начальную популяцию, используя случайное время начала в пределах ограничений приоритета. Затем с помощью генетических алгоритмов мы берем эту исходную популяцию и скрещиваем ее, комбинируя геномы с небольшой долей случайности (мутации). Потомство этой комбинации выбирается на основе функции приспособленности , которая включает в себя одно или несколько наших ограничений, таких как минимизация времени и минимизация дефектов. Мы позволяем этому процессу продолжаться либо в течение заранее отведенного времени, либо до тех пор, пока не найдем решение, соответствующее нашим минимальным критериям. В целом каждое последующее поколение будет иметь более высокую среднюю приспособленность, т. е. будет требовать меньше времени и более высокого качества, чем предыдущие поколения. В задачах планирования, как и в случае с другими решениями генетических алгоритмов, мы должны быть уверены, что не выбираем невозможных потомков, например потомков, которые нарушают наше ограничение приоритета. Нам, конечно, возможно, придется добавить дополнительные ценности пригодности, такие как минимизация затрат; однако каждое добавленное ограничение значительно увеличивает пространство поиска и уменьшает количество хорошо совпадающих решений.
См. также [ править ]
Библиография [ править ]
- Уолл, М., Генетический алгоритм планирования с ограниченными ресурсами (PDF)
- Лим, К.; Сим, Э., Планирование производства в условиях производства/восстановления с использованием генетического алгоритма (PDF)