Разработка и реализация гибридного генетического алгоритма для автоматизированного проектирования маршрутов обхода геометрических объектов

• Автор: Пушкарёва, Галина Витальевна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Новосибирск
• Количество страниц: 168 с. : ил.

1. Постановка задачи и метод решения

1.1. Содержание проблемы оптимизации траектории движения исполнительного инструмента

1.2. Методы решения оптимизационных задач маршрутизации

1.3. Выбор метода решения. Методология генетического программирования

1.4. Выводы

2. Гибридный генетический алгоритм

2.1. Общая схема разработанного гибридного генетического алгоритма

2.2. Определение вложенности контуров

2.3. Характеристика применяемых генетических операторов

2.3.1. Оператор скрещивания

2.3.2. Оператор мутации

2.3.3. Оператор селекции
2.4. Целенаправленное изменение хромосом
2.4.1. Оператор инверсии
2.4.2. Оператор разнообразия
2.5. Оценка временной сложности гибридного генетического алгоритма
2.6. Выводы
3. Исследование эффективности гибридного генетического алгоритма
3.1. Сравнительный анализ разработанного алгоритма с другими методами
3.2. Исследование процесса получения эффективного решения гибридным генетическим алгоритмом

3.3. Исследование влияния параметров генетического алгоритма на эффективность поиска
3.3.1. Число генераций и количество попыток
3.3.2. Размер популяции и степень её обновления
3.3.3. Вероятности скрещивания и мутации
3.4. Средства повышения эффективности применения генетического алгоритма
3.5. Выводы
4. Реализация гибридного генетического алгоритма
4.1. Программная реализация разработанного алгоритма и
её связь с графической БД системы AutoCAD
4.2. Интерфейс пользователя с программой
4.3. Тестовые примеры и инструкция пользователю
4.4. Выводы
Заключение
Список использованной литературы
Приложение

Актуальность проблемы. Содержательная сторона рассматриваемой задачи связана с решением проблемы автоматизации сложного и трудоемкого процесса генерации управляющих программ для станков ЧПУ тепловой резки металла, которые являются результатом сквозного цикла обработки информации от чертежа детали до программ ее изготовления в 14С-кодах конкретного оборудования. Известные программные комплексы автоматизированного проектирования управляющих программ в значительной мере используют элементы интерактивной графики, в то время как более перспективным представляется полная автоматизация проектных решений на основе математических моделей и оптимизационных методов [82-84].
Траектория движения режущего инструмента состоит из следующих элементов [80]:
1) внешних контуров вырезаемых деталей;
2) внутренних контуров;
3) траекторий, связывающих смежные контуры (вырезаемые с одной врезки);
4) траекторий переходов инструмента в выключенном состоянии от одной точки врезки к другой.
При резке тонколистового металла маршруты типа 3, как правило, отсутствуют, поскольку каждая деталь вырезается в этом случае с отдельной врезки. Для толстолистового проката затраты на сквозную пробивку металла оказываются столь значительны, что экономически целесообразным становится обработка деталей без выключения режущего инструмента.
Таким образом, задача состоит в минимизации траекторий холостого хода, числа врезок и оптимизации переходов от одной врезки к другой. Исходными данными для задачи построения рационального маршрута являются технологические карты раскроя. Конфигурацию плана раскроя образуют внутренние и внешние контуры вырезаемых деталей. Особенность и сложность задачи заключается в том, что она имеет дискретно-непрерывную структуру.

В этом случае сначала рассматривается местоположение начальной точки дуги (х],уі) относительно прямой х-Х(. Если начальная точка дугового сегмента лежит на этой прямой, то возможны две альтернативы расположения полилинии в окрестности этой точки, которые изображены на рисунке 2.5;
Х=Х;.
а) б)
Рис.2.5. Варианты расположения полилинии в окрестности начальной точки дуги (а — с одной стороны относительно прямой, б — с двух сторон)
В зависимости от имеющегося варианта необходимо:
а) занести в список Ьу ординату у і дважды, как вырожденный случай
пересечения (длина отсекаемого отрезка прямой х=х,- равна нулю);
б) занести в список Ьу ординату у].
Теперь рассмотрим наличие пересечения дуги (без конечных точек) с прямой Х=Х(. Для этого определим угол <р, стянутый дуговым сегментом, по его кривизне к, используя следующую формулу:
(р = Ааг^(к) (2.9)
Далее определим координаты центра дуги (а,Ь) по формулам (1.13) для параметра і=(р :