Разработка критериев выбора окончательного решения при поиске инструмента в экспертной системе технологического назначения
Разработка модели, которая описывает алгоритм оптимизации размещения инструментов по поверхностям в случае с двумя параметрами. Модернизированный до двух критериев алгоритм оптимизации на основе методов: генетические алгоритмы, метод ветвей и границ.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 08.05.2018 |
| Размер файла | 177,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики
Разработка критериев выбора окончательного решения при поиске инструмента в экспертной системе технологического назначения
доцент, кандидат технических наук
Филиппов А.Н.
Аннотация
В статье описывается математическая модель оптимизации размещения инструментов по поверхностям для двух критериев, и реализация модели, применяя метод “ветвей и границ” и генетический алгоритм.
Ключевые слова: автоматизация, генетический алгоритм, метод ветвей и границ.
Abstract
The article describes the mathematical model of optimization of placement of instruments on surfaces for two criteria, and implementation of the model applying the method of branches and borders” and the genetic algorithm.
Keywords: automation, genetic algorithm, the method of branches and borders.
Задачей оптимизации в математике называется задача о нахождении экстремума (минимума или максимума) вещественной функции в некоторой области. Как правило, рассматриваются области, принадлежащие Rn и заданные набором равенств и неравенств.
Для того чтобы корректно поставить задачу оптимизации необходимо задать:
1. Допустимое множество
2. Целевую функцию -- отображение
3. Критерий поиска (max или min).
Существующие в настоящее время методы поиска можно разбить на три большие группы: детерминированные, случайные, комбинаторные.
В случае с одним параметром задача оптимизации размещения [2] инструментов по поверхностям [3] выглядит так:
Минимизировать функцию:
при ограничениях:
yi = 0, если xij для всех j=1…n
yi= 1, в остальных случаях
где: aij- стоимость обработки j-й поверхности i-м инструментом
di - стойкость i-ого инструмента (фиксированная доплата)
n - количество инструментов
m - количество поверхностей
xij= 1 - для обработки j-й поверхности выбран i-й инструмент
xij= 0 -инструмент не выбран
yi= 1 - i-й инструмент используется
yi= 0 - i-й инструмент не используется
Для того чтобы решить задачу оптимизации для двух критериев требуется минимизировать взвешенную сумму функций f0(x) и f1(x):
где:
p - параметр, лежащий в пределах от 0 до 1, учитывающий степень стоимости функции f0(x) по сравнению с f1(x).
Например:
· При p (f0 много дороже, чем f1)
· При p (f0 много дешевле, чем f1)
Рис. 1 Блок схема генетического алгоритма
На рис.1 представлена блок схема генетического алгоритма для решения задачи оптимизации с двумя критериями [1].
В результате проделанной работы разработана математическая модель, которая описывает алгоритм оптимизации размещения инструментов по поверхностям в случае с двумя параметрами, а также представлен модернизированный до двух критериев алгоритм оптимизации на основе методов: генетические алгоритмы, метод ветвей и границ.
алгоритм генетический инструмент граница
Литература
1. Л. А. Гладков, В. В. Курейчик В. М. Курейчик, Генетические алгоритмы М: ФИЗМАТЛИТ, 2010, С. 368
2. Давыдова И.М. Схемы перебора в задачах размещения. - Л.: ЛГУ 1985. с. 30-31
3. Филиппов А. Н. «Разработка и исследование методов экспертных систем в САПР ТП механической обработки» - диссертация на соискание ученой степени кандидата технических наук. Л., 1991 - С. 71-76.
Размещено на Allbest.ru
...Подобные документы
Задача об оптимальном графе для децентрализованного поиска. Жадный алгоритм. Модель Клайнберга. Математическая модель. Алгоритмы решения. Алгоритм локального поиска. Табу алгоритм. Метод ветвей и границ. Выбор между одинаковыми соседями. Стартовый граф.
дипломная работа [4,1 M], добавлен 23.10.2016Оптимизация решения задачи с помощью алгоритма отжига. Анализ теории оптимизации как целевой функции. Метод градиентного спуска. Переменные и описание алгоритма отжига. Представление задачи коммивояжера через граф. Сведение задачи к переменным и решение.
курсовая работа [784,0 K], добавлен 21.05.2015Постановка и решение дискретных оптимизационных задач методом дискретного программирования и методом ветвей и границ на примере классической задачи коммивояжера. Этапы построения алгоритма ветвей и границ и его эффективность, построение дерева графов.
курсовая работа [195,5 K], добавлен 08.11.2009Общие сведения об управляющих автоматах, построенных на основе принципа программируемой логики. Горизонтально-вертикальное кодирование. Алгоритмы кодирования операционной части. Анализ результатов оценки критериев. Алгоритм поиска минимального покрытия.
дипломная работа [1,8 M], добавлен 07.08.2012Особенности метода ветвей и границ как одного из распространенных методов решения целочисленных задач. Декомпозиция задачи линейного программирования в алгоритме метода ветвей и границ. Графический, симплекс-метод решения задач линейного программирования.
курсовая работа [4,0 M], добавлен 05.03.2012Понятия оптимизации проектных решений. Нахождение максимума (минимума) линейной целевой функции. Схема алгоритма метода Саати для вычисления весов критериев. Создание приложения, позволяющего производить однокритериальную и многокритериальную оптимизацию.
курсовая работа [781,9 K], добавлен 23.02.2016Основные генетические операторы. Схема функционирования генетического алгоритма. Задачи, решаемые с помощью генетических алгоритмов. Математическая постановка задачи оптимизации. Решение Диофантова уравнения. Программная реализация. Создание пособия.
курсовая работа [391,4 K], добавлен 20.02.2008Описание генетических алгоритмов. Применение генетического алгоритма для решения задачи коммивояжера. Постановка задачи безусловной оптимизации. Изучение распространения генетических алгоритмов на модель с несколькими взаимодействующими популяциями.
дипломная работа [979,1 K], добавлен 30.05.2015Метод решения математической модели на примере решения задач аналитической геометрии. Описание согласно заданному варианту методов решения задачи. Разработка математической модели на основе описанных методов. Параметры окружности минимального радиуса.
лабораторная работа [310,6 K], добавлен 13.02.2009Алгоритмы нахождения кратчайшего пути: анализ при помощи математических объектов - графов. Оптимальный маршрут между двумя вершинами (алгоритм Декстры), всеми парами вершин (алгоритм Флойда), k-оптимальных маршрутов между двумя вершинами (алгоритм Йена).
курсовая работа [569,6 K], добавлен 16.01.2012Классы задач P и NP, их сводимость. Примеры NP-полных и NP-трудных задач. Сущность метода поиска с возвратом. Алгоритмы решения классических задач комбинаторного поиска. Решение задачи о восьми ферзях. Поиск оптимального решения методом ветвей и границ.
презентация [441,5 K], добавлен 19.10.2014Основные способы решения задач целочисленного программирования: округление решений до целого, метод полного перебора, применение оптимизационных алгоритмов. Алгоритм метода ветвей и границ. Пример с оптимизацией побочного производства лесничества.
презентация [323,6 K], добавлен 30.10.2013Автоматизация проектирования на основе применения ЭВМ. Алгоритм решения задачи расчета плоскоконической передачи. Контроль корректности функционирования и пригодности программы к эксплуатации. Оптимизация конической передачи. Условия выполнения программы.
курсовая работа [796,6 K], добавлен 24.06.2013Анализ предметной области. Разработка генетического алгоритма для оптимизации инвестиций. Спецификация требований и прецедентов. Проектирование пользовательского интерфейса информационной системы. Модели данных, используемые в системе и их взаимодействие.
дипломная работа [2,1 M], добавлен 24.08.2017Задача о ранце как задача комбинаторной оптимизации. Задача о загрузке, рюкзаке, ранце. Постановка и NP-полнота задачи. Классификация методов решения задачи о рюкзаке. Динамическое программирование. Метод ветвей и границ. Сравнительный анализ методов.
курсовая работа [1,7 M], добавлен 18.01.2011Размещение одного многоугольника внутри другого: разработка программного средства для построения характеристической области задачи. Алгоритм построения в случае выпуклых исходных объектов, их односвязности и многосвязности. Входные и выходные данные.
курсовая работа [423,3 K], добавлен 08.03.2012Алгоритм решения функциональной задачи. Выбор системы команд специализированной ЭВМ. Форматы команд и операндов. Содержательные графы микропрограмм операций АЛУ. Разработка объединенной микропрограммы работы АЛУ. Закодированные алгоритмы микропрограмм.
курсовая работа [265,5 K], добавлен 17.11.2010Разработка алгоритма оптимизации коэффициентов дискретного регулятора с законом ПИД по минимуму интегрального квадратичного критерия. Расчёт оптимальных параметров регулятора на основе описанных алгоритмов. Анализ переходных процессов в замкнутой системе.
практическая работа [1,4 M], добавлен 25.12.2011Программа для обучения графическому методу решения задач линейной оптимизации (ЗЛО). Необходимое серверное и клиентское программное обеспечение. Графический метод решения ЗЛО для произвольной задачи. Организационно-экономическое обоснование проекта.
курсовая работа [996,3 K], добавлен 14.10.2010Необходимые условия экстремума. Разработка машинного алгоритма и программы многомерной оптимизации для градиентного метода с использованием метода равномерного поиска. Проверка необходимых и достаточных условий экстремума для найденной точки минимума.
курсовая работа [249,8 K], добавлен 25.09.2013
