Генетические алгоритмы

В 1975г. Д.Х. Холланд предложил схему генетического алгоритма, который оказался очень удобен в решении задач раскроя. Генетические алгоритмы (ГА) представляют собой методы оптимизации, основанные на концепциях естественного отбора и генетики. В этом подходе, переменные представлены как гены на хромосоме. ГА показывают группу вариантов решения (популяции) на поверхности ответа. Через естественный отбор и генетические операторы, мутацию и рекомбинацию, отбираются хромосомы с лучшей пригодностью. Естественный отбор гарантирует, что хромосомы с лучшей пригодностью будут размножаться в будущих популяциях. Используя оператор рекомбинации, ГА объединяет гены родительских хромосом, чтобы сформировать новые хромосомы (детей), которые имеют высокую вероятность наличия лучшей пригодности, чем у их родителей. Мутация позволяет исследовать новые области поверхности.

Идею ГА подсказала сама природа и работы Дарвина. Делается предположение, что, если взять 2 вполне хороших решения задачи и каким-либо образом получить из них новое решение, то будет высокая вероятность того, что новое решение получится хорошим или даже более лучшим.

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

Рис. 10.5 - Формирование последовательности размещений

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

Допустим, нам нужно оптимизировать некоторую функцию F( X₁, X₂,.., X_n). В задачах раскроя очевидно, такая функция вычисляет КИМ. Мы ищем её глобальный максимум. Тогда, для реализации ГА нам нужно придумать, как мы будем хранить решения. По сути, нам нужно поместить все X₁-X_n в некоторый вектор, который будет играть роль хромосомы. Один из наиболее распространенных способов - кодировать значения переменных в битовом векторе. Hапример, выделим каждому иксу по 8 бит. Тогда наш вектор будет длины L=8*n. Для простоты будем считать, что биты лежат в массиве X[0..L-1].

Пусть каждая особь состоит из массива X и значения функции F на переменных, извлеченных из этого массива. Тогда ГА будет состоять из следующих шагов:

1. Генерация начальной популяции - заполнение популяции особями, в которых элементы массива X (биты) заполнены случайным образом.

2. Выбор родительской пары - элитный отбор, то есть берем K особей с максимальными значениями функции F и составляем из них все возможные пары (K*(K-1)/2).

3. Кроссинговер - берем случайную точку t на массиве X(0..L-1). Теперь, все элементы массива с индексами 0-t новой особи (потомка) заполняем элементами с теми же индексами, но из массива X первой родительской особи. Остальные элементы заполняются из массива второй родительской особи. Для второго потомка делается наоборот - элементы 0-t берут от второго потомка, а остальные - от первого.

4. Новые особи с некоторой вероятностью мутируют - инвертируется случайный бит массива X этой особи. Вероятность мутации обычно полагают порядка 1%.

5. Полученные особи-потомки добавляются в популяцию после переоценки. Обычно новую особь добавляют взамен самой плохой старой особи, при условии что значение функции на новой особи выше значения функции на старой плохой особи.

6. Если самое лучшее решение в популяции нас не удовлетворяет, то переход на шаг 2. Хотя, чаще всего этого условия нет, а итерации ГА выполняются бесконечно.

Преимущества генетических алгоритмов:

- они не требуют никакой информации о поверхности ответа;

- разрывы, существующие на поверхности ответа имеют незначительный эффект на полную эффективность оптимизации;

- они стойки к попаданию в локальные оптимумы;

- они хорошо работают при решении крупномасштабных проблем оптимизации;

- могут быть использованы для широкого класса задач;

- просты и прозрачны в реализации;

- могут быть использованы в задачах с изменяющейся средой.

Нежелательно и проблематично использовать ГА:

- в случае, когда необходимо найти точный глобальный оптимум;

- если время исполнения функции оценки велико;

- если необходимо найти все решения задачи, а не одно из них;

- если конфигурация является не простой (кодирование решения).

CALS-технологии

Основные понятия CALS-технологий

Термин CALS (Continuous Acquisition and Lifecycle Support — непрерывная информационная поддержка поставок и жизненного цикла) означает совокупность принципов и технологий информационной поддержки жизненного цикла продукции на всех его стадиях. Используется также термин Product Lifecycle Management (PLM).

Основой концепции CALS является повышение эффективности процессов жизненного цикла (ЖЦ) изделия за счет повышения эффективности управления информацией об изделии. Задачей CALS является преобразование ЖЦ изделия в высокоавтоматизированный процесс путем реструктуризации (реинжиниринга) входящих в него бизнес-процессов.

Первая часть термина «CALS» (Continuous Acquisition) означает постоянное повышение эффективности (развитие) как самого изделия, так и процессов взаимодействия между поставщиком и потребителем изделия в течение его ЖЦ. Вторая часть термина «CALS» (Life cycle Support) обозначает путь такого развития: внедрение новых организационных методик разработки изделия, например, параллельного проектирования или междисциплинарных рабочих групп. Это приведет к увеличению инвестиций на этапах создания и модернизации изделия, но позволит более полно учесть потребности заказчика и условия эксплуатации, что, в свою очередь, приведет к снижению затрат на этапах эксплуатации и обслуживания изделия и, в конечном итоге, к сокращению затрат на весь ЖЦ изделия.

Рис. 11.1 – Базовые принципы CALS-технологий.

Можно выделить две основные проблемы, стоящие на пути повышения эффективности управления информацией. Во-первых, с увеличением сложности изделий и применением для их разработки современных компьютерных систем, значительно увеличивается объем данных об изделии. При этом прежние методы работы с данными уже не позволяют обеспечивать их точность, целостность и актуальность при сохранении приемлемых временных и материальных затрат. Во-вторых, увеличение количества участников проекта по разработке изделия (особенно в случае виртуального предприятия) приводит к возникновению серьезных проблем при обмене информацией между участниками из-за наличия между ними коммуникационных барьеров (например, из-за несовместимости компьютерных систем).

Основное содержание концепции CALS, принципиально отличающее ее от других подходов, составляют инвариантные понятия, которые реализуются (полностью или частично) в течение жизненного цикла (ЖЦ) изделия.

Эти инвариантные понятия условно делятся на три группы:

- базовые принципы CALS;

- базовые управленческие технологии;

- базовые технологии управления данными.

К числу первых относятся:

- системная информационная поддержка ЖЦ изделия на основе использования интегрированной информационной среды (ИИС), обеспечивающая минимизацию затрат в ходе ЖЦ;

- информационная интеграция за счет стандартизации информационного описания объектов управления;

- разделение программ и данных на основе стандартизации структур данных и интерфейсов доступа к ним, ориентация на готовые коммерческие программно-технические решения (Commercial Of The Shelf - COTS), соответствующие требованиям стандартов;

- безбумажное представление информации, использование электронно-цифровой подписи;

- параллельный инжиниринг (Concurrent Engineering);

- непрерывное совершенствование бизнес-процессов (Business Processes Reengineering).

К числу вторых относятся технологии управления процессами, инвариантные по отношению к объекту (продукции):

- управление проектами и заданиями (Project Management/Workflow Management);

- управление ресурсами (Manufacturing Resource Planning);

- управление качеством (Quality Management);

- интегрированная логистическая поддержка (Integrated Logistic Support).

К числу третьих относятся технологии управления данными об изделии, процессах, ресурсах и среде.