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