Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Алгоритм случайного поиска относится к алгоритмам нелинейного математического программирования. Такие алгоритмы снискали себе широкую популярность при решении практических инженерных задач.
Простейший алгоритм – локальный неадаптивный алгоритм случайного поиска следующий (рис. 1).
Задаем начальную точку, представленную вектором X0, объявляем ее текущей и вычисляем в ней значений целевой функции.
Текущей точке придаем приращение в виде случайного вектора дельта X и вычисляется значение целевой функции.
Если значение целевой функции улучшилось, то данную точку делаем текущей.
Проверить условие останова. Если оно выполняется, то переходим на шаг 5, в противном случае на шаг 2.
Останов.
Рис. 1. Простой неадаптивный алгоритм случайного поиска локального оптимума
Достоинствами данного алгоритма являются его простота, устойчивость и интуитивная понятность. Недостатками – низкая скорость сходимости, а также неопределенность в выборе условия останова.
Существуют также адаптивные алгоритмы случайного поиска локального экстремума, обладающие более высокой скоростью сходимости.
Гораздо более эффективными и хорошо зарекомендовавшими себя практике являются адаптивные алгоритмы случайного поиска глобального экстремума. Их основная идея заключается в том, что поиск ведется не из какой-то одной начальной точки, а по всей области, и в процессе его выполнения изменяется закон распределения генерации вектора рабочих параметров (точек, в которых вычисляется значений целевой функции). Обычно на начальных этапах распределение является равномерным, а затем плотность вероятности увеличивается в районе предполагаемого оптимума (рис. 2). Следует заметить, что многие из этих алгоритмов хорошо зарекомендовали себя при решении задач как непрерывной, так и дискретной и дискретно-непрерывной оптимизации, а, следовательно, может использоваться при параметрическом, структурном и структурно-параметрическом синтезе объектов.
Рис. 2. Иллюстрация изменения плотности распределения вероятности для алгоритма случайного поиска (одномерный случай)
Существует огромное разнообразие алгоритмов случайного поиска, и все они с успехом применяются на практике ввиду их простоты, устойчивой работы, отсутствия необходимости вычисления производных, наглядности и удовлетворительной и хорошей сходимости, особенно на задачах большой размерности (иногда превышающей несколько тысяч, а то и десятки тысяч).
Эволюционные алгоритмы — направление в искусственном интеллекте (раздел эволюционного моделирования), которое использует и моделирует биологическую эволюцию. Различают различные алгоритмы: генетические алгоритмы, эволюционное программирование, эволюционные стратегии, системы классификаторов,генетическое программирование... Все они моделируют базовые положения в теории биологической эволюции — процессы отбора, мутации и воспроизводства. Поведение агентов определяется окружающей средой. Множество агентов принято называть популяцией. Такая популяция эволюционирует в соответствии с правилами отбора в соответствии с целевой функцией, задаваемой окружающей средой. Таким образом, каждому агенту (индивидууму) популяции назначается значение его пригодности в окружающей среде. Размножаются только наиболее пригодные виды. Рекомбинация и мутация позволяют изменяться агентам и приспособляться к среде. Такие алгоритмы относятся к адаптивным поисковым механизмам.
Эволюционные алгоритмы успешно использовались для задач типа функциональной оптимизации и могут легко быть описаны на математическом языке.
Генетический алгоритм — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссинговер. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.
Дата публикования: 2015-01-26; Прочитано: 1186 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!